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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

λ_i≥0, i = 1 ¸ m.

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

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