XIV Аттетков и др. Методы оптимизации (1081420), страница 43
Текст из файла (страница 43)
Проведите сравнительный анализ результатов, дайте их графическую интерпретацию. Перечислите методы, гарантированно приводящие к минимуму целевой функции за конечное число шагов поиска. 6.4. Решите задачу ~(хыхт) = 10(х1 — хз) + (х1 — 1) — ~ шш, выбрав в качестве начальной точку хо = ( — 1, 1) и задав значение параметра точности поиска е = 10 з. Примените методы циклического покоординатного спуска, Розенброка и Пауэлла. Оптимизируйте процесс поиска точки (1, 1) минимума целевой функции, используя различные алгоритмы одномерной минимизации на каждом шаге покоординатного спуска: дихотомии, золотого сечения, квадратичной и кубической интерполяции. 6. АЛГОРИТЛ1Ы ПРЯМОГО ПОИСКА Проведите сравнительный анализ алгоритмов по числу 1у шагов поиска.
Дайте графическую интерпретацию полученных результатов. 6.5. Используя методы прямого поиска, минимизируйте функцию Розенброка 2 (х1,хз) = 100(х, — хз) +(х1 — 1) с точностью е = 10 з, выбрав начальную точку хс = ( — 1, 1). Установите, какие из примененных алгоритмов не позволяют при заданной точности поиска получить точку минимума (1, 1) вследствие прсждсврсмсппого окончания процесса поиска.
6.6. Используя различные модификации метода Хука Дживса, минимизируйте функцию Химмельблау 1(х1,х2) = (х1+хз — 11) +(х1 +хз — 7) с точностью е = 10 з, выбирая различные на1эльные точки: а) (5, 5); б) (5, — 5); в) (О, 0); г) ( — 5, — 5); д) (5, 0).
Оптимизируйте процесс поиска путем изменения параметров алгоритма. Дайте графическую иллюстрацию полученных результатов. 6.7. Минимизируйте функцию Пауэлла 4' (х1, х2, хз ~ х4) = = (х1+10хз) +5(хз — х4) +(хз — 2хз) +10(х1 — х4), выбрав параметр точности поиска е = 10 з и начальную точку хс = (3, — 1, О, 1). Для этого используйте метод Нелдера-- Мида, оптимизируя процесс поиска подбором параметров алгоритма. Установите, можно ли получить точку минимума х* = (О, О, О, 0) целевой функции, используя поиск с помощью регулярного симплекса. 7. АНАЛИТИЧЕСКИЕ МЕТОДЫ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Общая задача нелинейного программирования может включать ограничения птпа равенсп~во, или ограничения титш нерве енот,ва, а также оба вида ограничений одновременно.
В этой главе сначала кратко обсудим задачу нелинейного программирования, в которую входят только ограничения типа равенства, а затем перейдем к общему случаю. 7.1. Минимизация целевой функции на заданном множестве Рассмотрим общую задачу математического программирования Уо1х) — ~ шш, х Е Й, (7.1) где й допустимое мнолеество, входящее в область определения Р(Я С вп целевой функции Д(х). Пока не будем уточнять, каким способом задано множество Й, но будем считать, что оно не пусто.
Если множество й компактное, то существует хотя бы одна точка х' Е Й, в которой непрерывная на этом множестве функция Д(х) достигает своего наименьшего значения ~Ъ 1. Следовательно, задача 17.1) в случае непрерывной целевой функции и компактного допустимого множества имеет решение.
Теорема 7.1. Если функция 7в1х) непрерывна на замкнутом множестве й С К" и для некоторого о Е К множество Х = = 1х Е Й: зв1х) < о~ не пустое и ограниченное в н", то задача (7.1) имеет решение. 302 7. АНАЛИТИИЕСКИЕ МЕТОДЫ Так как функция 1в(х) непрерывна в Й, множество Х, определенное нестрогим неравенством 1В(х) < о, является замкнутым. Действительно, если х Е Й вЂ” предельная точка о множества Х, то в любой окрестности этой точки можно указать точки множества Х. Возьмем произвольное число с > 0 и, согласно условию непрерывности функции 1в(х) в точке х, выберем окрестность Цх~,.6), для которой ~1в(х) — Ях~)~ < е при х Е Цхв,б) й Й.
В этой окрестности существует точка х1, принадлежащая множеству Х, т.е. для этой точки выполняется неравенство 1в(х') < сс Значит, 1в(хе) < Ях') + е < о+ е. Поскольку записанное неравенство верно для любого числа е > О, то 1с(х~) < о и х~ Е Х. Итак, множество Х содержит все свои предельные точки, а потому замкнуто. ФУнкЦиЯ 1в(х), непРеРывнаЯ на замкнУтом огРаниченном множестве Х, достигает на этом множестве наименьшего значения в некоторой точке х*. Из условия х* Е Х вытекает, что 1'в(х*) < о. Если х Е Й ~ Х, то в соответствии с определением множества Х выполняется неравенство 1с(х) > о. Поэтому 1с(х) >о>1с(х ), хЕЙ~Х, и значение целевой функции в точке х* является наименьшим на всем множестве Й. > Рассмотрим произвольную точку х Е Й.
Будем говорить, что единичный вектор е Е К" задает допустимое направление в точке х, если для некоторого числа е > 0 каждая точка х+1е, 1 Е (О, е), принадлежит множеству Й. Множество С(х) всех единичных векторов, каждый из которых задает в точке х Е Й допустимое направление, называют конусом допустимых направлений в точке х. Если множество Й выпуклое, то допустимое направление в точке х Е Й можно задать любым вектором х — х, определяемым произвольной точкой х Е Й. не совпадающей с х. Действительно, в этом случае для е = * в качестве б > 0 (х — х) можно выбрать е = ~х — х~. т.к мияимиаация целевой функции на аадаяном множестве 303 Теорема 7.2.
Пусть Функция Ях) дифференцируема* в точке х' е Ка. Если х' является точкой наименьшего значения функции Д(х) на множестве Й, то (дуясь Ях*), е) > О, е й С(х*). (7.2) ~ Выберем вектор е е С(х*) и соответствующее этому вектору число б > О, так что х*+ 1е е Й при 1 е (О,б). Функция ~ре(1) = = Д(х*+1е) определена на полуинтервале [О, б) и достигает наименьшего значения при 1 = О, .так как ~ре(0) = Д(х*) ( (,(б(х) = р(Х), где х = х*+ ге Е Й,. г. Е (О, б).
Отсюда вытекает, что > О, 1 е (О, б). Так как функция А(х) дифференцирусма в точке х*, то сложная функция ~ре(1) дифференцируема в точке Г = О. Поэтому существует предел Производная функции со,(~) в точке ~ = 0 представляет собой производную функции (о(х) в точке х' по направлению вектора е, которую с помощью градиента функции можно записать в виде (рас1 ~о(х*), е) [У). Таким образом, неравенство ео' (0) > 0 равносильно неравенству (7.2). ~ Утверждение теоремы 7.2 можно рассматривать как обобщение необходимого условия локального экстремума. Чтобы придать такой трактовке более точный смысл, введем следующее понятие.
Будем говорить., что функция Д(х), определенная на множестве, Й, имеет в точке х* Е Й локальный лаииимум иа мноэхестпве Й, если существует такая окрестность *Дифференцируемость функции в точке предполагает, что функция определена в некоторой окрестности этой точки, т.е. все точки дифференцируемости функции являются внутренними точками ее области определения.
ЗО1 7. АНАЛИТИЧЕСКИЕ МЕТОДЫ Г точки х*, что 1в(х) > )в(х*) при х Е Г Г~ Й. Если последнее неравенство в случае х у'= х* является строгим, то будем говорить о стпроеом локальном минимуме на мнохсестпве Й. Введенные понятия расширяют понятия локального минимума и строгого локального минимума: согласно определению, точка локального [строгого локального) минимума должна быть внутренней точкой множества Й. Повторяя почти дословно доказательство теоремы 7.2, можно показать, что если х* Е Й вЂ” точка локального минимума функции 7в(х) на множестве Й, а функция 1в(х) дифференцируема в точке х*, то имеет место условие (7.2).
Если точка х' является внутренней точкой множества Й, то конус допустимых направлений С(х') содержит все н-мерные единичные векторы, а условие (7.2) легко преобразовать в обычное условие локального экстремума функции, записанное в виде (Егас1 Ях'), е) = О, е Е ~". Действительно, в этом случае условие (7.2) выполняется для любой пары единичных векторов е и — е, а потому в этом условии знак нестрогого неравенства можно заменить знаком равенства. Кроме того, условие [е[ = 1 не является существенным, так как множитель, равный длине вектора е, можно вынести за знак скалярного произведения.
Отметим, что условие (рагЩх*), е) = О, е Е К",. эквивалентно условию Егаг1~в(х') = О. В самом деле первое условие непосредственно вытекает из второго. Наоборот, если верно первое условие, то равенство (Егаг1Д(х*), е) = О верно и при е = ягас1Ях'), т.е. [ягас1Д(х*)[з = О, что равносильно равенству Егас1Ях') = О "- обычной формулировке необходимого условия локального минимума [Ъ ).