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

ВВЕДЕНИЕ.

Глава I. МЕТОДЫ ПОГРУЖЕНИЯ ДЮ1 МИНИМИЗАЦИИ

ГЛАДКИХ ФУНКЦИЙ . п

§ 1.1. Метод обобщенно опорных гиперплоскостей для решения задачи математического программирования . II

§ 1.2. Метод типа условного градиента с частичным погружением допустимого множества.

§ 1.3. Итеративная регуляризация одного варианта метода типа условного градиента с погружением допустимого множества

§ 1.4. Проекционный метод с погружением допустимого множества.

§ 1.5. Вариант метода Ньютона с частичным погружением допустимого множества

Глава II. РЕЛАКСАЦИОННЫЕ СУБГРАДИЕНТНЫЕ МЕТОДЫ

МИНИМИЗАЦИИ.

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

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

§ 2.3. Конечный метод отыскания точки выпуклого множества.

§ 2.4. Метод условного £ - субградиента.

Глава Ш. РЕШЕНИЕ ТЕСТОВЫХ И ПРИШДШХ ЗАДАЧ.

§ 3.1. Решение тестовых задач методом условного

- субградиента.

§ 3.2. Применение метода типа условного градиента с погружением допустимого множества для решения задачи синтеза информационно-управляющей системы (ИУС)

§ 3.3. Применение метода условного £. - субградиента для решения задачи выбора оптимальных времен функционирования подсистем ИУС.

Построение методов решения задач нелинейного программирования и их численная реализация постоянно пользуются вниманием математиков-вычислителей. В тесной связи с разработкой методов находятся и вопросы оценки их эффективности (см.,напр., [ 15,47,49, 66,67,69,84,90] ). К настоящему времени накоплено значительное число методов минимизации нелинейных функций, складывается определенная их классификация. Различные подходы к построению методов решения нелинейных экстремальных задач предложены в [1-3,6,9,17, 18,23,44-46,48,50-52,55,63-65,68,75,79,81,83],и этот перечень работ далеко не полон. Среди упомянутых можно найти работы, посвященные методам минимизации выпуклых и невыпуклых, гладких и негладких функций. В последнее время большое внимание уделяется разработке методов минимизации недифференцируемых функций. Остановимся на некоторых из них подробнее.

Большую группу методов минимизации негладких функций образуют так называемые субградиентные методы. Одним из первых представителей этой группы является метод обобщенного градиентного спуска (ОГС), предложенный Н.З.Шором (см.,напр., [94]). В дальнейшем субградиентные методы разрабатывались в [20,21,28,29,59,62,72,76, 77,94,95]. Для ускорения скорости их сходимости были предложены варианты метода ОГС с растяжением пространства ([94 - 96]). В [41, 42] Я.И.Заботиным, А.И.Кораблевым, Р.Ф.Хабибуллиннм метод ОГС был распространен на задачи минимизации квазивыпуклых функций. В [94, 96] установлена связь методов ОГС и фейеровских приближений ([2527]), ОГС и методов отсечений ([69]).

Другую группу методов для минимизации недифференцируемых функций составляют £ - субградиентные методы и близкие к ним методы сопряженных субградиентов. Впервые £ - субградиенты использованы В.Ф.Демьяновым в алгоритмах типа наискорейшего спуска для решения минимаксных задач- (см., напр., [22]). В дальнейшем методы решения минимаксных задач разрабатывались, в частности, в С21,22, 43,62,89,94] . £ - субградиентные методы и методы сопряженных субградиентов минимизации произвольных выпуклых функций предложены в [21,62,70,71,82,87,101-103,104,108,109] . В работах А.И.Ко-раблева [58-61] ¿ - субградиентные алгоритмы обобщены на классы квазивыпуклых и псевдовыпуклых функций.

В последнее время выделился еще один важный класс экстремальных задач, которые требуют специальных методов решения. Это класс некорректных экстремальных задач. Первые методы их решения (методы регуляризации) принадлежат А.Н.Тихонову и подробно описаны в [10,85]. Методам регуляризации посвящены также работы [7,8, 10,11,86] . Идея этих методов заключается в последовательном решении так называемых стабилизированных задач. Оказывается, что для решения их можно применять некоторые известные методы минимизации функций, если согласовать параметры метода с параметрами стабилизации, или,другими словами, провести итеративную регуляризацию методов (см. ^10,12,13,24] ).

