Можно ли применить градиентный спуск к невыпуклым функциям?

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

Однако, как насчет функции на этом рисунке:

Здесь синий отрезок пересекает функцию красного цвета. Тем не менее, функция по-прежнему имеет один минимум, и поэтому градиентное снижение все равно приведет вас к этому минимуму.

Итак, мои вопросы:

1) Функция на этом рисунке выпуклая или невыпуклая?

2) Если он невыпуклый, то могут ли применяться методы выпуклой оптимизации (градиентный спуск)?

Функция, которую вы изобразили, действительно не выпуклая. Тем не менее, это квазивыпуклый .

$x_1, x_2, \ldots$$f(x_1) > f(x_2) > \ldots$

Градиентный спуск в конечном итоге будет сходиться к стационарной точке функции, независимо от выпуклости. Если функция выпуклая, это будет глобальный минимум, но если нет, то это может быть локальный минимум или даже седловая точка.

Квазивыпуклые функции - интересный случай. Любой локальный минимум квазивыпуклой функции также является глобальным минимумом, но квазивыпуклые функции также могут иметь стационарные точки, которые не являются локальными минимумами ($f(x) = x^3$например). Таким образом, теоретически возможно, что градиентный спуск застрянет в такой неподвижной точке, а не достигнет глобального минимума. В вашем примере, если плечо на левой стороне графика будет идеально выровнено, градиентный спуск может застрять там. Тем не менее, такие варианты, как метод «тяжелого мяча», могут быть способны «пролонгировать» и достичь глобального минимума.

Павел уже упомянул один важный момент:

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

Что затрудняет невыпуклую оптимизацию, так это наличие седловых точек и локальных минимумов, где градиент равен (0, ..., 0) и которые имеют произвольно плохое объективное значение.

Найти глобальный минимизатор в такой настройке, как правило, сложно для NP, и вместо этого нужно найти локальный минимизатор.

Однако обратите внимание, что:

• Вероятность того, что GD застрянет в седле, фактически равна 0 ( см. Здесь ).
• Тем не менее, наличие седловых точек может серьезно замедлить прогресс GD вниз, потому что направления низкой кривизны используются слишком медленно ( см. Здесь )

Таким образом, в зависимости от размерности вашей проблемы может быть целесообразно перейти к процедуре оптимизации второго порядка.