Convex Optimization

Що таке опукла оптимізація?

Опукла оптимізація - це розділ оптимізації, який працює над мінімізацією опуклої цільової функції при опуклих обмеженнях. Питання оптимізації вивчаються в цьому контексті, коли цільова функція і допустима множина є опуклими.

Опуклі оптимізаційні задачі є дуже важливими завдяки багатьом корисним властивостям, які спрощують їх розв'язування та вивчення. Наприклад, у випадку задач опуклої оптимізації оптимальний розв'язок гарантовано існує у вигляді глобального мінімуму. Крім того, існує багато ефективних методів розв'язування задач опуклої оптимізації, що дозволяє використовувати їх для задач величезних розмірів, які включають велику кількість свободи та обмежень.

Опуклі функції

Опукла функція - це функція, графік якої завжди вигнутий вгору, тобто відрізок, що з'єднує будь-які дві точки графіка, завжди лежить вище або на самому графіку. Іншими словами, функція f(x) є опуклою тоді і тільки тоді:

• f (λx + (1 - λ)y) ≤ λ f (x) + (1 - λ) f(y)

для довільних x та y з області визначення f та довільного λ на проміжку [0,1]. Вимога опуклості є визначальною ознакою опуклих функцій через цю нерівність.

Опуклі функції корисні в оптимізації та інших галузях математики завдяки низці ключових особливостей. Наприклад, вони завжди неперервні і мають єдиний глобальний мінімум, що означає, що задачі оптимізації опуклих функцій часто легко розв'язуються. Крім того, перша та друга похідні опуклої функції завжди добре поводяться, що спрощує вивчення поведінки функції та виконання оптимізаційних процедур, таких як градієнтний спуск.

Лінійні, квадратичні та експоненціальні функції є прикладами опуклих функцій. Багато функцій втрат і регуляризаційних умов у машинному навчанні також є опуклими, що робить їх добре придатними для оптимізації великих наборів даних і складних моделей.

Опуклі функції - це фундаментальна ідея в математиці, яка має багато застосувань в оптимізації, машинному навчанні та інших галузях науки і техніки.

Неопуклі функції

Неопукла функція має графік, який не обов'язково вигнутий вгору, що означає, що відрізок, який з'єднує будь-які дві точки на графіку, може опускатися нижче самого графіка. Іншими словами, функція f(x) є неопуклою, якщо x та y існують в області визначення f та λ в інтервалі (0,1) такі, що:

• f (λx + (1-λ)y) > λ f (x) + (1-λ) f (y)

Ця нерівність є визначальною ознакою неопуклої функції, оскільки вона порушує обмеження на опуклість.

• Неопуклі функції мають безліч особливостей, які ускладнюють оптимізацію.

Неопуклі функції, на відміну від опуклих, можуть мати багато локальних мінімумів, що означає, що методи оптимізації можуть збігатися до поганого розв'язку, а не до глобального мінімуму.

Більше того, похідні неопуклих функцій можуть бути розривними або погано поводитися, що ускладнює обчислення оптимізаційних процедур, таких як градієнтний спуск.

Неопуклі функції включають поліноміальні функції з більш ніж двома степенями, тригонометричні функції та численні функції, що використовуються в машинному навчанні, такі як функція активації ReLU. Опуклі та неопуклі функції, незважаючи на їх складність, широко використовуються в оптимізації та машинному навчанні, оскільки вони можуть пояснити складні взаємодії між змінними та досягти високої точності у складних задачах.

Вони є фундаментальним розділом математики, що має багато застосувань в оптимізації, машинному навчанні та інших галузях науки і техніки. З іншого боку, його неопуклість створює значні перешкоди для оптимізаційних алгоритмів і вимагає використання специфічних підходів для ефективної оптимізації.

Задача опуклої оптимізації

Опукла оптимізація - це дослідження оптимізаційних задач з опуклими цільовими функціями та наборами обмежень. До бажаних властивостей задач опуклої оптимізації відносяться унікальність оптимального розв'язку, глобальна оптимальність та ефективні методи знаходження розв'язку.

Задача опуклої оптимізації має наступний загальний вигляд:

• мінімізувати f(x) за умов
  g i(x) <= 0, i = 1,..., m
  

- x - змінна оптимізації,

- f(x) позначає опуклу цільову функцію,

- g i(x) позначає обмеження опуклої нерівності, а

- h j(x) позначає обмеження афінної рівності.

Опуклість f(x) та множини обмежень є суттєвою характеристикою цієї проблеми, яка вказує на те, що цільова функція та обмеження мають "чашоподібну форму".

Оптимізація портфеля, машини опорних векторів та обробка сигналів - все це приклади задач опуклої оптимізації. Типовим прикладом є лінійне програмування, яке є підмножиною опуклої оптимізації з лінійною цільовою функцією та обмеженнями.

Методи внутрішніх точок, градієнтні підходи та субградієнтні методи можуть бути використані для вирішення проблем опуклої оптимізації. Опукла оптимізація є чудовим інструментом для вирішення широкого спектру оптимізаційних задач, оскільки ці алгоритми показали себе надзвичайно успішними та ефективними на практиці.