XIV Аттетков и др. Методы оптимизации (1081420), страница 45
Текст из файла (страница 45)
В конкретной ситуации можно добиться выполнения этого ограничения, доопределив все функции вне множества Х, например, большим постоянным значением, которое не повлияет на процесс минимизации целевой функции. Сформулированная задача представляет собой частный случай обисей задачи матемапиачееноео ароераммирооания, за- 7.3. Общая задача нелинейного программирования 311 ключающейся в определении наименьшего значения целевой функции 7о(х) на допустимом множестве Й=1хЕХ: Цх) =О, .1=1,к, д (х) <О, з=1,т). (79) Отметим, что если все функции ))(х)., 1 = 1, и, и д;(х), 1 = 1, т, непрерывны в Я'.", то множество Й замкнуто.
В самом дслс, это множество можно представить как пересечение конечного числа множеств вида (х Е лч": у(х) < о), образованньгх непрерывной в Кп функцией ~р(х). В данном случае в качестве ~о(х) используются функции ))(х), — ~~(х), 1 = 1, к, и д,(х), 1 = 1, т, а а = О. Такие множества являются замкнутыми (см. доказательство теоремы 7.1). Поэтому и множество й, как пересечение конечного числа замкнутых множеств, является замкнутым. Большинство известных методов решения задачи нелинейного программирования позволяют найти лишь точки локального минимума целевой функции на заданном множестве.
В этой связи важную роль играет априорная информация о существовании решения задачи, т.е. информация о том, достигает ли целевая функция наименьшего значения на допустимом множестве. Если допустимое множество П в задаче нелинейного программирования замкнуто, то доказательство существования решения в этой задаче можно строить с помощью теоремы 7.1, проверяя непрерывность целевой функции Д(х) и ограниченность при некотором о множества П = (х Е й: Д(х) < гл1.
В частности, если множество й ограничено, а целевая функция непрерывна на Й, то задача нелинейного программирования имеет решение. Однако проверить ограниченность множества 11 (или П„) нс просто. Поэтому интсрссны другие условия, налагаемые на целевую функцию и ограничения и позволяющие делать заключение о существовании решения без использования ограниченности допустимого множества. В задаче выпуклого программирования, в которой целевая функция выпукла и допустимое 312 7.
АНАЛИТИЧЕСКИЕ МЕТОДЫ множество Й выпукло, любая точка локального минимума це- левой функции, согласно теореме 3.14, является решением этой задачи. Теорема 7.5. Если функции д, (х), ~, '= 1, т,, выпуклы в К", то множество Й = 1х Е К": дух) < О, 1 = 1, .т ) (7.10) является выпуклым. ~ Утверждение теоремы очевидно, если множество Й пусто или содержит всего лишь одну точку. Поэтому ограничимся случаем, когда это множество содержит по крайней мере две точки.
Выберем в нем произвольные точки х1 и хз. Тогда д;(х') < 0 и 9,,(хв) < О, г = 1, т. В силу определения 3.2 выпуклости функции для любого числа о Е (О, 1) имеем дг(ох1+ (1 о)хз) ~ ~одз(х1) + (1 о)дг(хз) ~ ~О, $ = 1, пь Поэтому точка ох1+ (1 — а)хз также принадлежит множеству Й, а это означает, .согласно определению 3.1, что Й является выпуклым множеством. ~ Замечание 7.1. Из теоремы 7.5 следует, что если допустимое множество Й определяется только ограничениями типа неравенства д;(х) < О, 1 = 1, гп, причем все функции д,(х) выпукяые в Ж", то множество Й выпукло. Наличие ограничений типа равенства усложняет проверку допустимого множества на выпуклость.
Однако если функции ~~(х) во всех ограничениях типа равенства являются линейными, а все функции д,(х) в ограничениях типа неравенства — выпуклыми, то допустимое множество выпукло. Действительно, в этом случае допустимое множество Й является пересечением множества Й вида (7.10) с гиперплоскостями Ях) = О, г = 1, ~п.
Множество Й выпукло в силу теоремы 7.5, гиперплоскости также являются выпуклыми множествами (см. пример 3.3). Поэтому множество Й, как пересечение выпуклых множеств, выпукло. ф Т.З. Общая задача нелинейного программирования 313 Ограничения типа неравенства в задаче нелинейного программирования введением дополнительных переменных можно преобразовать в ограничения типа равенства. Например, ограничения д,(х) < О, 1 = 1, т, с помощью дополнительных переменных е, мОжнО записать В Виде (7.11) д,(х)+я; =О, г = 1, пь Таким образом, общую задачу нелинейного программирования можно свести к частному случаю, .когда в задаче нет ограничений типа неравенства.
Это позволяет в решении задачи использовать технику исследования целевой функции на условный экстремум (см. 7.2). Впрочем, техника исследования функции на условный экстремум может использоваться и непосредственно в задаче, имеющей ограничения типа неравенства [У). Пример 7.1. Рассмотрим задачу нелинейного программирования < У( ,* ) — щ д1(зб,хя) < О, дя(хмхв) < О, дз(хмхз) < О, в которой функции зг(хмхэ), д1(хмхз),. дг(хмх2), дз(хмхя) непрерывно дифференцируемы в К~. Предположим, что множество Й, которое определяется тремя неравенствами, ограничено и имеет вид, изображенный на рис. 7.1.
В этой задаче наименьшее значение функции 1(хмх2) может достигаться либо во внутренней точке множества Й, т.е. в точке множества Йв = ((хм хя): дг(хм тя) < О, г = 1., 2, 3), либо на границе множества Й на одной из дуг АВ, АС, ВС, либо в угловых точках границы А, В, С. Поэтому решение задачи можно строить по следующей схеме. 314 7. АНА.*?ИТИЧЕСКИЕ МЕТОДЪ| Рис. 1.1 1. Определяем все стационарные точки целевой функции в области йс. 2. Решаем три задачи на условный экстремум < |'(хыхз) — ~ ех|г, ~~(хмхз) — + ехгг, ~Дхыхз) -+ ех1г, д|(хмхз) = О; (дз(хмхз) = О: ~ дз(хмхз) = О. Среди найденных точек отбираем те, которые попадают на соответствующую дугу АВ, АС., ВС. Например, из решений первой задачи нужно оставить такие точки (хм хз), которые удовлетворяют условиям дз(хмхз) < О, дз(хмхз) < О.
3. К точкам. отобранным в первых двух пунктах, добавляем угловые точки А, В, С, которые находятся из систем 4. Во всех отобранных точках вычисляем значение целевой функции и отбираем ту (иви те), в которой значение функции наименьшее. ф Описанный в примере 7.1 процесс анализа внутренних точек допустимого множества и различных частей границы можно д|(хмхз) = О. дз(хмхз) < О, дз(хыхз) = О; д|(хыхз) < О.
д2(х|,х2) = О, дз(хыхз) =О; д|(хмхз) = О. дз(хыхз) = О, дз(хыхз) < О. 315 7.3. Общая задача нелинейного программирования объединить в одну формальную процедуру. Рассмотрим общую задачу нелинейного программирования (7.8). Теорема 7.6. Если точка х* Е й является точкой локального минимума функции !б(х) на множестве Й вида (7.9), причем функции 7!(х), 1 = О,. й, и д,(х), с = 1, т, непрерывно дифференцируемы в окрестности точки х*, то существуют такие числа Лб ! = О, й, и р; ) О, 1 =1, т, одновременно не равные нулю, что для функции я т с(х) = Лб~б(х)+ ~> Л!Д!(х)+ Я !цд,(х) выполняется необходимое условие экстремума ягас11(х*) = О и., кроме того, выполняются условия дополняющей не- жесткости !л;д,(х*) =О, 1=1,п.
ф Теорему 7.6 принято называть теоремой Куна — Танкера*, а функцию! !,х) -- функцией Лаеранжа. Хотя функция Лагранжа определена для любых значений параметров Ль ! = О, й, и рн г' = 1, т, мы, учитывая утверждение теоремы Куна -- Таккера, будем рассматривать ее лишь при р; > О, г = 1, п. Отметим особую роль в этой теореме условий дополняющей нежесткости. В рассматриваемой точке х* локального минимума функции !б(х) на множестве Й каждое из ограничений д,(х) < О, г = 1, т, выполняется либо в виде равенства, .д,(х") = О, либо в виде строгого неравенства, д,(х") < О. Ограничения первого вида называют активными оераничениями, в то время как остальные неактивными оераничениями. Для активных ограничений соответствуквщее условие дополняющей Смл Алексеев В.М., Тмеомнрвв В.М., Фомин С.В.
Х АНАЛИТИЧЕСКИЕ МЕТОДЫ нежесткости выполнено. Неактивные ограничения в силу непрерывности фигурирующих в задаче функций выполняются в виде строгого неравенства не только в точке х*, но и в некоторой окрестности этой точки. Поэтому после удаления этих ограничений из задачи точка х' останется точкой локального минимума.
Полагая для таких ограничений р, = О, мы, с одной стороны, обеспечиваем выполнение условия дополняющей не- жесткости, а с другой удаляем соответствующее слагаемое из функции Лагранжа. В конечном счете утверждение теоремы Куна — Такксра сводится к обобщенному принципу Лагранжа. Вернемся к примеру 7.1 и поясним., как работает сформулированная теорема. В да|шом случае ограничений типа равенства нет, а есть три ограничения типа неравенства. Если точка х* находится внутри множества Й, то утверждение теоремы будет верно при р1 = рв = рз = О, Ла = 1.
Если точка х" находится на одной из дуг, например на дуге АВ, то в этой точке дз = О. Утверждение теоремы вытекает из обобщенного принципа Лагранжа для задачи с ограничениями типа равенства при р,1 = рв = О. Наконец, в угловой точке, например в точке А, выполняются два равенства д1 = О и дз = О. '-1тобы обеспечить условия дополняющей нежесткости, полагаем рз = О. При этом необходимое условие экстремума для функции Лагранжа состоит из двух уравнений, в которых неизвестны три параметРа Лш И1 и Рз, пРичем относительно этих паРаметРов система уравнений является линейной и однородной. Ясно, что такая система имеет ненулевые решения.
Пример 7.2. Рассмотрим задачу нелинейного программирования < Те(хмхз) = 1х1 — 3) +(хз — 3) — > шш — х~ (О, — хэ (О, к~+хе — 4(О. В этой задаче допустимое множество представляет собой замкнутую треугольную область на плоскости (рис. 7.2), в ?.л. Общая задача нелинейного программирования 317 которой непрерывная целевая функция достигает наименьшего значения.
Кроме того, нетрудно увидеть, 4 А1 что ограничения задачи линейные, а ц ., ------ ° А целевая функция, как квадратичная Ая: функция с положительно определенной матрицей, строго выпукла. По- л .. Я : д этому рассматриваемая задача относится к зада 1ам выпуклого про- Рис. 7.2 граммирования. Проследим на примере этой простейшей зада 1и, как работает теорема Куна - -.
Таккера. В этой задаче нет ограничений типа равенства, функция Лагранжа имеет вид А1Я1,х2) = ЛО (1х1 — 3) + 1х2 — 3) ) — /с1х1 — рзнав+Н31х1+х2 — 4). Записываем систему уравнений, включающую необходимое условие экстремума функции Лагранжа и условия дополняющей нежесткости: 2Лб1х1 — 3) — р1+ рз = О, 2Ло(*2 — 3) — рз + рз = О, Р1х1 = О, цэяв = О, Рз(х1+тв — 4) =О. В случае Ле = О из двух первых уравнений находим р1 = = цв = рз, причем общее значение этих трех коэффициентов ненулевое, так как по теореме Куна -- Таккера хотя бы один из множителей Лагранжа должен быть ненулевым. Из последних трех уравнений заключаем, что и1 = яз = О, я1+ ия = 4, а это невозможно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
