автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Разработка и систематизация численных методов условной оптимизации

РОССИЙСКАЯ АКАДЕМИЯ НАУК ВЫЧИСЛИТЕЛЬНЫ! ЦЕНТР

На правах рукописи Хадвн Бйталий Григорьевич

РАЗРАБОТКА И СИСТЕМАТИЗАЦИЯ ЧИСЛЕНШ МЕТОДОВ УСЛОВНОЙ ОПТИДСАЩИ

05.13.16 - применение вычислительной техники, иатеыати-ческого моделирования и математических методов в научных исследованиях

Авторефэрет диссертации на соискание ученой степени доктора <1нзико-ма тематических наук

Москва 1992

Работа выполнена в Вычислительном центре РАН.

Официальные опонвнты: доктор физико-математических наук,

профессор Ф.П.ВАСИЛЬЕВ,

доктор физико-математических наук, профессор В.Г.КАРМАНОВ,

доктор технических наук, профессор А.И.ПРОПОИ.

Ведущая организация: Институт математики и механики УрО РАН

Защита состоится " * _ 1992 .года

/-Г-'' '

в /-? на заседании специализированного совета Д 002.32.06

при Вычислительном центре РАН по адресу:

117967, Москва, ул. Вавилова, 40.

С диссертацией можно ознакомиться в библиотеке Математи-сческого института им. В.А.Стеклова РАН.

Автореферат разослав

1992 года.

Ученый секретарь специализированного совета Д 002.32.06

кандидат фи.-мат. наук (^/(¡МЛ&^гуШЩ, С.М.Шввртжн

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Теория и методы математического программирования интенсивно развивались в течение последних нескольких десятилетий. Связано это главным образом с появлением большого количества прикладных оптимизационных задач в экономике, проектировании, исследовании операций, которые потребовали для своего решения разработки новых алгоритмов, обладающих улучшенными вычислительными свойствами. Было предложено огромное количество численных методов, основанных на разных предпосылках и имеющих неодинаковую эффективность. Поэтому вакное значение приобретает проведение сравнительного анализа алгоритмов, поиска их внутреннего единства и связи мевду собой.

Особенно актуальной проблема систематизации численных методов стала в последнее время в связи с созданием систем оптимизации. Возможность включения в такие системы только ограниченного количества методов, а также желательность сравнительно простого управления ими, потребовали разработки универсальных численных схем, охватывающих достаточно большую часть существующих алгоритмов. Использование для этой цели общих конструкций методов позволяет не только выявить ранее не известные связи между ними, но также предложить ноше методы и построить их обобщения для решение более сложных оптимизационных задач.

Следует отметить, что вопрос систематизации численных методов условной оптимизации крайне актуален и с точки зрения внутренней логики развития самой науки оптимизации. Важность этой проблемы подчеркивалась всегда. Во многих монографиях и статьях по численным методам нелинейного программирования, опубликованным у нас в стране и за рубежом, их авторы рассматривали методы с единой точки зрения, искали имеющиеся между ними связи. При этом стремление добиться наибольшей общности приводило их к новым фундаментальным результатам в теории экстремальных задач, значительно расширяли понимание структуры числе: шх алгоритмов.

Среди подходов, на которые опирается систематизация численных методов условной оптимизации, одним из наиболее важных

является принцип Лагранха. Согласно ему для освобовдения от ограничений задача условной оптимизации сводится к другой задаче, решение которой может быть осуществлено с помощью уже известных алгоритмов. Применение этого принципа в более широком смысле позволяет трактовать многие методы нелинейного программирования как процедуры минимизации специальным образом построенных для каждого метода вспомогательных функций, быть может, с одновременным решением систем уравнений. Такой общий взгляд на методы дает возможность описать с единых позиций большинство методов последовательной безусловной минимизации, а также ряд итеративных методов спуска градиентного и ньютоновского типа. Это существенно упрощает переход с метода на метод.в системах оптимизации, открывает возможность построения интеллектуальных оптимизационных систем с настройкой на решаемую задачу, значительно пополняет арсенал вычислительных средств для решения сложных оптимизационных задач.

Цель работы состоит в создании единой теории ыетодов нелинейного программирования и в их классификации на базе этой теории, а также в построении новых методов нелинейного програгаш-рования и в обобщении ряда существующих методов для решения многокритериальных задач условной оптимизации.

Научная новизна. Предложен достаточно общий подход к построению численных методов нелинейного программирования. Данный подход позволяет в рамках единой конструкции охватить как многие известные численные методы, так и предложить ряд новых методов. Введено понятие вспомогательной функции метода и выявлены условия, при которых эта функция является точной, т.е. решение задачи нелинейного программирования сводится к ее однократной безусловной минимизации.

В тех случаях, когда вспомогательная функция не является точной, построены общие численные схемы отыскания их особых точек, приводящие к итеративным процессам, характерным для юогих известных численных методов последовательной безусловной минимизации и методов спуска. Для методов последовательной безусловной минимизации приводятся оценки близости решений вспомогательных задач к решению исходной задачи нелинейного програжи-

рования.

Предложен ряд новых методов решения задач нелинейного программирования, в том числе нетрадиционные методы параметризации целевой функции, барьерно-проективные методы, прямые и двойственные методы модифицированной функции Лагаранжа. Развитый в работе подход к построению численых методов нелинейного программирования распространен на решение задач условной многокритериальной оптимизации. Рассмотрены обобщения таких известных методов нелинейного программирования, как двойственный метод модифицированной функции Лагранжа, метод параметризации целевой функции, метод штрафных функций.

Теоретическая и практическая ценность. Теоретическая значимость диссертационной работы заключается в разработке общей методологии построения численных методов условной оптимизации. Предложенные на ее основе новые методы являются существенным вкладом в теорию условно-зкстремальных задач. Проведена классификация методов, показывающая единство многих численных методов нелинейного программирования. Разработан принцип, согласно которому методы нелинейного программирования стандартным образом переносятся на решение задач условной многокритериальной оптимизации, что открывает возможность создания унифицированных численных методов, предназначенных для решения задач как с одним, так и с несколькими критериями.

Предложенные в работе методы вошли в библиотеки программ различных версий диалоговой системы оптимизации ДИСО, внедренной во многие научные и проектные организации страны. Развитый в работе подход к классификации численных методов условной оптимизации положен в основу построения системы ДИСО/ПК-НЛП, предназначенной для решения задач нелинейного программирования на персональных компьютерах.

Алпробация работы. Результаты диссертации докладывались на республиканских, всесоюзных и международных конференциях, симпозиумах и школах-семинарах: Всесоюзный научно-технический семинар " Численные методы нелинейного программирования" (Харьков, 1979), Всесоюзный симпозиум " Системы программного обеспечения решения задач оптимального планирования" ( Пущино, 1980;

Нарва, 1982; Минск, 1986; Кострома, 1990 ), Научно-техническая конференция "Методы математического программирования и программное обеспечение" (Свердловск, 1984, 1967, 1989, 1991), Всесоюзная школа-семинар по оптимизации и ее приложениям в вкономике (Ашхабад, 1984; Душанбе, 1986), Всесоюзная научно-техническая конференция "Проблемы создания, опыт разработки, внедрение автоматизированных систем управления в нефтяной и газовой промышленности" (Сумгаит, 1990), Международная конференция " Многокритериальные задачи математического программирования (Ялта, 1988); Международная школа-семинар "Метода оптимизации и их приложения" (Иркутск, 1989); Меадународная конференция "Системы моделирования и оптимизация" (Лейпциг, 1989; Цюрих, 1991), III Советско-американский семинар "Оптимизация больших систем" (Москва, 1990), Международный симпозиум то математическому программированию (Амстердам, 1991).

Структура и объем работы. Диссертация состоит из введения, пяти глав, списка литературы и приложения. Общий объем диссертации - 281 страница.

Публикации. По теме диссертации опубликованы 30 работ, основные результаты отражены в приведенном списке литературы.

Во введении дается обоснование актуальности темы исследования, кратко формулируются те идеи, которые лежат в основе построения и систематизации численных методов условной оптимизации, приводится обзор полученных результатов.

В главе 1 вводятся исходные понятия и развивается обший подход к построению и классификации численных методов нелинейного программирования. В ней собраны также все необходимые для дальнейшего вспомогательные сведения и утверждения. В частности, сформулирован ряд условий оптимальности "нулевого порядка" без привлечения производных функций, входящих в постановку задачи.

Основной задачей, рассматриваемой в работе, является задача нелинейного программирования (НЛП) следующего вида: найти

СОДЕРЖАНИЕ РАБОТЫ

где f(x) и g(x) - непрерывные функции, отображающие n-мерно а евклидово пространство Е" в соответственно Е1 и Е™. Множество решений задачи (1) обозначается X .

В § 1 развивается общая концепция построения численных методов решения задачи (1). Показывается, что многие методы являются либо процедурами минимизации некоторой вспомогательной функции, либо процедурами ее минимизации в сочетании с решением систем уравнений.

Пусть Р произвольное замкнутое множество из Б11, содержащее XВводится вспомогательная функция Н(х,у), зависящая от исходных переменных г и от дополнительных параметров у. Эти дополнительные параметры для разных функций И(х,у) могут иметь разный смысл и, следовательно, обладать разной размерностью. Задаче (1) ставится в соответствие задача

min М(х,у), \2)

хер

ее решением является точечно-множественное отображение Х(у).

Среди всех функций М(х,у) выделяются функции двух основных типов - точные вспомогательные функции (ТВФ) и приближенные вспомогательные функции (ПВФ). функция М(х,у) называется ТВФ на множестве Р«У, если Х{у)=Х^ для всех уеУ. Со своэй стороны, функция И(х,у) называется ПВФ на Р*У, если отображение Х(у) строгое в У, и кроме того, можно указать такое множество У^еоЗУ, что для любой последовательностью сходящейся к Уж, множе-

ство прикосновения последовательности Х(ук) принадлежит Х^. В работе рассматриваются только такие ПВФ, для которых множество Yt выявляется в ходе решения некоторых систем уравнений. С этой целью вводится дополнительная вектор-функция G(x,y), подбираемая в каадом конкретном случае по функции М(х,у). Вместо (1) решается совместная задача

хеХ(у), G{x,y) = 0. (3)

Для решения этой задачи могут быть применены разнообразные численные методы отыскания решений систем уравнений в сочетании с методами безусловной минимизации. В работе рассматриваются два подхода к построению таких методов. Первый подход основан на использовании зависимости х(у), получащейся из решения за-

дачи (2). Подставляя ее в (3), приходим к следующему уравнению

С(х(у),у) = 0. (4)

Использование для решения (4) метода простой итерации и метода Ньютона приводит к следующим численным схемам

= Уь + осц,.«»). (5)

