Методы погружения в нелинейном программировании

Построение методов решения задач нелинейного программирования и их численная реализация постоянно пользуются вниманием математиков-вычислителей. В тесной связи с разработкой методов находятся и вопросы оценки их эффективности (см., напр., [ 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. Решена прикладная задача синтеза информационно-управляющей системы (ИУС). При решении использован метод с частичным погружением допустимого множества. Выбор метода был обусловлен спецификой задачи. Методом условного? — субградиента решена также задача выбора оптимальных времен функционирования подсистем ИУС. Алгоритм этого метода включен в математическое обеспечение проектирования ИУС кафедрой радиофизики КГУ.