Лекция 15. Метод покоординатного спуска и метод Ньютона

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

Примеры запуска:
  python coordinate_newton.py --variant 7 --output results_7
  python coordinate_newton.py --method coordinate --order 21 --output results_order21
  python coordinate_newton.py --example ill --output results_ill
  python coordinate_newton.py --example rotated --output results_rotated
  python coordinate_newton.py --example quartic --output results_quartic
  python coordinate_newton.py --example overshoot --output results_overshoot
  python coordinate_newton.py --example doublewell --output results_doublewell
  python coordinate_newton.py --example doublewell --method modified --delta 1

Методы:
 coordinate — точная последовательная минимизация по координатам квадратичной функции;
 steepest — наискорейший спуск с точным квадратичным шагом, для сравнения с лекцией 14;
 newton — полный шаг обычного Ньютона, без защиты от неопределенного Гессиана;
 damped — Ньютон с положительно определенным Гессианом и дроблением Армихо;
 modified — сдвиг Гессиана до минимального собственного значения delta, затем Армихо.

В квадратичных задачах compare запускает coordinate, steepest, newton, damped.
В нелинейных задачах compare запускает newton, damped, modified.
coordinate и steepest в этой программе доступны только для квадратичных задач.
Порядок координат --order 12 или 21 влияет только на coordinate.
--tol: допуск нормы полного градиента, по умолчанию 1e-6.
--max-iter: предел внешних итераций, по умолчанию 5000.
Для coordinate внешняя итерация — полный цикл из двух координатных подшагов.
--delta: нижняя граница собственных значений измененной матрицы, по умолчанию 1.
Это значение подобрано к масштабу примеров, а не является универсальной константой.
Армихо: начальный шаг 1, множитель дробления 1/2, sigma=1e-4, максимум 60 проб.

Примеры:
 main — задача лекций 13–14 с центром (1,-1), стартом (3,0), минимумом 3;
 ill — диагональный Гессиан diag(2,50), старт (2,1);
 rotated — Гессиан [[26,-24],[-24,26]] с тем же спектром, старт (2,1);
 quartic — x^4/4+x^2/2+2y^2, старт (1,1);
 overshoot — sqrt(1+x^2)+y^2/2, старт (2,0), демонстрация расходимости полного шага;
 doublewell — x^4/4-x^2/2+y^2/2, старт (1/4,1), два минимума и седловая точка.

В overshoot обычный newton намеренно ограничен тремя переходами даже при большем
--max-iter; это предотвращает продолжение явно расходящейся последовательности.
Это демонстрация, а не успешное завершение минимизации.
В doublewell обычный newton достигает малого градиента около седла.
Поле classification необходимо проверять вместе с status.

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

Счетчики:
 n_f — все вычисления функции в алгоритме, включая отклоненные пробы;
 n_grad — полные градиенты, включая начальный и конечный;
 n_hess — Гессианы для построения направления;
 n_solve — попытки решения систем для направления;
 n_partial — отдельные частные производные в координатных подшагах;
 n_hvp — дополнительные произведения A@g для шага наискорейшего спуска;
 coordinate_steps — число выполненных координатных подшагов, включая нулевые.
Расчет учебных ошибок, рисунки и финальная диагностика Гессиана не включены.
Спектральный анализ для сдвига не имеет отдельного счетчика, но требует затрат.
Счетчики итогового результата включают и работу неудавшегося шага, если он был.
В history alpha и mu в строке k>0 относятся к переходу k-1 -> k.

Статусы:
 gradient_tolerance — выполнен только критерий стационарности;
 iteration_limit — исчерпан предел внешних переходов;
 non_positive_hessian — Гессиан непригоден для защищенного метода без сдвига;
 singular_hessian — система не решается из-за вырожденности;
 not_descent — полученное направление не дает отрицательную производную;
 line_search_failed — не удалось принять пробу Армихо за 60 проверок;
 stalled — новая точка совпала со старой при еще большом градиенте;
 nonfinite — получены неконечные значения.

Диагностика:
 positive_definite_hessian — в итоговой приближенной стационарной точке H>0;
 indefinite_hessian — H имеет собственные значения разных знаков;
 inconclusive_or_nonminimum — прочие случаи, требуется дополнительный анализ;
 not_stationary_to_tolerance — внешний критерий не выполнен.
Малый градиент и даже H>0 в приближенной точке сами по себе не доказывают
глобальный минимум произвольной невыпуклой функции.
Для поставляемых квадратичных вариантов и выпуклых примеров минимум известен.
Для doublewell известны оба глобальных минимума; distance — расстояние до
ближайшего из них. В квадратичных задачах gap вычисляется устойчиво как e@A@e/2.
В нелинейных задачах gap=f-f_min может округляться к нулю раньше градиента.
