Силаева Т.А. - Методы решения задач оптимального проектирования ВС (Методы решения задач оптимального проектирования ВС (Силаева Т.А.)), страница 5

Опишите трн градиентных метода, их геометрический смысл и сравните методы между собоЙ. 4. Найдите решение заданной преподавателем задачи безусловной оптимизации функции с помощью классического метода и трех градиентных, выполнив в них две итерации. 5. Опишите методы случайного поиска и сравните их с градиентными. Работа 2. МЕТОДЫ РЕШЕНИЯ ЗАДАЧ УСЛОВНОЙ ОПТИМИЗАЦИИ Цель работы: изучить и практически овладеть основными методами решения задач условной оптимизации. ОБЩИЕ СВЕДЕНИЯ Методы решеяяя задач условной оптимязацин при ограничениях тяпа равенств Эти методы применяют для решения задач нелинейного программирования.

ЗО Решаемая аадача условной оптимизации функции 1(Х) при наличии ограничений типа равенств имеет следующий вид: в векторной форме < ехьг 1(Х), Х Ф(Х)= О или в координатной форме < ехзг ('(х, ...,х„), хы.,.,х <р (х1, ...,х„)= О (1= 1, т, т< и). (22) Методы решения этой задачи основаны на сведении ее к задаче безусловной оптимизации и применении уже рассмотренных методов решения таких задач. 1. Метод непосредственного исключения Решая т уравнений (2.2), находим т входящих в нвх переменных х ((= п — т+ 1,п~ в виде т функций от остальных и — т переменных х,. ((= 1, и — т ) Подставляем полученные функции в выражение для г'(Х), в результате чего задача (2.1)— (2.2) сводится к задаче безусловной оптимизации функции ( х.--) ехСг 1(хз,...,х„). Данный метод не очень удобен в применении, поэтому используется редко. 2.

Метод штрафных функций Это грубый метод с недостаточно хорошей сходимостью, но простой. Он применяется для нахождения первоначального приближения Х' ), а затем используют более точные методы. Соглас(О) но методу штрафных функций задача (2.1) — (2.2) условной оптимизации функции ('(Х) сводится к задаче безусловной оптимизации вспомогательной функции: ц (Х ) = г' (Х ) + оэ (Х ), 31 оз(Х) = ~ч„а,ср (Х), Ь(Х, Л) = у'(Х)+ ,'~ 2,~р,,(Х), — (Х,Л)= О [1= 1,л) дй аб / — (Х,Л)= О ~ )= 1,т '. Отсюда имеем л — ",(Х) = О [1= 1,л), ар.

р,.(Х)= О Ряс. 23 32 33 где в(Х) — штрафная функция. Ее выбирают таким образом, чтобы при выполнении ограничений (2.2) она обращалась в нуль, иначе (достаточно невыполнения д.(Х) = О хотя бы при одном ) ) 1 резко возрастала. Поэтому в качестве ю(Х) можно взять следующую функцию: где и — достаточно большие положительные константы прв по) иске минимума функции у'(Х) и отрицательные — прн максимуме.

3. Метод множителей Лаеранлеа В данном точном методе задача (2.1) — (2.2) условной оптимизации функции г"(Х) сводится к задаче безусловной оптимизации функции Лагранжа, имеющей вид: где Л= ~Л~,...,2. ) — вектор множителей Лагранжа. Полученную задачу безусловной оптимизации решаем с помощью классического метода, основанного на необходимом и достаточном условиях экстремума.

