Целевая функция и ландшафт

Целевую функцию полезно представлять как рельеф местности, а минимум — как самую низкую точку долины.

Ландшафт функции — графическое представление $f(x)$ как поверхности высоты над плоскостью переменных; минимум — дно впадины.

Рельеф вместо формул

Когда переменных две, $f(x_1,x_2)$ можно нарисовать как холмистую местность: над каждой точкой $(x_1,x_2)$ поднята «высота» $f$. Тогда оптимизация — это спуск слепого путника в самую низкую точку, ощупывающего наклон под ногами. Эта метафора работает и в $n$ измерениях, просто её нельзя нарисовать.

Удобный двумерный способ показать рельеф — линии уровня (как на топографической карте): кривые, вдоль которых $f$ постоянна. Близкие линии — крутой склон, редкие — пологий. Градиент всегда перпендикулярен линии уровня и указывает в сторону роста.

Словарь рельефа

Считаем высоты руками

Возьмём функцию $f(x,y)=(x-3)^2+(y+1)^2$. Это парабола-чаша с дном в точке $(3,-1)$, где $f=0$. Посчитаем высоты на нескольких точках и убедимся, что чем ближе к $(3,-1)$, тем ниже.

def f(x, y):
    return (x - 3) ** 2 + (y + 1) ** 2

points = [(0, 0), (1, 0), (3, -1), (3, 0), (5, 2)]
for (x, y) in points:
    print(f"f({x},{y}) = {f(x, y)}")

Вывод:

f(0,0) = 10
f(1,0) = 5
f(3,-1) = 0
f(3,0) = 1
f(5,2) = 13

Дно $(3,-1)$ действительно даёт $f=0$, и это единственный минимум: чаша выпуклая, оврагов и плато у неё нет. Большинство реальных функций куда коварнее.

Псевдо-карта линий уровня

Нарисуем грубую ASCII-карту: для сетки точек печатаем символ тем «темнее», чем меньше $f$. Видно концентрические кольца вокруг дна.

def f(x, y):
    return (x - 3) ** 2 + (y + 1) ** 2

for yi in range(3, -4, -1):     # y сверху вниз
    row = ""
    for xi in range(0, 7):      # x слева направо
        v = f(xi, yi)
        if v == 0:
            row += "@"
        elif v <= 4:
            row += "o"
        elif v <= 12:
            row += "."
        else:
            row += " "
    print(row)

Вывод:

       
  ...  
 ..o.. 
..ooo..
.oo@oo.
..ooo..
 ..o.. 

Символ @ — дно $(3,-1)$, кольца o и . — линии уровня вокруг него.

Как работает под капотом

Все методы спуска «видят» ландшафт только локально: им доступны значение $f(x)$ и, возможно, наклон $\nabla f(x)$ в текущей точке. Глобальной карты у них нет. Поэтому метод легко скатывается в ближайшую впадину и застревает в локальном минимуме, не зная, что за соседним хребтом есть впадина глубже. Борьба с этим — отдельная большая тема (метаэвристики, рестарты, выпуклость).

Частые ошибки

• Принять плато за минимум. На плоском участке наклон близок к нулю, но это не значит, что мы на дне.
• Игнорировать масштаб осей. Если $x$ в метрах, а $y$ в миллиметрах, «чаша» вытягивается в овраг — об этом будет урок про обусловленность.
• Думать, что минимум один. У невыпуклых функций впадин много.

Итоги

• Целевую функцию удобно представлять как рельеф, минимум — как дно впадины.
• Линии уровня показывают крутизну; градиент им перпендикулярен.
• Локальный минимум ≠ глобальный; седло, овраг и плато сбивают методы с пути.
• Методы спуска видят рельеф только локально.