Свойства выпуклых и гладких функций

Выпуклые функции не имеют перемежающихся подъемов и спусков, и, следовательно, локальных экстремумов. Дуга между точками на кривой f (X), выражающей выпуклую функцию (выпуклостью вниз), всегда лежит ниже прямой, соединяющей эти точки. Дуга между точками на кривой f (X), выражающей выпуклую функцию (выпуклостью вверх), всегда лежит выше прямой, соединяющей эти точки.

Если задача имеет выпуклую целевую функцию и выпуклую систему ограничений, то такая задача называется выпуклой задачей математического программирования.

Задача выпуклого программирования, если и - выпуклые функции , .

Гладкость функций означает непрерывность ее первых производных или существование и непрерывность ее частных производных первого порядка.

1. Если умножить выпуклую функцию на (-1), то функция вогнутая и наоборот.

2. Сумма конечного числа выпуклых функций - выпуклая функция.

- невыпуклые функции

, , , - выпуклые функции

- выпуклая функция, так как является суммой конечного числа выпуклых функций.

3. Пусть функции

- выпуклые. Тогда множество , определяемое условиями :

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

Функция имеет в точке абсолютный (глобальный) максимум, если выполняется неравенство , где - любая точка, принадлежащая области определения функции.

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

Теорема Вейерштрасса⁶. Непрерывная функция, определенная на ограниченном, замкнутом множестве, в одной из точек множества принимает максимальное (минимальное) значение.

Теорема о совпадении локального экстремума с глобальным (абсолютным). В любой задаче выпуклого программирования любой локальный минимум обязан совпадать с глобальным.

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

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

Теорема Куна –Таккера ⁷(для седловой точки). Посмотреть

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

Если эта область имеет внутренние точки, то есть выполняется условие Слейтера: существует решение X , такое, что _i(X) < 0 для всех i = 1  m; тогда для того чтобы X* было оптимальным решением задачи, необходимо и достаточно, чтобы существовал неотрицательный m-мерный вектор λ*(λ*₁,λ*₂,…,λ*_m) такой, что пара (X*, λ*) является седловой точкой функции Лагранжа.

, где ≥0 можно записать в виде неравенств, т.е.

f(X)+ λ*_i·_i(X) ≥ f(X*)+ λ*_i ·_i(X*) ≥ f(X*)+ λ_i ·_i(X*), i = 1  m.

λ_i≥0, i = 1  m.

При решении задач выпуклого программирования предполагаем, что целевая функция имеет единственный экстремум (то есть решается одноэкстремальная задача).

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