Лекция 14. Метод наискорейшего спуска

Требуется Python 3.10 или новее, NumPy и Matplotlib.
Распакуйте архив полностью в одну папку. Откройте в ней терминал:
  python -m pip install numpy matplotlib
  python steepest_descent.py
В Windows вместо python можно использовать py.

Примеры:
  python steepest_descent.py --example ill --output results_ill
  python steepest_descent.py --example nonlinear --output results_nonlinear
  python steepest_descent.py --variant 7 --output results_7
  python steepest_descent.py --method exact --tol 1e-8 --output results_exact
  python steepest_descent.py --method bisect --eta 1e-4 --output results_eta4

По умолчанию: основной пример, сравнение 1/L, 2/(m+L), точного шага и
численного поиска корня производной на луче. Для нелинейного примера
доступен только bisect. Все направления — ненормированный антиградиент.
Для 18 вариантов используется та же таблица, что в лекциях 10–13.

--tol задает норму градиента для внешней остановки (по умолчанию 1e-6).
--eta задает относительную точность направленной производной при поиске
шага: |phi'(alpha)| <= eta * ||g||^2 (по умолчанию 1e-8).
--max-iter ограничивает число внешних переходов (по умолчанию 5000).

Численный поиск начинает с alpha=1, увеличивает правый конец вдвое
до смены знака производной, затем делит интервал пополам.
Предпосылка: строгая выпуклость функции на луче и существование минимума.
Все поставляемые примеры удовлетворяют этой предпосылке. Этот поиск
не является универсальным глобальным решателем для невыпуклых функций.
Точная формула шага предназначена только для квадратичной функции с A>0.
Матрица A — Гессиан; коэффициенты a,b,c из вариантов дают A=2[[a,b],[b,c]].

Выходы в папке --output:
  *_history.csv — принятые точки, шаги, ошибки, нормы, ортогональность;
  bisect_trials.csv — все пробы производной по направлению;
  summary.json — итоговые статусы и счетчики;
  comparison.png — графики сходимости, 300 dpi.
Повторный запуск в ту же папку перезаписывает одноименные файлы.

n_f: вычисления функции внутри алгоритма.
n_grad: все вычисления градиента, включая пробы одномерного поиска;
принятый пробный градиент используется повторно.
n_hvp: дополнительные произведения A@g для точной формулы шага.
Вычисление спектра, учебных ошибок и построение рисунков не включены.
Стоимость одного вызова функции и градиента может различаться.

В строке k>0 alpha и orthogonality относятся к переходу из k-1 в k.
orthogonality = |g_k@g_(k-1)|/(||g_k|| ||g_(k-1)||).
При нулевом знаменателе записывается пустое значение (None/null).
Около минимума относительная ортогональность чувствительна к округлению.
Для квадратичной задачи gap вычисляется как e@A@e/2 без вычитания близких
значений функции. Известное решение используется только для проверки.

Статусы:
 gradient_tolerance — выполнен критерий по градиенту;
 iteration_limit — достигнут лимит внешних переходов;
 stalled — новая точка совпала со старой в машинной арифметике;
 nonfinite — получено бесконечное значение или NaN;
 bracket_failed — не найден интервал смены знака за 60 проб;
 line_search_limit — не достигнут критерий за 80 делений;
 line_search_stalled — интервал нельзя разделить в машинной арифметике.
Только первый статус подтверждает выполнение заданной точности.
В итоговых счетчиках учитываются и затраты неудачного поиска шага.
