Тема 2. Оптимизационные методы получения детерминированных оценок (стр. 7 )

Функция называется выпуклой в выпуклой области , если для любых двух точек и из области выполняется неравенство

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

для любого , .

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

.

Для выпуклых и вогнутых функций нескольких переменных имеют место следующие свойства:

·  Если – выпуклая функция, то функция вогнутая.

·  Линейная комбинация выпуклых (вогнутых) функций с неотрицательными коэффициентами также является выпуклой (вогнутой) функцией, то есть, если функции , выпуклые и числа , то функция

тоже выпуклая.

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

(2.8)

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

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

(2.9)

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

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

. (2.10)

Уравнение есть уравнение касательной к кривой в точке , поэтому согласно (2.10) касательная к выпуклой кривой всегда лежит ниже самой кривой (рис. 2.15).

Рис. 2.15. Иллюстрация неравенства (2.10)

Пример 2.8. Определить, является ли выпуклой функция двух переменных

.

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

, ,

, , .

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

.

Следовательно, данная функция выпукла на всей плоскости.

2.5.2. Понятие о выпуклом программировании

Пусть функция определена и дифференцируема в выпуклой области . В любой точке локального экстремума функции, лежащей внутри области , все частные производные обращаются в нуль. Такие точки называются стационарными. Определив стационарную точку, еще нельзя сказать, является ли она на самом деле точкой экстремума (локального или глобального), или вообще не является точкой экстремума. Поэтому для определения глобальных экстремумов требуется дополнительное, подчас очень сложное, исследование, включая, кроме того, и исследование на границе области. Однако, при отыскании глобального минимума выпуклой функции (или глобального максимума вогнутой функции) такое дополнительное исследование проводить не нужно. Точнее справедлива следующая теорема.

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

Для максимума выпуклой (минимума вогнутой) функции имеет место следующее утверждение.

Теорема 2. Пусть функция выпуклая (вогнутая) в области , тогда ее глобальный максимум (глобальный минимум) достигается на границе области.

Справедливость обеих теорем в случае двух переменных легко подтверждается геометрически. На рис.2.16 представлен график выпуклой функции . Стационарная точка (в этой точке касательная плоскость к поверхности параллельна плоскости ) является точкой глобального минимума функции. Глобальный максимум функции достигается в граничной точке .

Рис. 2.16. График выпуклой функции двух переменных

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

2.5.3. Теорема Куна-Таккера

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

(2.11)