Методы псевдовыпуклого программирования с параметризацией направлений и аппроксимацией множеств тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

На правах рукописи

УДК 519.85 003490941

Заботин Игорь Ярославич

МЕТОДЫ ПСЕВДОВЫПУКЛОГО ПРОГРАММИРОВАНИЯ С ПАРАМЕТРИЗАЦИЕЙ НАПРАВЛЕНИЙ И АППРОКСИМАЦИЕЙ МНОЖЕСТВ

01.01.09 — дискретная математика и математическая кибернетика

Автореферат

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

2 8 ЯНВ 2010

Казань — 2010

003490941

Работа выполнена на кафедре экономической кибернетики Государственного образовательного учреждения высшего профессионального образования "Казанский государственный университет им. В. И. Ульянова - Ленина".

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

профессор

Демьянов Владимир Федорович,

доктор физико-математических наук, профессор

Колоколов Александр Александрович,

доктор технических наук, профессор

Галиев Шамиль Ибрагимович. Ведущая организация: ГОУВПО "Иркутский государственный университ

Защита диссертации состоится 25 февраля 2010 г. в 14 часов 30 минут на заседании диссертационного совета Д 212.081.24 в конференц-зале библиотеки Казанского государственного университета (корп. 2) по адресу: 420008, г. Казань, ул. Кремлевская, 18.

С диссертацией можно ознакомиться в библиотеке Казанского государственного университета.

Автореферат разослан "Ц"_М|_20<0 г.

Ученый секретарь диссертационного совета, доцент

А. И. Еникеев

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

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

B., Голикова А. И., Голыитейна Е.Г., Евтушенко Ю. Г., Еремина И. И., Жадана В. Г., Колоколова А. А., Попова Л. Д., до настоящего времени выходят работы, относящиеся к теории или методам линейного программирования, а в области нелинейного выпуклого программирования, наряду с уже названными математиками, продолжают получать важные теоретические и практические результаты Антипин А. С., Белоусов Е. Г., Булавский В. А., Булатов В. П., Васильев Ф. П., Галиев Ш. И., Зоркальцев В. И., Ижуткин B.C., Левитин Е. С., Нурминский Е. А., Поляк Б. Т., Третьяков Н. В. и др.

Из раздела нелинейного программирования наибольшие трудности вызывают задачи невыпуклого программирования. Исследованию таких задач и построению методов их решения также уделено немало внимания. У многих, в том числе перечисленных выше авторов, есть значительные работы по невыпуклому программированию. Кроме того, систематические исследования в области невыпуклого анализа и невыпуклого программирования проводились, например, в работах Демьянова В. Ф., Заботина Я. И., Карманова В. Г., Кокурина М. 10., Коннова И. В., Кораблева А. И., Малоземова В. Н., Немировского А.

C., Нестерова Ю. Е., Пшеничного Б. II., Рубинова А. М., Стрека-ловского А. С., Стронгина Р. Г., Третьякова А. А., Федорова В. В., Фазылова В. Р., Хабибуллина Р. Ф., Хамисова О. В., Шора II. 3.

К невыпуклому программированию относится, в частности, раздел псевдовыпуклого программирования. Задачи псевдовыпуклого программирования являются непосредственным расширением класса задач выпуклого программирования. Понятие псепдовыпуклости для дифференцируемых функций было предложено еще в 1965 году О. Мапгасариапом. В 1974 году в работе Заботшга Я. И. и Корабле-ва А. И. введено определение недифференцируемых псевдовыпуклых функций и изучены некоторые их свойства. Хотя задача псевдовыпуклого программирования сформулирована уже давно, и на практике встречаются такие задачи, раздел псевдовыпуклого программирования исследован далеко не полно. Несмотря на то, что псевдовыпуклые функции по многим важным свойствам близки к выпуклым, хорошо изученный и развитый аппарат выпуклого анализа обычно не удается непосредственно использовать для построения и обоснования методов псевдовыпуклого программирования.

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

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

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

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

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

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

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

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

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

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

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

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

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

лого программирования. Некоторые из построенных методов применены для решения прикладных оптимизационных задач, связанных с проектированием технических систем.

Основные результаты диссертации.

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

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

3. Разработан подход к построению методов псевдовыпуклого про-

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

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

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

метода центров с иараметризованиими направлениями, строящимися с помощью решения задач линейного программирования.

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

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

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

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

Все перечисленные основные результаты выносятся на защиту.

Апробация работы. Результаты диссертации представлялись и обсуждались в 1984 - 2009 гг. на семинарах кафедры экономической ки-

бернетики Казанского государственного университета, кафедры радиофизики КГУ, семинарах слушателей ФПК и кафедры исследования операций МГУ, республиканском семинаре "Оптимизация вычислений" в Институте кибернетики Украины, семинарах в МЭСИ и Институте проблем управления, семинаре кафедры математической физики МГУ, практически всех итоговых научных конференциях КГУ за указанные годы, а также на Всесоюзной конференции "Статистические методы исследования функционирования сложных технических систем" (Москва, 1983), Научно-технической конференции Куйбышевского политехнического института (1986 ), 7-ом и 11-ом Всесоюзных симпозиумах "Системы программного обеспечения решения задач оптимального планирования" (Нарва-Иызсуу, 1982; Кострома, 1990), 7-ой, 8-ой, 11-ой Всесоюзных конференциях "Проблемы теоретической кибернетики" (Иркутск, 1985, Горький, 1988, Волгоград, 1990), Всесоюзной конференции "Методы математического программирования и программное обеспечение" (Свердловск, 1989), 9-ой -13-ой Всероссийских конференциях "Математическое программирование и приложения" (Екатеринбург, 1995, 1997, 1999, 2003, 2007), Всероссийских конференциях "Проблемы оптимизации и экономические приложения" (Омск, 2003, 2006), "Дискретный анализ и исследование операций" (Новосибирск, 2002, 2004), "Актуальные проблемы математического моделирования и информатики" (Казань, 2002), "Алгоритмический анализ неустойчивых задач" (Екатеринбург, 2001, 2004), 6-ом Всероссийском семинаре "Сеточные методы для краевых задач и приложения" (Казань, 2005), на 5-ой, 8-ой, 10-ой, 11-ой, 14-ой Байкальских международных школах-семинарах "Методы оптимизации и их приложения" (Иркутск, 1980, 1989, 1995, 1998, 2008), Международных конференциях "Проблемы оптимизации и экономические приложения" (Омск, 1997), "Дискретный анализ и исследование операций" (Новосибирск, 2000), 12-ой, 13-ой, 15-ой Международных конференциях " Проблемы теоретической кибернетики" (Нижний Новгород, 1999; Казань, 2002, 2008),

Публикации. По теме диссертации опубликовано 75 научных работ. Результаты, представленные в диссертации, отражены в 60 публикациях приведенного ниже списка литературы. В список входят 12 статей, относящихся к публикациям перечня ВАК ведущих на-

учных журналов и изданий Российской Федерации, и еще 10 статей, опубликованных в изданиях, включенных в системы цитирования "Springer", "Scopus" и др. Все основные результаты работы отражены в 12 статьях, относящихся к упомянутому перечню ВАК. Отметим, что из совместных работ в диссертацию включены только те результаты, которые получены автором лично. Деление результатов совместных публикаций подробно проведено во введении при описании результатов главы 4 и главы 6, где имеются ссылки на такие работы.

Структура и объем работы. Диссертация состоит из введения, шести глав, заключения и списка литературы (232 наименования). Общий объем диссертационной работы — 294 страницы.

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

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

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

В § 1.1 разработаны общие методы решения задачи

ттр(х), (1)

где G — П Gj, J = {1,..., m},G] С R„ - выпуклые замкнутые мно-

о

жества, внутренность Gj множества Gj непуста для всех j G J, g(x) - непрерывная достигающая на G своего минимального значения д"

о

функция. Подчеркнем, что, в частности, возможен случай G=- 0.

Первый метод (процедура 7Ti) вырабатывает последовательность приближенных решений р, следующим образом. Строится выпуклое

замкнутое множество Mt], содержащее хотя бы одну точку из мно-

с

жества У* решений задачи (1), выбираются точки у3 Е Gj Vj 6 J и число q € [1, +сх>). На i - ом шаге отыскивается точка ?/, £ M¡ (]{х € : д(х) < д*}. Если y¿ € G, то процесс заканчивается. В противном случае полагается J, = {j 6 J : yt <t Gj), для всех j £ J; в интервале {у3, у i) находится такая точка г- ^ Gj, что существует y¡ £ Gj, удовлетворяющая неравенству — 2/¿|) S <7 IIF> ~ 2г Ib Лля всех j £ J¿ выбирается конечное подмножество A¿ множества W'(z-, Gj) нормированных обобщенно-опорных к Gj в точке z¡ векторов и полагается Mi+1 = Mif]{x 6 Rn : (а, х — zf) < 0 Va 6 j G J¡}.

Обсуждаются реализации, связанные с выбором множеств Мц, А\ и точек z{. Если G\ = ... = Gm = G, Gi=- 0, функция <j(z) выпукла,

, о

у — ... = ут — у, и у £ G, то процедура 7Ti близка к известным методам погружений В.П.Булатова.

Теорема 1. Пусть последовательность {?/.}, построенная процедурой 7Г\, ограничена. Тогда любая ее предельная точка принадлежит множеству У*, а если при этом g(f¿) = rain g{x) Vi, то вся последова-

X f: А/, *

тельность {yt}, сходится к множеству Y* .

Приводятся две постановки приближенного решения задачи (1), в которых требуется отыскать точку х G G, удовлетворяющую неравенству д(х) < д* + £, где £ > 0, или неравенству д(х) < од*, где О < a < 1, если д* < 0, и 1 < о < оо, если д* > 0. Доказывается, что предложенными процедурами обе задачи решаются за конечное число шагов. При этом предлагаются простые практические критерии остановки работы процедур.

В § 1.2 предлагается в виде процедуры 7Г2 еще один метод решения задачи (1). В отличие от тх\ множество Мо в поцедуре тг2 содержит всю область G, а f/¿ являются точками приближенного минимума на множествах Mi не целевой функции, а вспомогательных функций gi{x) = д(х) + a¡/¿(x). При предположении ограниченности {y¡} для процедуры 7г2 доказана

Теорема 2. Пусть для последовательностей {«,}, {/¿(а)}, и множества G выполняются условия любого из перечисленных ииже пунктов: 1) a, —> 0, i —» оо, последовательность {/,(?/,)} ограничена; 2} a¡ > 0, i = 0,1,..., k{x) = 0 Vi € G, и ¿¡(а;) > 0 Vx i G, г = 0,1, ...;

3) Gф 0, a; > 0, i = 0,1,..., а; Ч 0, i -4 со, функции li(x), i = 0,1,..., неотрицательны на множестве Мд, и 1,(х) < у < оо Vx gG . Тогда любая предельная точка последовательности построенной прцедурой 7г2, принадлежит множеству У*.

Показано, что при определенных способах выбора функций /¡(ж) процедуру 7Г2 можно интерпретировать как варианты некоторых известных методов.

В § 1.3 на тех же идеях отсечений разработаны две процедуры (тгз, 7Г3) нахождения точки множества G с непустой внутренностью, которые также применимы для построения подходящих направлений и при этом не требуют знания вспомогательных точек у3. Пусть

о

у (¿G\ Р - конечное множество обобщенно-опорных к G в точке у векторов, Мо - выпуклое ограниченное замкнутое множество, содержащее точку у* — argminmax(р,х — у). Согласно поцедуре тгз на г

-ом шаге отыскивается точка у1 £ М1 , удовлетворяющая условию

max (р, — у ) < max {/>, у* — у). Если у\ 6 G, то процесс заканчива-р€Г

ется, в противном случае полагается hi — yi — y\iyi = y + ("i hi, где а; - максимальное из чисел a > 0, для которых у + ah% £ Со({у} U G), вычисляется

У,, «»> 0,

Vi + - Vi), a* = 0, % = Vi + KVi - Vi), zi = + (1 - где 0 < /I < p < 1, Ai e

[0,1]. Далее выбирается такое множество Ai С И71 (г;, 6'), что для всех a G Л,- выполняется неравенство (а,у — г,) < —S, и полагается Mi+1 = Mi П {ж 6 ii„ : (а,х- z{} < 0 Va € Л;}.

Процедура тг3 отличается от тг-j тем, что Mq содержит всю область G, а при нахождении точек у{ множество Р меняется от шага к шагу.

Лемма 1. Пусть последовательность {]!,}, построена процедурой тг3 или тг3. Тогда любая предельная точка этой последовательности принадлежит множеству G.

Лемма 2. Пусть у £ G\ G, последовательности {у,}, {у,}, {z{} построены процедурой 7г3, и 0 < a < 1. Тогда найдется номер ig такой, что выполнится неравенство max (р, у^ — у) < a min max (р, х — у),

причем, ylr> € G.

В виде алгоритмов Rl — R4 описываются и обосновываются реализации этих процедур для множеств G специального вида. На основе лемм 1, 2 доказывается, что для псевдовыпуклой функции f(x) алгоритмами Ri - R4 можно построить за конечное число шагов подходящее в точке у & D направление, выбирая в качестве G, например, множество E(f, D, у) = {х е Rn% & А < 1{у)}-

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

Решается задача

ттЩг) | х 6 D}, (2)

где множество D С Rn выпукло и замкнуто, diniD < п, а функция /о(х) пссвдовыпукла и непрерывно дифференцируема. В §§ 2.1, 2.3 предложены два метода решения этой задачи, объединенные следующей общей схемой. IIa к -ом шаге методов выбираются множества Dk С R„, удовлетворяющие введенным в тех же параграфах условиям А или В (причем, допускается выполнение неравенств dim Dk < dim D), в множествах Dk отыскиваются определенным образом вспомогательные точки хь- Затем из точки ж* по направлению Sk = х^ — Хк производится спуск в некоторую промежуточную точку Vk £ D, а очередное приближение Хк+\ произвольно выбирается в D лишь согласно неравенству

/o(®t+i) < /оЫ- (з)

Методы отличаются принципами выбора множеств D/; и точек х*. Множества Dk в методах могут полностью или частично содержать область D, а могут и содержаться в ней. Точки Хк, например, в первом методе находятся из условия

(/о(хк),хк ~ хк) < Ок min (fli(xk),x - хк), (4)

где а < стк < 1. Если положить в методах Dk = D, x^+i = vk = х-к + ßk$k, то при условии (4) они совпадают с методом условного градиента. Доказаны теоремы сходимости методов для всех случаев задания промежуточных точек Vk как с условием релаксации, так и

без него. При этом для обоснования нерелаксационных вариантов использована методика Ф. П. Васильева. При некоторых дополнительных требованиях на функцию /«(к) с применением известных теорем В. Г. Карманова получены следующие оценки скорости сходимости методов:

/о(зт) - /о < °о[1 + ао0т]-1, т = 1,2,..., (5)

где а0 = /о(хо) - /о, /0* = тт{/0(г) | х £ £>}, 0 > 0.

Заметим, что за счет условия (3) на этапе перехода от ид. к точке хь+1 можно подключать любые известные или новые алгоритмы, в которых итерационные точки принадлежат допустимой области, причем, сходимость таких смешанных алгоритмов остается обоснованной в связи с теоремами сходимости самих методов. Промежуточные точки Ук и условие (3) выбора приближений будут использоваться далее практически во всех предлагаемых методах, поэтому высказанное здесь замечание относительно построения на их основе комбинированных алгоритмов будет иметь силу и в дальнейшем.

В §§ 2.2, 2.4 предлагаются реализации методов из §§ 2.1, 2.3, основанные на различных способах задания множеств Ок и на конечных процедурах тг3. Полагая в этих процедурах О = Дь у* = у — и выбирал множество Мо многогранником, направления ¡¡к строятся в таких реализациях в виде — жд.) решением конечного числа задач линейного программирования (см. лемму 2). Отметим, что в виде реализации второго метода построена модификация метода условного градиента, в которой направления находятся путем минимизации традиционной вспомогательной линейной функции на аппроксимирующих В многогранных множествах Ок, построенных процедурами отсечений из гл. 1. В § 2.4 приводятся результаты численных экспериментов, проведенных с предложенными методами. На их основе реализации сравниваются между собой, а также с известными алгоритмами. Выявлены явные преимущества построенных алгоритмов с выбором Ик = Е(/о, О, у к), где ук Е В, перед методом условного градиента для "овражных" целевых функций.

В § 2.5 для задачи (1) предложен метод проекционного типа, вкладывающийся в ту же схему, что и методы §§ 2.1, 2.3. Направления вд. строятся в нем с помощью проектирования градиента целевой функции на подмножество О к С О или специально построенное множество

Аь, в частности, охватывающее область О. Доказаны теоремы сходимости метода, а также оценки скорости сходимости для всех способов задания точек Ук с условием релаксации и без него. Описаны реализации метода. Одна из них представляет собой модификацию метода проекции градиента, в которой на некоторых шагах в случае выполнения определенного условия операция проектирования вспомогательной точки может опускаться. Для задачи (2) с ограничениями Г) общего вида описаны алгоритмы метода, в которых множества Ль строятся в виде многогранных с привлечением упомянутых выше процедур аппроксимации £>, и подходящие направления отыскиваются с помощью решения задач квадратичного программирования.