Уъ+гУъ-Ы^^'^]'0^*'^- (6)

где а>0 - некоторый коэффициент.

Методы вида (5),(б) называются непрялыли методами решения задачи (1), так как основные "внешние" итерации в них проводятся по дополнительным параметрам у. В отличие от них методы, ис-пользуицие обратную зависимость у{х), получающуюся из решения уравнения ах,у)= 0, называются тгрямши. Эту зависимость можно подставить в функцию М(х,у) и искать минимум результирующей функции Ы{х,у(х)) по х. Возможен также несколько иной подход, основанный на использовании необходимых условий экстремума для задачи (2). Если множество Р совпадает со всем пространством и функция Ы(х,у) дифференцируема по х, то необходимо, чтобы

Ма(х,у) = О. (7)

После подстановки зависимости у(х) в это условие получаем уравнение Ых(х,у{х) )=0, решая которое методом простой итерации, приходим к итеративному процессу

В последующих параграфах этой главы разрабатываются средства для построения вспомогательных функций в методах обоих типов и обсувдаются особенности применения прямых методов в том случае, когда множество Р отлично от всего пространства Б".

Все вспомогательные функции строятся по определенным правилам с привлечением специальных свертывающх функций. (СФ), определения которых даются в § 2Пусть Б* и Е^ - неположительный и неотрицательный ортанты Б1; Б1 - прямая Б1, пополненная элементами {+<»} и {-оо}, ссб! Непрерывная функция С}(г), для которой выполнено одно из следующих трех условий:

а) Q(z^)<c, Q(z2)=c, z1 çintZ., > z2eZ2,

б) 0(2^=0, Q(zs)>c, z^tZ,. 22€lntZ2,

c) Q(z1)<c, Q(zz)>c, z^çintZ,, z2çintZz,

где ^ , Zz=E*, называется соответственно внутренней, внешней или смешанной СФ. Если множество Zz в этих условиях совпадает с El\intE*, то Q(z) называется, соответственно, строго внутренней, строго внешней или строго сляеиюшой СФ. В том случае, когда -oo<Q(0)<+«>, функция Q(z) называется собственной СФ, в противном случав - несобственной. Для простоты считается, что Q(0)=0 у всех собственных СФ. Неубывающая на Е1 СФ называется монотонной свертывающей функцией (МСФ).

Достаточно большое количество примеров МСФ, причем разных типов, может быть построено с применением гельдеровских норм и их обобщений. Положим при p?i0, и t^O:

= [S |zi|P]!/P a (i)=q-1tq

p t=i 4

и доопределим эти семейства функций в специальных случаях

lZlo=y/^(ri |24|]1/\ |Z|+ra= шах \г1\, |Z|^,= min \zl\, о (i) = In t + 0.5.

о

При этом считается, что функция |z|p равна нулю, если р<0 и хотя бы одна координата вектора z обращается в ноль, а также, что aq(t)=-<», если q^O и t=0. Тогда следующие три набора функций

