Галеев Э.М., Тихомиров В.М. - Краткий курс теории экстремальных задач (1050553), страница 12
Текст из файла (страница 12)
'Но это и есть условие стационарности функции Лагранжа х'Х Х (х, у', >с), если положить >ссс= . =>сь-с=О ~> 3 а м е ч а н и е. Из доказательства теоремы следует, что -если 1шР'(х) =У (т. е. если Р регулярно в х) и существует элемент >с~КегР'(2), длЯ котоРого (>с'(х), >с>(0, с=1,...,т (назовем это условие аналогом условия Слейтера), то >сссФО и, <ледовательно, можем полагать >се= 1.
53 25. Примеры 1. /(х) =/(хь хз) =хР— х~ха+хзз — 2х~+хз-«ех1г. Р е ш е н и е. Необходимое условие 1 порядка экстремума гладкой функции: д/ (х) д/(х) 1 2хд — х« — 2 = О; /' (х) = 0 с=э — = — = 0 чэ ) ах, Зх, 1 — х, +2ха-(-1=0. Решая эту систему уравнений, находим единственную стационарную точку Х= (хь хз) = (1, 0). Для проверки условий П порядка .выписываем матрицу вторых производных: Эта матрица по критерию Сильвестра (п. 2.1.2) положительно определена. По достаточному условию экстремума функции нескольких переменных (п. 2.1.2) (1, 0)~1осппп/. Нетрудно понять, что на самом деле (1, 0)енаЬзш(п/, а 5 „=+со. 2. 4х~+ Зхз-«ех1г; х~~+хз'=1.
Реш е н не. Применяем правило множителей Лагранжа для решения гладких задач с ограничениями типа равенств (п. 2.22). Функция Лагранжа: 2'=Х«(4х~+Зхз)+Х(х,з+хзз— — 1). Необходимое условие: Я'„=0 =«4Х«+2дх,=О, 31а+2Лх«=0, ' Если Х«=0, то ХФО, значит, нз предыдущих уравнений х~= =хз=О. Точка (О, 0) не является допустимой. Г)олагаем Х«=1. т Тогда х = — 2/ь, х«= — 3/2Х. Подставляя х~ и хз в ограничении хР+х««=1, получаем, что Л=+.5/2, и соответственно имеем две. стационарные точки (4/5, 3/5), ( — 4/5, — 3/5).
По теореме Вейерштрасса существуют решения задач нв максимум и минимум. Рассматривая значения функционала в стационарных точках, получаем (4/5, 3/5)~аЬзшах, Яптах=б, ( — 4/5, — 3/5)~аЬзт(п, Я и= — 5. 3. хР+хзз+х«« — !п1; 2х~ — хз+хз(5, х~+хз+х«=3. «г Решение. Применяем правило решения гладких задач с ограничениями типа равенств и неравенств (п.
2.4). Функция „~ Лагранжа: 2'=Ха(хР+ха'+ха') +Х~(2х~ — хз+х« — 5) +Аз(х, +хз+х« — 3). Необходимые условия: а) стационарности Я,,=Ос«2Л х,+23,,+Л,=О, 54 Я,„=О«»2Лохз+$ — Л,=О, Я„,=О«»2Лохз+Э +Л,=О; б) дополняющей нежесткости Л1 (2хо — хз+хз — 5) =0; в) неотрицательности ЛоъО, Л1ъО. в> Л =О~А,=Л»=0 — все множители Лагранжа — нули. Поз б) лежим Ло=1/2. Предположим Л,~О ~2х — х +х — 5=0, Выражая хь хз и хз из условия а) через Л1 и Лз й подставляя в уравнения х1+хз+хз= 3, 2х1 — хз+хз — 5=0. получим = — 9/!4(0 — противоречие с условием в). Пусть Л1=0. Тогда .х1 =хз=хз= 1 — критическая точка.
Функция !(х) =х1з+хгз+хзз-»+о» при )х)-~-со, значит, по следствию из теоремы Вейерштрасса (и. 1.2.1) решение задачи .существует, а в силу единственности критической точки решением может быть только она. Итак, х= (1, 1, 1)енаЬзш!п, .9 1=3.
4. (Ах, х> — !п1; (х, х>=1 (хенй", А=(аы)ос~ 1 — симметричная матрица). Решение. Существование решения Х очевидно из теоремы доз Вейерштрасса, ибо сфера 5" '=(х~!с"()х)з=(х, х)=1) компактна. Функция Лагранжа: Ы=Ло(Ах, х>+Л~(х, х). Необходимые условия: ,У,,(х, Ло, Л1) =0«»ЛоАх+Л~х=О, ЛоъО. Если Ло=О, то Л~ФО и, значит, х=О, что противоречит уравнению связи (х, х)=1.
Положим Ло=1, Тогда АХ= — Л12. Таким образом, решение — собственный вектор матрицы А. Домножив соотношение Ах= — Л|х на х, получим, что Я,= = — Л~,. иначе говоря, решение задачи на минимум — собственный вектор матрицы А, соответствующий наименьшему соб:ственному значению. 2.6. 0 методах решения зкстремальиых задач. Градиентный метод и метод Ньютона Ограничимся здесь простейшим случаем безусловной комечномерной минимизации, т.
е. минимизации (гладкой) функции ! в задаче без ограничений: )(х)-мп(; х~й". (з) 'Выше много внимания было уделено необходимым условиям экстремума. 55 (2г Теория экстремальных задач предлагает следующий рецепт-,, решения задачи (з). Надо найти все точки, удовлетворяющяе ' необходимому условию первого порядка' (т. е. теореме Ферма), .
1'(х) =О, (1) 2! а затем проверить нх на максимум и минимум с помощью крн- 4 теряев второго порядка. Но следует сказать, что прн решении 1 конкретных практических зада г ) с привлечением ЭВМ методы ра- ~ У зыскання экстремумов далеко не всегда прямо связаны с тео- !! рией экстремальных задач. Эта.4! Ф теория существенна для поннма- ''. ! ! ния постановок задач, всех возу ! можностей, заключенных в ннх„".' н т. п. Покажем, что существуют / ', н весьма эффективные, другие '!) х !/ ', методы, отличные (в применении„;, о х х, х, х например, к задаче о безусловной минимизации) от решения урав-, нения (1). Но начнем все-такн с давнего 1 р .г метода, принадлежащего Ньюто-,' ну, метода решения именно урав- „.-' нения (1).
м Пусть Р: К"-!'-К" — отображение класса С'. Для решения уравнения Р(х) =О применима следующая процедура. Беретсж некоторая точка х' н далее строится последовательность точек: по правилу: хь+!=х" — (Р'(хь)) !Р(х"), А=О, 1,.... Эту процедуру в случае н=1 см. на рнс. 2. Для нахождения точек минимума функции )~Се(й") в соответствия с (1) следует применить процедуру (2) (прн вы- ' ' бранном начальном приближении хь).
Тогда приходим к следующему итеративному процессу, который называется методом. ':. Ньютона: хь+! =хь — ()е(хь) )-!)'(хь) й — О 1 (3) Можно показать, что если )а удовлетворяет условию Лнпшнца н условию сильной выпуклости (1" (х) ьат) н норма, 1'(хь) достаточно мала, то метод (3) сходится к точке х глобального минимума 1' с квадратичной скоростью (!!хь — х~(~Сдть) ..
А следующий метод не связан прямо с решением уравнения, ' (1). Он состоит в следующем. Предположим, что )енС!(11 ).. Тогда следует выбрать снова некоторую начальную точку хь н построить последовательность точек по правилу хе+!=х" — аь)'(х"), аь)О, й=О, 1, .... (4) 56 Такого рода процедуры называют градиентными методами. Числа а" называют длиной шага метода. Идея метода проста.
Вектор 1'(х) смотрит в сторону наибольшего возрастания функции 1 в точке х, вектор — 1 — в сторону наибольшего убывания. Каждый раз, совершая итерацию (4), мы «спускаемся» по функционалу. Поэтому можно надеяться, что мы будем приближаться к точке минимума. Простейший вариант градиентного метода возникает, когда в (4) а"— = а=сопз1.
Можно показать, что если градиент1"'удовлетворяет условию Лившица,г1 ограничено снизу и а достаточно мало, то 1'(хь)- О при й — со, а если в дополнение предпо.ложить, что 1 †силь выпуклая функция, то обнаружится, что хь стремится к точке глобального минимума 1 со скоростью геометрической прогрессии. Сравнение двух описанных методов обнаруживает нх сильные н слабые стороны. У градиентного метода сильные стороны в простота вычислений н налагаемая-малая гладкость на 1, но сходится градиентный метод медленнее и требует экспериментов с выбором а.
Метод Ньютона сходится очень быстро, но прн довольно жестких требованиях гладкости на функцию. 'При этом он предполагает гораздо большой объем вычислений. Подробнее обо всем этом см. в 15; 16; 21], а также в монографии Ф. П. Васильева «Методы решения экстремальных задач» (М.: Наука, 1981). % З. ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Линейное программирование — один нз наиболее ролно теоретически разработанных разделов методов оптимизации.
В этом разделе изучают задачи об экстремуме линейной функции при ограничениях типа равенств н неравенств, задаваемых также линейными функциями. Такого рода задачи играют существенную роль в приложениях, особенно в экономике. В данном паРаграфе коснемся основных аспектов теории: вопросов, связанных с существованием решений,,критериев решения, численных алгоритмов, теории двойственности. 3.1. Симплекс-метод 3.1.1. Постановка задачи. Общей задачей линейного программирования назовем задачу (с, х>-»(п1; Ах(Ь.
(з) Задачи линейного программирования рассматриваются,- как правило, приведенными к канонической <с, х>-~зцр; Ах=Ь, х~О, (зк) 57 или к нормальной форме (с, х)-э-зцр; Ах<Ь, хъО. (з~~' Здесь х= (х„...,х„) еий", с= (сь..., с„) ай", Ь= (Ь„...
' ..., Ь„)енц'", А=(а!), ~п... „— матрица размеров тХи сь! столбцами а~= (аА...,а )) 1=1,...,п. Каноническая форма более удобна при описании алгорит-- мов решения, задачи (з) и (зи) часто используются при рас- ( смотрении проблем существования решений и двойственности. " Задачу в нормальной форме всегда можно свести к задаче в;, канонической или общей форме введением дополнительных координат и изменением матрицы А. Возможны и обратные сведения.
Например, если дана задача: (с, х)-~.зпр: Ах(Ь, хъ ъО, то можно ввести координаты х=(х„+ь...,х„+ ) и получить задачу в канонической форме: (с, х)-~.зпр; (а~, х>+х +;=Ьь хъ О, х)0. Обозначим С множество допустимых точек в задаче линейного программирования. Множество С вЂ” выпуклый многогранник в пространстве й". Нетрудно видеть, что экстремум линей-=г ной функции (если он существует) достигается в крайней (уг- ' ловой) точке выпуклого многогранника. Число крайних точек,: множества С, задаваемого в виде конечного числа линейных равенств и неравенств, является конечным (20, с. 190].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