Для задачи (2) с сильно выпуклой функцией }ц{х) в заключительном параграфе гл. 2 предлагается метод второго порядка, основанный на идеях метода Ньютона и алгоритмов из §§ 2.3, 2.5. В предлагаемом методе, в отличие от метода Ньютона, для построения подходящего направления а к = Хк — Х(., во-первых, можно использовать не все допустимое множество £7, а лишь его часть, например, Ок --Е(/о, £>, Хк), и, во-вторых, вспомогательную задачу минимизации традиционной квадратичной функции 1'\(х) для нахождения точки Хк можно решать не на множествах О или О к, а на содержащем их специально построенном множестве Д* более простого вида. С практической точки зрения аппроксимирующее множество Ак удобно строить как многогранное. Тогда задача выбора направления является задачей квадратичного программирования, и может быть решена за конечное число шагов. Способы построения указанных аппроксимирующих множеств па основе разработанных процедур отсечений описаны в § 2.6. Отметим, что на некоторых итерациях метода для отыскания 5/. достаточно решить задачу безусловной минимизации Рк(х). Кроме того, в методе заложена возможность нахождения приближений хк±1 с использованием условия (3). Доказана сходимость метода, получена оценка его скорости сходимости. Для случая, когда О задается нелинейными неравенствами, предложены реализации метода, в которых направления з/= строятся с помощью решения задач квадратичного программирования.

В третьей главе предлагаются алгоритмы условной минимизации гладких псевдовыпуклых функций с параметризованными направле-

ниями итерационного перехода.

§ 3.1 носит вспомогательный характер. В нем исследуются некоторые свойства задачи (2), где

В = {®еЛ»: < 0, ; £ ./}, (б)

функции ¡](х) псевдовыпуклы непрерывно дифференцируемы, а множество О регулярно по Слейтеру. Эти свойства связаны со спецификой строящихся далее методов и особенностями обоснования их сходимости.

В § 3.2 ставится и исследуется задача построения л точке хк 6 Б подходящего направления в виде

Ч = Е ац{хк)/;(хк), (7)

■'ел

где 1к = Л и{0}, Л - множество ек - активных в точке хк ограничений /](х). Для отыскания коэффициентов «¡(ж*.) предлагается решать одну из вспомогательных задач минимизации линейной функции Е {/о(ж/с), /,(£;.)} а, при некоторых ограничениях на переменные ¡е Л

a¿. Изучаются свойства этих задач, и доказывается теорема оптимальности точки Х(.. Далее предлагается метод решения задачи (2), (6), в котором на к -ом шаге для построения направления (7) отыскиваются числа а{(хк), г 6 1к, удовлетворяющие любому из четырех предложенных условий. Одно из них, например, выглядит следующим образом:

£ с-сф*) < £74 тш{ Е с1;сц\^{хк + Е «¿ЛЫ) < 6 ¡еЛ ieh ¡ел

где с* = (/¡¡(хк), Ц(хк)), 0 < а < сгк < 1. Остальные три отличаются от приведенного наличием дополнительных условий на переменные

а; и (или) заменой ограничений fj(xk + Е сц}\{хк)) < 0,] £ ./, на

¿ел

ограничения ^(хк + Е аЛ(хк)) < д,] € Л- Если Е с%а{(хк) = 0, то

■еЛ ' ¿ел

хк принадлежит множеству X* решений задачи (2), (6). Далее следует переход из точки хк по найденному параметризованному направлению во вспомогательную точку ь>к с шагом (Зк. Точки хк+] находятся в £) из условия (3).

В диссертации разрабатывается новая методика доказательства сходимости методов псевдовыпуклого программирования с параметризованными направлениями вида (7). До этой методике обосновывается сходимость описанного метода для всех видов шагов /3&, доказывается оценка (5) его скорости сходимости.

Заметим, что допустимые области задач поиска значений а,(ж/..), вообще говоря, не являются многогранными, если множество О имеет общий вид. В связи с этим, применяя уже использованные выше принципы аппроксимации множеств, для областей С): можно строить аппроксимирующие их множества в форме многогранников и, соответственно, ставить задачи поиска коэффициентов аДа^) в (7) в виде задач линейного программирования. С учетом этого замечания в §3.3 приводится одна из реализаций метода, в которой при нахождении решения а^Хк) вспомогательной задачи используются процедуры отсечений т^ или 7Г3. Каждая из процедур гарантирует отыскание значений аДгд.) за конечное число шагов. В § 3.3 проводится сравнение предложенного метода с идейно близкими известными методами выпуклого программирования, отмечаются его преимущества для определенных типов задач (2), (6). Приводятся также результаты численного сравнения на тестовых примерах некоторых алгоритмов метода между собой и с методом условного градиента.

Далее, для задачи (2) в §§ 3.4, 3.5 предлагаются проекционные алгоритмы, в которых, задачи проектирования могут иметь меньшее по сравнению с исходной задачей число переменных и ограничений, и проектирование вспомогательных точек может осуществляться на некоторые специально построенные многогранные множества. В § 3.4 предлагаются два алгоритма для задачи (2), (6), в которых направления вк имеют вид (7), а коэффициенты а,(х;.) отыскиваются с помощью одной из двух задач проектирования градиента целевой функции на некоторые множества Ок из линейного многообразия, определяемого градиентами /¡(хк), г 6 1к■ Как и в предыдущих алгоритмах, найденные направления используются для нахождения точки Ук, а приближение Хк+1 выбирается из условия (3). Доказаны теорема оп-тимгшьности точки Хк и теоремы сходимости методов, а также приведена оценка их скорости сходимости. Поскольку число неизвестных в задачах поиска я к зависит от количества активных в точке х-к ограничений, то при ш < тг такие задачи предпочтительнее традиционной

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

На случай задания области £) нелинейными функциями в § 3.5 предлагаются модификации этих алгоритмов. В модификациях направления (7) находятся путем проектирования градиента не на множества 0/:, как в исходных алгоритмах, а на аппроксимирующие их многогранные множества Дь Множества Д/,. с необходимым качеством аппроксимации строятся за конечное число шагов процедурами отсечений из гл. 1.

Использование параметризованных направлений возможно и в алгоритмах второго порядка. В § 3.6 для задачи (2), (6) с сильно выпуклой целевой функцией предлагается метод, близкий к описанному выше алгоритму из § 2.6. В этом методе при построении направлений в к коэффициенты аг(а-д.) в (7) отыскиваются путем минимизации вспомогательных выпуклых квадратичных функций от переменных

а,- на множествах £>/:, заданных неравенствами /}(х>,: -¡- £ «¿Л(жл-)) <

Шк

