XIV Аттетков и др. Методы оптимизации (1081420), страница 23
Текст из файла (страница 23)
замечание 3.3). В случае строгой выпуклости функция имеет не более одной точки локального минимума. Поскольку янобиан замены переменных 13.44) при любых значениях ~м ..., С„ отличен от нуля, любой стационарной точке ф, ..., © функции уф,...,Си) соответствует стационарная точка х* = = 1х» ...,х„'), х*. = еСз, 1 = 1,п, и наоборот.
Таким образом, минимизация позинома сводится к поиску его стационарных точек, причем для определения наименьшего значения позинома достаточно найти хотя бы одну стационарную точку. 151 3.7. Мини77излция поэиномав Здесь 6, = ~а7.ю7з у=1,п. Подберем нормированные веса ю; таким образом, чтобы функция о(ж, ю) не зависела от 7в. Для этого необходимо и достаточно, чтобы выполнялись равенства б, = О.
Другими словами, нормированные веса должны удовлетворять системе линейных уравнений а73и77 = О; 1 = 1, и. Е (3.47) 7=1 777 1* )=П( — „",) ' 7=1 и неравенство (3.46) преобразуется к виду 777 П 7В у(х) =Ее Пх1*' >ПИ =Яю) (348) 7,=1 7=1 7=1 Функцик1 а~(ю) называют двойстпвенной и позиному у(ж), а равенства (3.47) - условиями ортоеонольности (вектор с координатами ю„7 = 1, т7 ортогонален каждому из и столбцов матрицы (а;, ) размера т, х и). Такой выбор нормированных весов не всегда возможен.
Для существования нормированных весов, удовлетворяющих системе линейных уравнений (ЗА7), необходимо, чтобы эта система имела ненулевые решения. Однако даже если система (3.47) и имеет ненулевые решения, то среди них может не оказаться решений с положительными (или хотя бы неотрицательными) значениями неизвестных ю;: так будет, например, в случае, когда все коэффициенты а; являются положительными. Если нормированные веса ю, выбраны в соответствии с равенствами (ЗА7) 7 то 152 л. МИНИЛгИЗДЦИЯ ВЫПУКЛЫХ ФУНКЦИЙ В Кг" рассмотрим множество ги Иг = ((ю1, ..., ю ) Е Б™: ю! > О, г = 1, п1г ,'1 ю; = 1).
(3.49) г=1 Нетрудно показать, что это множество представляет собой выпУклУю оболочкУ злементов ю;е, Е 2~, 1, = 1, т, гДе е1г,.., еиг — стандартный базис в гч.~. Другими словами, И'— т-мерный выпуклвгй многогранник. Для двойственной функции 11(ю) верна следующая теорема. Теорема 3.20. Двойственная функция д(ю) на множестве Иг достигает наибольшего значения д' = с1 + ся +... + сгя В точке Ю* = (С1/11*г СЗ/11*г ..., Ст(ГД) Е И', И Зта тОЧКа ЕДИН- ственная. ~ Несложно, вычислив вторую производную, убедиться в том, что каждая из функций гр;(ю;) = — ю,1п(с,/иг;) является строго выпуклой при юг > О. Значит, и функция сг — 1вг((ю) = — 7 иг, 1п —, юг г=! как сумма строго выпуклых функций, является строго выпуклой (см.
теорему 3.8). Если эта функция достигает на И' наименьшего значения, то точка., в которой достигается наименьшее значение, согласно теореме 3.14, единственная. Значит, функция д(ю) может достигать наибольшего значения только в одной точке. Согласно неравенству взвешенных средних, гл а1(ю)=~( — ) <~ иг, — =~с!=а!, г=! г=-1 ' г= 1 причем это неравенство превращается в равенство в точке иг* с координатами ю,* = с„10*, 1 = 1, т.
Следовательно, д(ю) < < 11(ю'), ю Е И', и в точке ю* функция 11(ю) достигает наибольшего значения. ~ 3. Т. Минимизация познномон Пусть И'* — множество точек ю = (ю4, ..., ю„,) в выпуклом многограннике И', которые удовлетворяют условию (3.47). Множество И"* может быть и пустым, т.е. И'* = к. 11о если И'* ~ О, то позином у(х) имеет двойственную функцию д(ю), причем для любых ю Е И'* и х Е К~ выполняется неравенство о~(ю) < у(х). Следовательно,. позином у(х) ограничен снизу положительным числом, в качестве которого можно взять значение д(ю) в любой точке ю Е И". Можно показать, что в этом случае позином достигает наименьшего значения. При этом число д(ю) можно рассматривать как оценку снизу наименьшего значения позинома.
Отметим, что в некоторых случаях множество И'* может состоять нз единственной точки. Позином может не достигать наименьшего значения, хотя он и ограничен снизу нулем (например, функция 1/хч). Как показывает предыдущее рассуждение, .это возможно лишь в случае, когда множество И'* пусто. Пример 3.19. Выясним, достигает ли наименьшего значения позином у(х) = +х4хз+2хзхз+4хзхз, х = (хм хз,.
хз). Х12 2ХЗ Если позином достигает наименьшего зна 4ения, то оценим его. Запишем для этого позинома систему, включающую условие нормировки 2 ю, = 1 и условия ортогональности (3.47): з=1 иб+ю2+юз+ю4 = 1, ю4 +юз+ ю4 = Π— иб+юз+юз = О, — 4о~+и~з+ю4 = О. Решая эту систему линейных алгебраических уравнений, находим ее единственное решение ю = 2/5, юз = юз = юз = 1,15.
154 э. МИНИг 1ИЗАЦИН ВЫПУКЛЫХ ФУНКЦИЙ Таким образом, множество И"* не пустое и содержит единственную точку ю = (2/5, 1г'5г 1/5г 1/5). Значит, рассматриваемый позином на Й+ достигает наименьшего значения. з Поскольку И" ~= О, навином имеет двойственную функцию, которая в соответствии с (3.48) принимает вид (3.50) В точке й1 значение двойственной функции равно Поэтому наименьшее значение позинома у(х) не меньше 10.
ф Позином (3.42) называют рееулярным, если выполнены п равенств т г1 = ~ аг3сг = О, 1 = 1, п. (3.51) г — 1 Е =Е Сг а,г1нгг = Р ай — — — О, г=1 г=1 1=1,п. Это означает, что для регулярного позинома р(х) верны неравенства 11г < М < д(х)., х Е К"1 . (3.52) Теорема 3.21. Регулярный навином 11(х) достигает в В"' СВОЕГО НаИМЕНЬШЕГО ЗяаЧЕНИя у, = у(Х*) = 11* = С1+ Ся +... + Ст в точке х* = (1, 1, ..., 1) Н К" . Если навином регулярный, то координаты ю, = с1/д* точки пг* Е И', в которой, согласно теореме 3.20, двойственная функция 11(нг) достигает на т-мерном выпуклом многограннике И' наибольшего значения д*, равного а'" = с1+...
+ с, удовлетворяют у1жовиям ортогональности (3.47). Действительно, 155 3, 7. Минимизация иознномов Поскольку для регулярного позинома верны неравенства (3.52), достаточно показать, что в точке а* позином принимает значение д'. С помощью непосредственных вычислений получаем у(ж*) =Есгпх,"о =Ее.= Г. г1 31 ' г1 го — а13Цт,о =О, ~з =1, (353) 1 г=1 1=1 Эти уравнения сложные. Установить по ним существование стационарных точек, а тем более найти их не так просто, особенно при большом числе пг слагаемых в (3.42) и дробных показателях степеней. Введем дополнительные переменные п1 = ц П гв .", г = 1, га, 1=1 з =1пж, ) =1г а.
Тогда а1 х 1п — = Р аг 1птзг сг 1 —.1 Итак, поиск наименьшего значения регулярного позинома не составляет труда: оно достигается в точке а* с единичными координатами. Нерегулярный позином у(а) может не достигать наименьшего значения, но если известно, что наименьшее значение этим позиномом достигается., то значение д* = у(ж*) может рассматриваться как оценка сверху для наименьшего значения позинома. Как отмечено вьппе, если позином достигает наименьшего значения, то все точки наименьшего значения есть стационарные точки позинома. Поэтому задачу минимизации позинома можно решать, определяя его стационарные точки. Используя представления (3.42) и (3.43), получаем уравнения для стационарных точек позинома: э.
МИНИМИЗАЦИН ВЫПУКЛЫХ ФУНКЦИЙ Рйб и условия (3.53) можно записать в виде двух систем линейных уравнений а,, эу = 1п — ', г' = 1, пг. (3.54) Е»= —" сг 1=1 аОи; =О, у =1гн, Е г,=1 Теорема 3.22. Если позином у(х) достигает в точке х' = (хм ..., х„*) е 11~~ наименьшего значения у„= у(х*), то двойственная функция гг(пг) достигает на множестве И'* наибольшего значения г1(нг*) = у, в точке пг' Е И'* с координатами ш.,* = и;/у., где и, = ьбр,(х*), г =1, т. в'=с Ц(х;)'" =сер (х'), г = 1,гп, и э = 1ггх*., ~ = 1г н. Используя первую группу этих равенств, заключаем, что гя ги нг 1 = „) агз' ' =,'Е;агс'нг = О.
г=г уг уг г=1 Кроме того, т т Х ~— ~ сгрг(х ) г=1 г=1 уг Поэтому нг' Е И'*. ~ Покажем сначала, что точка иг' принадлежит множеству И'*, т.е. ее координаты ш,*. = сн/у„удовлетворяют равенству ~;пг,* = 1 и равенствам (3.47). Так как в точке х' позином г=1 у(х) достигает наименьшего значения, эта точка для позинома является стационарной. Следовательно, выполняются равенства (3.54), в которых 157 3.7. Минимизация ипзиномов Теперь вычислим значение двойственной функции в точке Ш*. ПОСКОЛЬКУ Ш,* = Пг) Уг = Сгуг(а*) !1Угг те сг у* гггс р,(ге*) Используя представление двойственной фунцииг находим ' "=ПЯ)'=П(,'.".) =(П" ")) П" Во втором произведении все показатели степени складыввкгтся, причем в сумме получаем ги ~ш,* = 1.
г=! Следовательно, это произведение равно у„. Первое произведе- ние преобразуем, учитывая вид функций р;(ж): с 1П вЂ” Пг* га П п П»!(*)~ '=ПП(.;)-а" =П(-;)" з=! где йз = — ~~г агушг* = О. г=! Значит, (П !*з) и аг(ш*) =у„. Так как Н(ш) ( у, для любой точки ш Е И'*1 то у. = г1(ш') является наибольшим значением д(ш) на И'*. ~ 158 а минил1излция Выпуклых ФункциЙ Е" — —.
и, а;,г =1п —, с, (3.55) где я, = 1пх, у' = 1, и, имеет решения, принадлежащие К" . При этом любое решение (з,*, ..., з„*) системы определяет точку х' = (хм ..., х„*), где я,*. = 1пх*;, у = 1, и, которая является точкой наименыпего значения позинома. Пусть позином у(х) достигает в К" наименьшего значения у„в некоторой точке х*. Тогда, согласно теореме 3.22, двойственная функция и(ю) достигает на множестве И'* наибольшего значения в точке ю* с координатами и),*. = и,/у,, где и, = с,р,(х'), г' = 1, т. Кроме того, с((ю') = у„, и мы можем записать и; = ю,'с1(ю*), г' = 1., т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