Однако, несмотря на большое количество работ в области нелинейного программирования, и сейчас еще численная реализация многих методов минимизации вызывает, зачастую, значительные сложности. Одной из причин трудной реализуемости некоторых методов является то, что в них для перехода от одной итерационной точки к другой приходится решать вспомогательные задачи условной минимизации, которые часто сами по себе не многим легче исходной задачи. Примером могут служить хорошо известные методы условного градиента, проекции градиента, метод Ньютона (см. С 9,23,55,63,68,79,83]) и некоторые другие. Эти методы характерны тем, что на каждом шаге для нахождения направления спуска в итерационной точке решается задача минимизации вспомогательной функции (линейной в методе условного градиента и нелинейной - в двух других) на допустимом множестве. Если допустимое множество задано нелинейными неравенствами, то упомянутые методы являются трудно реализуемыми, поскольку в таком случае решение вспомогательных задач в них связано с большими вычислительными затратами.

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

Одна из идей, на которую можно опираться цри построении методов такого типа, является идея погружения допустимого множества в некоторое выпуклое множество более простой структуры, например, в многогранник с целью упрощения подзадач нахождения итерационных точек. Эта идея присутствует, например, в методе опорных множеств В.П.Булатова (см. С 6]) ив ряде других методов погружения (см. [14,44,63,100,107,110]) следующим образом. Строится последовательность вложенных друг в друга выпуклых множеств, как правило многогранников, содержащих допустимое множество, и точки минимума целевой функции на этих охватывающих множествах принимаются за приближенные решения исходной задачи. В этих работах предложены способы построения аппроксимирующих множеств с помощью отсечений получаемых на каждом шаге итерационных точек. В случае, когда целевая функция линейна, в упомянутых методах подзадачи отыскания итерационных точек практически разрешимы, т.к. являются задачами линейного программирования. Идейно близкие методы отсечений использованы в [5,6,19,74] для решения многоэкстремальных задач. Операции погружения и отсечения множеств, в том или ином виде,используются также в работах [69,91,96,98,99,105,106] . Отметим,что если идею аппроксимации допустимого множества рассматривать широко, то метод линеаризации Б.Н.Пшеничного ([ 79,81] ) и ряд близких к нему алгоритмов (см.,напр., [73,81]) также можно отнести к своеобразным методам погружения, в которых на каждом шаге для решения задачи отыскания направления спуска производится аппроксимация допустимого множества многогранным путем его линеаризации.

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

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

Диссертация состоит из трех глав. Первая глава посвящена разработке методов погружения для условной минимизации гладких функций. Во втором, четвертом и пятом параграфах предложены методы минимизации, которые обобщают, соответственно, методы условного градиента, проекции градиента и метод Ньютона. Предложенные методы характерны тем, что в них на каждом шаге строится выпуклое замкнутое множество, частично или полностью содержащее допустимое множество, достаточно хорошо его аппроксимирующее, и для отыскания направления спуска решается задача минимизации вспомогательной функции на этом аппроксимирующем множестве. С практической точки зрения это множество удобно строить как многогранное. Если допустимое множество задачи определено нелинейными неравенствами, то предложенные в работе методы¡редпочтительнее упомянутых, поскольку вспомогательные задачи в них проще соответствующих вспомогательных задач методов условного градиента, проекции градиента и метода Ньютона. Отметим, что, если охватывающее множество в предложенных методах выбирать совпадающим с допустимым, то они превращаются в известные варианты названных методов. Кроме того, если в методе проекции градиента операция проектирования осуществляется на каждом шаге, то в методе из § 4 на некоторых итерациях она может опускаться. Этот факт позволил предложить в § 4 модификацию метода проекции градиента. Доказана сходимость предложенных методов и почти для всех их вариантов получены оценки скорости сходимости. Для построения аппроксимирующих множеств используется метод обобщенно опорных гиперплоскостей (00Г), разработанный в первом параграфе. Метод 00Г решения задачи математического программирования позволяет строить требуемые аппроксимирующие множества в виде многогранных множеств за конечное число шагов. В первом параграфе показано также, что метод 00Г может быть полезен для приближенного решения некоторых задач линейного программирования и, кроме того, может служить реализуемым способом отыскания направлений спуска в одном известном варианте метода условного градиента ((55] ). В третьем параграфе идея погружения применяется для решения некорректных задач. По методике Ф.П.Васильева (СЮ]) проведена итеративная регуляризация одного варианта предложенного во втором параграфе метода. Основные результаты первой главы опубликованы в [32 - 37] . В заметке [37] автору принадлежат теоретические результаты, а О.В.Боглаевским проведены алгоритмизация и численные эксперименты.

