XIV Аттетков и др. Методы оптимизации (1081420), страница 48
Текст из файла (страница 48)
В соответствии с (7.31) двойственная функция И(ю) имеет вид Ее значение д* в точке ю* равно Чтобы найти координаты точки я* = (х1, и,*, хз), в которой функция у(в) достигает на множестве Й наименьшего значения, решим систему уравнений (7.32), в данном случае принимающую следующий вид: а 2 Х1Х2 1/2 Х1 л2 '1 из 2 '2 хз = Юзд, ЮЗ + Ю4 Ю4 1оз + ю4 7.
АНАЛИТИЧЕСКИЕ МЕТОДЫ Эту систему можно решить и не преобразовывая ее в систе- му линейных уравнений с помощью соответствующей замены переменных. В результате будем иметь . б~*, 31г „7ЗЮ,*~ 4Ь ' ~ 4Ь ' ' з ), 4Ь ! Таким образом, исходная функция Яхм х.) достигает наименьшего значения точке х* Е гя с координатами Теорема 7.11. Функция Угх) ~~~ гггхгг х = (х1г хяг ° ° ° г хо) е 144 г 'г7 37) г=' где Нг > О, г = 1, п, рассматриваемая при ограничении о П," =А, г=-1 (7.38) А > О, у, > О, г = 1, и, достигает наименьшего значения рг, равного (7.39) В рассмотренном примере множество И'* содержало всего одну точку, которая и была искомой точкой максимума двойственной функции.
В общем случае это множество, определяемое линейными ограничениями, представляет собой аффинное многообразие, и задача определения наибольшего значения двойственной функции на этом множестве может оказаться сложной. Продемонстрируем использование неравенства взвешенных средних в одном частном случае, когда задача геометрического программирования имеет лишь одно ограничение типа равенства. Вопросы и задачи ~ Согласно неравенству взвешенных средних в форме (7.25)г примененному при Л, = уо имеем Неравенство взвешенных средних (7.25) превращается в равенство тогда и только тогда, когда попарно равны основания степеней под знаком произведения, т.е. когда равны величии,Л ны — '. При этом обе части равенства равны общему значению л' „л величин и .
В рассматриваемом случае неравенство превра- Л, щается в равенство, когда ~гРг Хг' г =р, 1 =1ги, "г'г откуда получаем "г'г р хг дг 1 = 1, и. Вопросы и задачи 7.1. Минимизируйте функцию 1'(хмхз) = х1 — хв при ограничении х~~+х~~ — — 1. Найдите стационарные точки и точки минимума.
Проанализируйте поведение функции, Лагранжа в окрестностях найденных точек. Классифицируйте найденные точки (точки минимума, максимума, седловые точки для функции Лагранжа по переменным х, Л). где 7 = 'у1 +'уз+... + уаг в единственной точке х* с координатами х,,* = — ' —. Ъ И Фт Е АНАЛИТИЧЕСКИЕ МЕТОДЫ 7.2. Решите задачу < (х1+ 1) + (х2 3) + п~Ж ,2,2 х, +х2 =1 и проверьте решение графически. 7.3. Решите задачу < (х1+1)2+(х2 — 3) -+шш х1+ 2х2 = 2 и проверьте решение графически. 7.4. Решите задачу < (х1+1)2+ (х2 — 3)2 — > ш1п; х1+ох2+ 11 < О и проверьте решение графически при значениях; а) сх = 1., 11 = О; б) о = -1, Р = 1; в) с2 = О, р' = О. 7.5.
Путем перехода к задаче геометрического программирования минимизируйте функцию Дх1,х2) = +6~/я+р. Х!Х2 8. ЧИСЛЕННЫЕ МЕТОДЫ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Известно достаточно много численных методов решения сформулированной в 7.1 общей задачи нелинейного программирования. Во многих из них использованы идеи, реализованные в численных методах безусловной минимизации (см. 4 6).
Главное отличие состоит в том, что при решении задачи нелинейного программирования необходимо учитывать ограничения, задающие допустимое мнозкество Й с Кв, на котором нужно найти точку х* Е Й минимума целевой функции ~о(х). В этой главе рассмотрены наиболее часто применяемые на практике численные методы решения такой задачи. 8.1.Метод условного градиента Для численного решения общей задачи нелинейного программирования ~в(х) — + шш, х Е Й С Б!", (8.1) где )в(х) — целевая функция, определенная на допуспшмом .множестве Й, можно применить модификацию одного из методов спуска.
Однако непосредственное использование методов спуска может привести к тому, что точка х, найденная па некоторой к-й итерации, .например, при помощи рекуррентных соотношений вида (4.20) или (4.36), выйдет за пределы допустимого множества,. т.е. х~ ф Й. Избежать этого в случае замкнутого ограниченного выпуклого множества Й и непрерывно дифференцируемой на нем выпуклой целевой функции можно следующим образом. 3. ЧИСЛЕННБ1Е МЕ ХОДЫ Пусть на й-й итерации известна точка х~ ~ б Й (на первой итерации (й = 1) выбрана начальная точка хо Е Й).
Используем главную линейную часть (8.2) приращения ~А=Хо(х) — Хо(х' ') =(дгабХо(х' '),х — х' ')+о(~х — х' '~) целевой функции Ях) в точке х~ ' для нахождения вспомога- тельного приближения хь из условия ~ь(х ) = гпш(8гас1 се(х ), х — х ). хео (8.3) (8гас1~о(х" '): х — хо) > > — ~8гас1Хо(х~ ')Йх — хо~ ) — ~8гас1Уо(х~ ')~Л и учитывая (8.2), находим Хь(х) = (8гас1~о(х" '),х — хо)+(8гас1,(о(хь '), хо — х~ 1) > > — /8тас1Хо(х~ ~)~й+(8гас1~о(х~ ~) хо — х ). Правая часть этого неравенства равна наименьшему возможному значению Ях) в искомой точке х~. Таким образом, имеем ~ (-ь) ( .8~ ( ь — с) -ь л-с) = — ~атаево(х' 'КЛ+ Ьгас1Ых" '),.хо — х' '), В силу замкнутости и ограниченности множества й и непрерывности линейной функции (ь(х) такая точка х всегда существует и лежит на границе дй этого множества (если таких точек несколько.
то можно выбрать любую из них). Для некоторых множеств, имеющих достаточно простую структуру, решение задачи (8.3) удается представить в явном виде. Например, если множество й является и-мерным замкнутым шаром радиуса Л с центром в точке хо е вС", т.е. Й = (х Е $~": ~х — ха~ < Л1, то, используя неравенство Коши--- Буняковского в виде 8.!.
Метод условного градиента или (8гас1Ув1хл '),х" — хв) = — ~бгас1Уо(х" ')~Л. Это равенство можно удовлетворить, если принять хя в В Кгас1 Уо1х ) ~8 ОЬ1*'-')~' В случае й = (1хс,...., х„) Е !и": и е [аз, Ьз], у = 1, и ) координаты точки х, которая расположена на границе дй и-мерного параллелепипеда й и в которой функция !8.2) се О) дБ*!х ) д =.! примет минимальное значение, равны д~в~х ) О д )~ хз Ь дуо(х' ') <О д -(сс1 *з !' = 1,п., 18.4) а при = 0 можно выбрать любое значение т. е ~сс., Ь ).
д~о1х" ') -ся) Если й = (х 6 ~3'."! сап х) < Ь„с'=1, т,) - многогранное множество, то !8.3) может быть сведено к решению основной задачи линейного программирования. Если же й=(хе!!с"!1ас,х) <Ь„1=1,т, Вх=сс), где В . - матрица размера 1 х и и с1 Е 1сФ, то для нахождения х" получим оба!у!о задачу линейного программирования. Для решения обеих этих задач после их приведения к стандартной задаче линейного программирования обычно используют сампле.нс-метод. Предположим, что задача !8.3) решена и точка х" найдена.
Если х" = хв с, т.е. ~я(х~) = О, то из !8.3) для любых х е й имеем (8гас1Яхв '), х — х" !) ) О. Тогда, согласно теореме 3.15, 34О 8. НИСЛЕННЫЕ МЕТОДЫ х~ 1 = х* — искомая точка минимума выпуклой функции Те(х) на множестве й, так что итерации прекращаем. В противном случае из (8.3) получаем ~ь(х~) = (8гадТв(х~ 1), х1 — х~ 1) ( О и полагаем х~ =х~ '+н1(х~ — х~ '), нь Е (О, Ц. (8.5) Ясно, что х~ Е й.
поскольку множество й выпукло. Таким образом, вспомогательное приближение х" на каждой й-й итерации задает вектор р" = х~ — х, определяющий на этой итерации допустимое направление. Оно является направлением спуска, в общем случае не совпадающим с направлением внтизрвдиенпт ю" = — 8гаоТе(хв 1) функции )е(х) в точке х~ ~ (рис. 8.1). Поэтому нахождение точки х~ путем выбора в (8.5) значения нь отличается от соответствующей итерации метода гридиентноео спуски. Это отличие послужило основанием для того, чтобы метод, связанный с решением задачи (8.3) и использованием (8.5), назвать методом условноео ерадиента.
Рис. 8.1 Определение 8.1. Допустимое направление, определяемое вектором рь, назовем возможным направлением спуска для функции ~е(х) из точки х~ 1 е й на множестве й С К", ЕСЛИ СущЕСтВуЕт таКОЕ ЧИСЛО ня ) О, ЧтО Хя 1+ Нря Е й Прн нЕ (О, нь) и выполнено неравенство 1е(х~ 1+нр") < 1е(х~ 1). 341 8.1. Метод условного градиента ( ) т ( й — 1+ й) й -й й — 1 (88) по аргументу к в полуинтервале (О, 1]. Для квадратичной целовой функции 7ейх), имеющей вид Ях) = — Ях, х) + (с, х), где Я положительно определен- 1 ная матрица порядка и, точка жй б (О, Ц минимума функции 1ой(к) единственна и может быть представлена в явном виде. Действительно, пусть рй возможное направление спуска.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
