Выпуклые задачи оптимизации

Задача (1.1) называется выпуклой, если X – выпуклое множество, а f(x) – выпуклая функция на X.

Множество X, содержащееся в называется выпуклым, если выполняется:

Выпуклое множество Невыпуклое множество

Функция f(x), определенная на выпуклом множестве называется выпуклой на X, если

(1.29)

Функция f(x) называется вогнутой, если функция -f(x) выпуклая.

Геометрическая иллюстрация выпуклой функции.

Любая точка хорды в случае выпуклой функции лежит не ниже соответствующей точки самой функции.

Проверка функции на выпуклость.

Функция f(x) является выпуклой на выпуклом множестве X, если ее матрица Гессе не отрицательно определена для всех .

Свойства выпуклых задач оптимизации:

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

Доказательство: считается, что задача (1.1) выпуклая.

Пусть – локальное решение задачи (1.1). Докажем, что – глобальное решение, то есть

Докажем от противного. Предположим, что не выполняется, то есть Таким образом - значение функции в окрестности точки (при λ=0 получаем саму точку , при увеличении λ - +добавка).

Получается, что:

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

2⁰ Необходимые условия оптимальности для выпуклых задач оптимизации являются также достаточными.

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