Находим необходимое условие экстремума функции Ь(Х, Л): Решив зту систему уравнений, получим значения Х и Л, которые удовлетворяют данной системе. Найденные точки (или точ- ка) Х являются стационарными, в в них необходимо провервть выполнение достаточного условия экстремума. Достаточное условие минимума функции 1 (Х, Л ) по Х точке Х вЂ” это положительная определенность в данной точке Х той части размером лх п матрицы Гессе функцви Ь(Х, Л), которая соответствует вторым частным производным от Ь(Х, Л) по Х (не по Л): Обозначение Л(Х') введено для указания зависимости значения Л от значения Х . Достаточное условие шах Ь(Х,Л) в точ- Х ке Х* — отрицательная определенность С(Х,Л(Х )). Рассмотрим геометрическую интерпретацию метода множителей Лагранжа. Пусть я= 2, т= 1.

На рис. 2 1 изобразим ливии постояявого уровня функции )(х~,х2)= с ( о= 1,3, причем е1> с2> сз) и кривую ограннчения у(х1, х 2) = О. Имеется трн точке касания кривой ограничения с линиямв постоянного уровня: Х1, Х2 и Хз Точки экстремума обязательно лежат на кривой ограниченая н являются точками касания атой кривой с линиями постоянного уровня.

Напомним„что точка Х называется локальным максиму- мом фуыкцви у(Х), еслв существует такая е-окрестность этой точки, что для .любой точки Х данной окрестности выполняется условие )'(Х ) ь,)'(Х ) . При минимуме )'(Х ) > ) (Х ) . Для глобального экстремума указанные условия должны выполняться для любой точки Х области допустимых значений. Отсюда следует, что если при движении вдоль крывой ограниченна в двух разных направлениях из точки касания данной кривой с линиев постоянного уровня значение функции в е-окрестности точки касания ые будет возрастать по сравнению со значением функции в точке касания, то данная точка является локальным максимумом.

Если же значение функции у(Х) не будет убывать, то точка касания — локальный минимум. Локальный максимум (минимум) будет одновременно н глобальным, если значение функции в любой точке кривой ограничения меньше (соответственно больше) или равно значению функции в точке касания. Если при движении из точки касания ливии постоянного уровня с кривой ограничения вдоль этой кривой в одном направлении функция у'(Х) возрастает„а в другом — убывает, то точка касания является точкой перегиба (стацвонарной точкой, во ые экстремумом).

На рис. 2.! имеем точки локальыого минимума Х! и локального максимума Хз, а также точку перегиба Хз, Если необходимые условия экстремума функции Ь(Х, Л) дают сложную систему уравпеыий, то используем следующий метод. 4. Метод лоиска седеоеой точки )бункции Лагранжа При нахождеыии минимума функции )(Х) функция Лагранжа 1 (Х,Л) имеет в точке (Х, Л ) седловую точку, если выполняется неравенство: Ь(Х,Л ) > Ь(Х,Л )> Ь(Х,Л) или, что тоже самое: Ь(Х,Л )= ш)о шах Ь(Х,Л)= шах тгп Ь(Х,Л). х л л х В методе поиска седловой точки функции Лагранжа задача условной минимизации функцви у(Х) при наличии ограничений (2.2) сводится к нахождению седловой точки функции Лагранжа Х (Х,Л). Ы (Х(й))+ ч; )„(й) Т( ~Х(й)) )=1 р) ~ (й) ,„('=' ") а,,'',! )), р (х(й)1 )), х(й»!) ) (й)+ ь(й) ~ ~ ),(й)+ ь(й)р (х(й)) а),.

у), 5. Метод проекции градиента Для решения задачи (2.1) — (2.2) условной оптимизации функции )"(Х) при налвчии ограничений (2.2) нельзя непосредственно использовать метод градиентного спуска, так как ые всякая (й+ !) полученная по этому методу точка Х будет удовлетворять данным ограничениям (2.2), т.е. условию Ф(Х )1= О. Паато( !й+!) 1 му для учета этого условия в методе проекции градиента на каждой итерации й вначале определяем по Х точку Х согласно ме!й) тоду градвеытного спуска: Х = Х(й)~ Л УУ~Х(й)) (2.3) (знак «+» используем при поиске максимума функции )(Х) и «-» прн мяыимуме), а затем находим проекцию Х точки (й+ 1) Х па поверхность Ф(Х)= О ( а более точно, ва гиперплоскость УФ !), являющуюся аппроксимацвей поверхности Ф(Х)= О при условии, что Ф(Х! ) = 01. ( !)+!)х Геометрическая интерпретация метода проекции градиента представлена на рис.

