Содержание к диссертации
Введение
Глава I. Особые точки модифицированных функций Лагранжа и их связь с задачей нелинейного программирования 12
1.1. Определения и вспомогательные результаты 12
1.2. Задача нахождения локального минимакса модифицированной функции Лагранжа 20
1.3. Задача нахождения локального максимина модифицированной функции Лагранжа 30
1.4. Задача нахождения седловой точки модифицированной функции Лагранжа 37
1.5. Задача нахождения локального минимума по ос. и (л. модифицированной функции Лагранжа 44
Глава 2. Численные методы решения задач нелинейного программирования, основанные на использовании модифицированных функций Лагранжа 49
2.1. Прямые методы модифицированной функции Лагранжа . 49
2.2. Метод простой итерации 58
2.3. Метод Ньютона 68
2.4. Двойственные методы модифицированной функции Лагранжа 72
Глава 3. Две версии метода линеаризации 83
3.1. Связь метода линеаризации с прямым методом модифицированной функции Лагранжа и методом точной штрафной функции 83
3.2. Некоторые свойства точной штрафной функции. 90
3.3. Вспомогательная задача первой версии метода линеаризации 94
3.4. Первая версия метода линеаризации 100
3.5. Вторая версия метода линеаризации 107
Глава 4. Библиотека программ нелинейного программирования диалоговой системы оптимизации ЛИСО 109
4.1. Вычислительные аспекты методов модифицированной функции Лагранжа и линеаризации 109
4.2. Характеристики методов библиотеки и некоторые рекомендации по их применению 133
Заключение 148
Литература 150
Приложение 159
- Определения и вспомогательные результаты
- Прямые методы модифицированной функции Лагранжа
- Связь метода линеаризации с прямым методом модифицированной функции Лагранжа и методом точной штрафной функции
- Вычислительные аспекты методов модифицированной функции Лагранжа и линеаризации
Введение к работе
Многие народнохозяйственные, естественнонаучные и инженерно-технические задачи носят оптимизационный характер и часто сводятся к задачам математического программирования. Методы оптимизации широко используются в прикладном системном анализе /см., например,С 1,23/. Многочисленные практические приложения способствуют бурному развитию вычислительных методов оптимизации. Опубликовано большое количество работ по методам математического программирования. Отметим хотя бы несколько монографий и учебников, вышедших за последние годы [ 3-25"].
Известно много различных численных методов нелинейного программирования. Не существует и, по-видимому, не будет существовать одного наилучшего во всех отношениях метода решения задач нелинейного программирования. Качество численного метода характеризуется многоми показателями. Свойства решаемых задач также обладают большим разнообразием. Отсутствие одного универсального численного метода приводит к необходимости создания человеко-машинных систем оптимизации, позволяющих выбирать подходящие методы для конкретной задачи и осуществлять управление процессом ее решения. При создании систем оптимизации важно иметь библиотеку программ, реализующих различные методы оптимизации, которые дополняли бы друг друга. В последнее время уделяется большое внимание созданию пакетов программ для решения задач оптимизации. Работы в этом направлении ведутся во многих организациях страны, например, в ИК АН УССР, ЦЭМИ, ВНИИСЙ, ИММ УНЦ АН СССР, Институте математики АН БССР, Институте технической кибернетики АН БССР и в других организациях. В ВЦ АН СССР продолжаются работы по дальнейшему развитию диалоговой системы оптимизации ДЇЇС0, которая предназначена для решения в диалоговом, автоматическом или пакетном режимах следующих задач: безусловной минимизации, нелинейного программирования, оптимального управления, решения систем нелинейных уравнений, глобальной оптимизации, многокритериальной оптимизации. Система ДИСО предназначена для БЭСМ-6, в настоящее время завершается ее переработка для ЭВМ типа СМ-4.
Библиотека программ методов нелинейного программирования в ДЙСО достаточно обширна, в нее вошли методы с различными свойствами, по возможности дополняющими друг друга и по-разному ведущими себя на различных этапах вычислительного процесса решения задачи. Разработке численных методов, которые обладают удачно дополняющими друг друга свойствами, для решения задач нелинейного программирования на основе применения различных модификаций функции Лагранжа, включению этих методов в диалоговую систему оптимизации дИСО и посвящена данная работа.
Классическая функция Лагранжа занимает важное место в нелинейном программировании. С ее помощью получаются необходимые и достаточные условия оптимальности, строятся многие вычислительные методы. Кроме того, функция Лагранжа и ряд связанных с ней понятий /множители Лагранжа, двойственная задача и т.д./ часто имеют содержательный смысл в терминах конкретной практической задачи, помогают более глубокому ее анализу.
В 1969 г. вышли работы М.Хестенса L ИЗ и М.Пауэлла Г2.Щ J , которые построили эффективный метод решения задачи нелинейного программирования, несколько изменив классическую функцию Лагранжа. Независимо от них аналогичные методы были предложены Ю.П.Сы-ровым и Ш.С.Чурквеидзе Г2 3Д и П.Хаархофом и Дж.Баесом [I 92 . Дальнейшее развитие это направление получило в работах А.Вержбиц-кого Clo] , А.Миеле Гз/J , Б.Т.Поляка и Н.В. Третьякова [ЪЪ, 14 ] , Е.Г.Голыптейна и Н.В.Третьякова І3] , р.Рокафеллара Сз , 3?J , Д.Бертсекаса LЗ %, 35J, Б.С.Раззгмихина I IS oJ, А.С.Антипина /-4 Г.Д.МайстровскогоГ /Л-С/и многих других авторов. Метод fZG, 2? J известен под названиями "метод множителей", "метод штрафных оценок", "метод сдвига ограничений", "метод модифицированной функции Лагранжа". Этот метод относится к двойственным методам. На внешних итерациях этого метода происходит пересчет по простым формулам множителей Лагранжа /двойственных переменных/, а на внутренних - решается задача минимизации модифицированной функции Лагранжа по прямым переменным исходной задачи нелинейного программирования.
На протяжении последних десяти лет появились работы, в ко торых вводились целые классы модифицированных функций Лагранжа. Ьто, например, работы К.Эрроу, Ф.Гоулда, C.Xoyf V&7 , Е.Г.Гольштейна и Н.В.Третьякова fV7, ki] , О.Мангасариана fV9J , Б.Корта и Д.Бертсекаса С °1 , а также Г$ "/-б J . Модифицированные Функции из этих классов обладают новыми полезными свойствами, отсутствующими у классической функции Лагранжа. Эти свойства могут быть использованы для получения новых условий оптимальности, новых численных методов, позволяют повысить эффективность некоторых существующих.
Как правило, все известные методы решения задачи нелинейного программирования основаны на редукции к какой-либо другой задаче или к последовательности некоторых задач. Такая редукция полезна, если эти новые вспомогательные задачи просты для численной реализации. С помощью классической функции Лагранжа исходная задача нелинейного программирования при некоторых предположениях сводится к задаче нахождения седловой точки, или к двойственной задаче /задаче на максимин/. Этой двойственной задаче присущи определенные недостатки, которые затрудняют применение некоторых численных методов нахождения максимина. Например, двойственная задача, как правило, бывает негладкой. Применение численных методов для решения прямой задачи /задачи на минимакс/, формулируемой с помощью классической функции Лагранжа, наталкивается на трудность, связанную с тем, что внутренняя задача имеет решением бесконечно большие значения множителей Лагранжа, если прямые переменные не удовлетворяют ограничениям исходной задачи нелинейного программирования. В работах, посвященных модифицированным функциям Лагранжа, центральное место обычно также отводится сед-ловой точке. При этом выявляется возможность улучшить свойства двойственной задачи, формулируемой с помощью модифицированной функции Лагранжа. Свойства прямой задачи , формулируемой с помощью модифицированной функции Лагранжа, обычно остаются такими же, как и. в случае использования классической функции Лагранжа. /см., например, I V?} ]/.
Развиваемый в данной работе подход основан на построении таких классов модифицированных функций Лагранжа, которые позволяют свести задачу нелинейного программирования к нахождению особой точки модифицированной функции Лагранжа. Особыми точками модифицированной функции Лагранжа могут быть точки безусловного локального минимакса, безусловного локального максимина, седловая точка, точка безусловного локального минимума по прямым переменным и множителям Лагранжа. Эта редукция задачи нелинейного программирования к нахождению особой точки модифицированной функции Лагранжа позволяет либо воспользоваться известными численными методами, например, методами нахождения безусловного локального минимакса, максимина, и т.д., либо, учитывая специфику модифициро - 8 ванной функции Лагранжа, предложить новые.
В § I.I вводятся некоторые определения и вспомогательные утверждения. В частности в работе широко используется простейшая модификация Функции Лагранжа, предложенная Ю.Г.Евтушенко ГS" Ч]. Ее основное отличие от классической функции Лагранжа в том, что множители Лагранжа при ограничениях типа неравенств возводятся в квадрат. В.Г.Іаданом в 1$$, ЭД были сформулированы достаточные условия второго порядка изолированного локального минимума в терминах этой функции. В дальнейшем изложении эти условия часто используются. Приводится связь между этими условиями и достаточными условиями второго порядка в форме Мак-Кормика Г Г Л .
В § 1.2 вводится важный класс модифицированных функций Лагранжа, который при определенных условиях позволяет свести исходную невыпуклую задачу нелинейного программирования в окрестности ее локального решения к задаче нахождения безусловного локального минимакса. Т.е. в этом случае в принципе возможно с помощью известных методов поиска безусловного локального минимакса находить решение исходной задачи нелинейного программирования. Заметим, что использование для этих целей классической функции Лагранжа или ранее предлагавшихся модификаций функции Лагранжа /например, ъ С № №]/ не"возможно, так как у такой прямой задачи на минимакс внутренняя задача на максимум по двойственным переменным имеет неограниченной решение при недопустимых значениях прямых переменных.
В § 1.3 с помощью введенной в предыдущем параграфе вспомогательной функции, но при другом аргументе, модифицируется Функция Лагранжа. Показано, что при определенных условиях невыпуклая задача нелинейного программирования в окрестности своего локального решения сводится к нахождению безусловного локального максимина такой модифицированной функции Лагранжа. Вводятся несколько более сложным образом модифицированные функции Лагранжа, позволяющие ослабить условия, при которых исходная задача сводится к задаче на безусловный локальный максимин.
В § 1.4 с помощью введенных ранее вспомогательных функций рассматриваются некоторые классы модифицированных функций Лагранжа, которые позволяют при определенных условиях свести задачу нелинейного программирования к нахождению седловой точки модифицированной функции Лагранжа. Для многих численных методов нахождения седловой точки требуется, чтобы матрица вторых производных по прямым переменным, вычисленная в седловой точке, была положительно определена," а матрица вторых производных по двойственным переменным, вычисленная в седловой точке, была отрицательно определена. Для введенных модификаций функции Лагранжа это полезное свойство выполняется.
В § 1.5 вводится класс модифицированных функций Лагранжа, который позволяет при определенных условиях свести исходную задачу нелинейного программирования в окрестности ее локального решения к задаче нахождения безусловного локального минимума по прямым и двойственным переменным.
Итак, введенные с помощью некоторых достаточно простых вспомогательных функций классы модифицированных функций Лагранжа позволяют при довольно естественных предположениях свести общую задачу нелинейного программирования в окрестности ее локального решения к задаче нахождения особой точки модифицированной функции Лагранжа. Свойства задачи нахождения особой точки /например, достаточная гладкость/ позволяют воспользоваться некоторыми известными численными методами или, используя специфику модифицирован - 10 ной функции Лагранжа, предложить более эффективные.
В первых трех параграфах главы 2 рассматриваются прямые методы модифицированной Функции Лагранжа, введенной в § 1.2. Это очень важный класс.методов. На внешних итерациях прямого метода производится пересчет прямых переменных по простым формулам, а на внутренних - решается задача максимизации модифицированной Функции Лагранжа по двойственным переменным. Т.е. специфика модифицированной Функции Лагранжа позволяет вместо применеия известных методов нахождения локального мищшакса предложить новые методы, состоящие, по-еути дела, в решении задачи безусловной максимизации по двойственным переменным и решении системы нелинейных уравнений в прямых переменных. Для решения системы рассмотрено применение метода простой итерации и метода Ньютона.
В § 2.4 рассмотрены двойственные методы с модифицированными функциями Лагранжа, введенными в предыдущей главе. Показано, что к этим модифицированным функциям целесообразно применять известные методы нахождения локального максимина. В этом параграфе приводится обзор некоторых двойственных методов из СЬ О . Двойственные методы "симметричны" прямым методам модифицированной Функции Лагранжа. В двойственных методах модифицированной Функции Лагранжа на внешних итерациях производится пересчет множителей Лагранжа по простым формулам, а на внутренних итерациях решается задача безусловной минимизации по прямым переменным модифицированной функции Лагранжа. й в прямом,и в двойственном методах основной объем вычислений приходится на решение внутренней задачи на безусловный экстремум. Но прямые методы требуют значитель но меньше обращений к вычислению функций, определяющих исходную задачу нелинейного программирования, чем двойственные.
Методы главы 2 являются локальными методами, т.е. сходятся из начальных точек, близких к решению. Вопршсу расширения области сходимости методов типа прямого метода модифицированной Функции Лагранжа посвящена третья глава. В этой главе предлагаются две версии метода линеаризации и рассматривается их связь с прямым методом модифицированной функции Лагранжа. В §§ 3.1, 3.2 приводятся некоторые вспомогательные сведения о негладких штрафных функциях. В § 3.3 формулируется и исследуется, вспомогательная задача линейного программирования, которая используется для нахождения направления спуска в первой версии метода линеаризации. В § 3.4 доказывается сходимость первой версии метода линеаризации, а в § 3.5 приводится вторая версия метода линеаризации. В предлагаемых версиях используется вспомогательная задача жнейного программирования. В этом их основное отличие от метода жнеаризации Б.Н.Пшеничного Г 5 3 , в котором вспомогательная задача - задача квадратичного программирования.
Глава 4 посвящена особенностям численной реализации прямого метода модифицированной функции Лагранжа и двух версий метода линеаризации, которые вошли в библиотеку численных методов ДЙСО. Приводятся некоторые результаты вычислительного эксперимента, . краткая сравнительная характеристика методов нелинейного программирования из библиотеки методов ДИСО и рекомендации по применению методов.
В приложении приводится пример практической задачи, успешно решеной с помощью прямого метода модифицированной функции Лагранжа системой ДИСО.
Определения и вспомогательные результаты
Будем рассматривать задачу нелинейного программирования следующего вида Здесь есть і -мерное евклидово пространство, функции -ffoc) и по меньшей мере дважды непрерывно дифференцируемы на Ък . Помимо общей задачи нелинейного программирования (i.l] будем рассматривать ее частные случаи: задачу с ограничениями типа равенств (Х-2) и задачу с ограничениями типа неравенств Предположим, что решение задач (І.і), (і.2), (і.3) существует. Множество решений любой из них обозначим через д В нелинейном программировании важную роль играет функция Лагранжа, которая для задачи (i.l) имеет вид где А е , Лс : О I zzi+I УК, есть вектор-столбец множителей Лагранжа; Qfx)- вектор-столбец с компонентами Qcfoc) І-\Г..}УУЬ Ч (О. 4} - скалярное произведение векторов си и І С помощью функции Лагранжа (1.4) формулируются необходимые и достаточные условия оптимальности для задачи (l.l). Обозначим через Х, ? множество точек "X , в которых выполнены необходимые условия первого порядка решения задачи (l.l), Здесь через 4 . обозначен градиент функции 4faO ; Q - матрица первых производных размера m хп. ; индекс т означает транспонирование. Условия (1.5) называются условиями Куна-Таккера. Точка -С 2 1 в которой выполнено (1.5) , называется точкой Куна-Таккера. Будем считать, что }{ не пусто и д Q X „ Введем индексные множества Определение. В точке [ }Л ]выполнено условие строгой дополняющей нежесткости, если AL 0 для всех і є- fa) . Определение. В точке Ос выполнено условие регулярности ограничений, если векторы градиенты Qc ("х ) , ( е-ЗСх% ) линейно независимы. В дальнейшем часто будут использоваться достаточные уело- вия второго порядка изолированного локального решения задачи (і.і) В точке ГХ С bj: точкаЗ Хуои для каждого ненулевого вектора Ч Ь такого, что причем 3х ), = » б е {с er )Ui )j » имеет место Здесь Cj . есть вектор-столбец градиента функции Qc fie) ; Z _,_ - матрица вторых производных по ос функции / х л ) размером к х п. . Если в точке[х выполнено условие строгой дополняющей нежесткости, то достаточные условия второго порядка изолированного локального решения задачи (І.і) в zc имеют следующий вид: точка осм "Х о , для каждого ненулевого вектора uef , удовлетворяющего условию имеет место В условиях (1.5) присутствует требование неотрицательности множителей Лагранжа, соответствующих ограничениям типа неравенств, т.е. л 1 о , С= С-+ \ уи. , что затрудняет применение некоторых численных методов для решения необходимых условий (1.5) Ю.Г.Евтушенко была предложена простейшая модификация функции Лагранжа, свободная от этого требования L Ь5"3 . Ниже она будет часто применяться. Итак, для задачи (і.і) введем функцию Лагранжа вида где U 6- tы , ft (и,) есть вектор-столбец с компонентами По сравнению с традиционной функцией Лагранжа (1.4) функция вида (i.IO) имеет преимущество, позволяющее не требовать неотрицательности двойственных переменных, соответствующих ограничениям типа неравенств. Для задачи (1.2) функция (ІЛО) переходит в обычную функцию Лагранжа
Прямые методы модифицированной функции Лагранжа
В предыдущей главе были введены некоторые классы модифицированных функций Лагранжа, которые позволяют при довольно естественных предположениях свести задачу нелинейного программирования в окрестности ее локального решения к задаче нахождения особой точки модифицированной функции Лагранжа. Такими задачами нахождения особой точки модифицированной функции Лагранжа являются: задача о безусловном локальном минимаксе /прямая задача/, задача о безусловном локальном максимине /двойственная задача/, задача нахождения безусловной локальной седловой точки, задача нахождения безусловного локального минимума по прямым переменным и множителям Лагранжа. Эти задачи могут быть проще исходной задачи нелинейного программирования. Их свойства /например, достаточная гладкость/ позволяют воспользоваться некоторыми известными численными методами нахождения максимина, седловой точки, методами безусловной минимизации или предложить новые. В первых параграфах данной главы основное внимание уделено численным методам решения общей задачи нелинейного программирования (I.I.IJ, основанным на ее редукции к следующей задаче нахождения безусловного локального минимакса модифицированной функции Лагранжа вида (1.2.4) Б теореме І.2.І показано, что при определенных условиях точка Куна-Таккера 2Y - L , Ь 1 где строгое локальное решение задачи (Ї.І.і), является при достаточно малых (Ґ строгим локальным решением минимаксной задачи (!!) Так как в предлагаемых методах к решается прямая задача fl.l) и при этом будет использоваться зависимость множителей Лагранжа от прямых переменных, то эти методы решения задачи нелинейного программирования по аналогии с известными двойственными методами /см.,например, \,Z ,1 } / были названы в і S" J прямыми методами модифицированной функции Лагранжа. В принципе для решения fl.l) можно применить численные методы нахождения локального минимакса, например, из I Ч гл.11, 61. Один из наиболее известных подходов к решению (I.I) состоит в нахождении Согласно теореме I.2.I, множество локальных минимумов задачи нелинейного программирования (і.І.Цпри определенных условиях принадлежит множеству локальных минимумов функции JI( X G ) ДЛЯ достаточно малых С О. Таким образом, Функция а[ , ) является точной штрафной функцией, аналогичной точной штрафной функции Р.Флетчера і ЬЧ Ы-1 Для отыскания локального решения задачи (І.2) мо&но в принципе использовать какой-либо метод безусловной минимизации. Например, метод градиентного спуска с постоянным шагом приводит к итеративному процессу Можно показать, что при выполнении условий теоремы І.2.І, существуют dM о и o(x d (d) такие, что для всех ? сґ , О ( CW метоЛ -3) локально сходится к о: со скоростью геометрической прогрессии. Но, к сожалению, в выражение для функции (Iforf) входят первые производные функций h) и gfa). Поэтому вычисление гра-диента Jl fa ) Функции п (?.,(?) требует знания уже вторых производных х( ) и Q X xC x) » что существенно ограничивает возможность использования метода .3). Таким образом, точные штрафные функции, как типаJl fa) ) , так и Флетчера, обладают одним и тем же серьезным недостатком: если в распоряжении имеются только первые производные Функций Vfr) и Я х) » т0 Для минимизации точной штрафной функции можно использовать только методы поиска без вычисления производных. Чтобы построить более эффективные процедуры минимизации точной штрафной функции /типа градиентных, квазиньютоновских/ требуется знание производных от // ) и 9 fa) до второго порядка включительно. Другой подход к решению задачи .1) состоит в использовании необходимых условий первого порядка локального минимакса, т.е. в нахождении стационарной точки функции /-/ (-х} -fa) . Для нахождения стационарной точки функции /-//be и fa) в принципе можно применить какой-либо метод решения систем нелинейных уравнений /см., например, I ЬЪ"] /к условиям стационарности
Связь метода линеаризации с прямым методом модифицированной функции Лагранжа и методом точной штрафной функции
Идея метода линеаризации достаточно проста. В некоторой точке зс — оск линеаризуются функции, определяющие задачу нелинейного программирования (i.I.l), и решается вспомогательная задача линейного программирования: Для того, чтобы исключить из линеаризованной задачи неограниченные решения, вводят некоторые дополнительные ограничения, например, где 3J , J-lj... Yi заданные величины, либо вместо (l.l) решают задачу квадратичного программирования: После решения вспомогательной задачи происходит переход к новой точке Направление спуска рк есть решение вспомогательной линеаризованной задачи, шаг о(у в различных версиях метода линеаризации находится своим определенным образом. .Различные версии метода линеаризации отличаются также видом дополнительного ограничения на р , способом выбора -jJ в задаче 1.1)-(1.2), либо правилом вычисления матрицы Ау в задаче (І.З). Во вспомогательные задачи могут входить все линеаризованные ограничения исходной задачи или часть из них, выбираемая по некоторому правилу. Одна из первых реализованных на ЭВМ версий, в которой использовалась вспомогательная задача (1.1)-(1.2), принадлежала Р.Гриффиту и Р.А.Стьюарду f 33 3 Однако эффективность их версии нельзя признать удовлетворительной [ 4 3. Это было подтверждено результатами вычислительного эксперимента, проведенного в ВЦ АН СССР. По числу обращений к вычислению -$fo) и С,(ос) и числу итераций при решении задачи нелинейного программирования эта версия значительно уступала методу линеаризации Б.Н.Пшеничного L Ъ2 . Тем не менее, на основе решения вспомогательной задачи линейного программирования Р.її.ФеДоренко построены достаточно эффективные алгоритмы метода линеаризации 1 , 2, Эффективность этих алгоритмов достигнута за счет весьма сложных правил назначения величин типа 3J в (і.2), ограничивающих величину направления спуска, правил перехода к новой точке для линеаризации функций исходной задачи и правил формирования ограничений в (l.l). Эти правила часто имеют эвристический характер, так что основу версии Р.іі.Федоренко составляет "имитация поведе- ния достаточно .опытного вычислителя, следящего за ходом процесса" В методе линеаризации Б.Н.Пшеничного і З в качестве вспомогательной решается задача квадратичного программирования , (і.з) при Ак = 1 ив (і.З) могут входить не все ун. ограничений. Эта версия достаточно глубоко изучена теоретически и имеются сведения о ее эффективном использовании на практике Г %]. Некоторые приемы, первоначально использование в этой версии, позже нашли применение в других методах оптимизации. Это, например, использование негладкой штрафной функции для расширения области сходимости L -?1 , использование правил формирования множества ограничений во вспомогательной задаче. В этой главе, следуя С Ч?; J, приводятся две другие версии метода линеаризации, близкие к методу Е Ч]. Основное отличие этих версий состоит в том, что в качестве вспомогательной решается задача линейного программирования вместо задачи квадратичного программирования. В предыдущей главе /параграф 2.2/ была показана связь между методом линеаризации L J и прямым методом модифицированной функции Лагранжа УСх-,и) )(2»2Л )9 когда U? -функция выбрана в виде У{1 і)-ті и решается задача нелинейного программирования ҐІ.І.2) с ограничениями типа равенств. При этом оказывается, что задача (2.2.19), решаемая на внутренних итерациях прямого метода модифицированной функции Лагранжа, является двойственной к вспомогательной задаче квадратичного программирования (2.2;20) в методе линеаризации f iT J» Известно, что метод линеаризации Сь ?Зможно рассматривать так же как некоторый специальный ме- ход минимизации точной недифференцируемой штрафной функции. С другой стороны, прямой метод (2.2.1) или (2.2.2J есть специальный метод нахождения безусловного локального минимакса модифицированной функции Лагранжа. Как связаны между собой задача нахождения безусловного локального минимакса модифицированной функции Лагранжа и задача нахождения точной штрафной функции? Прямая минимаксная задача, порождаемая обычной функцией Лагранжа L fa, ) п0 СУТИ дела, может рассматриваться как задача минимизации идеальной точной штрафной функции. Эта идеальная точная штрафная функция обращается ъ+оо при любой недопустимой точке ос / ос е JC/ и совпадает с -(-х) при допустимых ос / ос & ]С /. Непосредственно использовать для численного решения (i.I.l) прямую минимаксную задачу, порождаемую функцией Лагранжа / fe/J) не представляется возможным из-за неограниченности внутренней задачи при недопустимых точках х . Есть два способа преодоления этой трудности. Первый способ был рассмотрен в предыдущих главах. Он заключается в модификации функции Лагранжа с помощью добавления некоторой функции от частных производных по эс функции Лагранжа. В результате была получена модифицированная функция Лагранжа Н fx, }d) .
Вычислительные аспекты методов модифицированной функции Лагранжа и линеаризации
Алгоритмы некоторых рассмотренных в предыдущих главах методов вошли в диалоговую систему оптимизации ДИСО. Здесь обсудим особенности численной реализации этих методов, их достоинства и недостатки. Для решения общей задачи нелинейного программирования (Ї.І.І) из пря/мых методов модифицированной функции Лагранка в ДИСО вклю чен метод простой итерации вида (2.2.14 . В ДИСО этот метод по лучил название Сб. В методе Сб реализовано 3 версии. В первой версии используется модифицированная функция Лагранка И Ы; ) с -функцией вида [) tz/z в0 второй у - функция имеет вид i/a (-6)-= ia e ] ї - о. г-вь С і-І--6 г) 9 в третьей - ис- пользуются в f -функции три первых члена разложения в ряд Тейлора функции з (і ) = с U t . ОСНОВНБІМ достоинством прямых методов модифицированной функции Лагранка является сравнительная простота внутренней задачи максимизации 1-1( , , ) по и . Ее размерность определяется только числом ограничений в исходной задаче нелинейного программирования Iil.Ij. При решении внутренней задачи изменяются лишь двойственные переменные и , а прямые переменные х пересчиты-ваются только на внешних итерациях. Следовательно, только на внега- них итерациях приходится обращаться к вычислению функций 4-(-х) , Q f x) , определяющих задачу (i.I.l), и их градиентов. За К внешних итераций метода С6 требуется (т.- i)(t + () раз вычислить функции Л( ), 9е fa) і 6 = "/ ъ fa-n)K раз вычислить градиенты xfy}i $iMi с- ---у h/L Если Для вычисления градиента У (?) или Q fa) » С =\г..1ы используется конечно-разностная схема с шагом вперед, которая требует и. раз вычислить значения функции ffoc) или Q fa), I- .. УЪ) соответственно, то, как легко подсчитать, в методе Сб за к итераций будет выполнено (fa+i)(K(yi+t) +1) обращений к вычислению всех функций, определяющих задачу fl.I.I). При дифференцировании по конечно-разностной формуле с шагом вперед и назад общее число вычислений функций за К итераций составит (frt+/)fk(zu/)/) . Поэтому прямой метод модифицированной функции Лагранжа Сб целесообразно применять прежде всего для решения тех задач, вычисление - (-х) и fa)y которых требует существенных затрат машинного времени.! приложении приводится пример решения щкой задачи из области геофизики. Успешное решение этой практической задачи стало возможным только благодаря применению метода Сб. В і S3Сказывалось, что прямые методы модифицированной функции Лагранжа целесообразно применять для решения задач нелинейного программирования, у которых число переменных превышает число ограничений Ы . Двойственные методы модифицированной функции Лагранжа более эффективны для задач, у которых число ограничений УЬ. больше числа переменных А - . Однако, эту рекомендацию нельзя принимать совершенно однозначно. Так, с помощью системы ДИСО была решена практическая задача о выборе оптимальных параметров конструкции зерноуборочного комбайна. Задача имела только 4 ограни- чения при 16 переменных. Бремя ее решения на ЭВМ было гораздо меньше при применении двойственного метода,чем при прямом методе модифицированной функции Лаграюга, хотя последний и потребовал значительно меньше обращений к вычислению функций, определяющих задачу. Второй пример - тестовая задача, предложенная Р.П.Федо-ренко в I 5J под номером 22. В этой задаче только 2 переменные при 20 ограничениях. Прямой метод С6 гораздо эффективней решает эту задачу, чем двойственный метод модифицированной функции Лаг-ранка. Причины этих явлений примерно ясны. Число внешних итераций к 5 необходимых для получения решения с заданной точностью, определяется в основном априори нам не известными свойствами той системы нелинейных уравнений, к которой применяется метод простой итерации. Напомним, что в случае прямого метода модифицированной функции Лагранка эта система нелинейных уравнений в переменных ос имеет размер п х п, , а в случае двойственного метода - эта система в двойственных переменных имеет размер т т. К недостаткам прямых методов модифицированной функции Лагран-жа следует отнести локальный характер сходимости и проблему выбора коэффициента v Область сходимости зависит от многих факторов, в частности от вида функции #(-) Так довольно плохие результаты были по-лучены в экспериментах с Функцией (-6)-е — Ь . Хотя прямые методы работают и тогда, когда Функция (-б) строго выпукла только в окрестности нуля /например, _(-у) -(и -С /, для расширения области сходимости желательно, чтобы Ц?[-) была строго выпукла на всем пространстве F . В этом случае в точке а & Ji любой локальный максимум функции LI fa и t &") по U является одновременно и глобальным, поэтому безразлично, какой из них искать.