0.^ £ J, или ¡¡{хк + £ а{/[(хк)) < 0,^ £ Затем полагается »е/л

Щ = хк + (Зквк, (8)

и точка выбирается согласно (3). Сходимость метода обеспечивается за счет различных способов выбора шагов /3*. Несмотря на то, что в описанном методе задачи поиска коэффициентов в определенных случаях имеют меньшие, чем, например, в методе Ньютона, размерности, при задании множества О в общем виде они остаются достаточно сложны. В связи с этим в § 3.7 предлагается модификация метода, позволяющая использовать в задачах выбора направления вместо множеств Дь аппроксимирующие их многогранные множества А к из тех же линейных многообразий, что и В к- Тогда, несмотря на общий вид £>, процедурами отсечений из § 1.1 удается получать искомые коэффициенты «¡(г;;) в (7) с помощью задач квадратичного программирования. В §§ 3.6, 3.7 приводятся обоснования сходимости метода п его модификации, оценки скорости сходимости, а также реализации этих методов.

В § 3.8 предлагается и обосновывается еще один алгоритм решения задачи (2), (6) с параметризованными направлениями (7), который

идейно близок к методу возможных направлений Зойтендейка. Если в (2), (6) п > т, то задача выбора направления в построенном алгоритме выгодно отличается от традиционной задачи Зойтендейка по числу переменных и ограничений. Приближение строится здесь также на основе промежуточной точки из условия (3).

В § 3.9 строится алгоритм псевдовыпуклого программирования, основанный на идеях метода линеаризации и близких к нему алгоритмов. В отличие от этих методов предлагаемый алгоритм использует параметризованные направления (7), где коэффициенты находятся путем решения задачи квадратичного программирования. Обоснован критерий оптимальности итерационной точки, доказана теорема сходимости. Заметим, что, как и другие методы гл. 2, 3, данный алгоритм позволяет за счет условия (3) комбинировать его с любыми релаксационными методами, не обосновывая заново сходимость смешанных алгоритмов.

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

В § 4.1 строятся два релаксационных метода решения задачи (2) с дифференцируемой по направлениям строго псевдовыпуклой функцией /о(ж). В первом методе на к -ом шаге выбирается конечное множество Р;. нормированных обобщенно-опорных для функции /ц(ж) в точке Хк векторов, отыскивается точка Щ £ Д. = Е(}й, удов-

летворяющая неравенству

тах (р, хк - хЛ < сгк тт тах (р, х - хк), (9)

реД хеок реРк

где 0 < а < а к < 1, вектор як = хк — хк используется в виде (8) для построения промежуточной точки Vk с условием релаксации, а приближение х^+1 выбирается согласно (3).

Второй метод отличается от первого тем, что применяется для задачи (2) с дополнительным требованием к области Б, но, в то же вре-

мя, имеет более широкие возможности в выборе множеств А именно, 1\ строятся в нем из обобщенно-опорных для /о(ж) относительно множества D векторов. Для методов доказано следующее утверждение о сходимости.

Теорема 3. Пусть для функция /о(х) и множеств а D выполняются высказанные выше условия, и множество E(fo,D,xo) ограничено. Тогда для последовательности {жд.}, построенной первым из предложенных методов, справедливо предельное соотношение

Hm /оЫ - /о. (10)

К-УОО

Если множество D, кроме того, строго выпукло, то для последовательности {¡Ei}, построенной по второму методу, также выполняется равенство (10).

Приводится оценка скорости сходимости методов. Условие (9) позволяет строить такие реализации методов, где для отыскания х/: можно использовать алгоритмы R2, R?> из § 1.3, основанные на процедуре отсечений 7Г3, в которой G — Dk, у = хк, Р = Рк. При выборе в них множества Мц в виде многогранника искомая точка находится как Хк — У, с помощью решения конечного числа задач линейного программирования.

Развитый в гл. 3 подход с параметризацией направлений распространяется далее на алгоритмы условной минимизации негладкой псевдовыпуклой функции максимума. В § 4.2 ставится задача (2),

где /о(х) = шах /,(х), D = {х G Rn : fi{x) < 0, г £ J2}, функции i6Ji

fi(x), i £ J, псевдовыпуклы и непрерывно дифференцируемы в Rn, а множества индексов Ji, J2 таковы, что ф 0, JiU J2 = J, Jifl«^ = 0> Для ее решения предлагается метод, в котором направление спуска на каждом шаге строится как линейная комбинация градиентов активных функций, задающих целевую функцию /0(х) и область D, т. е. в виде sk = — Е «¿/¿(к;.-)- Коэффициенты находятся путем

решения системы Е (f'j{^k), > Vk, j £ J(xk,£k), а, > 0,

i£j(xk,ek), E Qi = 1 при некоторых положительных щ, или

i£J{*k,ek)

решением задачи линейного программирования. Затем вычисляется точка Vj. согласно (8) и приближение xk+i из условия (3). При некоторых условиях выбора чисел ек, rjk, ßk доказана сходимость метода.

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

Использованный в § 4.2 подход можно перенести и на те методы, в которых минимаксными являются вспомогательные задачи построения итерационных точек или направлений перехода. В § 4.3 на примере одного алгоритма решения задачи (2), (6) показывается, каким образом идея параметризации направлений может применяться в методах центров. В предлагаемом алгоритме на к -ом шаге строится вспомогательная функция максимума 1'):(х) на основе измененной целевой функции и функций ограничений исходной задачи. В точке хк находится направление б/, в виде линейной комбинации активных градиентов функции 1г1,(х). Затем но направлению в к из точки хк. производится спуск в точку V/- с лучшим значением функции ^(ж), а приближение находится из условия 1<\(хк+1) < ('.'<:). С использованием методики В. Ф. Демьянова и методики § 4.2 доказана сходимость алгоритма. Обсуждаются его реализации и преимущества перед некоторыми методами центров для определенного типа задач.

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

В § 5.1 для задачи

тт{/0(х) | г £ (11)

с псевдовыпуклой непрерывно дифференцируемой целевой функцией строится общий метод, в котором переход от точек Хк к промежуточным точкам ук происходит в некоторых линейных многообразиях М(хк), а затем приближение £ 11п выбирается согласно условию (3). На к -ом шаге этого метода Выбирается вектор г к £ Лп и число £к > о так, чтобы II Гк ||< £к И дк = /¡¡(хк) + тк ф 0. Задается непустое подмножество индексов IIк С Н = {1, ...,п}, выбираются векторы Л*, г £ Нк, так, чтобы вектор д^ был их линейной комбинацией, и строится линейное многообразие

М(хк) = {хеЯп:х = хк+ £ аД, V а{ £ ДЛ.

Далее, отыскивается такая точка vk £ М(хк), что fa(vk) < шк -f 6к, 5к > 0, либо /„(«*) < (1 - Afc)/o(®t) + ХьшЪ 0 < Л < Хк < 1, где ш*к — min /о(х), i7(arfc) = {ж Е Д„ : х - хк + адк,а £ Ri}. При-

ближеиие CEk+i £ ftn, как уже отмечено, выбирается из условия (3).

Доказано, что при ек < е < оо Ук, 5к —> 0, к —> оо, и дополнительном условии {/¡¡(хк),гк) > -7 || /0(хк) ||2, 0 < 7 < 1 на вектора гк для последовательности {ж/,}, построенной этим методом, выполняется равенство (10). Кроме того, доказаны еще две теоремы сходимости метода при других условиях выбора чисел 8к и точек vk. Получены оценки скорости сходимости метода для псевдовыпуклых и сильно выпуклых функций /о(г).

Отметим, что размерности многообразий М(хк) задаются на каждом шаге произвольно от 1 до п. За счет большой свободы в выборе множеств М(хк), вспомогательных точек vk и приближений метод допускает значительное число реализаций, которые приводятся в § 5.2. Среди них - известные алгоритмы выпуклого программирования, их модификации и новые алгоритмы минимизации псевдовыпуклых функций. К известным алгоритмам, которые являются реализациями предложенного метода, относятся методы наискорейшего спуска, покоординатного спуска, обобщенный метод градиентного спуска, метод изменения масштабов, метод Ньютона с регулировкой шага, квазиныотоновские алгоритмы, варианты метода сопряженных градиентов и многие другие. Для каждого из этих методов, а также для всех предлагаемых новых алгоритмов в § 5.2 доказывается выполнение тех или иных условий теорем сходимости общего метода и теорем, касающихся оценок его скорости сходимости. Тем самым для многих исследуемых в § 5.2 методов выпуклого программирования и новых алгоритмов обосновывается возможность их использования для задачи псевдовыпуклого программирования (11) и доказываются оценки скорости сходимости для псевдовыпуклых и сильно выпуклых функций. Таким образом, предложенный в § 5.1 подход к разработке методов решения задачи (11) позволяет строить новые одношаговые и многошаговые алгоритмы с практически произвольными процедурами обновления, модифицировать известные методы, расширяя их возможности в выборе направлений и шаговых множителей, а также по единой методике исследовать сходимость методов и получать

оценки скорости сходимости. Кроме того, поскольку процесс отыскания приближения из условия (3) в методе не конкретизирован, то за счет чередования различных способов построения точек V/, и можно получать всевозможные смешанные алгоритмы на основе известных и новых методов без дополнительного обоснования их сходимости.

В отдельный параграф (§ 5.3) выделены еще два алгоритма решения задачи (11), которые идейно близки к общему методу из § 5.1, но формально в него не вкладываются и потому обосновываются по другой методике. Эти алгоритмы уместно отнести к классу методов спуска по группам переменных. В § 5.3 предлагаются два критерия отбора групп переменных, участвующих в итерационных переходах. Один из этих критериев выглядит следующим образом. Подмножество Щ С Н = {1,..., гг} номеров переменных, по которым производится спуск на к -ом шаге выбирается из условия

V [д/оЮ[ 4-, V [Д/о(»*)|

;ея*! "ь | ¡6Я1 I где 0 < а < а к < 1. Оба предлагаемых критерия, во-первых, просты для проверки, во-вторых, гарантируют сходимость методов указанного класса, и в-третьих, позволяют выбирать на каждом шаге число переменных, входящих в эти группы, любым от 1 до п, т. е. производить переход в подпространствах любой размерности. На базе этих критериев и строятся упомянутые алгоритмы спуска по группам переменных. В том же § 5.3 доказываются теоремы их сходимости, обосновываются оценки скорости сходимости для псевдовыпуклой и сильно выпуклой функции, описываются реализации. Среди этих реализаций есть известные методы выпуклого программирования, которые, благодаря доказанным и § 5.3 теоремам, могут использоваться при решении более общих задач псевдовыпуклого программирования. Как и в некоторых известных эвристических методах, в предлагаемых здесь алгоритмах допустимо чередование шагов в подпространствах быстрых и медленных переменных, причем, размерности этих подпространств можно задавать заранее на каждой итерации. За счет условия (3) выбора точек .Т/.+; алгоритмы допускают их комбинирование с другими методами из этого же или другого класса.

Следующие три параграфа главы посвящены исследованию устойчивости алгоритмов решения задачи (11) к ошибкам вычисления гра-

диентов. Устойчивость в том или ином смысле методов выпуклого программирования изучается во многих работах, но используемые там подходы в большинстве случаев опираются на то, что исследуемые методы применяются для минимизации выпуклых, а не псевдовыпуклых функций. Предлагаемый здесь подход позволяет исследовать устойчивость в указанном смысле методов как выпуклого, так и псевдовыпуклого программирования. Этот подход основывается па разработанной в § 5.4 общей схеме решения задачи (11), в которой заложена возможность неточного вычисления градиентов целевой функции в итерационных точках. Поскольку сходимость и оценки скорости сходимости доказываются для схемы с учетом погрешностей вычислений, то тем самым обосновывается устойчивость тех алгоритмов, которые вкладываются в эту схему и в которых погрешности вычисления градиентов удовлетворяют тем же условиям, что и в общей схеме. Предлагаемая схема близка к методу из § 5.1. Итерационные переходы в ней тоже осуществляются в некоторых линейных многообразиях М(ж;.), но построенных с использованием неточно вычисленных градиентов. За счет определенной свободы в выборе многообразий М(хк) схема допускает различные реализации, среди которых - известные и новые алгоритмы. В §§ 5.5, 5.6 для этих алгоритмов на основе сформулированного выше принципа исследуется их устойчивость в указанном смысле. При этом приходится доказывать, что каждый из алгоритмов является частным случаем общей схемы. В указанных параграфах исследованы на устойчивость метод обобщенного градиентного спуска, так называемый нелинейный метод, методы покоординатного спуска и Ньютона, квазиньютоновские алгоритмы, метод многопараметрического поиска, а также многие другие известные и новые одношаговые и многошаговые алгоритмы. Отметим, что для многих исследованных алгоритмов справедливы оценки скорости сходимости общей схемы, полученные с учетом погрешностей вычисления градиентов, для псевдовыпуклых и сильно выпуклых функций.

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

ритмами.

Зачастую практические оптимизационные задачи вида (2) обладают специфической структурой за счет особенностей задания целевой функции или допустимого множества. В гл. 6 приведены соответствующие примеры и ссылки. Одной из таких особенностей можно считать задание области И в (2) в виде прямого произведения выпуклых замкнутых множеств г = 1,..., га, из пространств вообще говоря, различных размерностей. В § 6.1 строятся два метода минимизации гладкой псевдовыпуклой функции на множестве указанного вида. Методы характерны тем, что на каждом шаге итерационный переход при желании может производиться в иих лишь по части переменных задачи. В диссертации предлагается отличный от известных принцип выбора групп переменных, по которым производится спуск на каждом шаге. Формирование этих групп происходит в результате решения т вспомогательных задач минимизации некоторых вспомогательных функций на множествах Построенные на основе предложенного принципа методы отличаются друг от друга тем, что спуск на к -ом шаге в выбранном подпространстве происходит либо по конкретным направлениям, либо с большой долей свободы, привлекая любые релаксационные процедуры. Заложенный в методах критерий выбора групп переменных гарантирует их сходимость, позволяет заранее задавать желательную размерность подпространств, в которых производится спуск, дает возможность построения различных реализаций. Отметим, что предложенные методы можно комбинировать с другими алгоритмами, а решение задач минимизации вспомогательных функций на множествах Д можно проводить одновременно на многопроцессорных ЭВМ.

В § 6.2 ставится еще одна задача гшп{/,п(х) | х £ Л} специального вида. Функция представляет собой функцию максимума, характерную тем, что каждая из составляющих ее непрерывных функций /¿(ж,-), г = 1,...,7п, зависит от переменных хг £ не связанных с переменными остальных функций, а область £>, как и в § 6.1, задана в виде прямого произведения выпуклых замкнутых множеств С И,:, ■ Для поставленной задачи строится и обосновывается метод, который также можно отнести к алгоритмам спуска по группам переменных. Переход из текущей итерационной точки хК = (ж^, ...,3;^,), Е производится в методе лишь по тем переменным х,, для которых соот-

ветствующие функции ¡г(х,) являются активными в точке хк. Спуск по выбранным переменным ж, производится в областях I); с привлечением любых, вообще говоря различных, сходящихся алгоритмов.

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

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

Публикации

1. Заботин И. Я. О методах безусловной минимизации функции, использующих симплекс // Исслед. по прикл. матем. - Казань: Изд -во КГУ, 1979. - Вып. 7. - С. 55 - 64.

2. Заботин И. Я. К вопросу о выборе направлений спуска в задачах безусловной минимизации функций // Исслед. по прикл. матем. - Казань: Изд - во КГУ, 1981. - Вып. 9. - С. 37 - 42.

3. Заботин И. Я. Об одном методе типа условного градиента с частичным погружением допустимого множества // Системы программного обеспечения решения задач оптимального планирования. Тез. докл. 7 Всесоюз. симп. (Нарва - Иыэсуу, 16 - 24 анр. 1982 г.) - М.: ЦЭМИ АН СССР, 1982. - С. 132.

4. Заботин И. Я. О методах безусловной минимизации функций с наилучшими относительно множества направлениями спуска // Изв. вузов. Математика. - 1982. - N 7. - С. 11 - 16.

5. Заботин И. Я. Один вариант метода Ньютона с погружением допустимого множества. - Казань, КГУ, 1983. - 11 с. - Деп. в ВИНИТИ 20.01.83, N 353 - 83.

6. Заботин И. Я. Итеративная регуляризация метода условного градиента с погружением допустимого множества. - Казань, КГУ,

1983. - 15 с. - Деп. в ВИНИТИ 16.02.83., N 852 - 83.

7. Заботин И. Я., Кобчиков А. В., Крейнин М. И., Лямин Е. В. Статистический метод проектирования информационно - управляющих систем // Статистические методы исследования функционирования сложных технических систем (качество, эффективность, надежность). Материалы Всесоюз. науч. - практич. сем. (Москва, 24 - 26 мая 1983 г.) - М.: МЭСИ, 1983. - Ч. 1. - С. 212 - 213.

8. Заботин И. Я. Метод обобщенно - опорных гиперплоскостей для решения задачи математического программирования. - Казань, КГУ, 1982. - Деп. в ВИНИТИ 25.08.83., N 4633 - 83. - С. 19 - 28.

9. Заботин И. Я., Боглаевский О. В. О нерелаксационном процессе в методе минимизации функций с частичным погружением допустимого множества. - Казань, КГУ, 1982. - Деп. в ВИНИТИ 25.08.83., N 4633 - 83. - С. 29 - 34.

10. Заботин И. Я., Кораблев А. И. Метод условного е - субградиента // Изв. вузов. Математика. - 1983. - N 9. - С. 22 - 26.

11. Заботин И. Я. Метод типа проекции градиента, использующий погружение допустимого множества // Исслед. по прикл. матем. -Казань: Изд - во КГУ, 1984. - Вып. 11, часть 1. - С. 3 - 11.

12. Заботин И. Я., Лямин Е. В. Об одном варианте метода условного градиента // Исслед. по прикл. матем. - Казань: Изд - во КГУ,

1984. - Вып. 11, часть 1. - С. 11 - 23.

13. Заботин И. Я., Кобчиков А. В., Лямин Е. В. Применение одного варианта метода условного градиента для численного решения задачи синтеза информационно-управляющей системы // Прием и обработка информации в сложных информационных системах. - Казань: Изд - во КГУ, 1984. - Вып. 14. - С. 27 - 34.

14. Заботин И. Я., Кораблев А. И. Метод условного г - субградиента для минимизации квазивыпуклых функций // Проблемы теоретической кибернетики. Материалы 7 Всесоюз. конф. - Иркутск, 1985. - Ч. 2. - С. 64 - 65.

15. Заботин И. Я., Крейнин М. И. Релаксационный субградиентный метод минимизации строго выпуклых функций // Исслед. по прикл. матем. - Казань: Изд - во КГУ, 1987. - Вып. 14. - С. 34 - 42.

16. Заботин И. Я., Кобчиков А. В. Выбор оптимальных времен

функционирования подсистем в информационно - управляющих системах // Прием и обработка информации в сложных информационных системах. - Казань: Изд - во КРУ, 1987. - Вып. 16. - С. 10 -19.

17. Заботил И. Я. О минимизации функции максимума с разделяющимися переменными // Проблемы теоретической кибернетики. Тез. докл. 8 Всесоюз. конф. (июль, 1988) - Горький, 1988. - Ч. 1. - С. 119.

18. Заботин И. Я. Субградиентный метод отыскания седловой точки выпукло - вогнутой функции // Исслед. но прикл. матем. - Казань: Изд - во КРУ, 1988. - Вып. 15. - С. 6 - 12.

19. Заботин И. Я. О двух декомпозиционных методах типа координатного спуска // Методы математич. программирования и программное обеспечение. Тез. докл. б науч. конф. (Свердловск, 27 февр.

- 3 марта 1989 г.) - Свердловск: УрО АН СССР, 1989. - С. 94.

20. Заботин И. Я. О декомпозиционных методах решения некоторых экстремальных задач // Методы оптимизации и их приложения. Материалы Междунар. Байкальской школы - семинара (Иркутск, 10

- 19 сент. 1989 г.) - Иркутск: СЭИ СО АН СССР, 1989. - С. 95.

21. Заботин И. Я. О минимизации функции максимума специального вида // Исслед. по прикл. матем. - Казань: Изд - во КГУ, 1989.

- Вып. 16. - С. 101 - 108.

22. Заботин И. Я. О двух декомпозиционных методах условной минимизации функций // Системы программного обеспечения решения задач оптимального плакирования. Тез. докл. 11 Всесоюз. симп. (Кострома, 21 - 29 мая 1990 г.) - М: ЦЭМИ АН СССР, 1990. - С. 22.

23. Заботин И. Я., Кобчиков А. В. О выборе оптимальных соотношений между массами блоков радиоэлектронной системы // Прием и обработка информации в сложных информационных системах. - Казань: Изд - во КГУ, 1990. - Вып. 18. - С. 64 - 70.

24. Заботин И. Я., Кобчиков А. В., Пилюгин А. Г. О выборе оптимального числа радиолокационных станций в многопозиционных радиоэлектронных системах // Прием и обработка информации в сложных информационных системах. - Казань: Изд - во КГУ, 1990. - Вып. 18. - С. 70 - 75.

25. Заботин И. Я., Кобчиков А. В. О реализациях некоторых методов, применяемых при решении оптимизационных задач проектирования // Автоматика и телемеханика. - 1991. - N 1. - С. 169 -

26. Заботии И. Я. Методы спуска по группам переменных для условной минимизации функций // Проблемы теоретической кибернетики. Тез. докл. 11 Всесоюз. конф. (сентябрь, 1.990) - Волгоград, 1990. - Ч. 1(2). - С. 26.

27. Заботин И. Я. О некоторых методах спуска но группам переметных // Исслед. по прикл. матем. - Казань: Изд - во КГУ, 1992. -Вып. 19. - С. 24 - 33.

28. Заботин И. Я. Методы спуска по группам переменных для одного класса задач условной минимизации // Исслед. по прикл. матем.

- Казань: Изд - во КГУ, 1992. - Вып. 18. - С. 48 - 59.

29. Заботин И. Я. Алгоритмы с комбинированием активных градиентов для отыскания условного минимакса // Изв. вузов. Математика. - 1993. - N 12. - С. 52 - 58.

30. Заботин И. Я. Метод минимизации с выбором направлений в виде комбинации активных градиентов // Математич. программирование и приложения. Тез. докл. 9 Всерос. конф. (Екатеринбург, 27 февр. - 3 мар. 1995 г.) - Екатеринбург, 1995. - С. 98.

31. Заботин И. Я., Князев Е. А. Об одном варианте метода центров с адаптацией параметра // Математич. программирование и приложения. Тез. докл. 9 Всерос. конф. (Екатеринбург, 27 февр. - 3 мар. 1995 г.) - Екатеринбург, 1995. - С. 99.

32. Заботин И. Я., Князев Е. А. О некоторых вариантах параметризованного метода центров // Методы оптимизации и их приложения. Материалы 10 Байкальской Междунар. школы - семинара (Иркутск, 14 - 19 авг. 1995 г.) - Иркутск, 1995. - С. 99.

33. Заботин И. Я., Князев Е. А. Вариант параметризованного метода центров // Изв. вузов. Математика. - 1995. - N 12. - С. 26 -32.

34. Заботин И. Я. Метод условной минимизации с параметрическим заданием подходящих направлений // Изв. вузов. Математика.

- 1996. - N 12. - С. 17 - 29.

35. Заботин И. Я. Об алгоритмах минимизации с параметризованными направлениями спуска // Математич. программирование и приложения. Тез. докл. 10 Всерос. конф. (Екатеринбург, 24 - 28 февр. 1997 г.) - Екатеринбург, 1997. - С. 96.

36. Заботин И. Я. Алгоритмы прекционного типа с нараметричес-

ким заданием подходящих направлений // Проблемы оптимизации и экономические приложения. Материалы Междунар. конф. (Омск, 1 -5 июля 1997 г.) - Омск, 1997. - С. 73.

37. Заботин И. Я. Алгоритм второго порядка с параметризованными направлениями для задач условной оптимизации // Изв. вузов. Математика. - 1997. - N 12. - С. 62 - 72.

38. Заботин И. Я. Многошаговые алгоритмы безусловной минимизации псевдовыпуклых функций // Методы оптимизации и их приложения. Труды 11 Междунар. Байкальской школы - семинара (Иркутск, Байкал, 5-12 июля 1998 г.) - Т. 1. - Иркутск, 1998. - С. 77 -80.

39. Заботин И. Я. Об алгоритмах второго порядка с параметрическим заданием подходящих направлений // Методы оптимизации и их приложения. Труды 11 Междунар. Байкальской школы - семинара (Иркутск, Байкал, 5-12 июля 1998 г.) - Т. 1. - Иркутск, 1998.

- С. 51.

40. Заботин И. Я. Об одном подходе к построению алгоритмов безусловной минимизации псевдовьшуклых функций // Изв. вузов. Математика. - 1998. - N 12. - С. 29 - 39.

41. Заботин И. Я. Некоторые многошаговые методы безусловной минимизации и их устойчивость // Математич. программирование и приложения. Тез. докл. 11 Всерос. конф. (Екатеринбург, 22 - 26 февр. 1999 г.) - Екатеринбург, 1999. - С. 110.

42. Заботин И. Я. Об устойчивости некоторых методов безусловной минимизации // Проблемы теоретической кибернетики. Материалы 12 Междунар. конф. (Нижний Новгород, 17 - 22 мая, 1999 г.) - Ч. 1.

- М.: МГУ, 1999. - С. 75.

43. Заботин И. Я. Об алгоритмах с параметризованными направлениями в псевдовыпуклом программировании // Дискретный анализ и исследование операций. Материалы Междунар. конф. (Новосибирск, 26 июня - 1 июля 2000 г.) - Новосибирск, 2000. - С. 110.

44. Заботин И. Я. Об устойчивости алгоритмов безусловной минимизации псевдовыпуклых функций // Изв. вузов. Математика. -2000. - N 12. - С. 33 - 48.

45. Заботин И. Я. Один способ исследования устойчивости алгоритмов безусловной минимизации псевдовыпуклых функций // Алгоритмический анализ неустойчивых задач. Тез. докл. Всерос. науч.

конф. (Екатеринбург, 26 февр. - 2 марта 2001 г.) - Екатеринбург, Изд

- во Уральского ун - та, 2001. - С. 216.

46. Заботин И. Я. О сходимости алгоритмов безусловной минимизации псевдовыпуклых функций при наличии помех // Проблемы теоретич. кибернетики. Материалы 13 Междунар. конф. (Казань, 27

- 31 мая, 2002 г.) - Ч. 1. - М.: Изд - во центра прикладн. исследований при механико - математич. фак. МГУ, 2002. - С. 65.

47. Заботин И. Я. Проекционные алгоритмы с параметризованными направлениями спуска в псевдовыпуклом программировании // Исслед. по прикл. матем. и информатике - Казань: Изд - во Казанск. матем. общества, 2001. - Вып. 23. - С. 67 - 81.

48. Заботин И. Я. Вариант метода линеаризации с параметрическим заданием направлений итерационного перехода // Дискретный анализ и исследование операций. Материалы Российской конф. (Новосибирск, 24 - 28 июня 2002 г.) - Новосибирск: Изд - во Института математики, 2002. - С. 162.

49. Заботин И. Я. Метод с параметризованными направлениями для минимизации псевдовыпуклой функции / / Актуальные проблемы математического моделирования и информатики. Материалы науч. конф. (Казань, 30 янв. - 6 февр. 2002 г.) - Казань: Изд - во Казанск. матем. общества, 2002. - С. 41 - 42.

50. Заботин И. Я. Метод минимизации негладкой строго псевдо-выиуклой функции // Математич. программирование и приложения. Тез. докл. 12 Всерос. конф. ( Екатеринбург, 24 - 28 февр. 2003 г. ) -Екатеринбург, 2003. - С. 109.

51. Заботин И. Я. Метод условной минимизации строго выпуклых недифференцируемых функций // Проблемы оптимизации и экономические приложения. Материалы Всерос. конф. (Омск, 1-5 июля 2003 г.) - Омск: Наследие. Диалог Сибирь, 2003. - С. 120.

52. Заботин И. Я. Релаксационные алгоритмы условной минимизации негладких строго псевдовыпуклых функций // Изв. вузов. Математика. - 2003. - N 12. - С. 62 - 70.

53. Заботин И. Я. Алгоритм условной минимизации строго псевдовыпуклых функций // Алгоритмический анализ неустойчивых задач. Тез. докл. Всерос. конф. (Екатеринбург, 2-6 февр. 2004 г.) - Екатеринбург: Изд - во Уральского ун - та, 2004. - С. 273 - 274.

54. Заботин И. Я. О методах условной минимизации негладких

строго псевдовыпуклых функций // Дискретный анализ и исследование операций. Материалы Российской конф. (Новосибирск, 24 - 28 июня 2004 г. ) - Новосибирск: Изд - во Института математики, 2004.

- С. 162.

55. Заботин И. Я. Одна общая схема решения задачи математического программирования и ее использование в алгоритмах минимизации псевдовыпуклых функции // Сеточные методы для краевых задач и приложения. Материалы Всерос. семинара. (Казань, 1-4 окт. 2005 г.) - Казань: Изд - во К ГУ 2005. - С. 83 - 86.

56. Заботин И. Я. Две процедуры отсечений и их использование в методах минимизации // Проблемы оптимизации и экономические приложения. Материалы 3 Всерос. конф. (Омск, 11 - 15 июля 2006 г.)

- Омск, 2006. - С. 139.

57. Заботин И. Я. Схема решения задачи псевдовыпуклого программирования и ее реализации на основе процедур отсечений // Инфрормационный бюллетень .АГ 11 Ассоциации математического программирования. Конф. "Математич. программирование и приложения" (Екатеринбург, 26 фев. - 2 мар. 2007 г.) - Екатеринбург: УрО РАН, 2007. - С. 47 - 48.

58. Заботин И. Я. Применение некоторых процедур отсечений в методах псевдовыпуклого программирования // Проблемы теоретич. кибернетики. Материалы 15 Междунар. конф. (Казань, 2-7 июня 2008 г.) - Казань: Отечество, 2008. - С. 38.

59. Заботин И. Я. Общая процедура отсечений и ее использование в реализациях некоторых алгоритмов минимизации // Методы оптимизации и их приложения. Труды 14 Междунар. Байкальской школы

- семинара. - Т. 1. - Иркутск, ИСЭМ СО РАН, 2008. - С. 245 - 253.

60. Заботин И. Я. Метод с параметризацией направлений спуска и его реализации на основе процедур аппроксимации множеств // Проблемы оптимизации и экономические приложения. Материалы 4 Всерос. конф. (Омск, 29 июня - 4 июля 2009 г.) - Омск, 2009. - С. 139.

Подписано в печать 23.11.2009. Форм. 60 х 84 1/16. Гарнитура «Тайме». Печать ризографическая. Печ.л. 2. Тираж 120. Заказ 391.

Лаборатория оперативной полиграфии Издательства КГУ 420045, Казань, Кр.Позиция, 2а Тел. 231-52-12

Введение

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

1.1 Общие процедуры аппроксимации с частичным погружением допустимого множества для задачи математического программирования

1.2 Общая процедура аппроксимации с полным погружением допустимого множества для задачи математического программирования.

1.3 Две общие схемы отыскания точки выпуклого множества и их реализации

2 Методы условной минимизации гладких псевдовыпуклых функций с реализациями на основе процедур аппроксимации

2.1 Метод условной минимизациии гладких псевдовыпуклых функций

2.2 Некоторые реализации метода из

§ 2.1.

2.3 Метод типа условного градиента для задачи псевдовыпуклого программирования

2.4 Реализации метода из

§ 2.3 на основе частичного погружения допустимого множества

2.5 Метод проекционного типа в псевдовыпуклом программировании и его реализации на основе процедур аппроксимации множеств.

2.6 Метод второго порядка.

3 Алгоритмы с параметризованными направлениями для условной минимизации гладких псевдовыпуклых функций

3.1 Вспомогательные результаты.

3.2 Метод типа условного градиента с параметрическим заданием подходящих направлений

3.3 Реализация метода типа условного градиента с параметрическим заданием подходящих направлений на основе процедур аппроксимации

3.4 Проекционные алгоритмы с параметризованными направлениями спуска

3.5 Проекционные алгоритмы с параметризованными направлениями, использующие аппроксимацию допустимого множества.

3.6 Алгоритм второго порядка с параметризованными направлениями

3.7 Алгоритм второго порядка с параметризованными направлениями, использующий частичное погружение допустимого множества.

3.8 Вариант метода возможных направлений Зойтендейка с параметризованными направлениями для задачи псевдовыпуклого программирования

3.9 Вариант метода линеаризации с параметризованными направлениями итерационного перехода.

4 Методы условной минимизации негладких псевдовыпуклых функций

4.1 Релаксационные алгоритмы условной минимизации негладких строго псевдовыпуклых функций.

4.2 Алгоритмы отыскания условного дискретного минимакса.

4.3 Вариант параметризованного метода центров.

5 Алгоритмы безусловной минимизации псевдовыпуклых функций и исследование их устойчивости

5.1 Общий метод безусловной минимизации гладких псевдовыпуклых функций

5.2 Одношаговые и многошаговые алгоритмы, как реализации общего метода безусловной минимизации.

5.3 Методы спуска по группам переменных

5.4 Общая схема исследования устойчивости алгоритмов безусловной минимизации гладких псевдовыпуклых функций.

5.5 Исследование устойчивости некоторых одношаговых алгоритмов.

5.6 Исследование устойчивости некоторых многошаговых алгоритмов

6 Методы решения специальных и прикладных задач псевдовыпуклого программирования

6.1 Методы спуска по группам переменных для одного класса задач условной минимизации.

6.2 Метод условной минимизации функции максимума специального вида

6.3 Субградиентный метод отыскания седловых точек.

6.4 Использование предложенных методов при решении некоторых прикладных задач.

В связи с постоянно возникающими на практике оптимизационными задачами нелинейное программирование остается актуальным направлением исследований специалистов, работающих в области математической кибернетики и вычислительной математики. Большинство работ по нелинейному программированию относится к наиболее изученному его разделу выпуклого программирования. Различные подходы к построению методов выпуклого программирования и исследованию их сходимости предложены в [2, 8, 11, 16, 17, 21, 22, 23, 24, 26, 28, 34, 36, 38, 42, 45, 47, 48, 53, 54, 55, 58, 124, 133, 134, 140, 141, 143, 161, 167, 168, 173, 176, 178, 179, 185, 194, 200, 201, 205, 207], и этот перечень работ далеко не полон. К настоящему времени разработано значительное число методов минимизации как гладких, так и негладких выпуклых функций, ^и сложилась определенная их классификация. Можно привести примеры довольно больших классов методов выпуклого программирования, исследованных, в частности, в указанных выше работах. Это методы возможных направлений, методы типа линеаризации, штрафных и барьерных функций, методы центров, модифицированных функций Лагранжа и др. Большую группу методов минимизации недифференцируемых выпуклых функций образуют основанные на идеях метода обобщенного градиентного спуска [207] так называемые субградиентные методы (напр., [42, 57, 73, 151, 169, 174, 181, 202, 207]), связанные с методами фейеровских приближений (напр., [26, 54]), методами отсечений (напр., [6, 169]). Близкими к этой группе являются е - субградиентные методы, предложенные сначала в виде алгоритмов типа наискорейшего спуска для минимаксных задач (см., напр., [43]) и разработанные затем для минимизации как функций максимума, так и произвольных выпуклых функций (напр., [31, 42, 43, 68, 131, 159, 173, 186, 200, 201, 207, 223, 224, 230, 231]). В отдельные группы методов выпуклого программирования можно выделить алгоритмы погружений - отсечений (напр., [6, 7, 9, 21, 62, 69, 133, 161, 207, 210, 220, 229]), а также основанные на идеях, подробно описанных в [23, 24, 195] , методы регуляризации и итеративной регуляризации (напр., [25, 46, 189, 196]). Отметим, что в тесной связи с разработкой методов выпуклого программирования находились и находятся вопросы оценки их эффективности (напр., [7, 169, 170, 171, 193, 210]).

Однако, практикой востребованы и методы минимизации функций более общих, чем выпуклые. Исследованиям задач нелинейного программирования, не входящих в раздел выпуклого программирования, и построению методов их решения также посвящено немало публикаций (напр., [18, 30, 49, 128, 129, 130, 152, 164, 171, 172, 177, 179, 183, 190, 191, 192, 195, 203, 204, 212, 213, 215, 216, 218, 225, 228]). Среди них есть работы по методам решения многоэкстремальных задач, методам регуляризации, квазивыпуклому программированию и др. В последнее время интенсивно исследуются задачи равновесного программирования (напр., [4, 5, 15, 35, 153, 154, 155]), продолжают строиться методы решения вариационных неравенств (напр., [12, 13, 142, 148, 156, 182, 221, 222]).

Из задач математического программирования более общих, чем задача выпуклого программирования, ближе других к последней стоит задача псевдовыпуклого программирования. Понятие псевдовыпуклости для дифференцируемых функций было предложено еще в 1965 году О. Мангасарианом ([226]). В 1974 году в работе Заботина Я. И. и Кораблева А. И. ([127]) введено определение недифференцируемых псевдовыпуклых функций и изучены некоторые их свойства. Хотя задача псевдовыпуклого программирования сформулирована уже давно и методам ее решения также уделено определенное внимание (см., напр., [11, 29, 98, 105, 126, 127, 135, 157, 158, 214, 217, 226, 227, 232]), раздел псевдовыпуклого программирования изучен еще далеко не полно. При разработке и исследовании методов минимизации псевдовыпуклых функций возникают определенные трудности, связанные со спецификой задачи. Заметим, что псевдовыпуклые функции, действительно, близки к выпуклым по многим важным свойствам. Например, их лебеговы множества также являются выпуклыми, всякий локальный минимум совпадает с глобальным, множество точек минимума выпукло. Однако, хорошо изученный и развитый аппарат выпуклого анализа, на котором основаны построение методов выпуклого программирования и методика обоснования их сходимости, обычно не удается непосредственно использовать для разработки и обоснования методов псевдовыпуклого программирования.

Поскольку класс псевдовыпуклых функций (их примеры можно найти, в частности, в [11, 158]) существенно шире класса выпуклых функций, и псевдовыпуклые экстремальные задачи возникают на практике (напр., [158]), то дальнейшие исследования по численным методам псевдовыпуклого программирования полезны как с теоретической, так и с практической точки зрения. Данная диссертационная работа относится к исследованиям в области псевдовыпуклого программирования. Она посвящена построению методов условной и безусловной минимизации гладких и негладких псевдовыпуклых функций на основе параметризации направлений итерационного перехода и аппроксимации множеств. При этом разрабатываемые методы учитывают специфику как дифференцируемых, так и недифференцируемых псевдовыпуклых функций. Заметим, что за счет схожести обсуждаемых разделов математического программирования многие идеи могут быть естественным образом перенесены из выпуклого в псевдовыпуклое программирование. Однако, целью работы является не формальное обобщение и распространение известных алгоритмов выпуклого программирования на псевдовыпуклый случай, а разработка новых подходов к построению конструктивных методов псевдовыпуклого программирования с легко реализуемыми алгоритмами, а также новых методик исследования сходимости этих методов.

Несмотря на большое число работ по методам нелинейного программирования, и сейчас еще численная реализация многих из них вызывает значительные сложности. Одной из причин трудной реализуемости методов является то, что в них при построении итерационных точек приходится решать вспомогательные задачи, которые сами по себе немногим легче исходной задачи минимизации. В качестве примеров могут служить различные варианты метода условного градиента, проекционные алгоритмы, варианты метода Ньютона и ряд других алгоритмов выпуклого программирования, где для нахождения направлений итерационного перехода необходимо решать задачи условной минимизации вспомогательных функций с использованием всех или части ограничений исходной задачи. При задании допустимых множеств нелинейными неравенствами это требует больших вычислительных затрат. Кроме того, во многих методах (в том числе и только что упомянутых) размерности этих вспомогательных задач, т. е. число переменных и ограничений в них, совпадают с размерностями исходной задачи, а иногда и превышают их, что сказывается при решении такими методами задач большой размерности. Даже в тех методах, где, несмотря на общий вид ограничений, вспомогательные задачи построения итерационных точек явно упрощаются по сравнению с исходной задачей (метод возможных направлений Зойтендейка [22, 134, 143] , метод линеаризации [184, 185] , методы отсечений [21] и т. д.), число переменных (а часто и ограничений) в этих подзадачах не уменьшается по отношению к исходной задаче.

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

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

Коротко обсудим эти подходы. Сразу отметим, что в настоящей работе процедуры аппроксимации множеств применяются с иными, чем в известных методах погружений - отсечений, целями. Идея аппроксимации множеств, в частности на основе операций погружений и отсечений, используется в математическом программировании довольно давно. В том или ином виде она применяется для решения задач выпуклого программирования, многоэкстремальных задач, задач целочисленного программирования и др. (кроме названных выше работ, см. также [3, 24, 34, 61, 63, 64, 66, 66, 69, 70, 149, 150, 169, 175, 184, 185]). Так в методе опорных множеств [21] для задачи выпуклого программирования и в некоторых других методах погружений (напр., [9, 21, 66, 133, 220]) аппроксимация допустимого множества исходной задачи использована с целью упрощения подзадач отыскания итерационных точек следующим образом. Строится последовательность вложенных друг в друга множеств, как правило многогранников, содержащих допустимую область, и точки хк минимума на них целевой функции принимаются за приближенные решения задачи выпуклого программирования. Каждое из аппроксимирующих множеств получается из предыдущего путем отсечения найденной точки Хк

В данной работе при построении методов условной минимизации гладких и негладких псевдовыпуклых функций также используются погружающие множества. Однако, разработанные здесь процедуры аппроксимации допустимого множества D или его подмножеств Dk применяются в предложенных методах только для нахождения некоторых вспомогательных направлений s,t, а не самих приближений хк. В отличие от упомянутых известных методов погружений - отсечений последовательности {хк) строятся здесь принадлежащими D. Переход к очередной точке xk+i для каждого к = 0,1,. осуществляется так, что значение /0(2^+1) целевой функции в ней не превосходит значения /о(ж) во вспомогательной точке Vk — хк + pkski что позволяет еще распоряжаться выбором шагов рк и способами построения самой итерационной точки xk+i- При этом размерности аппроксимирующих множеств Мк, использующихся для отыскания направлений Sfc, могут отличаться от размерности dim D множества D, если Мк строятся для подмножеств Dk С D, имеющих меньшую, чем D, размерность. Заметим, что разработанные принципы аппроксимации позволили также сделать реализуемыми некоторые известные методы выпуклого программирования, которые трудноприменимы для задач с ограничениями общего вида.

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

Диссертация состоит из шести глав. Опишем последовательно содержание каждой из них.

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

В § 1.1 разработаны общие методы решения задачи гшп д{х), (0.1) где функция д(х) непрерывна в п - мерном евклидовом пространстве а множество (7 задано пересечением конечного числа выпуклых замкнутых множеств Gj С о о € <7, с непустой внутренностью й], причем, возможен, в частности, случай С— 0. Первый метод (процедура 7Гх) вырабатывает последовательность приближенных решений € Мг \ С, I — 0,1,., где - вложенные друг в друга вообще говоря неограниченные множества, содержащие хотя бы одно решение задачи (0.1). Аппроксимирующее множество Мг+1 строится на основе предыдущего М\ с использованием вспомогательных о точек Уз £0] путем отсечения от Мг- точки у{ конечным числом обобщенно - опорных гиперплоскостей. Обсуждаются реализации этой схемы, проводится сравнение ее с известными методами погружения, обосновывается сходимость. Приводится итерационный процесс решения задачи (0.1), обобщающий первую процедуру на случай, когда множества С^ принадлежат некоторому линейному многообразию меньшей, чем п, размерности.

В п.4 § 1.1 приводятся две постановки задачи минимизации д(х) на множестве С? с заранее заданной точностью. Доказывается, что предложенными процедурами отсечений в обоих случаях такая задача решается за конечное число шагов. При этом предлагаются простые практические критерии остановки работы процедур. Один из таких способов приближенного решения задачи (0.1) с наперед заданной точностью будет применяться далее для различных вспомогательных функций д(х) и множеств С? в реализациях предлагаемых методов псевдовыпуклого программирования при построении направлений итерационного перехода.

В п.5 § 1.1 для приближенного решения задачи (0.1) строится еще одна аналогичная 7Г1 процедура отсечений 7Гх, в которой точки уг выбираются принадлежащими допустимой области G. Показывается, что процедурой тх\ можно строить за конечное число шагов подходящие для функции д(х) относительно G направления в стационарных неэкстремальных точках. Эта процедура может быть полезна, например, в случае, когда в задаче (0.1) целевая функция квазивыпукла.

Далее, в § 1.2 предлагается в виде процедуры тг2 еще один общий метод решения задачи (0.1), близкий к процедуре 7гь в котором итерационные точки jjlt г = 0,1,., являются точками приближенного минимума на аппроксимирующих множествах Mi вспомогательных функций д{(х) = д(х) + а^(х). Для выбора чисел oii и функций k{x) имеются большие возможности. В лемме 1.4 обосновано, что любая предельная точка последовательности Щ} принадлежит множеству G, а в теоремах 1.1-1.4 доказана сходимость метода для различных способов задания последовательностей {«¿} и {/¿(z)}. В замечаниях 1.7 - 1.10 показано, что при определенных способах выбора функций U(x) и других параметров процедуру тгг можно интерпретировать как варианты некоторых известных методов, например, метода регуляризации, метода барьерных функций, штрафных функций.

В третьем параграфе гл. 1 на идеях § 1.1 построены две общие схемы отсечений для нахождения точки множества G (см. процедуры 7Гз,7Гз). Первая из них по сути также является методом решения задачи (0.1), где целевая функция имеет вид д(х) = шах (р, х - у), (0.2) о а Р - конечное множество обобщенно-опорных к G в точке у G векторов. Эта процедуо ра не требует знания вспомогательных точек yj EGj, которые используются в тг^яг на-каждом шаге при построении отсекающих гиперплоскостей. Роль yi играет здесь точка у, а отсечения строятся в точках ^ е (y,Vi)- Вторая из предложенных схем отличается от первой тем, что при нахождении точек yi множество Р в (0.2) меняется от шага к шагу. В результате использования любой из процедур 7Г3, будет найдена точка у{ е G или построится последовательность {уг}, у которой (см. лемму 1.5) любая предельная точка принадлежит G. В связи с этим 7Гз,7Гз действительно можно рассматривать как схемы отыскания точки выпуклого множества, однако подчеркнем, что ниже они будут применяться только как практические способы построения направлений спуска в предлагаемых методах минимизации. На основе замечаний 1.13, 1.14 и леммы 1.6 в п.2 данного параграфа приводятся примеры использования процедур 7Гз,7Гз. В виде алгоритмов Rl - RA описываются и обосновываются (утверждения 1.1 - 1.4) некоторые реализации этих процедур для множеств G специального вида. Во всех реализациях удобно выбирать начальное погружающее множество Mq выпуклым многогранником, a pj отыскивать как точки минимума функции (0.2) на множествах Mi. Доказано, что для гладкой или негладкой псевдовыпуклой функции /(ж) алгоритмами Ri - можно построить за конечное число шагов подходящее в точке у 6 D направление, выбирая в процедурах 7Гз,7Гз в качестве G лебегово множество

E(f,D,y) = Rn :xeD, f(x) < f(y)}.

Все относящиеся к гл. 1 результаты получены без участия соавторов и опубликованы в работах [62, 66, 113, 115, 119, 120].

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

В §§ 2.1, 2.3, 2.5 предложены три метода решения задачи mm{f0(x) | х 6 D}, (0.3) где множество D С Rn выпукло и замкнуто, dimZ) < п, а функция fo(x) псевдовыпукла и непрерывно дифференцируема. Первые два метода используют идеи метода условного градиента, а третий - метода проекции градиента. Предлагаемые методы объединены следующей общей схемой. На к - ом шаге методов выбираются множества Dk С Rn, удовлетворяющие введенным в тех же параграфах условиям Л, В или С (причем, допускается выполнение неравенств dim Dk < dim D), в множествах Dк отыскиваются некоторые вспомогательные точки хк, направления Sk = Хк — хк используются для нахождения дополнительных точек ^ G Д а очередное приближение € D строится так, что

Мхк+i) < /оЫ- (0-4)

Методы отличаются друг от друга принципами выбора множеств £)fc и способами задания точек Хк G Dk- При этом множества Dk могут полностью или частично содержать область D, а могут и содержаться в ней. Если положить в методах

Dk = D, xk+i = vk = xk-\- ßksk, то при Хк = argmin{^/o(x/.), х — х¡^j \ х G Dk} первые два метода совпадают с методом условного градиента, а при Хк — — Vkf'o(xk), Dk) третий метод является вариантом метода проекции градиента. Отметим, что в предложенном варианте метода проекции градиента традиционная операция проектирования вспомогательной точки (даже при ее выходе из D) может опускаться на некоторых итерациях, что полезно с практической точки зрения. Доказаны теоремы сходимости методов, получены оценки их скорости сходимости для всех случаев задания точек как с условием релаксации, так и без него.

В §§ 2.2, 2.4, 2.5 предлагаются реализации этих методов, основанные на различных способах задания множеств Д; и на конечных процедурах тгх, 7Гз построения точек Хк, в которых С? = Д,, у! — у = X/,. При выборе в тгх, 7г3 начального погружающего множества М0 в виде многогранника точки хк в таких реализациях будут находиться путем решения задач линейного или квадратичного программирования. В § 2.4 приводятся результаты численных экспериментов, проведенных с первыми двумя методами. На их основе реализации сравниваются между собой, а также с известными алгоритмами. Выявлены явные преимущества построенных алгоритмов с выбором Д, = Е(/0, Д у к), где у к 6 Д перед методом условного градиента для "овражных" целевых функций. Заметим, что за счет условия (0.4) на этапе перехода от вспомогательной точки и* к приближению Хк+1 предложенные методы можно комбинировать практически с любыми известными или новыми алгоритмами условной минимизации, в которых итерационные точки принадлежат допустимой области, причем, сходимость таких смешанных алгоритмов остается обоснованной в связи с теоремами 2.1, 2.3 - 2.5, 2.8, 2.10. Промежуточные точки г^ и условие (0.4) выбора приближений Хк+\ будут использоваться далее почти во всех предлагаемых в диссертации методах, поэтому высказанное здесь замечание относительно построения на их основе всевозможных комбинированных алгоритмов будет иметь силу и в дальнейшем.

Для решения задачи (0.3) с сильно выпуклой функцией /о(х) в заключительном параграфе гл. 2 предлагается метод второго порядка, основанный на идеях метода Ньютона и алгоритмов из §§ 2.3, 2.5. В предлагаемом методе, в отличие от метода Ньютона, для построения на к-ом шаге подходящего направления в к = %к ~ во-первых, можно использовать не все допустимое множество Д а лишь его часть, например, Д = Е(/о, Б,Хк), и, во-вторых, вспомогательную задачу минимизации традиционной выпуклой квадратичной функции х) для нахождения точки Хк можно решать не на множествах И или .Д, а на содержащем их специально построенном множестве Ак более простого вида. С практической точки зрения аппроксимирующее множество А к удобно строить как многогранное. Тогда задача выбора направления в методе является задачей квадратичного программирования, и может быть реше;на за конечное число шагов (см., напр., [22], с. 314). Отметим также, что на некоторых итерациях метода для отыскания направления вк достаточно решить только задачу безусловной минимизации ^.(ж). Кроме того, в методе заложена возможность нахождения приближений Хк+1 с использованием промежуточных точек Ук = %к + Рквк и условия (0.4). Доказана сходимость метода, получена оценка его скорости сходимости. Описаны реализации метода, в которых применяется конечная процедура отсечений из § 1.1 построения аппроксимирующих множеств А к и, соответственно, точек Хк

Основные результаты гл. 2 опубликованы в работах, которые распределены по параграфам этой главы следующим образом. К §§ 3.2, 3.3 относятся [92, 93, 101], к §§ 3.4, 3.5 - [94, 101, 105, 107], к §§ 3.6, 3.7 - [95, 97], к § 3.8 - [93], и наконец, к § 3.9 - [106]. Все приведенные в гл. 2 результаты получены и опубликованы в названных работах без участия соавторов.

Как уже подчеркивалось, размерности множеств Вк, используемых в методах главы 1, могут быть меньше размерности множества £>. Тогда задачи выбора направлений в этих методах имеют меньшую размерность, чем основная задача (0.3). Гл. 3 посвящена разработке таких алгоритмов условной минимизации, где принцип уменьшения размерности вспомогательных задач поиска направлений за счет специального выбора множеств Ик является основной идеей алгоритмов. Множества Ик в предлагаемых здесь методах выбираются из линейных многообразий, определяющихся градиентами целевой функции и активных в точке ж* ограничений исходной задачи (0.3). Другими словами, в гл. 3 на примере методов условной минимизации гладких псевдовыпуклых функций реализуется описанный выше подход параметризации направлений итерационного перехода, который позволяет для некоторых типов задач математического программирования снизить число переменных и ограничений в задачах построения приближений хк по отношению к некоторым известным методам.

Первый параграф гл. 3 носит вспомогательный характер. В нем исследуются некоторые свойства задачи (0.3), где

Я = {ж е Яп : }]{х) < О, jeJ}, (0.5)

J — {1, .,т}, функции /¿(ж) псевдовыпуклы непрерывно дифференцируемы, а множество И регулярно по Слейтеру. Эти свойства связаны со спецификой строящихся далее методов и особенностями обоснования их сходимости.

В § 3.2 ставится и исследуется задача построения в точке хк € -О подходящего направления в виде X) °ь{хк)/Лхк), (0.6)