Qlext)(z) = а (¡z I -<ххдХ+<х>, -co<q<+co,

Р • Ч Ч т р

g(int) (z) = _о (|Z I ) —оо^р^+оо, -co<S<+«>, (9)

Г.S в " — "f"

= <v«z+iP> -°в<к1г>.

где г|=гаах[0,г4], z^minfO.z*], являются соответственно внешними, внутренними и смешанными МСФ, причем при р>0, q>0, г$0, а>0 - собственными строгими МСФ. В частном случае, когда p=q=r=a=1, последняя функция переходит в линейную функцию. При р=», г=-» и q=s=1 она образует функцию максимума.

В работе наряду со СФ используются их сопряженные и поляр- ныв функции, определяемые соотношениями

Я*(г ¡г) = вир Кг,г > -

= агевир вир Кг,г >-ц£2(г)1. ° цеН(2о) гея °

Здесь М(го)={ц: <г,го> $ V Функция £Г(г|2) является

неубывающей функцией множеств. Если функция в (г) неотрицательна на Ег, то функция 0°(г|2) также обладает этим свойством.

Во многих методах вспомогательная функция может быть представлена в виде

Щх.у) = Н(/(х)-у,В(в(х))), (10)

где Н и В - произвольные ОФ. С помощью этой функции в § 3 получены простейшие достаточные условия оптимальности "нулевого" порядка. Эти условия естественно зависят от типа свертывающих функций Н и В, однако, как правило, они состоят из оптимизационной задачи и условий типа равенства, т.е. имеют вид (3). Это позволяет использовать данные условия при обосновании правомерности применения конкретной функции И(х,у) в качестве ПВФ.

Если множество Р входит в постановку задачи НЛП в качестве дополнительного ограничения, то непосредственное использование процесса (8) для ее решения невозможно из-за изменения условия (Т), которое в данном случае принимает вид

11х(х,у) е Г(аг|Р), (11)

где й*(,г|Р) - конус двойственный к конусу возможных направлений относительно множества Р в точке х. В § 4 обсуадаются два способа, применяемых в таких случаях к учету множества простой структуры.

Первый способ основан на использовании штрафных функций. Пусть Q(z) - гладкая выпуклая кофинитная функция, достигающая своего минимума на равного нулю, в начале координат. Тогда множество минимумов выпуклой функции

1Г(р,д|Р) = «*(р|Ч-Р) (12)

по первому аргументу совпадает с Я*(д|Р). в том случае, когда

функция ?Г(р,д|Р) дифференцируема по р, условие (11) будет выполняться, если (7Га)р(»г(:г,у),:г|Р) = О, где (Иа) - произведение справа функции № на константу а>0. Подставляя сюда зависимость у (г) и применяя для решения получившегося уравнения метод простой итерации, получаем вместо (8) следующий итеративный процесс:

= - (13)

Заметим, что если вместо (12) рассмотреть функцию

7(р,д|Р) = <Г(р|Р-д), (14)

то она достигает своего минимума по Р в точках полярного конуса Я°(д|Р), являщегося обратным к конусу Я*(д|Р).

Второй способ учета дополнительных ограничений основан на использовании сюръективных отображений. Он применялся в работах В.С.Михалевича, Н.Н.Редковского и А.Е.Перекатова. Согласно этому способу вводится новое пространство, имеющее ту же размерность, что и исходное пространство, и на нем определяется непрерывно-дифференцируемое отображение, переводящее все пространство в множество Р или, по крайней мере, в его внутренность. Применяя теперь в новом пространство к преобразованной задаче НЛП известные прямые методы, можно после перехода назад в старое пространство получить численные методы, учитывающие присутствие в задаче множества Р. В работе данный подход используется в § 16 для построения барьерно-проективных методов типа метода Кармаркара.

В § 5 рассматривается задача обобщенного нелинейного программирования (ОНЛП), в которой /(х) является г-мерной вектор-функцией, а для определения допустимого множества X и множества оптимальных решений используются соответственно рефлексивные бинарные отношения Я^ и Я^, т.е.

Х={г€гп: ОЯ^х)}, Хф=Хф(Я/)={г#е1: /(х)Я//(х<) Ухе*}.

Задачи такого вида ставились и исследовались Д.Б.Юдиным.

Для задачи ОНЛП получены условия оптимальности, которые являются по существу распространением на случай произвольных бинарных отношений условий оптимальности, полученных в § 3 для задачи (1). Вспомогательная функция теперь составляется в виде:

М(х,у) = НЩ/(х)-у),В{в(х))), (15)

где А, В и Н - произвольные МСФ. При выводе условий требуется, чтобы функции В и А были согласованы в определенном смысле соответственно с отношениями и с отношением й^, двойственным к й^. Под этим, как правило, понимается совпадение нижних сечений этих отношений с лебеговскими множествами функций В и А или их включение.

Важным частным случаем задачи ОНЛП является задача многокритериальной оптимизации (МКО), в которой отношением й^ является отношение Парето, а - отношение, двойственное к слабому отношению Парето. Таким образом, в этой задаче допустимое множество X то К9, что и в задаче (1), а множество оптимальных решений определяется как

