Методы оптимизации и исследование операций для бакалавров информатики. Часть 2

тельно) определена в этой точке.

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

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

Квадратичная

Исключительно важную роль в нелинейном

функция

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

чает квадратичную, линейную составляющие и свободный член:

где D — симметричная квадратная матрица (матрица квадратичной формы). Градиент и матрица Гессе для квадратичной функ-

34 Глава 9. Теория выпуклого программирования

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

Можно показать (см., например, [16, с. 214]), что путем переноса начала координат в точку

−→ = −1 −1−→

X 2 D c

где λi — собственные числа матрицы D.

Форма поверхности равных значений целевой функции (в двумерном случае — изоцелевых линий) целиком определяется опре-

деленностью матрицы D и ее собственными числами.

→−

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

мерные концентрические эллипсоиды (в двумерном случае — эл-

→− →−

липсы) с центром в X , являющейся точкой минимума Q(X ). Размеры главных осей эллипсоидов определяются собствен-

ными числами M = λ1 λ2 · · · λn = m. Таким образом, степень сплющенности эллипсоидов определяется отношением наибольшего и наименьшего собственных чисел матрицы D, которое называется числом обусловленности (conditional number) матрицы и обозначается cond(D). Если cond(D) = Mm ≈ 1, то поверхности равных уровней близки к сферическим, если же cond(H) 1,

−

Рис. 9.9. Пример выпуклой квадратичной функции

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

Углы между направлениями главных осей эллипсоидов и любой из координатных осей можно измерить, применив формулу для

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

= 1, получим выражение для угла между малой полуосью эллипса (ей соответствует б´ольшее собственное значение λ1) и осью абсцисс

Отсюда ϕ = 67, 5◦ (см. рис. 9.9). Заметим, что для случая двух переменных угол наклона эллипса можно определить непосред-

ственно по матрице D квадратичной формы: tg 2ϕ = 2d12

d11 − d22

[18, с. 66].

Продолжим пример и посмотрим, как ведет себя градиент.

→−

Возьмем точку X 0 = (−3, 0.5)T . Градиент функции в этой точке равен

и направлен, как видно, влево и вниз. Соответственно вектор антиградиента направлен вправо и вверх (из-за недостатка места длины векторов на рисунке уменьшены).

Построим касательную к изолинии в данной точке. Ее уравнение имеет вид

Выполняя скалярное произведение, получаем уравнение прямой −9x1 − 9x2 − 22.5 = 0. Если привести его к виду уравнения в

9.3. Классические задачи оптимизации

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

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

гих переменных в неограниченной области

−→

f (X ) = f (x1, . . . , xn) → min, 0 < xj < ∞, j = 1, . . . , n.

Вкурсе математического анализа доказывается [15, с. 31], что

не о б х о д и м ы м условием локального минимума является равенство нулю всех частных производных (теорема Ферма):

→−

∂f (X ) = 0, j = 1, . . . , n. (9.15) ∂xj

Это равенство является условием первого порядка (first order condition) и может быть записано в компактной векторной форме

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

Д о с т а т о ч н ы м условием локального минимума является

→−

положительная определенность матрицы Гессе H(X ) в стационарной точке. Этот факт представляется достаточно очевидным, так