Шк где = «/ли{0}> ¿к ~ множество - активных в точке Хк ограничений /¿(ж). Для отыскания коэффициентов а^Хк) предлагается решать одну из трех вспомогательных задач минимизации линейной функции £ \1а(хк)> /[(хк) / Щ ПРИ некоторых ограниче

•е/* х ' ниях на переменные а*. Изучаются свойства задач отыскания коэффициентов «¿(жк), и доказывается теорема оптимальности точки в терминах этих задач. Далее для решения задачи (0.3), (0.5) предлагается метод, в котором направления в к в точках ж к строятся в виде (0.6), причем, вспомогательные задачи поиска коэффициентов а^Хк) могут решаться приближенно. Точки хк+1 находятся из условия (0.4) с привлечением дополнительных точек При переходе от ж к к Ук по направлению допустимы различные способы задания шагов. Доказывается сходимость метода для всех видов шагов, приводятся оценки скорости сходимости.

Заметим, что допустимые области О к вспомогательных задач поиска значений «¿(ж^), вообще говоря, не являются многогранными при задании множества И в общем виде, а значит, задачи выбора направления в точках хк могут быть достаточно сложны с практической точки зрения. Однако, в методе заложена возможность неточного решения указанных задач. В связи с этим, применяя уже использованные выше принципы аппроксимации множеств, можно для областей Ск строить аппроксимирующие их множества в форме многогранников и, соответственно, ставить задачи поиска коэффициентов о.г{хк) в (0.6) в виде задач линейного программирования. С учетом этого замечания в § 3.3 приводится одна из возможных реализаций метода, в которой на каждой итерации при нахождении приближенного решения оц(хк), г 6 вспомогательной задачи используются процедуры отсечений -к^ или 7Гз, описанные выше. Каждая из процедур гарантирует отыскание искомых значений аг(хк) за конечное число шагов, и при этом на каждом шаге процедуры независимо от вида Б решается задача линейного программирования. В § 3.3 проводится сравнение предложенного метода псевдовыпуклого программирования с идейно близкими известными методами выпуклого программирования, отмечаются его преимущества для определенных типов задач (0.3). Приводятся также результаты численного сравнения на тестовых примерах некоторых алгоритмов метода между собой и с методом условного градиента.

Далее, во многих известных методах проекционного типа задачи поиска в итерационных точках направлений спуска немногим проще исходной задачи выпуклого программирования, поскольку размерности вспомогательных задач проектирования совпадают с размерностями исходной задачи, а сама операция проектирования вызывает большие трудности, когда допустимая область И определена нелинейными функциями. В связи с этим в §§ 3.4, 3.5 предлагаются проекционные алгоритмы решения задачи псевдовыпуклого программирования, в которых, во-первых, задачи проектирования для построения подходящих направлений могут иметь меньшее по сравнению с исходной задачей число переменных и ограничений, и, во-вторых, несмотря на общий вид множества I), проектирование вспомогательных точек может осуществляться на некоторые специально построенные многогранные множества. Уменьшение количества переменных и ограничений задач проектирования в предлагаемых алгоритмах происходит, как и выше, за счет параметрического способа (0.6) представления направлений перехода, а упрощение операции проектирования с применением многогранников - за счет уже использованных выше принципов и способов аппроксимации множеств. Итак, в § 3.4 приводятся и обосновываются два алгоритма для задачи (0.3), (0.5), в которых направления зк имеют вид (0.6), а коэффициенты а^хк) отыскиваются с помощью одной из двух задач проектирования градиента целевой функции на некоторое множество Ик из линейного многообразия, определяемого векторами /[{хк), г £ Д. Поскольку число неизвестных а^хк) в этих вспомогательных задачах зависит от количества активных в точке хк ограничений, то при т < п такие задачи предпочтительнее традиционной задачи выбора направления, например, в методе проекции градиента. К тому же, при использовании в предложенных алгоритмах второй из вспомогательных задач проектирования число ограничений в ней также меньше, чем в упомянутом известном методе, а в случае ^ = 0 она вообще не требует решения. На случай задания области Б нелинейными функциями в § 3.5 предлагаются модификации обсуждаемых алгоритмов, использующие заложенные в проекционном методе параграфа 2.5 идеи аппроксимации множеств В модификациях направления (0.6) строятся путем проектирования градиента не на множества как в исходных алгоритмах, а на аппроксимирующие их многогранные множества Д^, что удобнее с практической точки зрения. Отметим, что все алгоритмы из §§ 3.4, 3.5 за счет построения дополнительных точек у^ и условия (0.4) допускают возможность комбинирования их с другими релаксационными алгоритмами.

Использование параметризованных направлений для уменьшения размерностей задач их поиска возможно и в методах второго порядка. В §§ 3.6, 3.7 приводятся примеры построения таких методов. В § 3.6 для задачи (0.3), (0.5) с сильно выпуклой целевой функцией предлагается алгоритм, близкий к описанному выше в § 2.6 методу второго порядка. В этом алгоритме при построении направлений коэффициенты аг(хк) в (0.6) отыскиваются путем минимизации выпуклых квадратичных функций на некоторых множествах И к, размерности которых определяются количеством активных в точках хк ограничений. Несмотря на то, что эти вспомогательные задачи поиска коэффициентов в определенных случаях имеют меньшие, чем, например, в методе Ньютона, размерности, при задании множества И в общем виде они остаются достаточно сложны. В связи с этим в § 3.7 предлагается модификация алгоритма параграфа 3.6, позволяющая использовать в задачах выбора направления вместо множеств Ик аппроксимирующие их многогранные множества Дк из тех же линейных многообразий, что и Тогда, несмотря на общий вид Б, процедурами отсечений из § 1.1 удается получать искомые коэффициенты аг{хк) в комбинации (0.6) с помощью задач квадратичного программирования. В §§ 3.6, 3.7 приводятся обоснования сходимости алгоритма и его модификации, оценки скорости сходимости, а также реализации алгоритмов.

В § 3.8 предлагается еще один алгоритм решения задачи (0.3), (0.5) с параметризованными направлениями (0.6), который идейно близок к известному методу возможных направлений Зойтендейка. В отличие от методов с параметризацией из предыдущих параграфов главы этот алгоритм позволяет, независимо от вида ограничений (0.5), ставить задачи отыскания коэффициентов в (0.6) как задачи линейного программирования. Если размерность п пространства переменных исходной задачи превышает число т ограничений в ней, то предлагаемая задача выбора направления в построенном алгоритме выгодно отличается от традиционной задачи Зойтендейка по числу переменных и ограничений.

Использованный выше принцип параметризации может быть применен в алгоритмах, принадлежащих и другим классам методов. Один из таких примеров приведен в § 3.9. Здесь строится алгоритм псевдовыпуклого программирования, основанный на идеях метода линеаризации и близких к нему алгоритмов, в которых к построению направлений правлекаются задачи квадратичного программирования. В отличие от упомянутых методов предлагаемый алгоритм использует параметризованные направления вида (0.6), где коэффициенты аг(хк) находятся также путем решения задачи квадратичного программирования. Однако, применяемый здесь способ выбора направлений при определенных условиях на размерности исходной задачи (0.3), (0.5) может быть предпочтительнее используемого в методах типа линеаризации. Заметим, что , как и другие методы гл. 2, 3, данный алгоритм позволяет за счет условия (0.4) комбинировать его с любыми релаксационными методами, не обосновывая заново сходимость смешанных алгоритмов.

Основные результаты третьей главы опубликованы. Распределение публикаций по параграфам выглядит следующим образом. К §§ 3.2, 3.3 относятся работы [92, 93, 101], к §§ 3.4, 3.5 - [94, 101, 105, 107], к §§ 3.6, 3.7 - [95, 97], к § 3.8 - [93], к § 3.9 - [106]. Все результаты гл. 3 получены и опубликованы в указанных работах без соавторства.

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

В § 4.1 строятся два релаксационных метода решения задачи (0.3) с негладкой строго псевдовыпуклой функцией /0(ж), в которых вспомогательные задачи близки к задачам построения подходящих направлений в алгоритмах минимизации гладких функций из §§ 2.1, 2.2. Близость заключается в том, что в предлагаемых методах целевые функции задач выбора направления могут быть линейными, а допустимые области Ик этих задач совпадают с лебеговыми множествами Е(/.о, И, х^). Второй из этих методов отличается от первого тем, что применяется к задаче (0.3) с дополнительным требованием строгой выпуклости множества И, но, в то же время, имеет более широкие возможности в выборе подходящих направлений по сравнению с первым методом. Отметим, что в методах заложена возможность неточного решения задач выбора направления. В связи с этим в реализациях методов для отыскания этого приближенного решения предлагается использовать процедуру отсечений тт3 из § 1.3. При выборе в ней начального аппроксимирующего множества М0 в виде многогранника искомое направление спуска строится с помощью задач линейного программирования за конечное число шагов. В том же параграфе обсуждаются результаты численных экспериментов, проведенных с целью сравнения методов между собой.

Развитый в гл. 3 подход с параметризацией направлений для минимизации гладких функций распространяется далее на алгоритмы условной минимизации псевдовыпуклой функции максимума. В § 4.2 ставится задача (0.3), (0.5), где /о(х) определена в виде функции максимума гладких псевдовыпуклых функций. Для ее решения предлагается метод, в котором направление спуска на каждом шаге строится как линейная комбинация градиентов активных функций, задающих целевую функцию и ограничения (0.5). Коэффициенты комбинации находятся путем решения системы линейных неравенств или задачи линейного программирования. Доказана сходимость метода, получены оценки скорости сходимости, описаны алгоритмы метода. За счет параметрического представления направлений эти алгоритмы имеют определенные преимущества перед рядом известных методов нахождения дискретного минимакса в случае, когда общее число функций, определяющих исходную задачу, существенно меньше п.

Использованный в § 4.2 подход к решению задачи минимизации функции максимума можно перенести и на те методы, в которых минимаксными являются вспомогательные задачи построения итерационных точек или направлений перехода в итерационных точках. В последнем параграфе главы 4 на примере одного алгоритма решения задачи (0.3), (0.5) показывается, каким образом идея параметризации направлений может применяться и быть полезной с практической точки зрения в методах центров. В предлагаемом алгоритме на каждом шаге строится вспомогательная функция максимума Рк(х) на основе измененной целевой функции и функций ограничений исходной задачи (0.3), (0.5), и из текущей итерационной точки Хк производится переход в новую точку Ук с лучшим значением функции Рк{х). Используемое при этом направление имеет вид линейной комбинации активных в точке хк градиентов функции Гк (х), а коэффициенты комбинации находятся с помощью решения системы линейных неравенств или задачи линейного программирования. Очередное приближение Хк+1 отыскивается из условия 1) < После обоснования сходимости метода обсуждаются его реализации и возможные преимущества перед некоторыми методами центров для определенного типа задач.

Публикации, на основе которых написана гл. 4, распределяются по параграфам следующим образом. К § 4.1 относятся работы [60], [108] - [112], к § 4.2 - [87], [88], а к § 4.3 - [89] - [91]. Заметим, что § 4.3 диссертации написан по результатам совместной статьи [91], которая посвящена разработке варианта параметризованного метода центров для задачи выпуклого программирования. Князеву Е. А. в этой статье принадлежат леммы 2, 4 и первая часть доказательства теоремы сходимости, а Заботину И. Я. - предлагаемый метод, лемма 3, теорема оптимальности точки, а также теоремы 2, 3 и вторая часть доказательства теоремы сходимости метода. Однако, заметим, что результаты данного параграфа диссертации носят более общий по сравнению с результатами статьи [91] характер, т. к., во-первых, они получены для задачи псевдовыпуклого программирования, и, во-вторых, сам предлагаемый здесь метод обобщает метод из работы [91].

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

В § 5.1 для задачи

1шп{/0(г) | х Е Яп} (0.7) с псевдовыпуклой непрерывно дифференцируемой целевой функцией строится и обосновывается общий метод, в котором переход от точек хк к промежуточным точкам Ук происходит в некоторых линейных многообразиях М(хк), а затем приближение Хк+\ € Яп выбирается согласно условию о(а*+1) < /оЫ- (0-8)

Размерности многообразий задаются на каждом шаге произвольно от 1 до п. За счет большой свободы в выборе множеств М(хь), вспомогательных точек V/; и приближений хь+1 метод допускает значительное число реализаций, которые приводятся в § 5.2. Среди них - известные алгоритмы выпуклого программирования, их модификации и новые алгоритмы минимизации псевдовыпуклых функций. К известным алгоритмам, которые являются реализациями предложенного метода, относятся методы наискорейшего спуска, покоординатного спуска, обобщенный метод градиентного спуска, метод изменения масштабов, метод Ньютона с регулировкой шага, квазиньютоновские алгоритмы, варианты метода сопряженных градиентов и многие другие. Для каждого из этих методов, а также для всех предлагаемых новых алгоритмов в § 5.2 доказывается выполнение тех или иных условий теорем 5.1 - 5.3 сходимости общего метода и теорем 5.4, 5.5, касающихся оценок его скорости сходимости. Тем самым для многих исследуемых в § 5.2 методов выпуклого программирования и новых алгоритмов обосновывается возможность их использования для задачи псевдовыпуклого программирования (0.7) и доказываются оценки скорости сходимости для псевдовыпуклых и сильно выпуклых функций. Таким образом, предложенный в § 5.1 подход к разработке методов решения задачи (0.7) позволяет строить новые одношаговые и многошаговые алгоритмы с практически произвольными процедурами обновления, модифицировать известные методы, расширяя их возможности в выборе направлений и шаговых множителей, а также по единой методике исследовать сходимость методов и получать оценки скорости сходимости. Кроме того, поскольку процесс отыскания приближения из условия (0.8) в методе не конкретизирован, то за счет чередования различных способов построения точек Ук и Хк+1 можно получать всевозможные смешанные алгоритмы на основе известных и новых методов без дополнительного обоснования их сходимости.

В отдельный параграф (§ 5.3) выделены еще два алгоритма решения задачи (0.7), которые идейно близки к общему методу из § 5.1, но формально в него не вкладываются и потому обосновываются по другой методике. Эти алгоритмы уместно отнести к классу методов спуска по группам переменных. В данный класс можно включить хорошо известный метод покоординатного спуска и его варианты, метод градиентного спуска по быстрым переменным ([166, 167]) и некоторые другие, в том числе эвристические, алгоритмы. Отметим, что в алгоритмах спуска по быстрым и медленным переменным (напр., [166]) используется эвристический прием чередования переходов в подпространствах быстрых переменных с переходами по группам медленных переменных. Несмотря на определенную практическую пользу такого чередования при минимизации "овражных" функций (см. [166]), у этих алгоритмов, кроме вопросов о критериях отбора групп переменных на каждом шаге, остаются открытыми вопросы об их сходимости и оценках скорости сходимости. В связи с этим могут оказаться полезными предлагаемые в § 5.3 критерии отбора групп переменных, участвующих в итерационных переходах строящихся здесь алгоритмов. Эти критерии, во - первых, просты для проверки, во -вторых, гарантируют сходимость методов указанного класса, и в - третьих, позволяют выбирать на каждом шаге число переменных, входящих в эти группы, любым от 1 до п, т. е. производить переход в подпространствах любой размерности. На базе этих критериев и строятся упомянутые алгоритмы спуска по группам переменных. В том же § 5.3 доказывается их сходимость, обосновываются оценки скорости сходимости, описываются реализации. Среди этих реализаций есть известные методы покоординатного спуска и спуска по быстрым переменным, которые благодаря теоремам сходимости 5.6 - 5.9 могут использоваться при решении более общих задач (0.7). Как и в упомянутом методе [166], в предлагаемых здесь сходящихся алгоритмах допустимо чередование шагов в подпространствах быстрых и медленных переменных, причем, размерности этих подпространств можно задавать заранее на каждой итерации. За счет условия (0.8) выбора точек 2^4.1 алгоритмы допускают комбинирование с методами этого же или другого класса.

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

Предлагаемая схема близка к методу из § 5.1. Итерационные переходы в ней тоже осуществляются в некоторых линейных многообразиях М(хк), но построенных с использованием неточно вычисленных градиентов. За счет определенной свободы в выборе многообразий М(хк) схема допускает различные реализации, среди которых - известные и новые алгоритмы. В §§ 5.5, 5.6 для этих алгоритмов на основе сформулированного выше принципа исследуется их устойчивость в указанном смысле. При этом приходится доказывать, что каждый из алгоритмов является частным случаем общей схемы. В указанных параграфах исследованы на устойчивость метод обобщенного градиентного спуска, так называемый нелинейный метод [197], методы покоординатного спуска и Ньютона, квазиньютоновские алгоритмы, метод многопараметрического поиска [205], а также многие другие известные и новые одношаговые и многошаговые алгоритмы. Отметим, что для многих исследованных алгоритмов справедливы оценки скорости сходимости общей схемы, полученные с учетом погрешностей вычисления градиентов, для псевдовыпуклых и сильно выпуклых функций.

Все результаты гл. 5 опубликованы. К § 5.1 относится работа [98], к § 5.2 - [60, 96, 98, 99], к § 5.3 - [77, 78, 85], к § 5.4 - [99, 102, 103, 104], к § 5.5 - [99, 102, 103, 104], к § 5.6 - [96, 99, 102]. Все описанные в пятой главе результаты получены (и опубликованы в названных работах) без участия соавторов.

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

Зачастую практические оптимизационные задачи вида (0.3) обладают специфической структурой за счет особенностей задания целевой функции или допустимого множества. В гл. 6 приведены соответствующие примеры и ссылки. Одной из таких особенностей можно считать задание области Б в (0.3) в виде прямого произведения выпуклых замкнутых множеств г = 1 ,.,т, из пространств вообще говоря, различных размерностей. В § 6.1 строятся два метода минимизации гладкой псевдовыпуклой функции на множестве указанного вида. Методы характерны тем, что на каждом шаге итерационный переход при желании может производиться в них лишь по части переменных задачи. В связи с этим методы могут быть отнесены к алгоритмам спуска по группам переменных наряду с некоторыми известными алгоритмами выпуклого программирования (напр., [9, 37, 56]). В диссертации предлагается отличный от известных принцип выбора групп переменных, по которым производится спуск на каждом шаге. Формирование этих групп происходит в результате решения т вспомогательных задач минимизации некоторых функций ^(ж) на множествах Построенные на основе предложенного принципа методы отличаются друг от друга тем, что спуск на к -ом шаге в выбранном подпространстве происходит либо по конкретным направлениям, либо с большой долей свободы, привлекая любые релаксационные процедуры. Заложенный в методах критерий выбора групп переменных гарантирует их сходимость, позволяет заранее задавать желательную размерность подпространств, в которых производится спуск, дает возможность построения различных реализаций. Среди них можно выделить вариант метода покоординатного спуска для задачи (0.3) с множеством И в виде параллелепипеда, алгоритм спуска по быстрым переменным, алгоритмы, в которых допустимо чередование переходов по быстрым и медленным переменным. Отметим также, что предложенные методы можно комбинировать с другими алгоритмами, а решение упомянутых вспомогательных задач минимизации ^(ж) на множествах можно проводить одновременно на многопроцессорных ЭВМ, что поможет сократить время построения направлений спуска.

В § 6.2 ставится еще одна экстремальная задача специального вида. Функция Р(х) в (0.9) представляет собой функцию максимума, характерную тем, что каждая из составляющих ее непрерывных функций /¿(гг^), г = 1, .,т, зависит от переменных Х( € не связанных с переменными остальных функций, а область И, как и в § 6.1, задана в виде прямого произведения выпуклых замкнутых множеств Д С Ящ- Изучаются свойства задачи (0.9). Доказывается, что для ее решения нет необходимости в последовательном решении всех частных задач

Если х* — (х\, ■■■,х^п) - решение задачи (0.9), то необязательно для каждого г = 1, .,тп компонента х\ является решением соответствующей задачи (0.10). Для поставленной задачи (0.9) в том же параграфе строится и обосновывается метод, который также можно отнести к алгоритмам спуска по группам переменных. Переход из текущей итерационной точки хк = .,0;^), х1- е Д, производится в методе лишь по тем переменным ж,-, для которых соответствующие функции /¿(^¿) являются активными в точке хк. Спуск по выбранным переменным х.{ производится в областях А с привлечением любых, вообще говоря различных, сходящихся алгоритмов М*.

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

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

Результаты главы 6 полностью опубликованы. Они описаны в работах [78, 80, 84, 86], с относящихся к § 6.1, в работах [75, 79], касающихся § 6.2, в статье [76], относящейся тт{^(ж) | х е £>}

0.9)

I х1 е А-}.

0.10) к § 6.3, и наконец, в работах [71, 74, 81, 83], относящихся к § 6.4. Все представленные в §§ 6.1 - 6.3 результаты получены и опубликованы в названных работах без участия соавторов. Статьи, касающиеся решения прикладных задач из § 6.4, являются совместными. В связи с этим отметим, что прикладные оптимизационные задачи данного параграфа, относящиеся к проектированию радиоэлектронных систем, были предложены автору руководителем упомянутых договоров доцентом кафедры радиофизики КГУ Кобчиковым А. В. Их математические постановки, описанные в § 6.4 диссертации, разрабатывались авторами указанных статей совместно, а использованные при решении задач алгоритмы и результаты экспериментов, приведенные в том же § 6.4, принадлежат Заботину И. Я.

Заметим также, что в диссертации имеются ссылки и на некоторые другие совместные работы автора, например, [65, 67, 73, 82]. Однако, опубликованные в них результаты никак не представлены в диссертации и, соответственно, не выносятся на защиту, поэтому деление результатов между соавторами для таких работ здесь не производится.

Автор выражает благодарность участникам научного семинара кафедры экономической кибернетики КГУ, а также профессору И. В. Коннову за полезные обсуждения и замечания в ходе работы над диссертацией.

Заключение

Подводя итог, перечислим основные результаты диссертационной работы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6. Показано, что примененная в методах условной минимизации идея параметризации направлений в некотором смысле может быть использована и при разработке алгоритмов безусловной минимизации псевдовыпуклых функций. Для этого разработана общая схема минимизации в Яп гладких псевдовыпуклых функций, в которой на каждом шаге сначала производится переход от текущей итерационной точки Хк к промежуточной точке Ук в некотором линейном многообразии М(хк), а затем произвольно выбирается приближение хк+1 с лучшим по отношению к Ук значением целевой функции. За счет большой свободы в выборе многообразий М(хк) и точек Ук, Хк+1, во-первых, построены новые одношаговые и многошаговые алгоритмы минимизации псевдовыпуклых функций (как реализации общей схемы), во-вторых, доказано, что многие известные методы безусловной минимизации выпуклых функций вкладываются в построенную схему, а значит, пригодны для минимизации псевдовыпуклых функций, в-третьих, обоснована возможность распараллеливания процесса минимизации такими алгоритмами, и, в-четвертых, доказана возможность построения на основе известных и новых алгоритмов, вкладывающихся в эту общую схему, различных смешанных методов.

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

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

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

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

1. Антипин, А. С. Непрерывные и итеративные процессы с операторами проектирования и типа проектирования Текст] / А. С. Антипин // Вопр. кибернетики. Вычислительные вопросы анализа больших систем. М., 1989. - С. 5 - 43.

2. Антипин, А. С. Методы нелинейного программирования, основанные на прямой и двойственной модификации функции Лагранжа Текст] / А. С. Антипин. М.: Изд- во Всесоюзн. науч. исследов. института системн. исследований, 1979. - 74 с.

3. Антипин, А. С. Метод линеаризации Текст] / А. С. Антипин // Нелинейные динамические системы: качественный анализ и управление. М.: ИСА РАН - 1994, N2.- С. 4- 20.

4. Антипин, А. С. Вычисление неподвижных точек симметричных экстремальных отображений Текст] / А. С. Антипин // Изв. вузов. Математика. 1997. - N 12.- С. 3 15.

5. Антипин, А. С. Равновесное программирование: проксимальные методы Текст] / А. С. Антипин // Журн. вычисл. матем. и матем. физ. 1997. - Т. 37. - N 11. -С. 1327 - 1339.

6. Анциферов, Е. Г. Алгоритм симплексных погружений в выпуклом программировании Текст] / Е. Г. Анциферов, В. П. Булатов // Журн. вычисл. матем. и матем. физ. 1987. - Т. 27. - N 3. - С. 377 - 384.

7. Анциферов, Е. Г. К полиномиальным методам в выпуклом программировании Текст] / Е. Г. Анциферов, В. П. Булатов // Оптимизация: модели, методы, решения. Новосибирск: Наука, 1992. - С. 4 - 29.

8. Аоки, М. Введение в методы оптимизации Текст] / М. Аоки. М.: Наука, 1977. -343 с.

9. Ащепков, Л. Т. Методы решения задач математического программирования и оптимального управления Текст] / Л. Т. Ащепков, Б. И. Белов, В. П. Булатов, О. В. Васильев, В. А. Срочко, Н. В. Тарасенко. Новосибирск: Наука, 1984. - 233 с.

10. Бабич, М. Д. Исследование полной погрешности в задачах минимизации функционалов при наличии ограничений Текст] / М. Д. Бабич, В. В. Иванов // Укр. матем. журн. 1969. - Т. 21. - N 1. - С. 3 - 14.

11. Базара, М. Нелинейное программирование. Теория и алгоритмы Текст] / М. Базара, К. Шетти. М.: Мир, 1982. - 583 с.

12. Бакушинский, А. Б. Методы решения монотонных вариационных неравенств, основанные на принципе итеративной регуляризации Текст] / А. Б. Бакушинский // Журн. вычисл. матем. и матем. физ. 1977. - Т. 17. - N 6. - С. 1350 - 1362.

13. Бакушинский, А. Б. Некоторые методы решения систем монотонных вариационных неравенств Текст] / А. Б. Бакушинский // Численные методы оптимизации. -Иркутск: СЭИ АН СССР, 1978. С. 13 - 26.

14. Бахвалов, Н.С. Численные методы. Анализ, алгебра, обыкновенные дифференциальные уравнения Текст] / Н. С. Бахвалов. М.: Наука, 1973. - 631 с.

15. Беленький, В. 3. Итеративные методы в теории игр и программировании Текст] / В. 3. Беленький, В. А. Волконский, С. А. Иванков, А. Б. Поманский, А. Д. Шапиро. М.: Наука, 1974. - 240 с.

16. Белоусов, Е. Г. О непрерывности точечно множественных отображений, связанных с методом штрафных функций Текст] / Е. Г. Белоусов // Изв. вузов. Математика. - 1996. - N 12. - С. 3 - 8.

17. Бертсекас, Д. Условная оптимизация и методы множителей Лагранжа Текст] / Д. Бертсекас. М.: Радио и связь, 1987. - 400 с.

18. Богомолов, II. А. О методе вычисления стационарных точек общей задачи нелинейного программирования Текст] / Н. А. Богомолов, В. Г. Карманов // Журн. вычисл. матем. и матем. физ. 1977. - Т. 17. - N 1. - С. 72 - 78.

19. Брегман, Л. М. Нахождение общей точки выпуклых множеств методом последовательного проектирования Текст] / Л. М. Брегман // ДАН СССР. 1965. - Т. 162. -N3.-0. 487- 490.

20. Булавский, В. А. Об одном типе проекционных методов в математическом программировании Текст] / В. А. Булавский // Оптимизация. Новосибирск: Наука, 1972. - С. 11 - 22.

21. Булатов, В. П. Методы погружения в задачах оптимизации Текст] / В. П. Булатов. Новосибирск: Наука, 1977. - 158 с.

22. Васильев, Ф. П. Численные методы решения экстремальных задач Текст] / Ф. П. Васильев. М.: Наука, 1988. - 552 с.

23. Васильев, Ф. П. Методы решения экстремальных задач Текст] / Ф. П. Васильев.- М.: Наука, 1981. 400 с.

24. Васильев, Ф. П. Методы оптимизации Текст] / Ф. П. Васильев. М.: Факториал Пресс, 2002. - 823 с.

25. Васильев, Ф. П. Об итеративной регуляризации метода условного градиента и метода Ньютона при неточно заданных исходных данных Текст] / Ф. П. Васильев, М. Д. Ячимович // Докл. АН СССР. 1980. - Т. 250. - N 2.-е. 265 - 269.

26. Васин, В. В. Операторы и итерационные процессы фейеровского типа (теория и приложения) Текст] / В. В. Васин, И. И. Еремин. Москва - Ижевск: Институт компьютерных исследований, НИЦ "Регулярная и хаотичная динамика", 2005. -200 с.

27. Вилков, А. В. Метод отыскания глобального минимума функции одного переменного Текст] / А. В. Вилков, Н. П. Жидков, Б. М. Щедрин // Журн. вычисл. матем. и матем. физ. 1975. - Т. 15. - jV 4. - С. 1040 - 1042.

28. Габасов, Р. Методы оптимизации Текст] / Р. Габасов, Ф. М. Кириллова. Минск: Изд - во Б ГУ, 1981. - 352 е.

29. Габидуллина, 3. Р. К сходимости метода условного градиента для одного класса невыпуклых функций Текст] / 3. Р. Габидуллина // Исслед. по прикл. матем. -Казань: Изд во КГУ, 1987. Вып. 14. - С. 15 - 25.

30. Галиев, Ш. И. Нахождение субоптимальных решений максиминных задач Текст] / Ш. И. Галиев // Журн. вычисл. матем. и матем. физ. 1985. - Т. 25. - N 11. -С. 1738.

31. Галиев, Ш. И. Направления убывания для минимаксиминных задач Текст] / Ш. И. Галиев // Журн. вычисл. матем. и матем. физ. 1994. - Т. 34. - N 3. - С. 323- 343.

32. Геминтерн, В. И. Оптимизация в задачах проектирования Текст] / В. И. Гемин-терн, М. С. Штильман. М.: Знание, 1982. - 64 с.

33. Гирсанов, И. В. Лекции по математической теории экстремальных задач Текст] / И. В. Гирсанов. М.: Изд - во МГУ, 1970. - 117 с.

34. Голиков, А. И. Две модификации метода линеаризации в нелинейном программировании Текст] / А. И. Голиков, В. Г. Жадан // Журн. вычисл. матем. и матем. физ. 1983. - Т. 23. - N 2. - С. 314 - 325.

35. Голъштейн, Е. Г. Обобщенный градиентный метод отыскания седловых точек Текст] / Е. Г. Гольштейн // Экономика и матем. методы. 1972. - Т. 8. - N 4. - С. 569 - 579.

36. Голъштейн, Е. Г. Градиентный метод минимизации и алгоритмы выпуклого программирования, связанные с модифицированными функциями Ланранжа Текст] / Е. Г. Гольштейн, Н. В. Третьяков // Экономика и матем. методы. 1975. - Т. 11.- N 4. С. 730 - 742.

37. Голъштейн, Е. Г. Методы расчета и синтеза импульсных автоматических систем Текст] / Е. Г. Гольштейн, Д. Б. Юдин // Автоматика и телемеханика. 1963. -Т 24. - N 12. - С. 1643 - 1659.

38. Гроссман, К. Нелинейное программирование на основе безусловной минимизации Текст] / К. Гроссман, А. А. Каплан. Новосибирск: Наука, 1981. - 184 с.

39. Гуткин, Л. С. Оптимизация радиоэлектронных устройств Текст] / Л. С. Гуткин.- М.: Сов. радио, 1975. 368 с.

40. Данилин, Ю. М. Минимизация нелинейных функционалов в задачах с ограничениями Текст] / Ю. М. Данилин // Кибернетика. 1970. - N 3. - С. 93 - 100.

41. Данилин, Ю. М. Методы минимизации, основанные на аппроксимации исходного функционала выпуклым Текст] / Ю. М. Данилин // Журн. вычисл. матем. и матем. физ. 1970. - Т. 10. - N 5. - С. 1067 - 1080.

42. Демьянов, В. Ф. Недифференцируемая оптимизация Текст] / В. Ф. Демьянов, Л. В. Васильев. М.: Наука, 1981. - 384 с.

43. Демьянов, В. Ф. Введение в минимакс Текст] / В. Ф. Демьянов, В. Н. Малоземов.- М.: Наука, 1972. 368 с.

44. Демьянов, В. Ф. Численные методы разыскания седловых точек Текст] / В. Ф. Демьянов, А. Б. Певный // Журн. вычисл. матем. и матем. физ. 1972. - Т. 12. -N 5. - С. 1099 - 1127.

45. Демьянов, В. Ф. Приближенные методы решения экстремальных задач Текст] / В. Ф. Демьянов, А. М. Рубинов. Л.: Изд - во ЛГУ, 1968. - 180 с.

46. Денисов, Д. В. Метод итеративной регуляризации в задачах условной минимизации Текст] / Д. В. Денисов // Журн. вычисл. матем. и матем. физ. 1978. - Т.18. - N 6. - С. 1405 - 1415.

47. Дикин, И. И. Итеративное решение задач математического программирования Текст] / И. И. Дикин, В. И. Зоркальцев. Новосибирск: Наука, 1980. - 144 е.

48. Евтушенко, Ю. Г. Методы решения экстремальных задач и их применение в системах оптимизации Текст] / Ю. Г. Евтушенко. М.: Наука, 1982. - 432 с.

49. Евтушенко, Ю. Г. Численный метод поиска глобального экстремума функций (перебор на неравномерной сетке) Текст] / Ю. Г. Евтушенко // Журн. вычисл. матем. и матем. физ. 1971. Т. 11. - N 6. - С. 1390 - 1404.

50. Евтушенко, Ю. Г. Метод половинных делений для глобальной оптимизации функции многих переменных Текст] / Ю. Г. Евтушенко, В. А. Ратькин // Технич. кибернетика. 1987. -N1.-0. 119 - 127.

51. Еремин, И. И. Теория линейной оптимизации Текст] / И. И. Еремин. Екатеринбург: Изд - во "Екатеринбург", 1999. - 312 с.

52. Еремин, И. И. Введение в теорию линейного и выпуклого программирования Текст] / И. И. Еремин, Н. Н. Астафьев. М.: Наука, 1976. - 192 с.

53. Еремин, И. И. Нестационарные процессы математического программирования Текст] / И. И. Еремин, В. Д. Мазуров. М.: Наука, 1979. - 288 с.

54. Ермольев, Ю. М. Методы стохастического программирования Текст] / Ю. М. Ермольев. М.: Наука, 1976. - 240 с.

55. Ермольев, Ю. М. Математические методы исследования операций Текст] / Ю. М. Ермольев, И. И. Ляшко, В. С. Михалевич, В. И. Тюптя. Киев: Вища школа, 1979.- 312 с.

56. Ермольев, Ю. М. О минимизации недифференцируемых функций Текст] / Ю. М. Ермольев, Н. 3. Шор // Кибернетика. 1967. - N 1. - с. 101 - 102.

57. Жадан, В. Г. Об одном классе итеративных методов решения задач выпуклого программирования Текст] / В. Г. Жадан // Журн. вычисл. матем. и матем. физ.- 1984. Т. 24. - N 5. - С. 665 - 676.

58. Заботин, И. Я. О методах безусловной минимизации функции, использующих симплекс Текст] / И. Я. Заботин // Исслед. по прикл. матем. Казань: Изд - во КГУ, 1979. - Вып. 7. - С. 55 - 64.

59. Заботин, И. Я. К вопросу о выборе направлений спуска в задачах безусловной минимизации функций Текст] / И. Я. Заботин // Исслед. по прикл. матем. Казань: Изд - во КГУ, 1981. - Вып. 9. - С. 37 - 42.

60. Заботин, И. Я. О методах безусловной минимизации функций с наилучшими относительно множества направлениями спуска Текст] / И. Я. Заботин // Изв. вузов. Математика. 1982. - N 7. - С. 11 - 16.

61. Заботин, И. Я. Один вариант метода Ньютона с погружением допустимого множества Текст] / И. Я. Заботин; Казань, КГУ, 1983. 11 с. - Деп. в ВИНИТИ 20.01.83, N 353 - 83.

62. Заботин, И. Я. Итеративная регуляризация метода условного градиента с погружением допустимого множества Текст] / И. Я. Заботин; Казань, КГУ, 1983. 15 с. - Деп. в ВИНИТИ 16.02.83., N 852 - 83.

63. Заботин, И. Я. Метод условного е субградиента Текст] / И. Я. Заботин, А. И. Кораблев // Изв. вузов. Математика. - 1983. - N 9. - С. 22 - 26.

64. Заботин, И. Я. Метод типа проекции градиента, использующий погружение допустимого множества Текст] / И. Я. Заботин // Исслед. по прикл. матем. Казань: Изд - во КГУ, 1984. - Вып. 11, часть 1. - С. 3 - 11.

65. Заботин, И. Я. Об одном варианте метода условного градиента Текст] / И. Я. Заботин, Е. В. Лямин // Исслед. по прикл. матем. Казань: Изд - во КГУ, 1984. -Вып. 11, часть 1. - С. 11 - 23.

66. Заботин, И. Я. Метод условного е субградиента для минимизации квазивыпуклых функций Текст] / И. Я. Заботин, А. И. Кораблев // Проблемы теоретической кибернетики. Тез. докл. 7 Всесоюз. конф. - Иркутск, 1985. - Ч. 2. - С. 64 - 65.

67. Заботин, И. Я. Релаксационный субградиентный метод минимизации строго выпуклых функций Текст] / И. Я. Заботин, М. И. Крейнин // Исслед. по прикл. матем. Казань: Изд - во КГУ, 1987. - Вып. 14. - С. 34 - 42.

68. Заботин, И. Я. О минимизации функции максимума с разделяющимися переменными Текст] / И. Я. Заботин // Проблемы теоретической кибернетики. Тез. докл. 8 Всесоюз. конф. ( июль, 1988 ) Горький, 1988. - Ч. 1. - С. 119.

69. Заботин, И. Я. Субградиентный метод отыскания седловой точки выпукло вогнутой функции Текст] / И. Я. Заботин // Исслед. по прикл. матем. - Казань: Изд - во КГУ, 1988. - Вып. 15. - С. 6 - 12.

70. Заботин, И. Я. О минимизации функции максимума специального вида Текст] / И. Я. Заботин // Исслед. по прикл. матем. Казань: Изд - во КГУ, 1989. - Вып. 16. - С. 101 - 108.

71. Заботин, И. Я. О выборе оптимальных соотношений между массами блоков радиоэлектронной системы Текст] / И. Я. Заботин, А. В. Кобчиков // Прием и обработка информации в сложных информационных системах. Казань: Изд - во КГУ, 1990.- Вып. 18. С. 64 - 70.

72. Заботин, И. Я. О реализациях некоторых методов, применяемых при решении оптимизационных задач проектирования Текст] / И. Я. Заботин, А. В. Кобчиков // Автоматика и телемеханика. 1991. - N 1. - С. 169 - 172.

73. Заботин, И. Я. Методы спуска по группам переменных для условной минимизации функций Текст] / И. Я. Заботин // Проблемы теоретической кибернетики. Тез. докл. И Всесоюз. конф. ( сентябрь, 1990 ) Волгоград, 1990. - Ч. 1(2). - С. 26.

74. Заботин, И. Я. О некоторых методах спуска по группам переменных Текст] / И. Я. Заботин // Исслед. по прикл. матем. Казань: Изд - во КГУ, 1992. - Вып. 19.- С. 24 33.

75. Заботин, И. Я. Методы спуска по группам переменных для одного класса задач условной минимизации Текст] / И. Я. Заботин // Исслед. по прикл. матем. Казань: Изд - во КГУ, 1992. - Вып. 18. - С. 48 - 59.

76. Заботин, И. Я. Алгоритмы с комбинированием активных градиентов для отыскания условного минимакса Текст] / И. Я. Заботин // Изв. вузов. Математика. -1993. N 12. - С. 52 - 58.

77. Заботин, И. Я. Вариант параметризованного метода центров Текст] / И. Я. Заботин, Е. А. Князев // Изв. вузов. Математика. 1995. - N 12. - С. 26 - 32.

78. Заботин, И. Я. Метод условной минимизации с параметрическим заданием подходящих направлений Текст] / И. Я. Заботин // Изв. вузов. Математика. 1996. -N 12. - С. 17-29.

79. Заботин, И. Я, Об алгоритмах минимизации с параметризованными направлениями спуска Текст] / И. Я. Заботин // Математич. программирование и приложения. Тез. докл. 10 Всерос. конф. ( Екатеринбург, 24 28 февр. 1997 г. ) - Екатеринбург, 1997. - С. 96.

80. Заботин, И. Я. Алгоритмы прекционного типа с параметрическим заданием подходящих направлений Текст] / И. Я. Заботин // Проблемы оптимизации и экономические приложения. Тез. докл. Междунар. конф. ( Омск, 1-5 июля 1997 г. ) -Омск, 1997. С. 73.

81. Заботин, И. Я. Алгоритм второго порядка с параметризованными направлениями для задач условной оптимизации Текст] / И. Я. Заботин // Изв. вузов. Математика. 1997. - N 12. - С. 62 - 72.

82. Заботин, И. Я. Об одном подходе к построению алгоритмов безусловной минимизации псевдовыпуклых функций Текст] / И. Я. Заботин // Изв. вузов. Математика. 1998. - Л/" 12. - С. 29 - 39.

83. Заботин, И. Я. Некоторые многошаговые методы безусловной минимизации и их устойчивость Текст] / И. Я. Заботин // Математич. программирование и приложения. Тез. докл. 11 Всерос. конф. ( Екатеринбург, 22 26 февр. 1999 г. ) -Екатеринбург, 1999. - С. 110.

84. Заботин, И. Я. Об устойчивости некоторых методов безусловной минимизации Текст] / И. Я. Заботин // Проблемы теоретической кибернетики. Тез. докл. 12 Междунар. конф. ( Нижний Новгород, 17 22 мая, 1999 г. ) - Ч. 1. - М.: МГУ, 1999.- С. 75.

85. Заботин, И. Я. Об устойчивости алгоритмов безусловной минимизации псевдовыпуклых функций Текст] / И. Я. Заботин // Изв. вузов. Математика. 2000. -N 12. - С. 33 - 48.

86. Заботин, И. Я. Проекционные алгоритмы с параметризованными направлениями спуска в псевдовыпуклом программировании Текст] / И. Я. Заботин // Исслед. по прикл. матем. и информатике Казань: Изд - во Казанск. матем. общества, 2001.- Вып. 23. С. 67 - 81.

87. Заботин, И. Я. Метод минимизации негладкой строго псевдовыпуклой функции Текст] / И. Я. Заботин // Математич. программирование и приложения. Тез. докл.

88. Всерос. конф. ( Екатеринбург, 24 28 февр. 2003 г. ) - Екатеринбург, 2003. - С. 109.

89. Заботин, И. Я. Релаксационные алгоритмы условной минимизации негладких строго псевдовыпуклых функций Текст] / И. Я. Заботин // Изв. вузов. Математика. 2003. - ЛГ 12. - С. 62 - 70.

90. Заботин, И. Я. Методы выпуклого программирования, основанные на возможных направлениях Текст] / И. Я. Заботин, Я. И. Заботин. Набережные Челны: Филиал Казанск. ун - та в г. Набережные Челны. - 2006. - 44 с.

91. Заботин, И. Я. Две процедуры отсечений и их использование в методах минимизации Текст] / И. Я. Заботин // Проблемы оптимизации и экономические приложения. Материалы 3 Всерос. конф. ( Омск, 11-15 июля 2006 г. ) Омск, 2006. -С. 139.

92. Заботин, И. Я. Двойственность и двойственный метод в линейном программировании Текст] / И. Я. Заботин, Я. И. Заботин. Набережные Челны: Филиал Казанск. ун - та в г. Набережные Челны. - 2007. - 43 с.

93. Заботин, И. Я. Применение некоторых процедур отсечений в методах псевдовыпуклого программирования Текст] / И. Я. Заботин // Проблемы теоретич. кибернетики. Тез. докл. 15 Междунар. конф. ( Казань, 2-7 июня 2008 г. ) Казань: Отечество, 2008. - С. 38.

94. Заботин, Я. И. О вычислении конусов обобщенно опорных функционалов Текст] / Я. И. Заботин // Исслед. по прикл. матем. - Казань: Изд - во КГУ, 1971. - Вып. 4. - С. 3 - 10.

95. Заботин, Я. И. Контрпримеры к некоторым алгоритмам Зойтендейка Текст] / Я. И. Заботин // Изв. вузов. Математика. 1976. - N 11. - С. 32 - 37.

96. Заботин, Я. И. Минимаксный метод решения задачи математического программирования Текст] / Я. И. Заботин // Изв. вузов. Математика. 1975. - N 6. - С. 36 - 43.

97. Заботин, Я. И. Алгоритмы в методе центров с аппроксимацией множества допустимых решений Текст] / Я. И. Заботин, А. А. Андрианова // Изв. вузов. Математика. 2001. -N 12. - С. 41 - 45.

98. Заботин, Я. И. Релаксационный метод решения задачи условной минимизации функции максимума Текст] / Я. И. Заботин, О. А. Кашина // Исслед. по прикл. матем. Казань: Изд - во КГУ, 1987. - Вып. 14. - С. 25 - 34.

99. Заботин, Я. И. Псевдовыпуклые функционалы и их экстремальные свойства Текст] / Я. И. Заботин, А. И. Кораблев // Изв. вузов. Математика. 1974. -N 4.-С. 27-31.

100. Заботин, Я. И. Об одном обобщении понятия опорного функционала Текст] / Я. И. Заботин, А. И. Кораблев, Р. Ф. Хабибуллин // Труды 5-ой зимн. школы по матем. программированию и смежн. вопросам. М., 1973. - Вып 1. - С. 190 - 203.

101. Заботин, Я. И. Условия экстремума функционала при наличии ограничений Текст] / Я. И. Заботин, А. И. Кораблев, Р. Ф. Хабибуллин // Кибернетика. -1973. N 6. - С. 65 - 70.

102. Заботин, Я. И. О минимизации квазивыпуклых функционалов Текст] / Я. И. Заботин, А. И. Кораблев, Р. Ф. Хабибуллин // Изв. вузов. Математика. 1972. -N 10. - С. 27 - 33.

103. Заботин, Я. И. К сходимости методов отыскания минимакса Текст] / Я. И. Заботин, М. И. Крейнин // Изв. вузов. Математика. 1977. - N 10. - С. 56 - 64.

104. Завриев, С. К. Об устойчивости вычислительной схемы метода сопряженных градиентов Текст] / С. К. Завриев // Вопр. кибернетики. Анализ больших систем. -М., 1992. С. 102 - 118.

105. Зангвилл, У. И. Нелинейное программирование Текст] / У. И. Зангвилл. М.: Сов. радио, 1973. - 312 с.

106. Зойтендейк, Г. Методы возможных направлений Текст] / Г. Зойтендейк. М.: Ин. лит., 1963. - 176 с.

107. Зоркалъцев, В. И. Семейство проективных алгоритмов Текст] / В. И. Зоркальцев // Оптимизация: модели, методы, решения. Новосибирск: Наука, 1992. - С. 90 -116.

108. Зуховицкий, С. И. Алгоритм для решения задачи выпуклого программирования Текст] / С. И. Зуховицкий, Р. А. Поляк, М. Е. Примак // Докл. АН СССР. 1963. - Т. 153. - N 5. - С. 991 - 994.

109. Зуховицкий, С. И. Численный метод для решения задачи выпуклого программирования в гильбертовом пространстве Текст] / С. И. Зуховицкий, Р. А. Поляк, М. Е. Примак // Докл. АН СССР. 1965. - Т. 163. ~ N 2. - С. 282 - 284.

110. Ижуткин, В. С. Об одном классе методов возможных направлений решения задачи выпуклого программирования Текст] : автореф. дисс. . канд. физ. мат. наук / Ижуткин Виктор Сергеевич. - Казань, 1973. - 14 с.

111. Ижуткин, В. С. Об использовании эллипсоидной нормализации при решении задач выбора направления в методе линеаризации Текст] / В. С. Ижуткин // Вестник МГУ. Сер. 15. Вычислит, матем. и кибернетика. 1988. - N 3. - С. 43 - 49.

112. Ижуткин, В. С. О гибридном методе нелинейного программирования, использующем криволинейный спуск Текст] / В. С. Ижуткин, М. Ю. Кокурин // Изв. вузов. Математика. 1986. - iV 2. - С. 61 - 64.

113. Ижуткин, В. С. Методы приведенных направлений для задачи нелинейного программирования Текст] / В. С. Ижуткин, М. Ю. Кокурин // Журн. вычисл. матем. и матем. физ. 1988. - Т. 28. -N12.- С. 1799 - 1814.

114. Калашников, В. В. Решение двухуровнего вариационного неравенства Текст] / В. В. Калашников, Н. И. Калашникова // Кибернетика и системный анализ. 1994. -N6.-C. 178 - 180.

115. Карманов, В. Г. Математическое программирование Текст] / В. Г. Карманов. -М.: Наука, 1986. 288 с.

116. Князев, Е. А. Метод центров с адаптацией параметров на основе наискорейшего спуска Текст] / Е. А. Князев // Исслед. по прикл. матем. Казань: Изд - во КГУ, 1988. - Вып. 15. - С. 13 - 24.

117. Князев, Е. А. О параметризованной модификации метода центров для решения задачи выпуклого программирования Текст] / Е. А. Князев ; Казань, КГУ, 1983.- 18 с. Деп. в ВИНИТИ 18. 08. 83, N 4553 - 83.

118. Кобчиков, А. В. Синтез структуры и определение основных показателей качества информационно управляющих систем на ранних этапах проектирования Текст] / А. В. Кобчиков // Изв. АН СССР. Технич. кибернетика. - 1984. -N 2. - С. 180- 184.

119. Кокурин, М. Ю. Об одном подходе к коррекции несовместных вариационных неравенств Текст] / М. Ю. Кокурин // Изв. вузов. Математика. 1991. - N 4. - С. 16 - 24.

120. Колоколов, А. А. Регулярные разбиения и отсечения в целочисленном программировании Текст] / А. А. Колоколов // Сиб. журн. исслед. операций. 1994. - Т. 1. - N 2. - С. 18 - 39.

121. Конное, И. В. Метод типа сопряженных субградиентов для минимизации функционалов Текст] / И. В. Коннов // Исслед. по прикл. матем. Казань: Изд - во КГУ, 1984. - Вып. 12. - С. 59 - 62.

122. Коннов, И. В. О свойствах опорных и квазиопорных векторов Текст] / И. В. Коннов // Исслед. по прикл. матем. Казань: Изд - во КГУ, 1990. - Вып. 17. - С. 50 - 57.

123. Коннов, И. В. Двухуровневый субградиентный метод поиска седловых точек выпукло вогнутой функции Текст] / И. В. Коннов // Журн. вычисл. матем. и матем. физ. - 1993. - Т. 33. - ÍV 4. - С. 495 - 502.

124. Коннов, И. В. Комбинированные релаксационные методы для поиска точек равновесия и решения смежных задач Текст] / И. В. Коннов // Изв. вузов. Математика.- 1993. ÍV 2. - С. 46 - 53.

125. Коннов, И. В. Применение метода типа линеаризации при решении негладких равновесных задач Текст] / И. В. Коннов // Изв. вузов. Математика. 1996. - N 12. - С. 54 - 62.

126. Коннов, И. В. О системах вариационных неравенств Текст] / И. В. Коннов // Изв. вузов. Математика. 1997. - N 12. - С. 79 - 88.

127. Корабле в, А. И. О релаксационных методах минимизации псевдовыпуклых функций Текст] / А. И. Кораблев // Исслед. по прикл. матем. Казань: Изд - во КГУ, 1980. - Вып. 8. - С. 3 - 8.

128. Кораблев, А. И. Субградиентные методы минимизации псевдовыпуклых функционалов Текст] : дис. . канд. физ. мат. наук / Кораблев Анатолий Иванович. -Казань, 1979. - 107 с.

129. Кораблев, А. И. £ субградиентный метод решения нелинейных экстремальных задач Текст] / А. И. Кораблев // Исслед. по прикл. матем. - Казань: Изд - во КГУ, 1979. - Вып. 7. - С. 3 - 11.

130. Левитин, Е. С. Методы минимизации при наличии ограничений Текст] / Е. С. Левитин, Б. Т. Поляк // Журн. вычисл. матем. и матем. физ. 1966. - Т. 6. - N 5. - С. 787 - 823.

131. Любич, Ю. И. Общая теория релаксационных процессов для выпуклых функционалов Текст] / Ю. И. Любич, Г. Д. Майстровский // Успехи матем. наук. 1970.- Т. 25. Вып. 1. - С. 57 - 112.

132. Мину, М. Математическое программирование Текст] / М. Мину. М.-. Наука, 1990. - 488 с.

133. Михалевич, В. С. Методы невыпуклой оптимизации Текст] / В. С. Михалевич, А. М. Гупал, В. И. Норкин. М.: Наука, 1987. - 280 с.

134. Михалевич, В. С. Сложные системы и решение экстремальных задач Текст] / В. С. Михалевич, Ю. М. Ермольев, В. В. Шкурба, Н. 3. Шор // Кибернетика. 1967.- N 5. С. 29 - 39.

135. Моисеев, H. Н. Численные методы в теории оптимальных систем Текст] / H. Н. Моисеев. М.: Наука, 1971. - 424 с.

136. Моисеев, H. Н. Методы оптимизации Текст] / H. Н. Моисеев, Ю П. Иванилов, Е. М. Столярова. М.: Наука, 1978. - 352 с.

137. Мухачева, Э. А. Математическое программирование Текст] / Э. А. Мухачева, Г. Ш. Рубинштейн. М.: Наука, 1987. - 274 с.

138. Немировский, А. С. Сложность и эффективность методов оптимизации Текст] / А. С. Немировский, Д. Б. Юдин. М.: Наука, 1979. - 383 с.

139. Нестеров, Ю. Е. Об одном подходе к построению оптимальных методов минимизации гладких выпуклых функций Текст] / Ю. Е. Нестеров // Экономика и матем. методы. 1988. - Т. 24. - Вып. 3. - С. 509 - 517.

140. Нестеров, Ю. Е. Эффективные методы в нелинейном программировании Текст] / Ю. Е. Нестеров. М.: Радио и связь, 1989. - 383 с.

141. Нефедов, В. Н. Отыскание глобального максимума функции нескольких переменных на множестве, заданном ограничениями типа неравенств Текст] / В. Н. Нефедов // Журн. вычисл. матем. и матем. физ. 1987. - Т.27. - N 1. - С. 35 -51.

142. Нурминский, Е. А. Численные методы решения детерминированных и стохастических минимаксных задач Текст] / Е. А. Нурминский. Киев: Наукова думка, 1979. - 158 с.

143. Нурминский, Е. А. Об одном классе методов выпуклого программирования Текст] / Е. А. Нурминский // Журн. вычисл. матем. и матем. физ. 1986. - Т. 26. - N 8.- С. 1150 1159.

144. Панин, В. М. О некоторых методах решения задач выпуклого программирования Текст] / В. М. Панин // Журн. вычисл. матем. и матем. физ. 1981. - Т. 21. - N 2. - С. 315 - 328.

145. Пинягина, О. В. Общий метод выпуклого программирования с заданной точностью Текст] / О. В. Пинягина, В. Р. Фазылов // Изв. вузов. Математика. 1995. -N 12. - С. 63 - 73.

146. Пиявский, С. А. Один алгоритм отыскания абсолютного экстремума функции Текст] / С. А. Пиявский // Журн. вычисл. матем. и матем. физ. 1972. - Т. 12. - N 4. - С. 888 - 896.

147. Полок, Э. Численные методы оптимизации. Единый подход Текст] / Э. Полак. -М.: Мир, 1974. 376 с.

148. Поляк, Б. Т. Введение в оптимизацию Текст] / Б. Т. Поляк. М.: Наука, 1983. -384 с.

149. Поляк, Б. Т. Сравнение скорости сходимости одношаговых и многошаговых алгоритмов оптимизации при наличии помех Текст] / Б. Т. Поляк // Технич. кибернетика. 1977. - iV 1. - С. 9 - 12.

150. Поляк, Б. Т. Минимизация негладких функционалов Текст] / Б. Т. Поляк // Журн. вычисл. матем. и матем. физ. 1969. - Т. 9. - N 3. - С. 509 - 521.

151. Попов, JI. Д. Об одноэтапном методе решения лексикографических вариационных неравенств Текст] / JI. Д. Попов // Изв. вузов. Математика. 1998. - N 12. - С. 71 - 81.

152. Пропой, А. И. К теории максиминных задач Текст] / А. И. Пропой // Журн. вычисл. матем. и матем. физ. 1971. - Т. 11. - N 1. - С. 65 - 78.

153. Пшеничный, Б. Н. Метод линеаризации Текст] / Б. Н. Пшеничный. М.: Наука, 1983. - 136 с.

154. Пшеничный, Б. Н. Численные методы в экстремальных задачах Текст] / Б. Н. Пшеничный, Ю. М. Данилин. М.: Наука, 1975. - 320 с.

155. Ржевский, С. В. е субградиентный метод решения задачи выпуклого программирования Текст] / С. В. Ржевский // Журн. вычисл. матем. и матем. физ. - 1981.- Т. 21. N 5. - С. 1126 - 1132.

156. Родионов, А. В. О методе тяжелого шарика Текст] / А. В. Родионов // Вопр. кибернетики. Модели и методы анализа больш. систем. М., 1991. - С. 96 - 104.

157. Саттаров, Р. Н. Метод нахождения минимакса при наличии ограничений Текст] / Р. Н. Саттаров // Исслед. по прикл. матем. Казань: Изд - во КГУ, 1988. - Вып. 15. - С. 30 - 37.

158. Скарин, В. Д. О методе регуляризации для противоречивых задач выпуклого программирования Текст] / В. Д. Скарин // Изв. вузов. Математика. 1995. - N 12.- С. 81 88.

159. Стрекало в ский А. С. Элементы невыпуклой оптимизации Текст] / А. С. Стре-каловский. Новосибирск: Наука, 2003. - 356 с.

160. Стрекаловский А. С. Условия глобальной оптимальности в задачах cl.с. программирования Текст] / А. С. Стрекаловский. Иркутск: Иркутский государственный университет, 1997. - 61 с.

161. Стронгин, Р. Г. Численные методы в многоэкстремальных задачах Текст] / Р. Г. Стронгин. М.: Наука, 1978. - 240 с.

162. Сухарев, А. Г. Оптимальный поиск экстремума Текст] / А. Г. Сухарев. М.: МГУ, 1975. - 100 с.

163. Сухарев, А. Г. Курс методов оптимизации Текст] / А. Г. Сухарев, А. В. Тимохов, В. В. Федоров. М.: Наука, 1986. - 328 с.

164. Тихонов, А. Н. Методы решения некорректных задач Текст] / А. Н. Тихонов, В. Я. Арсенин. М.: Наука, 1979. - 288 с.

165. Тихонов, А. Н. О регуляризации задач минимизации на множествах, заданных приближенно Текст] / А. Н. Тихонов, Ф. П. Васильев, M. М. Потапов, А. Д. Юрий // Вестник МГУ. Сер. вычисл. матем. и киберн. 1977. - N 1. - С. 4 - 19.

166. Третьяков, А. А. Две схемы нелинейного метода оптимизации в экстремальных задачах Текст] / А. А. Третьяков // Журн. вычисл. матем. и матем. физ. 1984.- Т. 24. N 7. - С. 986 - 992.

167. Фазылов, В. Р. Опорный конус для многогранника Текст] / В. Р. Фазылов // Исслед. по прикл. матем. Казань: Изд - во КГУ, 1980. - Вып. 8. - С. 15 - 17.

168. Фазылов, В. Р. Метод опорых векторов с составным шагом для решения задачи отыскания точки выпуклого множества Текст] : дис. . канд. физ. мат. наук / Фазылов Валерий Рауфович - Казань, 1982. - 117 с.

169. Фазылов, В. Р. Отыскание минимакса с заданной точностью Текст] / В. Р. Фа-зылов // Журн. вычисл. матем. и матем. физ. 1994. - Т. 34. - N 5. - С. 793 -799.

170. Федоров, В. В. Численные методы максимина Текст] / В. В. Федоров. М.: Наука, 1979. - 280 с.

171. Хабибуллии, Р. Ф. Субградиентный метод минимизации выпуклых функционалов и оценки его эффективности Текст] / Р. Ф. Хабибуллин // Исслед. по прикл. матем. Казань: Изд - во КГУ, 1984. - Вып. 12. - С. 25 - 35.

172. Хамисов, О. В. Алгебраическое решение задач невыпуклого квадратичного программирования Текст] / О. В. Хамисов // Автоматика и телемеханика. 2004. -N 2. - С. 41 - 60.

173. Хамисов, О.В. Глобальная оптимизация функций с вогнутой минорантой Текст] / О. В. Хамисов // Журн. вычисл. матем. и матем. физ. 2004. - Т. 44. - N 9. -С. 1552 - 1563.

174. Химмелъблау, Д. Прикладное нелинейное программирование Текст] / Д. Хим-мельблау. М.: Мир, 1975. - 536 с.

175. Хотеев, С. В. О многошаговых градиентных методах в задачах оптимизации Текст] / С. В. Хотеев // Вопр. кибернетики. Модели и методы анализа больш. систем. М., 1991. - С. 104 - 111.

176. Шор, Н. 3. Методы минимизации недифференцируемых функций и их приложения Текст] / Н. 3. Шор. Киев: Наукова думка, 1979. - 199 с.

177. Элъстер, К. X. Введение в нелинейное программирование Текст] / К. - X. Эльстер, Р. Рейнгардт, М. Шойбле, Г. Донат. - М.: Наука, 1985. - 264 с.

178. Юдин, Д. Б. Задачи и методы стохастического программирования Текст] / Д. Б. Юдин. М.: Сов. радио, 1979. - 392 с.

179. Юдин, Д. Б. Информационная сложность и эффективные методы выпуклого программирования Текст] / Д. Б. Юдин, А. С. Немировский. М.: Наука, 1977. - 460 с.

180. Юрлов, Ф. Ф. Технико экономическая эффективность сложных радиоэлектронных систем Текст] / Ф. Ф. Юрлов. - М.: Сов. радио, 1980. - 280 с.

181. Arrow, К. J. Quasi concave programming Текст] / К. J. Arrow, А. С. Enthoven // Econometrica - 1961. - V. 29. - N 4. - P. 779 - 800.

182. Bereanu, В. Quasi convexity, strictle quasi - convexity of composite objective functions Текст] / В. Bereanu // Rev. franc, automat., inform., recy. oper. - 1972.- V. 6. iV 1. - P. 15 - 26.

183. Cottle, R. W. On pseudo convex functions of nonegative variables Текст] / R. W. Cottle, J. A. Ferland // Mathem. Progr. - 1971. - V. 1. - N 1. - P. 95 - 101.

184. Ferland, J. A. Mathematical programming problems with quasi convex objective functions Текст] / J. А/ Ferland // Mathem. Progr. - 1972. - V. 3. - iV 3. - P. 296 -301.

185. Greenberg, H. J. A review of quasi convex functions Текст] / H. J. Greenberg, W. P. Pierskalla // Oper. Res. - 1971. - V. 19. - N 7. - P. 1553 - 1570.

186. Gupta, S. K. Generalized pseudo convex functions Текст] / S. K. Gupta, S.K. Bhatt // Cah. Cent. Etud. Reach. Oper. - 1972. - V. 14. - TV 4. - P. 213 - 222.

187. Handbook of Generalired Convexity and Generalized Monotonicity Текст] / Eds.: N. Hadjisavvas, S. Komlosi, S. Schaible. Berlin, Springer, 2005. - 672 p.

188. Huard, P Resolution of mathematical programming with nonlinear constraints by the method of centres Текст] / P. Huard // Nonlinear programming. Amsterdam, North Holland, 1967. - P. 207 - 219.

189. Kelley, J. E. The cutting plane method for solving convex programs Текст] / J. E. Kelley // SIAM J. - 1960. - V. 8. - N 4. - P. 703 - 712.

190. Konnov, I. V. Equilibrium models and variational inequalities Текст] / I. V. Konnov.- Elsevier, Amsterdam, 2007. 250 p.

191. Konnov, I. V. Combined relaxation methods for variational inequalities Текст] / I. V. Konnov. Springer, Berlin, 2001. - 181 p.

192. Lemarechal, C. An algorithm for minimizing convex functions Текст] / С. Lemarechal // Proc. IFIP Cong. Amsterdam, 1974. - P. 552 - 556.

193. Lemarechal, C. Nondifferentiable optimization subgradient and e subgradient methods Текст] / С. Lemarechal // Lect. Notes Econ. and Mathem. Syst. - 1975.- N 117. P. 191 - 199.

194. Luenberger, D. G. Quasi convex programming Текст] / D. G. Luenberger // SIAM J. Appl. Math. - 1968. - N 5. - P. 1090 - 1095.

195. Mangasarian, O. L. Pseudo convex functions Текст] / О. L. Mangasarian //J. Soc. industr. and appl. math. Ser. A. - 1965. - V. 3. - P. 281 - 290.294 1

196. Mangasarian, 0. L. Convexity, pseudo convexity and quasi - covexity of composite functions Текст] / О. L. Mangasarian // Cah. Cent. etud. rech. oper. - 1970. - V. 12. -N 2. - P. 114 - 122.

197. Mifflin, R. Semismooth and semiconvex functions in constrained optimization Текст] / R. Mifflin // SIAM J. Contr. and Optim. 1977. - V. 15. - N 6. - P. 959 - 972.

198. Veinot, A. F. The supporting hyperplane method unimodal programming Текст] / A. F. Veinot // Oper. Res. 1967. - V. 15. -N 1. - P. 147 - 152.

199. Wolfe, P. On the convergence of gradient methods under constraint Текст] / P. Wolfe // IBM J. Res. Dev. 1972. - V. 16. - N 4. - P. 407 - 411.

200. Wolfe, P. A method of conjugate subgradients for minimizing nondifferentiable functions Текст] / P. Wolfe // Math. Program. 1975. - Study 3. - P. 145 - 173.

201. Zhu, D. Coupling the auxiliary problem principle with descent methods of pseudoconvex programming Текст] / D. Zhu, P. Marcotte // EJOR 1995. - V. 83. -N 3. - P. 670 - 685.