XIV Аттетков и др. Методы оптимизации (1081420), страница 24
Текст из файла (страница 24)
Отметим, что функция й(ю) достигает наибольшего значения в единственной точке. Действительно, множество И'* есть пересечение выпуклого многогранника И' с линейным многообразием, заданным системой линейных уравнений (3.47). Значит, И'* выпуклое множество. Как было отмечено выше (см. доказательство теоремы 3.20), функция — 1пс1(х) является строго выпуклой. Поэтому она на И'* имеет единственную точку минимума, а функция о(ю) --- единственную точку максимума. Для точки х* наименьшего значения позинома выполняются равенства (3.54), а так как и, = и~,*.д(ю*), 1 = 1, т, то вторая группа этих равенств совпадает с (3.55).
Следовательно, значения я1 = х',, у' = 1, п, дают решение системы (3.55). Пусть теперь система (3.55) имеет решение (з~, ..., з*) и х* = (х1, ..., х'„) .. соответствующая точка, для которой Теорема 3.23. Пусть двойственная позиному у(х) функция д(ю) достигает в точке ю' = (ю,*..., ю„',) Е И'* наибольшего значения и и; = ю,*д(ю*), 1 =1, пь Позином у(х) достигает в К" наименьшего значении тогда и только тогда, когда система т уравнений 159 3, 7. Ъ|ииимизилия лозииомои !пх*. = з*., у' = 1, и. Тогда из системы (3.55) находим р!1Х*) = П(х*)" = ехр1~> ай !пх*.) = — ' = / „и,, ю,*.о!(!о*) 1=1 1=! Поэтому тя, ~П у(х') = ~~> с!р!(х') = д(ш*) 7 и," = Й(ял*). 1=1 1= ~ В данном !лучае И'* ~ О и, значит, верны неравенства (3.52), в которых с1* = я!1!о').
Отсюда делаем вывод, что значение д(х*) = о(!о*) является наименьшим значением позинома у(х*) вК",. > Теоремы 3.22 и 3.23 позволяют задачу поиска стационарных точек позинома, т.е. решение системы уравнений 3.54, заменить задачей исследования на условный максимум двойственной функции, ограничения в которой являются линейными. Такая задача может оказаться более простой, а решив ее, можно найти решение исходной задачи минимизации позинома. Пример 3.20. Позином у(х) = +Х1Х2+2Х2ХЗ+4Х1хз, Х = (Х1; Х2, ХЗ) Е Р~., Х1Х2ХЗ рассмотренный в примере 3.19, не является регулярным, так как для этого позинома не выполнено ни одно из условий (3.47): †4+1+4=1, †4+1+2= †, †4+2+4=2. Однако для него множество И" не пусто (см. пример 3.19), и поэтому в !9? он достигает наименьшего значения.
В качестве оценки сверху наименьшего значения этого позинома можно взять значение у(1,1,1) = 11, которое, отметим, является наименьшим значением любого регулярного позинома с теми же 100 3. МИНИЛЗИЗАЦИН ВЫПУКЛЫХ ФУНКЦИЙ коэффициентами с;, но соответствующим образом измененными коэффициентами а; .. Поскольку множество И" состоит всего из одной точки ю, то найденное в примере 3.19 значение двойственной функции д(ю) = 10 является наибольшим ее значением в И~*. Следовательно, наименьшее значение позинома у(х) равно у, = 10. Найдем координаты х*, з = 1, 2, 3, точки х', в которой позином 91х) принимает значение д, = 10. Используя вычисленные в примере 3.19 координаты ю~ —— = 2/5, ю~ — — юз —— ю,~ — — 1/5 точки ю и наибольшее значение д(ю) = 10 двойственной функции, в соответствии с 13.55) получаем систему уравнений: ю1д(ю*) (2/5) 10 — я1 — яз — яз=1п =1п =О, с1 4 юзд(ю*) (1/5) 10 я~+ля =1п з =1п =1п2, сз 1 ю~д(ю*) 11/5) 10 сз 2 ю4д(ю*) 11/5) 10 з1+ яз = 1п = 1п = — 1п2.
сз 4 Решая эту систему линейных уравнений., находим я1 — — О, яз —— = 1п2, яз — — — 1п2, откуда х1 — — 1, хз —— 2, хз — — 1/2. Непосредственной проверкой можно убедиться, что у„= 10. Вопросы и задачи 3.1. Установите, являются ли выпуклыми множества: а) Й = ((хм х.) Е Кз: 2х1+ хз < 2, 2х1 — хз > — 2, хз ) 0); б) Й = ((хм хз) Е 11к: х~ — хз ( 2, х~ + х~ з( 4); в) Й = (1хы хз, хз) Е К: хз 3 х1+ хз); г) Й = (1хм хз, хз) Е нз' хз ( ~т + х 161 Вопросы и задачи 3.2. Проверьте, какие из указанных функций являются выпуклыми в К": а) !"!х1,х2) = х2! + 2х!хя — 10х! + бх2, б) ! !х1~х2) х! + х2+х1+х2+х1х2: 4 4,2 2,2 2.
в) 11х1 х2) х е-!х!4хО. г) ! !х1) 22, хз) = 2х1 + х! х2 + х2 + 2хз — бх1хз', д) 2'(х1,х2,хз) = ехр(х21 + х22+ х~з). 3.3. Проверьте, является ли функция 1!х1,х2) = х21+ х22+ + !х1+ х2) ' выпуклой на множестве 51 = ((х1, хз) Е К; х! + хя > О, х1+ х2 ( — ъ'2). 3.4. Докажите, что если );!х), 4 = 1, пг, выпуклые !строго выпуклые) функции на выпуклом множестве Й С К", то функция д!х) = шах Ях) 1=1, ти выпукла 1строго выпукла) на Й. 3.5.
Докажите, что если д!х) выпуклая скалярная функция в К", то функция 1!х) = — 1,1д(х) является выпуклой на множестве Й = (х Е К": д(х) > О). 3.6. Покажите, что произведение выпуклых функций необязательно выпукло. Существуют ли подклассы выпуклых функций, замкнутые по отношению к умножению? 3.7. Пусть Й С К" - выпуклое множество.
Докажите,. что функция у1х) = шГ ~~х — у~~ выпукла на Й. Запишите функцию уе!1 ?'(х) в явном виде, если Й = (!х1, х2) б К2: х21 + х2 2< 1). 3.8. Пусть !'!х) выпуклая !строго выпуклая) функция в К" и 11х+ зср) > 1 !х) при х Е К" и зс Е ~(0., д), где б > О. Покажите, что функция !р !зс) = 1!х + зср) является неубывающей 1возрастающей) функцией переменного зс.
162 З. Л1ИНИМИЗАиИЯ ВЫПУКЛЫХ РУНКЦИй 3.9. Покажите, что если функция Дх) выпукла в К", то функция д(у) = ш1' ~(х), где А — матрица размера шхп., Ах.:д 11тп 3.10. С помощью необходимых и достаточных условий экстремума выделите среди стационарных точек заданных функцией те, которые являются точками локального максимума или локального минимума; а) ~(хмхз) = (х~~ — хз) + (х~ — 1); б) 1(хмх2) = (х1 х~) + (Х1 1) 3.11. Найдите и классифицируйте стзционарныс точки сле- дующих функций: а) Дхы хз) = х, — х~ ха + хз — 2х~ + Зхз — 4; б) ~(хмхз) = 2х~~+4х~х~ ~— 10хчхз+х~~, в) 1(хмхз) = 2х~ + 4х~х~ — 10хчхз+ хз, г) Дхмхз) = 2х~~+ 4х~х~~ — 10х~хг+ хз~,' д) Дхмхз) =2х~+4х1хз г10х~хэ+хгз Графически проиллюстрируйте полученный результат. Уста- новите, какие из указанных функций являются унимодальными выпуклыми (сильно выпуклыми) функциями.
3.12. Запишите функции, двойственные позиномам 2х~~хз + + хз/х~ + 3/(х~х~~) и хатха((2хз) + 2хз/х~ + х~/(4хз) + 2хз. Укажите дополнительные условия, которым должны удовлетворять аргументы этих функций. 3.13. Решая двойственную задачу. найдите точки локального минимума и наименьшее значение следующих позиномов (коэффициенты а, б и с положительны): а) ахз(х, +бхз+с/(х,хг~) б) ах,(х, +ах,хз+с((х~~х,"): в) ах,/х', + Ьх', х, + с~(х~х,). ,2 з я!4 ья а 4.
ЧИСЛЕННЫЕ МЕТОДЫ БЕЗ'УСЛОВНОЙ МИНИМИЗАЦИИ Численное решение задач безусловной минимизации функций многих переменных, как правило, значительно сложнее, чем решение задач минимизации функций одного переменного. В самом деле, с ростом числа переменных возрастают объемы вычислений и усложняются конструкции вычислительных а.лгоритмов, а также более сложным становится анализ поведения целее ой ф унции. Методы численного решения задач многомерной безусловной минимизации многочисленны и разнообразны. Условно их можно разделить на три больших класса в зависимости от информации, используемой при реализации метода. 1. Метаоды куяееоео порядка, или прямоео поиска, стратегия которых основана на использовании информации только о свойствах целевой функции. 2.
втетподы первоао порядка, в которых при построении итерационной процедуры наряду с информацией о целевой функции используется информация о значениях первых производных этой функции. 3. Метаоды етпороео порядка, в которых наряду с информацией о значениях целевой функции и ее производных первого порядка используется информация о вторых производных функции. Методы первого и второго порядков хорошо разработаны.
Для большинства из них имеется строгое обоснование, проведено аналитическое исследование их свойств, доказана сходимость, получены оценки скорости сходимости для некоторых классов целевых функций. Описание алгоритмов этих методов и иллюстрирующие эти алгоритмы примеры представлены 164 4. ЧИСЛЕННЫЕ МЕТОДЫ БЕЗУСЛОВНОЙ МИНИМИЗАЦИИ ниже (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
