Optimization Atlas

LandscapeЛандшафт

What an optimization problem looks like from above, and what makes one hard.Как задача оптимизации выглядит сверху и что делает её трудной.

pointточка—

f(x)—

∇f(x)—

‖∇f‖—

λ₁, λ₂ ofматрицы ∇²f—

κ = |λ|_max/|λ|_min—

curvatureкривизнаmove the cursor over the plotнаведите курсор на график

Test functionТестовая функция

ViewВид

Both views use the same logarithmically spaced levels, so narrow valleys stay visible.Оба вида строятся по одним и тем же уровням с логарифмическим шагом, поэтому узкие овраги остаются видны.

Gradient arrow under the cursorСтрелка градиента под курсором Mark known optima and saddlesОтмечать известные оптимумы и сёдла

Five words that decide everythingПять слов, которые решают всё

A minimum is a point from which no small move decreases f. A problem is convex when every chord lies above the graph, and then any local minimum is already global. It is smooth with constant L when the gradient never changes faster than L, which is exactly what makes the step 1/L safe. The condition number κ = λ_max/λ_min of the Hessian says how elongated the level sets are, and a large κ is the narrow valley in which plain gradient descent zigzags. At a saddle point the Hessian has eigenvalues of both signs, so the surface curves up along one direction and down along another and the gradient still vanishes. Everything else in this atlas is a strategy for coping with these five facts.Минимум — это точка, из которой никакой малый сдвиг не уменьшает f. Задача выпуклая, если любая хорда лежит не ниже графика, и тогда всякий локальный минимум уже глобальный. Она гладкая с константой L, если скорость изменения градиента нигде не превышает L, — именно это и делает шаг 1/L безопасным. Число обусловленности гессиана κ = λ_max/λ_min показывает, насколько вытянуты множества уровня, а большое κ — это и есть тот узкий овраг, в котором обычный градиентный спуск идёт зигзагом. В седловой точке у гессиана есть собственные значения обоих знаков: вдоль одного направления поверхность изгибается вверх, вдоль другого — вниз, а градиент всё равно обращается в нуль. Всё остальное в этом атласе — способы справиться с этими пятью фактами.

Continuous optimizationНепрерывная оптимизация

Click the plot to move the starting point. Every enabled method restarts from there.Щёлкните по графику, чтобы перенести начальную точку. Все включённые методы перезапускаются из неё.

ConvergenceСходимость

methodметод	k	f(x_k)	‖∇f‖	f evalsвызовы f	∇f evalsвызовы ∇f	stateсостояние

Stochastic optimizationСтохастическая оптимизация

Minimise an average of 200 quadratic terms. Every term has its own minimum; the one you want sits at their centre.Минимизируем среднее 200 квадратичных слагаемых. У каждого слагаемого свой минимум, а искомый лежит в их центре.

The noise ballШар шума last 200 iterates, zoomed on x*последние 200 итераций, окрестность x* крупным планом

Escape the saddleВыход из седловой точки both start on the ridgeоба стартуют на гребне

ConvergenceСходимость: F(x) − F*

optimizerоптимизатор	updatesобновления	epochsэпохи	F − F*	‖x − x*‖	batchбатч	stateсостояние

Constraints and nonsmoothnessОграничения и негладкость

Hover the plot to see any point projected onto the feasible set; click to move the starting point.Наведите курсор на график, чтобы увидеть проекцию любой точки на допустимое множество; щёлкните, чтобы перенести начальную точку.

Why L1 gives sparsityПочему L1 даёт разреженность same f, two penaltiesодна и та же f, два штрафа

Soft thresholdingМягкая пороговая функция prox ofфункции λ|x|

ConvergenceСходимость: f(x) − f*

methodметод	k	f(x)	f − f*	optimalityмера оптимальности	stateсостояние

Discrete optimizationДискретная оптимизация

Seven independent widgets. Each one runs the real algorithm a step at a time; nothing here is a recording.Семь независимых виджетов. Каждый выполняет настоящий алгоритм шаг за шагом; здесь ничего не записано заранее.

Cheat sheetШпаргалка

Every method in the course in one table, generated from the same registries the playgrounds run on. Click any row to open its widget with a matching setup already applied.Все методы курса в одной таблице, собранной из тех же реестров, на которых работают интерактивные разделы. Щёлкните по любой строке, чтобы открыть соответствующий виджет с уже подобранной настройкой.