2.2, где при л= 2 в т= 1 изображены 35 Из определения седловой точки следует, что в ней достигается минимум функции Лагранжа по Х и максимум по Л. Поэтому можно применять для функции Лагранжа Ь(Х, Л) итерационные методы решения задач безусловной оптимизации функции, рассмотренные в первой лабораторной работе. Например, расчетные формулы поиска минимума функции )'(Х) согласно методу градиентного спуска будут следующвми: Х(й") т Х'+ Р= ХОО+ Л Х. (2.4) точки Х®, Х и Х( +1), кривая ограничения ч)(Х)= 0 (частный случай при л= 2 и и= 1 поверхности ограничений Ф(Х) = 0), прямая и (частный случай гиперплоскости О( + ), векторы (й + 1) (й « 1) Р и Л Х, связанные с Х ), Х и Х следующим соотношением: 2. Определяем в точке ХОО градиент Ч('(Х(~)), вектор Ф(ХОО) функций из огранвченвй (2.2) в матрицу А = [а),~ первых частных производных а,= — 2 (Х()) (г= 1,и, (т 1,л).

3. Вычисляем матрицу В=Ау ( Ах Ат1-' пх т лх т)«тх л пх т) и вектор ЛХ= Ь( В Ат+ Е 17У(Х(й))- В Ф(Х(й)), пх1 (лхттхп лхл) пх( пхт тх1 Рп«. 2.2 Итак, согласно (2.4) и (2.3) задача нахождения точки Х(й+1) сводится к поиску вектора Р или вектора йХ. Проекцией точки Х на множество () + называется точка (й+ 1) Х, для которов ((Х~ ) — Х ~(т ш(п ((Х вЂ” Х ((т Р ° - 1!! Хе У В результате решения првведенной задачи условной минимизации по нахожденвю Р с помощью метода множителей Лагранжа получено выражение для определения Р, а по нему согласно (2.3) — (2.4) выражение для ЬХ.

Тогда алгоритм решения исходной задачи (2.1) — (2.2) условяой оптимизации функции /(Х) прв наличии ограничений типа равенств по методу проекции градиента состоит в следующем. 1. Принимаем й= О. Выбираем начальное приближение Х(0), точность решения е и шаг л в направлении поиска безусловного экстремума. где под матрицами и векторами указаны их размерности; знак «+» при Е вспользуем при поиске максимума функции )(Х) и «-» при минимуме; А = [а,.„~ т нированием матрацы А = [а,| — матрица, полученная транспаЕ= [е;«1 — единичная матрица размером л х л (епт 1, е(й= 0 при )т й ) 4. Определяем Х = Х + ЬХ.

(й+ 1) (й) 5. Провернем условие завершения итерационного процесса поиска экстремума ~ у(Х )- ~(Х ) ) ~ < е (г= О, 1 ), Если условие выполняется, то переходим к и. 6, иначе принимаем й = й+ 1 н переходим к и. 2. 6. Конец алгоритма, Отметим, что каждый элемент з -«обратной матрицы Ю (где Я= [г «1 — квадратная матрица с ненулевым определителем ()е13) образуется как алгебраическое дополнение 1)й элемента з)е в определителе де( 8, деленное на сам определитель: < ех'«г ЦХ), Хе Хй Х1) = (Х < Ч (Х) < О < Рз«. 2.3 или з координатной форме ехьг 1~х ~,...,х„), 1''"' « цю (х~,...,х„)< О (1= 1,т) (2.6) 39 38 Методы решенвв задач условной оптимизацвн прн ограничениях типа неравенств Этв методы применяют для решения задач нелинейного программирования.