XIV Аттетков и др. Методы оптимизации (1081420), страница 19
Текст из файла (страница 19)
Проверим, является ли выпуклой квадратичная функция У(тз хьюз) =х1+ив+из х1тз хятз хзт1+т1+ия+хз+1. з 2, 2 Для этой функции запишем матрицу Гессе У," л хзхз я Ух, хз л Хъзхз 2 — 1 — 1 — 1 2 — 1 — 1 — 1 2 Р хзхз у л хзз'3 П хзхз Непосредственным вычислением убеждаемся, что Ае1 Н = О. Это значит, что матрица Гессе не может быть положительно определенной.
Пеотрицательность диагональных элементов не позволяет сразу же сделать заключение о том, что матрица Н знаконеопределенная. Поэтому необходимо проверить на знак все диагональные миноры. В данном случае речь идет о проверке трех диагональных миноров второго порядка. Непосредственно из вида матрицы Н заключаем, что все три диагональных минора одинаковы и равны 2 — 1 — 1 2 Следовательно, матрица Н неотрицательно определенная, а квадратичная функция выпуклая в Кз.
Отметим, что для квадратичной функции положительнэл определенность матрицы Гессе Н является не только достаточным, но и необходимым условием строгой выпуклости. Действительно, если матрица Н неотрицательно определена., но 125 3.3. Дифференцируемые выпуклые функции не является положительно определенной, то эта матрица вырождена.
Значит, существует хотя бы одномерное линейное подпространство, на котором квадратичная форма функции равна нулю. На этом подпространстве сама квадратичная функция линейна, а потому не является строго выпуклой. Пример 3.12. Выясним, существует ли выпуклое множество Й С К, на котором функция 11л1ооо2) и1+и2 2 1и2+ 1 ,з „з является строго выпуклой. Запишем матрицу Гессе этой функции Для полОжительного Ответа на поставленный вопрос достаточно указать множество, на котором матрица Гессе положительно опреде- 112 лена. Согласно критерик1 Сильвестра, для этого требуется выполо 1 пение двух условий: Ь1 = бнэ1 > О И.
и Ь2 = еЫ Н = Збт1нэ2 — 1 > О. Соответствующее множество 11, ограниченное гиперболой х1х2 = 1/36, представлено на рис. 3.1. Поскольку при и1и2 ( 1/36 определитель матрицы Гессе отрицателен, в области Й2 между двумя ветвями гиперболы матрица Гессе является знаконеопределенной. В области йз в третьем квадранте Ь1 ( О и о"12 > О, т.е. матрица Гессе отрицательно определена. Таким образом. область П является максимальной областью строгой выпуклости рассматриваемой функции.
126 а мииимизлция Выпуклых Функций 3.4. Условия минимума выпуклых функций Поиск наименьшего значения функции многих переменных — сложная задача. Напомним некоторые факты, относящиеся к этой задаче. Точка, в которой функция достигает своего наименьшего значения, является точкой локального минимума этой функции.
Поэтому для определения наименьшего значения функции, если функция достигает его, достаточно найти все точки локального минимума этой функции и среди них выбрать ту (или те), в которой функция имеет наименьшее значение. Такой подход возможен, если функция имеет конечное (и относ ительно небольшое) число точек локального минимума.
Точки локального минимума функции, являющиеся внутренними точками области определения функции, можно искать, опираясь на необходимое условие экстремума функции. Если внутренняя точка х' Е П множества П С К" есть точка локального минимума функции 1(х), определенной на 11, и функция 1(х) дифференцируема в точке х*, то эта точка является стационарной точкой функции 1(х), т.е, в этой точке выполняется условие (3. 24) дги1~(х*) = О, где дгас1~(х*) . градиент функции в точке х*. Таким образом, точки локального минимума внутри области определения это либо стационарные точки, либо точки недифференцируемости функции (критические точки).
Поэтому точку наименьшего значения функции, если она существует, можно искать, сравнивая значения функции во всех стационарных и критических точках функции. Выяснять, какие из этих точек являются точками локального минимума, не нужно. Проверить, является ли стационарная точка точкой локального минимума, можно с помощью достаточного условия экстремума. Если функция ~(х) дважды непрерывно дифференци- 3.4. УСлОвия иияиыуиа выпуклых функций 127 руема в стационарной точке х' и матрица Гессе Н(х*) функции 7'(х) в этой точке положительно определена, то х' является точкой строгого локального минимума. Функция может достигать наименыпего значения в граничной точке области определения. Дифференциальные свойства функции многих переменных можно в этом случае использовать, если границей области определения является гладкая кривая или поверхность.
В этом случае можно поставить задачу на условный экстремум, в которой уравнения связи описывают границу области, и определить точку, в которой функция достигает наименьшего значения,.как точку условного локального минимума. В остальных случаях необходимо непосредственное исследование функции на границе области определения, а ее дифференциальные свойства не могут помочь в решении задачи.
Необходимые и достаточные условия экстремума функции многих переменных далеко не всегда обеспечивают решение задачи минимизации. Использование необходимого условия локального экстремума приводит к необходимости решать систему нелинейных уравнений, что само по себе является сложной задачей. Функция может иметь большое (или даже бесконечное) число стационарных и критических точек, и тогда выбрать точку наименьшего значения функции среди них сложно. Наконец, трудности возникают, если точка наименьшего значения находится на границе области определения функции. Достаточные условия экстремума могут помочь выделить среди стационарных точек те, которые являются точками локального минимума.
Тем самым сокращается общее число точек, „подозрительных на наименьшее значение". Однако даже если стационарная точка определена, функция дважды непрерывно дифференцируема в ней, матрица Гессе в этой точке вычислена, то это еще не гарантирует определенного ответа, является ли исследуемая точка точкой локального минимума. Дело в том, что матрица Гессе может оказаться неотрица- 128 3. Л1ИИИЫИЗЛЦИЯ ВЫПУКЛЫХ ФУИКЦИЙ тельно определенной. А в этом случае на поведение функции в окрестности стационарной точки оказывают влияние дифференциалы высших порядков (если такие, конечно, существуют).
Все указанные трудности можно преодолевать с помощью методов, в которых не используя>тся дифференциальные свойства функции. И в этом случае важную роль могут играть другие, не связанные с дифференцируемостью, свойства функции. Некоторые выводы о существовании и единственности точек локального минимума можно сделать для вьтукяых функций. Теорема 3.14. Если функция ~(х), определенная на выпуклом множестве Й С й", является выпуклой, то эта функция в любой точке локального минимума достигает наименьшего в Й значения. Множество всех точек локального минимума функции выпукло. Функция, строев выпуклая на выпуклом множестве, имеет не более одной точки локального минимума.
~ Пусть х* Е Й - точка локалыюго минимума функции 1(х). Предположим, что в этой точке значение функции не является наименьшим на множестве Й, т.е. существует точка у* е Й, для которой 1(у*) < 1(х*). Рассмотрим сечение функции 1(х), соответствующее паре точек у' и х*, т.е. функцию одного переменного ~р(1) = ~(~у*+ (1 — 1)х').
Эта функция в силу выпуклости множества Й определена по крайней мере на отрезке ~0, 1]. Покажем, что в точке ~ = 0 функция у(~) достигает на ~0, 1] наибольшего значения. Действительно, с учетом неравенства ~(у*) < ~(х*) при 1 Е (О, 1) < 1Ях*) + (1 — 1)Ях*) =1(х') = ~(0). Для произвольной окрестности Г точки х* существует настолько малое число ~ ) О, что х = ~у*+ (1 — ~)х* Е Г.
Тогда 3.4. У~ловил милям мя вмлуклмх ф~ якцяй 129 а это противоречит тому, что точка ж* есть точка локального минимума. Таким образом., предположение о том, что в точке локального минимума и* функция не достигает наименьшего значения, неверно. Из доказанного следует,что во всех точках локального минимума выпуклая функция Дж) имеет одно и то же значение, равное наименьшему значению шу этой функции. Очевидно, что каждая точка, в которой функция принимает значение гп1, является точкой локального минимума функции.
Следовательно, множество точек локального минимума функции совпадает с множеством 1 '(т1) прообразом значения т1 при отображении ц = У(~) Теперь покажем, что множество 1 ~(гну) точек локального минимума функции 1 (и) является выпуклым. Это утверждение очевидно, если множество пустое или содержит лишь одну точку. Поэтому будем считать, что оно содержит не менее двух точек. Рассмотрим две точки х, .в~ Е 1 (гну), в которых функция 1(ж) принимает одно и то же значение ту. Тогда в каждой точке т = 1а~ + (1 — 1)тз, 8 Е (О, Ц, имеем 1(в) ) т1, так как ш1 — наименьшее значение функции в й. В то же время в силу выпуклости функции ((х) 1(х) = Яж'+ (1 — 1)ж ) < ~ ~1~(т ) + (1 — 1) ~(х ) = Ьау+ (1 — 1)гв1 = гну.
Таким образом, во всех точках отрезка [х', хз) функция 1(х) принимает постоянное значение гп1. Следовательно, для любых точек ж, ж Е ) (тпу) имеем (ж, ж ] С ) (т1), т.е. множество ~(гну) является выпуклым. Наконец, покажем, .что в случае строго выпуклой функции множество 1 ''(ту) не может содержать более одной точки. Если функция ('(ж) строго выпуклая, то для любых различных точек ж~, жз Е Й и любого числа 1 Е (О, 1) выполняется строгое 3. Л1ИНИМИЗЛЦИЯ ВЫЛ'КЛЫХ а УНКЦИй Р30 неравенство Предположим, что х~, х~ Е 1 ~(тиу) точки локального минимума.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
