Понятия выпуклого множества и выпуклой функции

Классическая задача на условный экстремум

Задача условной оптимизации

Задача безусловной оптимизации

Задача (1.1) называется задачей безусловной оптимизации, если Х= Rⁿ, т.е. если она имеет вид

f(x) ® min, хÎRⁿ. (1.5)

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

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

Пусть

- вектор первых частных производных (градиент) функции f в точке х*ÎRⁿ;

- матрица вторых частных производных (гессиан) функции f в точке х*ÎRⁿ.

Нижеследующая теорема указывает необходимое условие локаль­ной оптимальности первого порядка.

Теорема 1.2. Пусть функция f дифференцируема в точке х*ÎRⁿ. Если х* — локальное решение задачи (1.5), то

f'(x*) = 0. (1.6)

Точка х*, удовлетворяющая условию (1.6), называется стацио­нарной точкой функции f или задачи (1.5). Стационарная точка не обязана быть решением, т.е. (1.6) не является достаточ­ным условием оптимальности. Для выявления «посторонних» стацио­нарных точек может использоваться необходимое условие локальной оптимальности второго порядка.

Теорема 1.3. Пусть функция f дважды дифференцируема в точке х*ÎRⁿ. Если х* - локальное решение задачи (1.5), то матрица f" (х*) неотрицательно определена, т. е.

при всех hÎRⁿ. (1.7)

Достаточное условие локальной оптимальности содержит харак­терное усиление требований на матрицу f"(х*).

Теорема 1.4. Пусть функция f дважды дифференцируема в точке х*ÎRⁿ. Предположим, что f'(х*) = 0, а матрица f"(х*) положи­тельно определена, т.е.

при всех hÎRⁿ, h ¹ 0. (1.8)

Тогда х* - строгое локальное решение задачи (1.5).

В тех случаях, когда функция f достаточно проста, теоремы 1.2-1.4 позволяют явным образом решить задачу (1.5). При этом для исследования матрицы f"(х*) на неотрицательную и положи­тельную определенность, как правило, используется критерий Силь­вестра.

Пример 1.1. Рассмотрим задачу

, х*ÎRⁿ.

Условие (1.6) имеет здесь вид

, .

Решениями этой системы (стационарными точками) являются x^l = (0,0) и x² = (1,1). При этом

, , .

По критерию Сильвестра матрица f"(х¹) не является неотрицательно определенной, а матрица f"(х²) положительно определена. Тогда, в силу теоремы 1.3, точка х¹ не может быть решением задачи; в силу теоремы 1.4 точка х² - строгое локальное решение задачи.

Задача (1.1) называется задачей условной оптимизации (условной задачей), если X - собственное под­множество пространства Rⁿ. Для такой задачи сохраняют силу утверждения теорем 1.2—1.4, если ее локальное решение x* является внутренней точкой допустимого множества Х (х* Î int X). Однако для многих условных задач минимум дости­гается именно на границе, в силу чего для них эти классические результаты анализа неприменимы. При переходе от безус­ловных к условным задачам все вопросы оптимизации становятся более сложными.

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

, a Î R.

Для геометрической интерпретации данной (двумерной) задачи необходимо изобразить ее допустимое множество Х и несколько харак­терных линий уровня целевой функции f (рис.1.1).

а) б)

Чтобы отразить характер изменения функции, у данной линии уровня L_a полезно ставить знак «+» с той стороны, где f принимает значения, большие a, и знак «—» - с другой. В геометрическом плане поиск (глобального) решения сводится к нахождению минимального числа a* среди всех a таких, что линия уровня L_a, имеет непустое пересечение с Х. При этом любая точка является решением задачи, а само a* = f(х*) - мини­мальным значением функции f на X. Как отмечалось, возможны два случая: х* лежит внутри (рис.1.1, а) и на границе (рис.1.1, б) множества X.

Пример 1.2. Пусть в задаче (1.1) допустимое множество Х представляет собой круг единичного радиуса с центром в нуле, а целевая функция f имеет вид f (x)=(x₁ - 2)²+(x₂ - 1)² (рис.1.2). Ее линия уровня L_a, при a > 0 является окружностью радиуса с центром в точке (2, 1), при a = 0 вырождается в эту точку, а при a < 0 пуста. Геометрически ясно, что здесь - это та из указан­ных окружностей, которая касается круга X. Отсюда без труда определяется, что решением данной задачи служит .

Рис 1.2

Классическая задача на условный экстремум. Это задача (1.1) (или (1.4)) с допустимым множествомX, заданным системой конечного числа уравнений:

.

Обычно эта задача записывается в виде

f(x)® min,

g_i(x)= 0, i = 1,…,m, (1.9)

т.е. явно указывается не само допустимое множество, а система, его определяющая.

При исследовании задачи (1.9) важную роль играет ее функция Лагранжа, т. е. функция

,

где хÎRⁿ, y₀ÎR, y=(y₁,…,y_m) Î R^m. Частные производные этой функции по координатам вектора х имеют вид

. (1.10)

Составленный из них вектор обозначается через , т. е.

. (1.11)

Теорему о необходимых условиях локальной оптимально­сти в задаче (1.9), известная как правило множителей Лагранжа.

Теорема 1.5. Пусть функции f, g₁, ..., g_m непрерывно диффе­ренцируемы в некоторой окрестности точки х*ÎRⁿ. Если х* - ло­кальное решение задачи (1.9), то существует число и вектор , не равные нулю одновременно и такие, что

. (1.12)

Если при этом градиенты линейно независимы (условие регулярности), то .

Условие (1.12) с учетом (1.11) означает, что градиенты линейно зависимы. В частности, если т =1, то и коллинеарны.

Фигурирующие в теореме 1.5 числа называются множителями Лагранжа. Любая точка х*, удовлетворяющая при некоторых и , , условию (1.12), а также условию допустимости