X = (х а: тах 1/*(х)~/1{х * * * *

Для задачи МКО с помощью функции Лагранжа

Иг) = <и,/(х)-у> + <и,в(аг)>, (16)

где z=lx,u,vty'l, у&Г, и - вектор, принадлежащий симплек-

г .

су 5г={иейТ: 2 и =1}, сформулирован ряд условий оптимальности.

4 = 1

От известных условий Ю.Б.Гермейера и Да Канха-Полака они отличаются только тем, что в них имеется дополнительное требование, заключающее в том, чтобы в точке г^, соответствующей оптимальной точке хл, функция Иг) обращалась в ноль.

Вторая глава диссертации посвящена исследованию ТВФ. В настоящее время среди ТВФ наиболее хорошо изучены точные штрафные функции, предложенные И.И.Ереминым и У.Зангвиллом. В работе показано, что и среди других классов методов найдутся соответствующие им вспомогательные функции М(х,у), которые при определенных обстоятельствах становятся точными. При выводе условий, обеспечивающих точность вспомогательной функции М(х,у), везде предполагается, что у функции Лагранжа

Их.и) = /(х)+<и,£(.г)>, (17)

составленной для задачи (1), существует седловая точка [;г ,у ] на множестве

Сначала в § 6 рассматривается случай, когда вспомогательная функция Mix,у) имеет следующий аддитивный вид

Mix,у) = A(f(x),y) + B(g(x)), ' (18)

где B(g) - некоторая собственная СФ, A(f,y) - произвольная непрерывная функция двух аргументов, неубывающая по первому из них.

Теорема 6.1. Пусть функция B(g) является строго внешней собстственной СФ и 0<£°(у#|^)<+оо. Пусть, кроме того, функция A(f,y) удовлетворяет условию

Alf,y)-Alf^,y) > [(/-/+)/5°(yJ^)]_ Vye7, V/^. (19)

Тогда задаваемая (18) функция Mix,у) является ТВФ для задачи (1) на множестве P*Y.

Используя утверждение этой теоремы, можно оценить область значений параметра у, при которых происходит совпадение решения задачи минимизации (2) и решения исходной задачи НЛП (1). Особенно просто эти оценки получаются в случае, когда A(f,y) является выпуклой функцией по /.

Утверждение теоремы 6.1 сохраняется и в случае, когда Big) является внутренней СФ, однако при этом требуется, чтобы В=Х и вместо (19) выполнялось неравенство

Alf,у) - А(/ф,у) > (/-/,)/B°(vJ£?) Vy€y. V/>/..

В § Т рассматривается вспомогательная функция более сложного неаддитивного вида

*(т,у) = H(A(f{x),y),B(g{x))), (20)

где Я - собственная МСФ. Использование таких функций Mix,у) позволяет значительно расширить класс возможных ТВФ.

Теорема 7.1. Пусть выполнены предположения теоремы 6.1 и пусть A(f,у) является выпуклой монотонно возрастающей функцией первого аргумента, причем

О < вир вир ^ С < -к», yZY UdAfif^.V)

тогда если найдется такое множество №В1, что A(ft,у)еГ для любых уеУ и

ff(i,(t,-i)+/(Cß°(üjEm))) > Я(^,0) П^Т, Vitt,,

(

то функция (20) - ТВФ для задачи (1) на множестве Р«У.

Особенно просто условия этой теоремы проверяются для квазивыпуклых функций Н и для функций А{/,у), имеющих вид A(f,y)= —f—y или ЖЛУ)=У~1Л Получены также соответствующие условия для случая, когда B{g) является внутренней собственной СФ или строго смешанной СФ. Построены примеры аддитивных и неаддитивных ТВФ с применением СФ из наборов функций (9).

Так как точная штрафная функция

М(х,у) = + B(g(x)) (21)

является частным случаем вспомогательной функции (17), то утверждение теоремы 6.1 и следующие из нее оценки остаются справедливыми и для нее. Однако для этой функции, благодаря ее простому виду, можно получить и более тойкие оценки, причем не требуя наличия у функции Лагранжа седловой точки. В § 8 для случая, когда B(g) является выпуклой СФ, показано, что если в точке xt выполнены достаточные условия второго порядка изолированного локального минимума в задаче (1), то штрафная функция будет оставаться точной в некоторой окрестности хф. Получены оценки сверху и снизу для штрафного коэффициента у.

В § 9 рассматривается другой класс ТВФ, которые отличаются от предложенных раннее функций только тем, что в них вместо минимизируемой функции /(г) используется функция Лагранжа L(x,v). Впервые функция такого вида была рассмотрена В.Д. Скариным, им была предложена соответствующая модификация точной штрафной функции. В работе исследуются более общие аддитивные и неадци-тивные ТВФ следующего вида

Ы(х,у) = A(L(x,v),w) + B(g(x)), (22)

М(х,у) = fi(A(L(x,v),w) ,B(g(x))).

В этих функциях вектор дополнительных параметров у включает в себя как коэффициент w, так и вектор двойственных переменных и. Получены общие условия, при которых функции (22) являются точными и построены примеры функций, удовлетворяющие этим условиям. По смыслу эти условия аналогичны утверждениям теорем 6.1 и '7.1.

В третьей главе рассматриваются непрямые методы решения задач НЛП, которые являются по существу методами последователь-

ной безусловной минимизации. Эти методы базируются на использовании вспомогательной функции (10) или ее обобщений, когда свертывающие функции Ни В зависят от своих собственных дополнительных параметров, включаемых в этом случае в вектор у. Разные типы СФ (внутренние, внешние или смешанные) в различных сочетаниях приводят к разнообразным вспомогательным функциям с отличающимися друг от друга свойствами. Показывается, что если множество Р компактно, то функция (10) при определенных комбинациях функций Я и В является ПВФ для задачи (1). При выводе этих условий, особенно в случае, когда Р^Х, считается, что допустимое множество в задаче (1) удовлетворяет условию регулярности, т.е. множество X ={хе^1 g(x)<0} не пусто и его замыкание совпадает с X.

Сначала в § 10 рассматриваются методы штрафных функций. В этих методах в качестве функции Н используется линейная СФ, а в качестве В - зависящая от положительного коэффициента функция где В - внутренняя, внешняя или смешанная СФ. В силу линейности функции Н параметр у в (10) можно опустить, поскольку он не влият на решение оптимизационных задач (2), а его роль переходит к коэффициенту р. В результате получаем штрафную функцию (21).

Теорема 10.1. Пусть функция В является собственной строго внешней или внутренней СФ (в последнем случае дополнительно предполагается, что РсХ). Тогда функция (21) - ПВФ для задачи (1) на множестве Р«У, где У={уе£1: у>0>. Если функция В является несобственной внутренней СФ, то функция (21) будет ПВФ на множестве где У={уеЕ1: 0<у<с), с - произвольная положи-

тельная константа.

Если функция Н отлична от линейной, то мы приходим к вспомогательным функциям, используемым в методах параметризации целевой функции (называемых также методами центров, методами нагруженного функционала). В § 11 рассматривается случай, когда обе входящие в вспомогательную функцию 11 (ос,у) свертывающие функции Н и В являются функциями одного типа - либо обе внешние, либо обе внутренние. В первом случае получаются методы внешних центров, во втором - методы внутренних центров. Приводятся

также условия, при которых функция (10) является ПВФ.

Теорема 11.1. Пусть функции Я и В являются собственными строго внешними СФ, причем функция Н - МСФ. Тогда вспомогательная функция (1G) - ПВФ для задачи (1) на множестве Р*У, где У= ={уеЕ1: у^}. Если функция Н является строго внутренней СФ, а функция В - собственной внутренней СФ, то функция (10) - ПВФ для задачи (1) на множестве X*Y, где У={уеЕ1: у>/^>.

Особый интерес представляет использование в вспомогательной функции (10) СФ разных типов - внутренних в качестве Н и внешних в качестве В или наоборот. Этот случай рассматривается в § 12, где предлагаются два новых нетрадиционных метода параметризации целевой функции. Выясняются также условия, при которых комбинации СФ разных типов дают ПВФ. При этом требуется, чтобы вспомогательная функция Jf(x,y) получалась такой, что

*Ц,'Л)=0 люб01*0 t-X-, ■

Теорема 12.1. Пусть функция Н является собственной внешней МСФ, а функция В - несобственной внутренней положительной СФ. Тогда функция (10)) - ПВФ для задачи (1) на множестве X*Y, где

Теорема 12.4. Пусть функция Н является несобственной строго внутренней положительной МСФ, а функция В - несобственной строго внешней отрицательной СФ. Тогда функция (10)_- ПВФ для задачи (1) на множестве X*Y, где 7={уеЕ1: fQj^f^ >. f - произвольное число из интервала ). /<t=min{/(x): хеРЬ

Согласно утверждениям данных теорем следующие три функции, Построенные с помощью МСФ из наборов (9),

Ш{х,у) = (/(x)-y)/[1 + (/(x)-y)+|-g(x)|rl, (23)

U(x,y) = (/(x)-y)2 / |-g(x)ir , (24)

*(*,У) = |g+<*)|p / <У-/(*»+. (25)

при гф и рЯ являются ПВФ. Функции (23) и (24) удовлетворяют условиям теоремы 12.1, функция (25) - условиям теоремы 12.4.

Используя вспомогательную функцию (23) и схему пересчета оценок (5) с G=Jf, получаем следующий метод решения задачи (1)

xk е Arg min 1(Пх)-ук)+/1: + (Г(х)-ук)+ |-g(x)|r]), (26)

Если (1) есть задача выпуклого программирования, то с помощью вспомогательных функций (24) и (25) на основе схемы (б) можно построить два других непрямых метода решения (1):

т18€АГвтШ{(/(х)-1/Л)2/|-б(х)|г}, Уы-Уъ+Шх )-у )/г, (27)

хЛ€Агвт1п{I8+(х)/(Ук-/(х))+}, ук+1= 2уь- /СТА). (28)

Здесь в первом случае во втором - множество Р

предполагается выпуклым. Доказывается сходимость всех трех процессов (26)-(28) к решению задачи (1).

Применение в (10) линейных функций в качестве Ни В приводит к функции Лагранжа (17). Роль дополнительных параметров у в этом случае играют двойственные переменные и. Непрямые методы, основанные на использовании функции Лагранжа и ее модификаций, рассматриваются в § 13. Они предназначены для решения, задачи (1), в которой допустимое множество определяется ограничениями типа равенства и неравенства

X = £*(х)=0, ^(хХО, 1+1 (29)

Для этой задачи Ю.Г.Евтушенко была предложена функция Лагранжа, являющаяся простейшим обобщением классической функции (17),

Х(х,у) = /(х) +• <А.(и),в(х)>, (30)

где А.(у) - вектор-функция с компонентами А.'(и)=и{,

(и)=£(и1), £(1) - сильно вогнутая дважды непрерывно дифференцируемая функция на Е1, достигающая своего минимума на Е1, равного нулю, при t=0 . С помощью функции (30) достаточные условия изолированного локального минимума второго порядка записываются в довольно симметричном виде, а именно, Jpeбyeтcя, чтобы точка [х^.гМ была стационарной точкой функции £(х,и) и

<у,Ьхх(.хф,иф)у> > О, <г,Ъь„(хт,и^)г> < 0 (31)

для любых ненулевых уеЕ", г^Ё*, таких, что = О,

А. (у )г = О.

и « '

Введем функцию

У(Р) = ЕФ(Р'). (32)

{=1

где ) - дважды непрерыно дифференцируемая функция, удовлетворяющая^ условиям (0)=0, фtt(0)>0. С помощью функции (32) функция Ъ(х,ь) модифицируется следующим способом

Ы(х,у,б) = Ъ(х,V) + о У(2 (г,и)), о>0. (33)

Таким образом, здесь к функции Лагранжа добавляется член, "штрафующий" за невыполнение условия допустимости для ограничений типа равенства и условия дополняющей нежесткости для ограничений типа неравенства.

Минимизируя функцию М(х,и,о) по х, получаем зависимость х(ь,а), которая после ее подстановки в условие й(х,и)= =Ур(1и(х,и))=0, приводит к уравнению Ур(Ъи(х(и,о),и))=0. Если применить для его решения метод простой итерации и метод Ньютона, то получаем следующие итеративные процессы:

+ (34)

= - Л'1 (^,0)7^2^^)). (35)

где хъ=х(и. ,о), А=&7 (Ъ (х(у,о),у) )/(Зу, а>0 - некоторый шаг.

/9 Л р V

Доказывается, что если в точке [х^,уг] выполнены достаточные условия второго порядка (31), то существуют такие о>0, а(о), что для всех о>о и 0<а<а(о) процесс (34) локально сходится к у# со скоростью геометрической прогрессии. Процесс (35) сходится к иш с квадратичной скоростью.

Глава IV посвящена прямым методам решения задач НЛП. Основное внимание здесь уделяется методам, построенным на применении функции Лагранжа и ее модификаций. Для этих функций зависимость у (г) сводится к зависимости v(x) двойственных переменных от прямых, которая, как правило, существует и легко определяется.

Сначала в § 14 рассматриваются методы решения общей задачи НЛП (1), (29), в которой используется модифицированная функция Лагранжа (МФЛ), симметричная в некотором смысле к функции (33),

/V л»

Н(х,и,1) = 1(х,и) - т 7(Бт(х,и))ш 1>0.

Если в стационарной точке ^„.и,] выполнено правое нера-

венство (31) и градиенты активных ограничений линейно независимы, то для любого т>0 существует изолированное локальное решение v(x,i) задачи максимизации

max M(x,V,l), v£Em

такое, что v(xt ,ч)=иф. После подстановки этой зависимости в условие Vp(Lx(x,v))=0 приходим к уравнению Vp(Lx(x,v(x,i))) = 0. Применяя для его решения метод простой итерации и метод Ньютона, получаем итеративные процессы

= - aVVW*' = (36>

1 ~

= ** - г ^У V**'<3T>

где r(x)=d7 (L (x,v(x,t)))/dx. Если в задаче (1), (29) выголне-

р X

ны достаточные условия второго порядка (31), то метод (36) локально сходится к xt со скоростью геометрической прогрессии, метод (37) локально сходится к х^ с квадратичной скоростью.

Метод (36) в частном случае, когда в качестве cp(t) используется функция cp(t)=i2/2, изучался А.С.Антипиным. Он тесно связан с методом проекции градиента, а именно, если в задаче (1), (29) имеются только ограничения типа равенства, причем линейные, то вырабатываемое им направление совпадает с проекцией антиградиента целевой функции /(¿г) на допустимое множество. В § 15 рассматривается задача выпуклого программирования

min f(x), т£ХПР

где множество X определяется так же, как и в задаче (1), Р -выпуклое замкнутое множество, f(x) и gl(х), - выпуклые

функции. Для этой задачи строятся методы типа метода (36), которые обладают сходимостью в большом на множестве Р. Используя обычную функцию Лагранка и функцию (12), составим МФЛ

U(x,v,a) = L(x,v) - (Wa)(Lx(,x,v),x\P), а>0, (38)

и рассмотрим следующий итеративный процесс

= ** - т)рах(хЛ),хь\Р), (39)

где vk является решением задачи максимизации функции (38) по v

на Е^ при х=хъ. Доказывается существование такого cL>0, что метод (39) сходится к Хф для любых xqzP и с&х. Показано также, что если функции /(.г) и gt(x), - линейные, то метод схо-

дится к Х% за конечное число шагов.

В следующем § 16 рассматриваются барьерно-проективные методы для решения задачи НЛП

min f(x), К = {хеЕ?: g(a?) = о}. (40)

Для того, чтобы освободиться от требования неотрицательности переменных, здесь согласно второму из способов, описанных в § 4, используется сюръективное преобразование х=£{у) пространства в неотрицательный ортант ££ или, по крайней мере, в его внутренность. После замены переменных приходим к задаче

min /(z), Z = iz€E": g(z) = 0}. (41)

z£Z

Здесь: /(z)=/(£(z)), g(z)=g(£(z)). функция Лагранжа для этой задачи имеет вид L(z,v)=f(z)+<g(z),v>. Модифицируем ее аналогично (38), причем считаем для простоты, что (p(t)=t2/2. Тогда получим

U(z,v,т) = L(z,v) - \ \Lz{z,v)\z. (42)

Непрерывный аналог метода (36) для задачи (41) запишется в виде

z = -Iz(z,v(z,т)), (43)

где зависимость u(z,x) определяется из решения задачи максимизации функции ¥(г,и,т) по и.

Если вернуться к исходным переменным, то функция (42) и уравнение (43) примут вид

M(x,v,i) = L(x,v) - 2 <Lx(x,v),G{x)Lx(x,v)>, (44)

x = -G(x)Lx(x,v(x, i)), (45)

где С(х)=Я(г)Нт (x), H(x) - матрица Якоби d£(z)/dz для преобразования £fz), вычисленная в точке (х). В работе рассматривается в основном случай, когда преобразование координат строится в следующем виде х1=£1(г1), матрица G{x) для такого преобразования является диагональной. В частном случае, когда I1(t)=t2/4, получаем G(x)=D(x). Здесь D(x) - диагональная мат-

рица с t-м диагональным элементом х1. При использовании функции ?i(i)=exp(i) имеем соответственно G(x)=l£(х). В любом случае, из-за наличия в правой части уравнения (45) матрицы G(x) траектории, удовлетворяющие этому уравнению, не покидают положительного ортанта. Они сходятся к допустимому множеству, решение задачи (40) - точка х^ - является асимптотически устойчивым положением равновесия.

Дискретный вариант метода (45) записывается следующим образом

1 = " V^W^'V' = v(xk,z). (46)

В последнее время к итеративным процессам такого вида уделяется много внимания, особенно после того, как Кармаркаром в 1984 г. был предложен его полиномиальный алгоритм, предназначенный для решения задач линейного программирования. Здесь же в отличие от большинства появившихся затем вариантов метода Кармаркара рассматривается общая нелинейная задача и не предполагается, чтобы начальное приближение было допустимым.

Теорема 16.2. Пусть в точке х^ , являющейся изолированным локальным решением задачи (40), выполнены достаточные условия второго порядка и градиенты всех активных ограничений линейно независимы. Тогда для любого т>0 можно указать такое а(т), что для всех 0<a<ä(a) процесс (46) с постоянным шагом afe=a локально сходится к хсо скоростью геометрической прогрессии.

В том случае, когда в задаче (40) ограничения типа равенства линейные и градиент целевой функции удовлетворяет условию Липшица, можно установить более сильное утверждение относительно процесса (46), а именно, для любой допустимой начальной точки xq>0 и для любых достаточно малых постоянных ак метод сходится к точке хл, в которой выполнены необходимые условия первого порядка для задачи (40). Последовательность {/(.rft)} при этом монотонно убывает.

В § 17 исследуются вопросы применения барьерно-проективно-го метода (46) для решения задачи линейного программирования

min <о,х>, X =

где А - матрица размером т*п. Предполагается, что задача (47) и двойственная к ней не вырождены. Тогда множество стационарных точек систем (45), (46), принадлежащих допустимому множеству, состоит из конечного числа его угловых точек. Решение задачи (47) - точка х^ - также является положением равновесия для этих систем. С помощью теоремы о первом приближении показывается, что траектории системы (45) локально экспоненциально сходятся к

дискретный вариант (46) для достаточно малых постоянных а^ также сходится к хл со скоростью геометрической прогрессии.

Метод (46) обладает сходимостью в большом на множестве Х^СхеЕ"-: Ах=Ъ,,х>0), причем при более сложной стратегии выбора шага ай, когда ак полагается равным аь=а(хь), где

•а(х) = р / тах [I)"1 (х)С?(х)Х (х,и(х,т))]{, 0<р<1. (48)

х

В том случае, когда среди ограничений задачи (47) есть ог-

п I

раничение симплексного вида 2 х =Я>0, для методов (45) и (46),

{=1

в которых С(х)=0(х), можно построить функцию Ляпунова и получить оценки ее убывания. Пусть х - решение задачи (47). Составим функцию

Ф(х) = [ 1п11 - 1п ].

i=1 * *

Эта функция неотрицательна на X и равна нулю в том и только том случае, когда х=хф.

Теорема 17.3. Пусть х(хоД) - траектория системы, выходящая при t=0 из точки хоеХо. Тогда существуют такие числа 0<Хо^й°<+<о, что для всех {^0 имеют место неравенства

Ф(хо)е-к°* « Ф(х(хоД)) « Ф(хо)е~Ко*.

Если Jв к JN - номера соответственно базисных и внебазис-ных переменных в точке В - матрица базиса, а{ - 1-й столбец матрицы А, v9 - решение двойственной задачи, то имеют место следующие выражения для величин £° и £о:

К° = тах Ь*(х .у ),

, _ _ X * *

К = min LlJx , v ) 1--^ E -г1" + 1-

° t€Jw 1 L 2 J6JB ° -I

Для дискретного процесса (46) показывается, что если шаг afc выбирается согласно (48), то для любого xoeXQ существует такое 0<Р(хо)<1, что для всех 0<ß<]J(xo) и К^О имеет место оценка

7<W 1-SV2).

Последняя глава V посвящена построению численных методов решения задач МКО. В развиваемом здесь подходе в отличие от многих общепринятых приемов решения таких задач предлагается не сводить предварительно задачу MHO к задаче НЛП и применять к решению последней известные методы НЛП, а наоборот, сами численные методы НЛП обобщить таким образом, чтобы они позволяли отыскивать решения задач с несколькими критериями. В работе рассматриваются в основном обобщения непрямых методов НЛП, таких, как методы штрафных функций, методы параметризации целевой функции, метод модифицированной функции Лагранжа. Однако точно таким путем можно обобщить и прямые методы, например метод линеаризации, метод возможных направлений и т.д. Для простоты везде считается, что множество Р совпадает со всем пространством

В § 18 изучается метод штрафных функций для решения задач МКО, основанный на использовании вспомогательной функции

H(x,y,t) = Aif(x)-y) + tB(g(x)),

где А - строго смешанная СФ, В - строго.внешняя собственная СФ, t>0. Обозначим через F = lyeiT: y=f(x), xtX} множество достижимых оценок. В методе задается начальный вектор yj£intF+, где F+=F+E^, и выбирается произвольное направление eeintiT. Предполагается также, что как и в обычном методе внешних штрафных функций, задана последовательность монотонно возрастающих положительных чисел ttfc>. стремящихся к бесконечности.

На к-ы шаге из решения задачи

minИ(х,у ,tk) (49)

находится точка xk~x{yb,tk) и после этого определяется новый

вектор уровней по формуле

Ун, 1 = У* + oc^.y^.t^.eje, (50)

где o(x,y,t,e)=M+(x,y,t)/A(e), M+(x,y,t)=maxiO,M(x,y,t)]. Если функция A(z) является выпуклой положительно однородной строго смешанной СФ, то построенная последовательность векторов lyk) обладает тем свойством, что все ук лежат на луче 7+(уо,е), выходящем из точки уо по направлению е, и не принадлежат множеству intF+..

В работе доказывается, что при некоторых дополнительных предположениях, естественных для метода внешних штрафных функций, решения задач (49) существуют, а последовательность Cyfc} сходится к точке у„1(уо,е), в которой луч 7+<У0»е) пересекает границу множества При этом все предельные точки xt последовательности ixk) принадлежат Хф. Если точка yi>(yo,e) является оптимальной по Парето оценкой, то любая предельная точка хф реализует эту оптимальную оценку. Таким образом, параметризация множества оптимальных значений критериев Рздесь осуществляется только за счет выбора направления е. Это позволяет строить точные сечения множества

Предлагается также обобщение метода внутренних штрафных функций, в котором функция B(g) является внутренней СФ (собственной или несобственной). Он отличается от метода внешних штрафов только правилами выбора векторов уо, направлений е и последовательности а именно, теперь требуется, чтобы

уо€Р+, eeintiT и ltk} - последовательность положительных чисел, стремящихся к нулю. Минимизация вспомогательной функции проводится на множестве X и пересчет векторов yfe осуществляется по следующей рекуррентной схеме:

Уъ*1 = Уь+о^ь.Уь.е)6. а{х,у,е)= min IS^tlL., (51)

этом методе ly^i - монотонно убывающая последовательность векторов, лежащих на луче 7 +(уо,е). Как и в предыдущей версии метода штрафов, она сходится к той точке, где луч 7+(yo.e) пересекает границу множества F+.

В следующем § 19 строятся обобщения метода параметризации целевой функции для решения задачи МКО. Вспомогательная функция

в этом методе имеет вид- (15), причем функция Я обязательно отлична от линейной. Сначала рассматривается случай, когда все три функции А, В и Я являются строго внешними собственными СФ. Тогда справедливо следующее утвервдение:

Лемма 19.1. Если y^jfintF и M(xtt,yt )=□, то (у

Метод аналогичен методу внешних штрафных функций. Требуется, чтобы был задан начальный вектор уровней yo£intF+ и выбрано направление eeintH^. Итерации в методе проводятся по следующей рекуррентной схеме

Уь+1 - Ум + о{хк,ук,е)е, - (52)

где а(х,у,е)=Щх,у)/Н(А(е),0).

Для выпуклой задачи MHO может быть предложена другая версия метода, отличающаяся от (52) только правилом выбора коэффициента о(х,у,е). Предположим дополнительно, что функция H(t,1) дифференцируема всюду на Е2 за исключением, быть может, границы ортанта Ef. Положим

о(х,у,е) = А(/(х)-у) + -5-. (53)

Bt (A{f{x)-y),B(g(x)))

Если Я и А - выпуклые положительно-однородные строго внешние СФ, то в обеих версиях метода на каждом шаге y^intF . Доказывается, что все предельные точки последовательностей (х^У, порождаемые методами (52) и (53), сходятся к Хл. Отметим, что процесс (52) с выбором о(х,у,е) согласно (53) есть обобщение второй версии метода Моррисона, которая является по существу итеративным процессом типа (6).

Наряду с методом внешних центров рассматривается также метод внутренних центров для решения задач МКО. В этом методе при составлении вспомогательной функции (15) предполагается, что функции А, В и Я являются строго внутренними СФ, причем функции А и В собственными СФ. Начальный вектор уо берется из множества intF+, вектор е - из множества intZT, минимизация функции М(х,у) проводится на допустимом множестве X. Процесс имеет вид (52), однако теперь коэффициент а(х,у,е) определяется по формуле (51). Доказывается сходимость этого метода.

В § 20 строится обобщение двойственного метода ММ. В нем

с помощью функции Лагранжа (16) и функции (14) составляется МФЛ

М(г,а) = Ь(г) + (7а)(£и(г),и|5г) + (7а)(Ьи(;г),и(54)

В частном случае, когда критерий один, она переходит в МФЛ, исследованную многими авторами (Р.Рокафеллар, Д.Бертсекас, Б.Т. Поляк, Е.Г.Гольштейн и Н.В.Третьяков и др.).

Будем считать, что в точке выполнены достаточные ус-

ловия второго порядка, т.е. можно указать такие у

у {Ег, что

Кг,)=0, 1(г)=0. П г(1(г()+и()=0, (г^+и^О

и

<<3,Ь (г )сг> > О

XX * '

для любого ненулевого Здесь: П^(0) - проекция вектора ц на множество Q;

к = Ме^шс,: </х(х^),<з>=о, £е!1, <^х(хг),а>=о, /е!г>, Я, = ШеЕГ1: <Г1х(хг),с1>ф, ^ = II: (хфН/*>.

кг = шап: <£>х(х^) ,а>ф, J<iJг}, ¿г = {/: ^(х)=0),

I, = а: и*>0>, Г_ = {/: 1^>0}. 1 » ' 2 * *

При выполнении этих условий можно указать такую константу а^>0, что при 0<а<а^ для всех ш=[и,и,у! из некоторой окрестности точки существует изолированное локальное решение х(ю,а) задачи минимизации функции (54) по х.

Снова зададимся вектором уровней у^ЯГ и направлением Положим у(уо,е,о)=уо+ое, оо=0 и построим итеративный

процесс:

У* = хн €'Агв тзлп М{х,ик,ик,ук,а),

х£Е

п3"(1Л)/а + V* иь+1= + V • (55)

Процесс (55) можно, рассматривать как метод простой итерации для решения системы уравнений

(7а)р(1и(г(ш,а),и,у,у(уо,е,о)),и|5г) = О,

(7а) (1и(х(ш,а),и,и,у(уо,е,о)),= 0,

*(х(!У,а),и,и,у(уо,е,о),а)/<и,е> = 0.

Обозначим через ср(х,у) вектор-функцию, первыми г компонентами которой являются функции /1(х)-у1, а последующими т компонентами - функции ^(х). Обозначим также <7о(х,у)={1:ф{(х,у)=0}.

Определение. В точке [дг^.у^] выполнено условие регулярности, если <р (.г^.у^фО для любого ненулевого вектора б., у которого сумма первых г компонент равна нулю и <з'=0, .

Основным результатом этого параграфа является

Теорема 20.1. Если в точке выполнены достаточные условия второго порядка и условие регулярности, матрица Ъхх(г^) не вырождена, то можно указать такое а+>0, что для всех 0<а<а^ процесс (55) локально сходится к Си^.и^.у^] со скоростью геометрической прогрессии. Последовательность сходится к х^.

Здесь, как и во всех предыдущих методах МКО, если у есть оптимальная оценка, то хреализует эту оценку.

В приложении дается краткое описание диалоговой системы оптимизации ДИСО/ПК-КШ, предназначенной для решения задач НЛП на персональных ЭВМ. При разработке этой системы использовался предложенный в диссертации подход к построению и систематизации численных методов условной оптимизации

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

1. Предложен общий принцип построения численных методов условной оптимизации, основанный на интерпретации методов либо как процедур минимизации вспомогательных функций, либо как процедур минимизации этих функций в сочетании с решением систем нелинейных уравнений. Проведена классификация ряда методов нелинейного программирования в соответствии с этим принципом. Показано, что данный подход является достаточно плодотворными и позволяет не только охватить многие известные численные методы нелинейного программирования, но и предложить новые методы. Введены понятия'точных и приближенных вспомогательных функций.

2. Изучены точные вспомогательные функции, позволяющие находить решение задачи нелинейного программирования в результате их однократной минимизации. Получены достаточные условия, при которых вспомогательная функция является точной.

3. Дан конструктивный способ построения приближенных вспомогательных функций и предложены численные схемы отыскания их особых точек, приводящие к различным классам методов решения задач нелинейного программирования.

4. Для задач нелинейного и обобщенного нелинейного программирования получены достаточные условия оптимальности, позволяющие обосновывать выбор конкретных функций в качестве приближенных вспомогательных функций методов.

5. Предложены два новых класса методов параметризации целевой функции, которые основаны на использовании нестандартных комбинаций свертывающих функций.

6. Предложены прямые и непрямые методы решения задач нелинейного программирования, основанные на применении специальных модификаций функции Лагранжа.

7. На базе сюръективных отображений разработан класс барь-ерно-проективных методов. Показана связь этих методов с прямыми методами модифицированной функции Лагранжа, исследованы вопросы применения барьерно-проективных методов для решения задач линейного программирования.

8. Предложен принципиально новый подход к построению численных методов решения задач условной многокритериальной оптимизации, основанный на обобщении методов нелинейного программирования. Рассмотрены соответствующие обобщения методов штрафных функций, методов параметризации целевой функции и метода множителей Лагранжа.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Голиков А.И., Жадан В.Г. Итеративные методы решения задач нелинейного программирования с использованием модифицированных функций Лагранжа // Журн. вычисл. матем. и матем. физ. -1980. - Т. 20, * 4. - С. 874-888.

2. Евтушенко Ю.Г., Жадан В.Г. Релаксационный метод решения задач нелинейного программирования // Журн. вычисл. матем. и матем. физ. - 1977. - Т. 17, * 4. - С. 73-87.

3. Евтушенко Ю.Г., Жадан В.Г. Об одном подходе к систематизации численных методов нелинейного программирования // Изв.

АН СССР. Сер. техн. кибернетика. - 1983. - N 1. - С. 47-59.

4. Евтушенко Ю.Г., Жадан В.Г. К вопросу о систематизации численных методов нелинейного программирования. Методы последовательной безусловной минимизации // Сообщ. по прикл. матем. М.: ВЦ АН СССР, 1988. - бб с.

5. Евтушенко Ю.Г., Жадан В.Г. Точные вспомогательные функции в задачах оптимизации // Журн. вычисл. матем. и матем. физики. - 1990. - Т. 30, Л 1. - С. 43-57.

6. Евтушенко Ю.Г., Жадан В.Г. Барьерно-проэктивные и барь-ерно-ньютоноваше численные метода оптимизации (случай нелинейного программирования) // Сообщения по вычисл. матем. М.: ВЦ АН СССР, 1991. - 64 с.

7. Жадан В.Г. 0 двух классах методов решения задач нелинейного программирования // Докл. АН СССР - 1980. - Т. 254, № 3. - С. 531-534.

8. Жадон В.Г. Модифицированные функции Лагранжа в нелинейном программировании // Журн. вычисл. матем. и матем. физики. -1982. - Т. 22,2. - С. 296-308.

9. Жадан В.Г. Методы возможных направлений в диалоговой системе оптимизации ДИСО// Пакеты прккл. программ: Метода оптимизации. М.: Наука, 1984. - С. 93-102.

10. Жадан В.Г. Об одном классе итеративных методов решения задач выпуклого программирования //•Журн..вычисл. матем. и матем. физики. - 1984. - Т. 24, Л 3. - С. 25-32.

11. Жадан В.Г. О некоторых оценках коэффициента штрафа в методах точных штрафных функций // Журн. вычисл. матем. и матем. физики. - 1984. - Т. 24, №8.-- С. 1164-1171.

12. Жадан В.Г. Метод параметризации целевых функций в условной многокритериальной оптимизации // Журн. вычисл. матем. и матем. физики. - 1986. - Т. 26, Л 2. - С. 177-189.

13. Жадан В.Г. Методы штрафных функций в задачах условной многокритериальной оптимизации // Кибернетика и вычислительная техника, вып. 3, 1987. - С. 219-229.

14. Жадан В.Г. Условия оптимальности в задачах обобщенного математического программирования // Проблемы прикладной математики и информатики. М.: Наука, 1987. - С. 208-218.

15. Жадан В.Г. Метод модифицированной функции Лагранжа для задач многокритериальной оптимизации // Журн. вычисл. матем. и матем. физики. - 1988. - Т. 28, J6 11. - С. 1603-1618.

16. Жадан В.Г. О некоторых обобщениях методов нелинейного программирования для решения задач многокритериальной оптимизации // Многокритериальные задачи математического программирования. Тез. докл. межд. конференции (г.Ялта). Киев, 1988. - С. 25-26.

17. Жадан В.Г., Кушнирчук В.И. Пакет методов многокритериальной оптимизации в системе ДИСО. - В сб.: Пакеты прикладных программ. Программное обеспечение оптимизационных задач. М.: Наука, 1987. - С. 17-26.

18. Жадан В.Г., Мазурик В.П. Нелинейное программирование в системе ДИСО/ПК. - Сообщения по программному обеспечению ЭВМ. М.: ВЦ АН СССР. - 44 с.

19. Evtushenko Yu.G., Zhadan V.G. New approaohee.in optimization techniques // Leoture Notes in Control and Information SoienoeB, 143. System Modelling and Optimization, Proceedings of the 14th IPIP Conferenoe, Leipzig, 1989. - P. 21-37.

20. EvtuBhenko Yu.G., Zhadan V.G. Exaot auxiliary funo-tions // Inforaiatioa. - 1990. - V 1, * 1. - P. 40-58.

21. Zhadan V.G. Methods of centers in nonlinear programming // Leoture Notes in Control and Information SoienoeB, 143. System Modelling and Optimization, Proceedings of the 14th IFIP Conferenoe, Leipzig, 1989. - P. 252-261.

Жадан Виталий Григорьевич Разработка и систематизация численных методов условной оптимизации

Подписано в печать 25.06.92. Формат бумага 60«84 1/16 Тирах 100 экз. Заказ 91 . Бесплатно

Отпечатано на ротапринтах в ВЦ РАН 117967, Москва, ГСП-1, ул. Вавилова, 40