Вторая глава посвящена релаксационным методам минимизации недифференцируемых функций. В первом параграфе предлагаются две общие итерационные схемы отыскания точки выпуклого множества из R , использующие его погружение, описываются их реализации. С помощью одной из них можно за конечное число шагов для строго выпуклой функции получать в точке у направления спуска, погружая в многогранник множество ЧЧ*) ^ ср(у ) } .Оказывается, что построенное таким образом направление спуска позволяет существенно уменьшить значение функции. Этот факт использован в следующем параграфе при построении релаксационного субградиентного метода минимизации строго выпуклых функций. Этот метод является обобщением на случай негладких функций одного метода минимизации, предложенного автором в [31] . В третьем параграфе предлагается общая схема нахождения элемента из конуса, сопряженного к выпуклому конусу и на её основе строится конечный метод отыскания точки выпуклого множества Q . Предлагаются различные реализации его для случая, когда G^i^ € F(х) ^ 0 } } f(oc) - квазивыпуклая в R. функция. В § 4 разработан метод условного £ - субградиента для минимизации квазивыпуклой в R^ функции •f(x) на выпуклом замкнутом множестве. Способ построения направления спуска в методе условного £ - субградиента основан на предложенном в § 3 методе отыскания точки из множества. Этот способ интересен тем, что обобщает известный подход проектирования нуля на выпуклую оболочку субградиентов и позволяет в итерацион

ИОНОЙ точке Хк за конечное число малых итераций отыскать направление спуска такое, что £+ ) ^ ^(х^) - £ , Ч > О , для некоторого . Метод предусматривает также возможность выбора вектора из менее жесткого условия. Для этого случая по схеме, распространяющей методику В.Г.Карманова ([53 - 55]) на негладкие задачи, получена оценка скорости сходимости метода к £ -- оптимальному значению функции 4 (ос) . Предложены различные реализации метода для задач безусловной и условной минимизации, одна из которых допускает возможность использования погружающего множества с целью упрощения решения вспомогательных задач построения направлений спуска, когда допустимое множество задано в общем виде, Основные результаты второй главы опубликованы в [31,38] . В [38] А.И.Кораблеву принадлежит постановка задачи. Метод условного В- - субградиента разрабатывался авторами совместно. И.Я.Заботи-ну принадлежат обоснование сходимости метода и некоторые его реализации.

В третьей главе обсуждаются результаты численных экспериментов: при решении некоторых тестовых задач методом типа условного градиента из § 2 первой главы и методом условного £ - субградиента. Во втором и третьем параграфах этими методами, соответственно, решены задача синтеза информационно-управляющей системы (МУС) и задача выбора оптимальных времен функционирования подсистем ИУС, Результаты этой главы опубликованы в [57].

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

ЗАКШОЧЕНИЕ

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

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

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

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

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

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

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

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

8. Построен конечный метод отыскания точки выпуклого множества и на его основе разработан метод условного £ - субградиента для минимизации квазивыпуклых функций при наличии ограничений. Описаны реализации метода. Получена оценка скорости его сходимости.

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

10. Решена прикладная задача синтеза информационно-управляющей системы (ИУС). При решении использован метод с частичным погружением допустимого множества. Выбор метода был обусловлен спецификой задачи. Методом условного £ - субградиента решена также задача выбора оптимальных времен функционирования подсистем ИУС. Алгоритм этого метода включен в математическое обеспечение проектирования ИУС кафедрой радиофизики КГУ.

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

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

3. Богомолов H.A., Карманов В.Г. О методе вычисления стационарных точек общей задачи нелинейного программирования. Ж. вычислит.матем. и матем. физики, 1977, т. 17, J& I, с. 72-78.

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

5. Булатов В.П. Методы аппроксимации в многоэкстремальных задачах. В кн.: Тезисы докл.конф. "Экстремальные задачи и их приложения". Горький, 1971.

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

