Условия оптимальности

Минимум гладкой функции узнаётся по двум признакам: нулевой градиент и положительная кривизна.

Стационарная точка — точка, где $\nabla f(x)=0$. Это необходимое условие локального экстремума гладкой безусловной задачи.

Необходимое условие первого порядка

Представьте, что вы стоите во впадине. В любую сторону шаг ведёт вверх — значит наклон во все стороны нулевой, иначе нашлось бы направление спуска. Формально: если $x^*$ — локальный минимум гладкой $f$, то

$$\nabla f(x^*)=0.$$

Это необходимое, но не достаточное условие: ему удовлетворяют и максимумы, и сёдла. Все такие точки называют стационарными. Поиск минимума гладкой функции = поиск корня уравнения $\nabla f(x)=0$ — отсюда родство оптимизации и решения нелинейных уравнений (метод Ньютона работает и там, и там).

Достаточное условие второго порядка

Чтобы отличить минимум от седла и максимума, смотрят на гессиан в стационарной точке:

$\nabla f(x^*)=0$ и $\nabla^2 f(x^*)$ положительно определён $\Rightarrow$ строгий локальный минимум.
$\nabla f(x^*)=0$ и $\nabla^2 f(x^*)$ отрицательно определён $\Rightarrow$ строгий локальный максимум.
$\nabla^2 f(x^*)$ знаконеопределён $\Rightarrow$ седло.

Разбор примера

$f(x,y)=x^2-y^2$. Градиент $\nabla f=(2x,-2y)$ обнуляется только в $(0,0)$. Гессиан там $\begin{bmatrix}2&0\\0&-2\end{bmatrix}$ — собственные числа $+2$ и $-2$, значит седло: по оси $x$ чаша, по оси $y$ купол. Проверим кодом, что вокруг нуля есть и более низкие, и более высокие точки.

def f(x, y):
    return x * x - y * y

center = f(0, 0)
print("f(0,0)   =", center)
print("f(0.1,0) =", round(f(0.1, 0), 4), "(выше -> рост по x)")
print("f(0,0.1) =", round(f(0, 0.1), 4), "(ниже -> спад по y)")
print("Вывод: (0,0) — седло, не минимум")

Вывод:

f(0,0)   = 0
f(0.1,0) = 0.01 (выше -> рост по x)
f(0,0.1) = -0.01 (ниже -> спад по y)
Вывод: (0,0) — седло, не минимум

Численная проверка стационарности

На практике алгоритм останавливают, когда $\lVert\nabla f(x_k)\rVert$ становится меньше порога $\tau$. Посмотрим, как градиент стремится к нулю по мере приближения к дну чаши $f(x)=(x-2)^2$.

def grad(x):           # производная (x-2)^2 = 2(x-2)
    return 2 * (x - 2)

for x in [0.0, 1.0, 1.5, 1.9, 1.99, 2.0]:
    g = grad(x)
    stop = "СТОП" if abs(g) < 1e-2 else ""
    print(f"x={x:<5} |grad|={abs(g):.3f} {stop}")

Вывод:

x=0.0   |grad|=4.000 
x=1.0   |grad|=2.000 
x=1.5   |grad|=1.000 
x=1.9   |grad|=0.200 
x=1.99  |grad|=0.020 
x=2.0   |grad|=0.000 СТОП

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

Все итеративные методы по сути ищут корень $\nabla f(x)=0$. Поэтому критерий останова — малость нормы градиента. Но осторожно: на плато градиент тоже мал, хотя минимума нет; и наоборот, в крутом овраге около минимума градиент бывает велик. Поэтому в серьёзных солверах комбинируют несколько критериев: малость градиента, малость шага $\lVert x_{k+1}-x_k\rVert$ и малость изменения функции.

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

Объявить минимумом любую стационарную точку. Это может быть седло или максимум — проверяйте гессиан.
Единственный критерий останова. Только по градиенту легко остановиться на плато; комбинируйте критерии.
Забыть про границы. Условие $\nabla f=0$ верно для безусловной задачи; с ограничениями минимум может лежать на границе, где градиент не нулевой.

Итоги

Необходимое условие минимума гладкой безусловной задачи: $\nabla f(x^*)=0$.
Достаточное: плюс положительно определённый гессиан.
Поиск минимума = поиск корня $\nabla f=0$; останов — по малости градиента (плюс ещё критерии).