g_i(x*)= 0, i = l, ..., m, (1.13)

называется стационарной точкой задачи (1.9).

Как и в случае безусловной задачи оптимизации, стационарные точки задачи (1.9) не обязаны быть ее решениями. Здесь также существуют необходимые и достаточные условия оптимальности с привлечением вторых производных. Обозначим через

матрицу вторых производных функции Лагранжа по координатам вектора х.

Теорема 1.6. Пусть функции f, g₁, ..., g_m дважды дифферен­цируемы в точке х*ÎRⁿ и непрерывно дифференцируемы в ее неко­торой окрестности, причем градиенты линейно независимы. Если х* - локальное решение задачи (1.9), то

при любых , у*, удовлетворяющих (1.12), и всех h ÎRⁿ таких, что

, i = 1, …, m. (1.14)

Теорема 1.7. Пусть функции f, g₁, ..., g_m дважды дифферен­цируемы в точке х*ÎRⁿ, удовлетворяющей (1.13). Предположим, что при некоторых и выполняется условие (1.12) и, кроме того,

при всех ненулевых h ÎRⁿ, удовлетворяющих (1.14). Тогда х* - стро­гое локальное решение задачи (1.9).

В простейших случаях теоремы 1.5—1.7 позволяют решить за­дачу в явном виде.

Пример 1.3. Пусть требуется найти локальные решения задачи

,

где а > 0 и b > 0 - заданные числа. Ясно, что указанное в тео­реме 1.5 условие регулярности здесь выполнено. Выпишем (регу­лярную) функцию Лагранжа:

.

Поскольку , то система для опре­деления стационарных точек имеет вид:

, .

Без труда проверяется, что эта система имеет три решения:

1) x₁ = 0, x₂ = 1, y = b/3;

2) x₁ = 1, x₂ = 0, y = a/3;

3) , , .

Далее, имеем

.

Для указанных решений эта матрица принимает соответственно вид

, , .

Условие (1.14) выглядит здесь следующим образом:

.

Для первых двух решений это означает, что h₂ = 0 и h₁ = 0 соот­ветственно. Отсюда ясно, что матрицы A¹ и А² удовлетворяют усло­вию, указанному в теореме 1.7 (хотя, заметим, они не являются положительно определенными). Следовательно, точки (0, 1) и (1, 0) - строгие локальные решения исследуемой задачи. Для матрицы A³ заведомо не выполняется условие, указанное в теореме 1.6. Поэтому точка не может быть решением данной задачи. Ясно, однако, что эта точка служит строгим локальным решением задачи максимизации той же функции при тех же ограничениях

Иногда задачу (1.9) удается решить, используя лишь теорему 1.5.

Множество Х Ì Rⁿ называется выпуклым, если при всех х¹, х² Î X, l Î [0, 1]. Иными словами, множество Х выпукло, если оно вместе с любыми своими двумя точками х¹ и х² содержит соединяющий их отрезок, т. е. множество вида

[x¹, x²] = {x Î Rⁿ | x = x² + l(x¹ - x²), 0 £ l £ 1}

(рис. 1.4).

Рис.1.4. а) Выпуклое множество; б) невыпуклое множество

На числовой прямой R выпуклыми множествами являются все­возможные промежутки, т.е. одноточечные множества, интервалы, полуинтервалы, отрезки, полупрямые и, наконец, сама. прямая. При­мерами выпуклых множеств в пространстве Rⁿ служат само прост­ранство, любое его линейное подпространство, одноточечное множе­ство, шар, отрезок, а также следующие множества:

– прямая, проходящая через точку х⁰ в направлении вектора h;

– луч, выходящий из точки х⁰ в направлении h;

(1.15)

– гиперплоскость с нормалью р;

, (1.16)

– порождаемые ею полупространства.

Все перечисленные множества, кроме шара, являются частными случаями выпуклого множества вида

X = {x Î Rⁿ | Ax £ b} = { x Î Rⁿ | á ai, xñ £ b_i, i = 1,…, m}, (1.17)

где A – некоторая матрица размера т ´ п со строками a₁, …, a_m, b = (b₁, …, b_m) ÎR^m (т = 1, 2, ...). Множества вида (1.17) принято называть полиэдральными или просто полиэдрами. Таким образом, полиэдр — это множество решений некоторой системы конечного числа линейных неравенств, или, что то же самое, пересечение конечного числа полупространств.

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

(1.18)

при всех х¹, х² Î Х, l Î [0, 1]. Если при всех х¹, х² Î Х, x¹ ¹ x², l Î [0, 1] неравенство (1.18) выполняется как строгое, то f называется строго выпуклой на X. Функция f назы­вается (строго) вогнутой, если функция – f (строго) выпукла.

Геометрически выпуклость функции f означает, что любая точка произвольной хорды графика f располагается не ниже соответствую­щей точки самого графика (рис.1.6, а). Для вогнутой функции взаимное расположение хорды и графика обратно (рис.1.6, б). Функции f (х) = х², f(x) = e^x выпуклы наR; f(x) = ln x вогнута на множестве положительных чисел; f(x) = sin x вогнута на [0, p] и выпукла на[p, 2p]. Отметим, что указанные функции, в самом деле, строго выпуклы или вогнуты. Функция f(x)= ||x|| выпукла, f(x) = ||x||² строго выпукла на Rⁿ. Функцию вида

f(x)= áa, xñ + b, (1.19)

где a Î Rⁿ, bÎ R, будем называть линейной. Ясно, что для линей­ной функции неравенство (1.18) выполняется как равенство. Поэтому она одновременно выпукла и вогнута на Rⁿ, но не строго.

Рис. 1.6. а) Выпуклая функция; б) вогнутая функция