7. Васильев Ф.П. О регуляризации некорректных экстремальных задач. Докл. АН СССР, 1978, т. 241, & 5, с. I00I-I004.

8. Васильев Ф.П. О рехуляризащш некорректных задач минимизации на множествах, заданных приближенно. Ж.вычисл.матем. и матем.физики, 1980, т. 20, № I, с.38-50.

9. Васильев Ф.П. Численные методы решения экстремальных задач. М.: Наука, 1980. - 520 с.

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

11. Васильев Ф.П., Ковач М. О регуляризации некорректных экстремальных задач с использованием штрафных и барьерных функций. Вестник Московск.ун-та. Сер.вычислит.матем. и ки-берн., 1980, № 2, с. 29-35.

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

13. Васильев Ф.П., Ячимович М.Д. Об итеративной регуляризации метода Ньютона. Ж.вычисл.матем. и матем.физики,1981,т.21, В 3, с.775-778.

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

15. Данилин Ю.М., Морарь В.А. Квазиньютоновские методы условной минимизации. Кибернетика, 1979, Л? 5, с. 80-86.

16. Данилин Ю.М., Пиявский С.А. Об одном алгоритме отыскания абсолютного минимума. В кн.: Теория оптимальных решений. Вып. 2. Киев : Изд-во ИК АН УССР, 1967.

17. Демьянов В.Ф. Модифицированный метод обобщенного градиента при наличии ограничений. Вестник ЛГУ, 1978, 19, с. 2529.

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

19. Демьянов В.Ф., Малоземов В.Н. Введение в минимакс. М.: Наука, 1972. - 368 с.-ш

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

21. Денисов Д.В. Метод итеративной регуляризации в задачах условной минимизации. Ж.вычислит.матем. и матем.физики, 1978, т. 18, № 6, с. I405-I4I5.

22. Еремин И.И. Метод фейеровских приближений в выпуклом программировании. Матем.заметки, 1968, т.З, с. 217-234.

23. Еремин И.И. Применение метода фейеровских приближений к решению задач выпуклого программирования с негладкими ограничениями. Я.вычислит.матем. и матем.физики, 1969, т.9, $5, с. II53-II60.

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

25. Ермольев Ю.М. Методы решения нелинейных экстремальных задач. Кибернетика, 1966, № 4, с. I-I7.

26. Ермольев Ю.М., Шор Н.З. 0 минимизации не дифференцируемых функций. Кибернетика, 1967, № I, с.101-102.

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

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

29. Заботин И.Я. Об одном методе типа условного градиента с частичным погружением допустимого множества. В сб.: Системы программного обеспечения решения задач оптимального планирования. Тезисы до,юг. УП Всесоюзн.симп. - М.,1982,с. 132.

30. Заботин И.Я. 0 методах условной минимизации функций с наилучшими относительно множества направлениями спуска. Известия вузов. Математика, 1982, № 7, с.11-16•

31. Заботин И.Я. Один вариант метода Ньютона с погружением допустимого множества. Казань, 1983. - II с. - Рукопись представлена Казан .ун-том. Деп. в ВИНИТИ 20 января 1983,$ 353-83 Деп.

32. Заботин И.Я. Итеративная регуляризация метода условного градиента с погружением допустимого множества. Казань, 1983, - 15 с. - Рукопись представлена Казан.ун-том. Деп. в ВИНИТИ 16 февраля 1983, № 852-83 Деп.

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

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

35. Заботин Я.И. О вычислении конусов обобщенно-опорных функционалов. В сб.: Исследования по прикладной математике. Ка-нззань, 1971, вып.4, с.3-10.

36. Заботин Я.И., Кораблев А.И., Хабибуллин Р.Ф. 0 минимизации квазивыпуклых функционалов. Известия вузов, Математика,1972, JS 10, с. 27-33.

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

38. Заботин Я.И., Крейнин М.И. К сходимости методов отысканияминимакса. Известия вузов. Математика, 1977, $ 10, с.56-64.

39. Зангвилл У.И. Нелинейное программирование. М.: Сов.радио,1973. 312 с.

40. Зойтендейк Г. Методы возможных направлений. М.: ИЛ,1963. - 175 с.

