Почему невыпуклость должна быть проблемой в оптимизации?

Я был очень удивлен, когда начал читать что-то о невыпуклой оптимизации в целом, и я увидел такие утверждения:

Многие важные практические проблемы являются невыпуклыми, и большинство невыпуклых задач трудно (если не невозможно) решить точно в разумные сроки. ( источник )

или

В общем, NP-трудно найти локальный минимум, и многие алгоритмы могут застрять в седловой точке. ( источник )

Я делаю вид невыпуклых оптимизаций каждый день, а именно расслабление молекулярной геометрии. Я никогда не считал это чем-то хитрым, медленным и склонным застрять. В этом контексте мы имеем явно многомерные невыпуклые поверхности (> 1000 степеней свободы). Мы используем в основном технику первого порядка, основанную на самом крутом спуске и динамическом гашении, например, FIRE , которые сходятся за несколько сотен шагов к локальному минимуму (меньше, чем DOF). Я ожидаю, что с добавлением стохастического шума он должен быть чертовски устойчивым. (Глобальная оптимизация - это отдельная история)

Я как-то не представляю, как должна выглядеть поверхность потенциальной энергии , чтобы эти методы оптимизации застряли или медленно сходились. Например, очень патологическая PES (но не из-за невыпуклости) является этой спиралью , но это не такая большая проблема. Можете ли вы привести наглядный пример патологического невыпуклого ПЭС?

Поэтому я не хочу спорить с цитатами выше. Скорее у меня такое чувство, что я что-то здесь упускаю. Возможно, контекст.

$\arg\min f(x)$

1. Возможное решение: конкретный выбор решающей переменной и соответствующего ей целевого значения , AND ф ( х ⋆$x^\star$$f(x^\star)$
2. Доказательство оптимальности: математическое доказательство того, что выбор является глобально оптимальным, т. Е. Что выполняется для любого выбора . f ( x ) ≥ f ( x ⋆ ) $x^\star$$f(x) \ge f(x^\star)$$x$

Когда выпуклый, оба ингредиента легко получаются. Градиентный спуск находит подходящее решение которое делает градиент исчезающим . Доказательство оптимальности следует из простого факта, изложенного в MATH101, что если выпуклая и ее градиент обращается в нуль в , то является глобальным решением.х ⋆ ∇ F ( х ⋆ ) = 0 е ∇ е х ⋆ х $f$$x^\star$$\nabla f(x^\star)=0$$f$$\nabla f$$x^\star$$x^\star$

Когда невыпуклый, возможное решение все еще может быть легко найти, но доказательство оптимальности становится чрезвычайно трудным. Например, мы можем запустить градиентный спуск и найти точку . Но когда невыпуклый, условие необходимо, но больше не достаточно для глобальной оптимальности. Действительно, этого даже недостаточно для локальной оптимальности, то есть мы даже не можем гарантировать, что является локальным минимумом, основанным только на его информации о градиенте. Один из подходов - перечислить все точки, удовлетворяющие∇ F ( х ⋆ ) = 0 F ∇ F ( х ) = 0 х ⋆ ∇ F ( х ) = $f$$\nabla f(x^\star)=0$$f$$\nabla f(x)=0$$x^\star$$\nabla f(x)=0$ , и это может быть сложной задачей даже в одном или двух измерениях.

Когда математики говорят, что большинство проблем невозможно решить, они действительно говорят, что доказательство (даже локальной) оптимальности невозможно построить . Но в реальном мире нас часто интересует только вычисление «достаточно хорошего» решения, и это можно найти бесконечным количеством способов. Для многих крайне невыпуклых задач наша интуиция говорит нам, что «достаточно хорошие» решения на самом деле являются глобально оптимальными, даже если мы не в состоянии доказать это!

Примером хитрой низкоразмерной задачи может быть:

Учитывая, что вы достигли локальных минимумов, как вы можете быть уверены, что это что-то близкое к мировым минимумам? Как вы узнаете, является ли ваш результат уникальным оптимальным решением, если оно является глобально оптимальным? Как вы можете создать надежный алгоритм для всех холмов и долин, чтобы он не застрял где-нибудь?

Пример, подобный этому, - это когда вещи могут стать сложными. Очевидно, что не все проблемы такие, но есть некоторые. Что еще хуже, в промышленных условиях функция затрат может занимать много времени для вычисления И иметь проблемную поверхность, подобную приведенной выше.

Пример реальной проблемы

Примером, который я мог бы использовать на работе, является оптимизация алгоритма наведения ракеты, который мог бы быть устойчивым при многих условиях запуска. Используя наш кластер, я мог получить необходимые измерения производительности примерно за 10 минут для одного условия. Теперь, чтобы адекватно оценить надежность, мы бы хотели, по крайней мере, выборку условий для оценки. Допустим, мы выполнили шесть условий, поэтому оценка этой функции затрат занимает один час.

Нелинейная динамика ракет, динамика атмосферы, процессы с дискретным временем и т. Д. Приводят к довольно нелинейной реакции на изменения в алгоритме наведения, что затрудняет оптимизацию. Тот факт, что эта функция стоимости будет невыпуклой, делает факт, что для оценки большой проблемы требуется много времени. Пример, подобный этому, - это то, где мы стремимся получить лучшее, что можем, за отведенное нам время.

Проблема заключается в седловых точках, которые обсуждаются в посте, который вы связали. Из аннотации одной из связанных статей :

Однако в целом трудно гарантировать, что такие алгоритмы даже сходятся к локальному минимуму из-за существования сложных седловых структур в больших размерностях. Многие функции имеют вырожденные седловые точки, так что производные первого и второго порядка не могут различить их с локальными оптимумами . В этой статье мы используем производные более высокого порядка, чтобы избежать этих седловых точек: мы разработали первый эффективный алгоритм, который гарантированно сходится к локальному оптимуму третьего порядка (в то время как существующие методы имеют не более второго порядка). Мы также показываем, что NP-сложнее расширить это до нахождения локального оптимума четвертого порядка.

По сути, у вас могут быть функции, в которых у вас есть седловые точки, которые неотличимы от локальных минимумов при рассмотрении 1-го, 2-го и 3-го производных. Вы можете решить эту проблему, перейдя к оптимизатору более высокого порядка, но они показывают, что поиск локального минимума 4-го порядка является NP трудным.

$x^2y+y^2$

Вы могли бы использовать ряд эвристических методов, чтобы избежать таких точек, которые могут работать для многих (большинства?) Примеров из реального мира, но нельзя доказать, что они всегда работают.
В сообщении, на которое вы ссылаетесь, они также обсуждают условия, при которых вы можете избежать таких седловых точек за полиномиальное время.