XIV Аттетков и др. Методы оптимизации (1081420), страница 22
Текст из файла (страница 22)
Такова, например, функция Дх) = е одного действительного переменного. Вторая производная этой функции положительна: 1 "(х) = е 1 Поэтому она является строго выпуклой. В то жс время функция )'(х) возрастающая и не имеет точек локального минимума, т.е.
она не достигает наименьшего значения. 3.6. Примеры минимизации квадратичных функций Использование необходимого и достаточного условий локального минимума выпуклой функции рассмотрим на примсрах минимизации квадратичных функций.,Любая квадратичная функция Дх) может быть представлена в виде суммы 1(х) = Ях, х) + (с., х) квадратичной (Ях, х) и линейной (с, х) форм, при этом матрица Гессе Н(х) этой функции постоянна и связана с матрицей С,) квадратичной формы соотношением Н=2Я. З.б. Приьсвры минимизации каадрахичн сх функций 143 Рассмотрим квадратичную функцию ~(х) = — (Нх, х) + (с, х) 1 (3.37) с положительно определенной матрицей Гессе Н порядка н и фиксированным вектором с Е ас". Градиент этой функции равен 8тас1~(х) = Нх+ с.
(3.38) )'(х*) = — — (НН 'с, Н 'с)+ (с., Н 'с) = — (с, Н 'с). (3.39) * 1 1 2 2 Отметим, что если матрица Н квадратичной функции не является положительно определенной, то она может быть вырожденной. В этом случае либо функция не имеет стационарных точек, либо стационарных точек бесконечно много. Пример 3.15.
Исследуем на минимум функцию ~(хм хе) = , 2 . 2 = х, + 2хс хе + 4хх Рассматриваемая функция представляет собой квадратичную функцию с матрицей Гессе Так как матрица Н положительно определена, то она имеет обратную матрицу Н '. Иэ необходимого условия 8гас1~(х') = = О локального минимума функции с учетом (3.38) находим, что функция имеет единственнукь стационарную точку х' = = — Н сс. Рассматриваемая функция сильно выпуклая на вьилуклом множестве Б'." (см. пример 3.13). Значит, эта функция строго вьтуклаа (см. 3.5).
Поэтому, согласно теоремам 3.14 и 3.15, необходимое условие локального минимума является и достаточным условием. В стационарной точке х* функция (3.37) принимает значение 144 з. минимизлция выпуклых г ункций Нетрудно проверить (например, с помощью критерия Сильвестра), что матрица Н положительно определенная. Значит, функция имеет единственную стационарную точку х* = = — Н ~ с = — Н ~0 = О, в которой принимает наименыпее значение. ПРимеР 3.16. КваДРатичнаЯ фУнкцил ((хмхз) = хз~+ 2х~ хз также представляет собой квадратичную форму и имеет матрицу Гессе УХ = 2 ( Эта матрица знаконеопределенная, но является невырожденной. Поэтому функция имеет единственную стационарную точку х* = — Н '0 = О.
Но поскольку функция не выпуклая (матрица не является неотрицательно определенной), делать какие-либо заключения о наличии экстремума в точке х' нельзя. И действительно, точка 0 не является ни точкой локального минимума, ни точкой локального максимума, так как ее матрица Гессе в этой точке знаконеопределенная (Ч). Нетрудно убедиться, приведя квадратичную форму к каноническому виду, что график рассматриваемой функции представляет собой гиперболический параболоид с седловой точкой (О, 0).
Функция ~р(1) = ~(8,0) = Р (сечение функции ~(х~.,хз) при хз = 0) имеет при ~ = 0 строгий локальный минимум, в то время как функция ф(8) = ((г,— 1) = — 1 (сечение функции ~(хм хз) при х~ = — хя) при 1 = 0 имеет строгий локальный максимум. Пример 3.17. Квадратичную функцию ('(хмхз) = х~~ + +2х~хз+х~~ можно записать в виде ((хмхэ) = (х~+хз) . От- 2 сюда сразу следует, что она достигает наименьшего значения, равного нулю, в каждой точке прямой х~ + хя = О. Матрица Гессе этой функции имеет вид Я=2( 3.6.
Привары иииимиааиии каадратичн ~х функций 145 и является неотрицательно определенной. Значит, функция вы- пуклая, а каждая стационарная точка является точкой наи- меньшего значения функции. Необходимое условие локального минимума приводит к системс уравнений 2х~+2хз =О, 2х1+ 2хз = О, из которой заключаем, что стационарной является любая точка вида (1, — 1), 1Е и, т.е. точка, лежащая на прямой х~ +хе = О. ПРиведЯ квадРатичнУю фоРмУ Дх~,.хз) = (х~ + хг)з к каноническому виду, легко убедиться, что график функции представляет собой параболический цилиндр [ПЦ. Пример 3.18.
Квадратичная функция ~(х1;х2) — бх~ 4х~ха + 3хз + 4ч 5(х~ + 2хз) + 22 (3.40) (3.41) ~(х) = (Ах, х) + (Ь, х) + с, где х=(хм х2) ЕК, А=, Ь=, с=22. Матрица А положительно определенная, так как имеет угловые миноры Ь~ = 6 ) 0 и Ьз = 6 3 — ( — 2) = 14 ) О. Значит, рассматриваемая функция сильно выпуклая в 2 и имеет единственную стационарную точку х*, являющуюся точкой наименьшего далее используется в качестве базовой при сравнительном анализе различных численных методов безусловной минимизации и выявлении достоинств и недостатков их вычислительных свойств.
Поэтому представляет интерес подробное аналитическое исследование свойств этой функции. Функцию ~(хм хе) можно представить в виде 3. МИНИМИЗАЦИЯ ВЫПУКЛЫХ ФУНКЦИЙ 146 значения. Эту точку можно найти по формуле х* = — Н 'Ь, где Н = 2А — матрица Гессе функции. Так как 14 2 6 то 28 2 6 8тГ5 — 2тГ5 В этой точке функция принимает значение ('(ж*) = — 28. Приведем квадратичную форму (Аж, а) функции к каноническому виду. Для этого найдем собственные значения матрицы А, составив ес характеристическое уравнение с1е1(А — Л7) = = О, где 1 - единичная матрица второго порядка. В данном случае это уравнение имеет вид 6 — Л вЂ” 2 — 2 3 — Л Раскрывая определитель в левой части уравнения, получаем (6 — Л)(3 — Л) — 4 = О, или Лт — 9Л + 14 = О. Это квадратное уравнение имеет корни Л1 = 2 и Лз = 7, которые и являются собственными значениями матрицы А.
Поскольку собственные значения различны, а матрица А симметрическая, то соответствующие этим собственным значениям собственные векторы ортогональны [Ъ ). Координаты собственных векторов найдем, решая СЛАУ (А — Л1)е = О, которая при Л = Л1 = 2 и Л = Лз = 7 сводится к соответствующим системам 4:с1 — 2хз = О, — 2т1+из =О, < — и1 — 2из = О, — 2т1 — 4из = О. т Решением первой системы является вектор (1 2), а второй т вектор ( — 2 1) . Нормируя эти векторы, получаем единичные т т векторы е', = (1~ъ'5 2/ъ 5) и е~ = ( — 2/ь'5 1/Л), образующие в Кз ортонормированный базис. В этом базисе матрицей 3.6.
Примеры минимизации каадратичн ~х Функций 147 квадратичной формы является диагональная матрица Л с диагональными элементами, совпадазощими с собственными значениями, а квадратичная форма (Аж, т) примет канонический вид (Лр, у) = Л1у2+ Л2у2~ = 291~ + 7у2~, у = (у1., у2). Координаты собственных векторов е1 и е2, записанные по столбцам, формируют матрицу перехода Г к новому, каноническому базису, которая в данном случае имеет вид 1 2 Я Д 1 (1 — 2 Я~2 1 чгз Д Поскольку матрица Г определяет переход от одного ортонормированного базиса к другому, она является ортогональной ~1Ч]. Поэтому обратнук1 матрицу У ' можно найти с помощью т транспонирования: Г = Г .
С помощью матрицы перехода можно найти координаты вектора Ь в новом базисе по формуле Ь' = Г 1Ь, что в рассматриваемом случае дает Таким образом, квадратичная функция в новой системе координат принимает вид 71(У1,у2) = 2у, + 7р2+20у1 + 22. С помощью выделения полных квадратов проводим дальнейшее упрощение вида функции: 71(д1,р2) = 21у1+5) +7р2 — 28, или Яз1,з2) = 2з12+ 7з22 — 28, где з~ = р1+ 5 и з2 = у2. Из найденного представления функции вытекает, что график рассматриваемой функции представляет собой эллиптический параболоид ~П1). 148 з. минОмиздиия выпукдых оъ'нкций Преобразование функции проведено за два шага: сначала переход к переменным у1, у2, а затем — к переменным 21, Формулы связи исходных переменных х1, х2 с конечными переменными 21 и 22 имеют вид 21 — 222 Х1 = — Л., Л 221 + 22 х2 = — 2Л.
1/5 Началом конечной системы координат является точка 01, которая в исходной системе координат имеет координаты х1 = — 1/5, х2 = — 2ъ'5. Все три системы координат покаРис. З.З заны на рис. 3.3. Линиями уровня функции /(х1, х2) являются подобные эллипсы (см. рис. 3.3). Найдем, нэпример, уравнение линии уровня, проходящей через точку хв = ( — 2, 1). Подстановка координат этой точки в (3.40) дает значение функции /(хв) = 57.
Следовательно, эта точка расположена на линии уровня /(хбх2) = 57. Переходя к конечной системе координат 012122, получаем уравнение /(21, я2) = 22~~ + 7222 — 28 = 57, или 2 2 1 2 85/2 85/7 Таким образом, искомая линия уровня эллипс с полуосями а = ~,~85/2 - 6,52 и 6 = /85/7 - 3,48. Найденная линия уровня показана на рис. 3.3 жирной линией. 3.7. Минимизация позиномов В прикладных задачах минимизации целевая функция часто имеет вид ев (3.42) у1х) = )' с~рг (х) ~ г=-1 149 3.7.
Минимизация цозииоиов с, > О, 1 = 1, т, а функции р~х) =П:" з=-1 13.43) а,у Е Б', 1= 1, т, у =1, и, определены на множестве К" =((хм ...х„)ЕК":х,>О, 1=1,п) точек с положительными координатами. Функцию вида 13.42) называют позиномом. Почином при определенных значениях показателей степени а,. может не быть вьиуняой функцией.
Однако с помощью замены переменных х:=е~", у=1,п, 13.44) он преобразуется в выпуклую функцию в Кп. Это показано в примере 3.9. Там же показано, что эта функция является строго выпуклой функцией в том случае, когда матрица А = (и,:) имеет ранг, равный и.
Поскольку функция уф,...,С„) выпукла в 1~", ли>бая точка ее локального минимума является точкой наименьшего значения функции 1см. теорему 3.14). Более того, так как эта функция дифференцируема в яС", множество ее точек наименьшего значения совпадает с множеством стационарных точек 1см.