41. Иванов В.В. Об алгоритмах быстрого спуска. Докл.АН СССР, 1962, т. 143, № 4, с. 775-778.

42. Иванов В.В. Об оптимальных алгоритмах минимизации функций некоторых классов. Кибернетика, 1972, J& 4, с. 81-94.

43. Иванов В.В., Людвиченко В.А. Об одном методе последовательной безусловной минимизации решения задач математического программирования. Кибернетика, 1977, В 2, с. 1-8.

44. Иванов В.В., Людвиченко В.А., Шхалевич B.C., Трубин В.А., Шор Н.З. Вопросы повышения эффективности алгоритмов минимизации функций и математического программирования. Киев, 1979. - 54 с. (Препринт/институт кибернетики.: 79-59).

45. Ижуткин B.C. Мультиплексный метод для задачи выпуклого программирования. Кибернетика, 1973, J6 3, с. 123-127.

46. Ижуткин B.C. Метод спуска с оператором проектирования для решения задачи выпуклого программирования. Тезисы докл.У!

47. Всесоюзн.конф.по экстрем, задачам и их приложениям. Таллин, 1973, с. 148.

48. Ижуткин B.C. Об одном классе методов возможных направлений решения задачи выпуклого программирования: Автореф.дис. . канд.физ.-мат.наук Казань, 1973. - 14 с.

49. Карманов В.Г. Оценки сходимости итерационных методов минимизации. Ж.вычислит.матем. и матем.физики, 1974, т. 14, № I, с. 3-14.

50. Карманов В.Г. об одном подходе к исследованию сходимости релаксационных процессов минимизации. Ж.вычислит.матем. и матем.физики , 1974, т.14, № 6, с. I58I-I585.

51. Карманов В.Г. Математическое программирование. М.: Наука, 1980. - 256 с.

52. Кобчиков A.B. Об одном подходе к проектированию информационно-измерительных систем. В сб.: Прием и обработка информации в сложных информационных системах. Казань, 1980, с. 8-14.

53. Кораблев А.И. О релаксационных методах минимизации псевдовыпуклых функций. Известия вузов. Матем., 1978, № 10,с.99-101.

54. Кораблев А.И. Субградиентные методы минимизации псевдовыпуклых функционалов: Автореф.дис. . канд.физ.-мат.наук, Казань, 1979. - 22 с.

55. Кораблев А.И. субградиентный метод решения нелинейных экстремальных задач. - В сб.: Исследования по прикладнойматематике. Казань, 1979, с. 3-II.

56. Кораблев А.И., Миронов О.В. Один алгоритм £ субградиентного метода минимизации и его применение. - В сб.: Исследования по прикл. математике. Казань, 1979, с.12-18.

57. Крейнин М.И. Релаксационные алгоритмы минимизации недифференцируемых функций: Автореф.дис. . канд.физ.-мат.наук, Казань, 1981. - 14 с.

58. Левитин Е.С., Поляк Б.Т. Методы минимизации при наличии ограничений. S.вычислит.матем. и матем.физики, 1966, т.6,1. В 5, с. 787-823.

59. Лямин Е.В. Один способ выбора длины шага в методе условного градиента. Казань, 1980. - 10 с. - Рукопись представлена Казан.ун-том. Деп. в ВИНИТИ 30 июля 1980, № 2710-80 Деп.

60. Лямин Е.В. К сходимости одного варианта метода условного градиента. Казань, 1981. - 18 с. - Рукопись представлена Казан.ун-том. Деп. в ВИНИТИ I июня 1981, № 2613-81 Деп.

61. Михалевич B.C. Последовательные алгоритмы оптимизации и их применение. Кибернетика, 1965, Л I, с.45-46.

62. Михалевич B.C. Последовательные алгоритмы оптимизации и их применение. Кибернетика, 1965, № 2, с.85-89.

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

64. Немировский A.C., фцин Д.Б. Сложность задач и эффективность методов оптимизации. М.: Наука, 1979. - 384 с.

65. Ненахов Э.И. 0 методе сопряженных субградиентов для решения задач безусловной оптимизации. В сб.: Теория оптимальных решений. Киев, 1976, с. 3-10.

66. Панин В.М. О некоторых методах решения задач выпуклого программирования. S.вычислит.матем. и матем.физики, 1981,т.21, № 2, с.315-328.

67. Пиявский С.А. Один алгоритм отыскания абсолютного экстремума функций. К.вычислит.матем. и матем.физики, 1972, т.12,4.

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

69. Поляк Б.Т. Один общий метод решения экстремальных задач. -Докл. АН СССР, 1967, т.174, £ I, с.33-36.

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

71. Поляк Б.Т. Методы минимизации при наличии ограничений. -В сб.: Матем. анализ, сер. "Итоги науки и техники". М.: ВИНИТИ АН СССР, 1974, т.12, с. 147-198.

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

73. Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи. -М.: Наука, 1980. 319 с.

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

75. Ржевский C.B. £ субградиентный метод решения задачи выпуклого программирования. - Ж.вычислит.матем. и матем.физики, 1981, т.21, № 5, с. II26-II32.

76. Cea Ж. Оптимизация. Теория и алгоритмы. М.: Мир, 1973. - 244 с.

77. Сухарев А.Г. Оптимальный поиск экстремума. М.: Изд-во МГУ, 1975. - 100 с.- И 785. Тихонов А.И., Арсенин В.Я. Методы решения некорректных задач. М.: Наука, 1979. - 288 с.

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

79. Фазылов В.Р. Метод опорных векторов с составным шагом для решения задачи отыскания точки выпуклого множества: Авто-реф.дис. . канд.физ.-мат.наук. Казань, 1982. - 12 с.

80. Фазылов В.Р. Опорный конус для многогранника. В сб.: Исследования по прикладной математике. Казань, 1980, вып.8, с.15-17.

81. Федоров В.В. Численные методы максимина. М.: Наука.-280 с.

82. Хачиян Л.Г. Полиномиальные алгоритмы в линейном программировании. Ж.вычислит.матем. и матем. физики, 1980, т. 20, № I, с. 51-68.

83. Чан-Хань. Приближенные методы решения задач выпуклого программирования. Ж.вычислит.матем. и матем. физики, 1977, т.17, £ 4, с.905-914.

84. Шор Н.З. О классе почти-дифференцируемых функций и одном методе минимизации функций этого класса. Кибернетика, 1972, № 4, с.65-70.

85. Шор Н.З. Обобщенные градиентные методы минимизации негладких функций и их применение к задачам математического программирования. (Обзор). Экономика и мат.методы, 1976,т.12, вып.2, с. 337-356.

86. Шор Н.З. Методы минимизации недифференцируемых функций и их приложения. Киев: Наукова думка, 1979. - 200 с.

87. Jahn J. A globally convergent method for nonlinear programming.- Math. Operationsforsch. und Statist. Ser. Optimiz.,1981, v.12, N 4, p. 493-5II.

88. Kelley J.E. The cutting-plane method for solving convex programs. SIAM J., I960, v.8, N 4, p.703-712.

89. Lemarechal C. An algorithm for minimizing convex functions,- In: Proc. IFIP Cong. 74.Amsterdam, 1974, p. 552-556.

90. Lemarechal C. Nondifferentiable optimization subgradient and £,-subgradient methods. Lect.Notes Econ. and Mathem. Syst., 1975, N117, p.I9I-I99.

91. Lemarechal C. An extension of Davidon methods to nondifferentiable problems. Math. Program., 1975, Study, 3, p.95-109.

92. Mifflin R. An algorithm for constrained optimization with semismooth functions. RR-77-3, TIASA. - Laxenburg,. Austria, 1977. - 32p.

93. Topkis D.M. Cutting plane methods without nested constraint., sets. Operat. Res., 1970, КЗ.

94. Topkis D.tt. A cutting plane algorithm with linear and geometric rates of convergence. J. Optimiz. Theory and Appl.,1982, v.36, N I.j07. Yeinot A.F. The supporting hyperplane method for unimodal programming. Oper. Res,, 1967, v.15, N I, p.147-152,

95. Wolfe P» On the convergence of gradient methods under constraint. IBM Jr Res. Dev., 1972, v.l6, N4, p.407-411.

96. Wolfe P. A method of conjugate subgradients for minimizing Nondifferentiahle functions. Math, program., 1975, Study, 3, p.145-173.

97. Zontendijk G. Nonlinear programming : a numerical Survey. -SIAM J. Control., 1966, v.4, N I, p.194- 210.