Стохастические алгоритмы внешних аппроксимаций для решения выпуклых задач полубесконечной оптимизации тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Федосова, Алина Валерьевна

• Федосова, Алина Валерьевна
• кандидат физико-математических наук
• 1999

Оглавление диссертации кандидат физико-математических наук Федосова, Алина Валерьевна

Введение.

Глава X. Общий стохастический метод внешних аппроксимаций для решения задач полубесконечной оптимизации

§1Л .Постановка задачи црлубесконечной оптимизации.

§1.2.Математический аппарат и основные обозначения.

§1.3.Схема активизированного поиска критических ограничений.

§1.4.Квазиоптимальные функции и квазиоптимальные множества.

§1.5.0бщий стохастический метод внешних аппроксимаций.

Глава 2. Алгоритмы стохастического метода внешних аппроксимаций для решения выпуклых задач полубесконечной оптимизации

§2.1 .Постановка выпуклых задач полубесконечной оптимизации.

§2.2.Стохастический алгоритм внешних аппроксимаций с учетом ограничений неравенств.

§2.3.Механизм учета ограничений равенств в задачах полубесконечной оптимизации

§2,4.Стохастический алгоритм внешних аппроксимаций с учетом ограничений равенств и неравенств.

Глава 3. Численное исследование задачи упруго-пластического кручения стержня

§3.1 .Физическая интерпретация и постановка задачи

§3.2.Сведение экстремальной постановки к выпуклой задаче полубесконечной оптимизации.

§З.З.Характеристика программного обеспечения.

§3.4.Проблема выбора локального алгоритма для активизированного поиска критических ограничений

§3.5.Численное решение задачи при различных сечениях стержня.

§3.6.Численное решение задачи при различных вариантах учета граничных условий

§3.7.0бсуждение результатов.

Введение диссертации (часть автореферата) на тему «Стохастические алгоритмы внешних аппроксимаций для решения выпуклых задач полубесконечной оптимизации»

Рассмотрим задачу математического программирования Р° : f(x) min g(x,y)< 0 Vy 6 У0, где функции /(ж) и д(х,у) предполагаются непрерывно дифференцируемыми на Х°, Xй X У0 - выпуклых компактах; X0 С Y0 С TZ1. Здесь и далее Ит - m-мерное пространство.

В поставленной задаче множество У0 задает систему ограничений, определяющих допустимое множество задачи Р°. В случае конечного множества У0, задача Р° - это обычная задача математического программирования с конечным числом ограничений. Во многих реальных случаях множество У0 не является конечным, например, если у играет роль времени или пространственных координат. Поэтому если число переменных конечно, а число ограничений бесконечно, то такие задачи называются задачами полубесконечной оптимизации (semi-infinite programming).

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

Задачи полубесконечной оптимизации возникают в различных областях приложений [50, 20, 41]. Например, формулируются как полубесконечные задачи с ограничениями, зависящими от времени или пространственных координат: контроль загрязнения воздуха [45, 50, 75], инженерный дизайн [66, 65], проблема моментов [44, 52] и другие.

Задача Чебышевской аппроксимации также может быть представлена как линейная задача с бесконечным числом ограничений: заданы непрерывные функции /,<?ь <72? на интервале [а, Ь]. Необходимо найти линейную комбинацию функций <?ъ 32? которая наилучшим образом аппроксимирует /, подбирая числа a,xi,x2,. а —» min

Е ЗД'О) - а < f(t), - « < -/№> г € [а, 6].

Существуют причины, по которым задачи полубесконечной оптимизации вызывают особый интерес:

- нередко, на практике оказывается удобным, когда допустимая область в модели с ограничениями, зависищими от некоторого параметра у (времени, пространства, и т. п.), задана значением одного неравенства д(хи х2,.,хк;у) < г (у), а не большим числом несвязных ограничений типа д^х \,х2, < П.

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

- одна из причин изначального интереса к исследованию задач БГР состоит в стремлении исследователей объединить и расширить численные методы для решения задач Чебышевской аппроксимации.

Методам решения таких задач посвящено значительное число работ [41, 76, 50, 37, 42, 77, 78, 34, 65, 66, 45, 44, 52, 47, 46, 75, 67, 63, 49, 69, 70, 72, 55, 61, 56, 59, 60, 48, 33].

Теоретические основы задач полубесконечной оптимизации развиты достаточно глубоко [41, 52, 48, 33]. В вычислительном аспекте, который менее исследован, известны некоторые конкретные задачи аппроксимации и оптимального управления [45, 50, 75, 66, 65, 44, 52] и другие. Из последних работ следует отметить обзоры Полака [65] и Хеттиша с Кортанеком [50] задач полубесконечной оптимизации с точки зрения недифференцируемой и гладкой оптимизации соответственно, обзор Римтсена и Горнера [69] численных методов для общих гладких задач БГР.

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

Р(Уп) : найти х € € лги I № = шI /м>, а; [х j»J

ЛГ[Г„] = 6 Xo I д(х, у) < 0 Vi/ е у„}, некоторой заданной точности на две группы.

Множества Yn, задающие систему ограничений в задачах P(Yn), являются конечными

Г„|<+оо, п = 1,2,.

Методы, в которых такая проверка не требуется относятся к классу прямых стохастических градиентных методов [26, 10, 11, 32, 23]. Задача полубесконечной оптимизации pö в случае несложного отыскания максимума а(х. у) max может быть успешно сведена к негладкой задаче оптимизации min niax '&(z1 у), поэтому к ней применимы и градиентные методы минимизации выпуклых негладких функций, основанные на известной процедуре Эрроу-Гурвица [32] для отыскания minmaxt?^, у). Итерационный процесс в этих методах строится по формулам: n+1 - - а„ * Уп)

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

Исходная задача полубесконечной оптимизации ро заменяется последовательностью обычных задач оптимизации P(Yn), которые решаются с помощью соответствующих алгоритмов линейного или нелинейного программирования. Такие алгоритмы называются методами последовательной аппроксимации. В них на каждой итерации некоторые из исходных ограничений отсутствуют, и элементы последовательности хп, п — 1,2,. будут недопустимыми по отношению к исходному множеству К0. Поэтому такие алгоритмы относятся к методам внешней аппроксимации. Их можно разделить на два класса в зависимости от способа формирования множеств Уп.

К первому классу методов последовательной аппроксимации принадлежат методы, для которых на каждой итерации Уп Уп-\. Таким образом, на каждом шаге находятся новые ограничения и задача решается без учета старых ограничений. К ним можно отнести некоторые методы обмена [41], метод Еауе8-2ап§\¥гП1 [37] и другие методы [26, 10, 11, 23]. Так как на каждой итерации множество Уп не включает критические точки множеств У],., 5^,-1, то обычно множества Уп имеют маленькую размерность. Недостаток этих методов заключается в том, что часто трудно проверить является ли глобальным максимум, полученный при решении внутренних задач.

Данный класс алгоритмов в которых Уп ^ Уп-\ делится на активные и пассивные методы.

В активных методах для поиска критических точек для формирования множества Уп сначала решается внутренняя задача

ХТ{х) : д(х,у) шах. уе¥°

К таким алгоритмам относятся, например, алгоритмы, основанные на методе квазиградиентов [26, 23], которые в то же время являются прямыми градиентными методами. Если задачу Р° переписать в виде м гшп

Р0) = тахд(х,у) < 0, то итерационный процесс в этом случае задается формулами: хп + ап*Сп

Уп € Уор^п), п= ( Г(хп), если фп) = д(хп,уп)< 0 д'х(хп, уп) = (р'(хп), в противном случае

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

Ко второму классу отнесем такие методы, в которых Yn D Yn-j. В этом случае все или некоторые из критических точек множеств Yi.Yn-i войдут в множество Yn. В этой группе находится большинство методов, ориентированных на задачи полубесконечной оптимизации, такие как методы дискретизации [41, 47, 46, 68, 69, 48], полунепрерывные [46, 69], методы, основанные на локальной редукции [41, 69, 46]. Остановимся на их основных чертах.

Первый из вышеуказанных подходов к решению задач SIP заключается в минимизации целевой функции на конечном подмножестве бесконечного множества ограничений, и повторении этой процедуры для расширенного множества ограничений, когда требуется более высокая точность или, в случае, когда необходимо получить оценку точности полученной последовательности решений. Более подробно, идея заключается в последовательном вычислении "приближенного решения" дискретизированной задачи полубесконечной оптимизации P{Yn) для п — 1,2,. по одному из алгоритмов конечномерной оптимизации. Процедуры такого типа относят к методам дискретизации. Используемая в них последовательность узлов {1^} обычно описывается a priori. Иногда бывает, что такая последовательность определяется a posteriori (или "адаптивно"), когда информация, полученная на га-м шаге дискретизации используется для определения Yn+\. Такой вариант метода наиболее эффективен и последовательно уточняет дискретизацию с учетом результатов предыдущей итерации.

Методы дискретизации состоят не просто в замене бесконечного множества ограничений конечным подмножеством несвязных ограничений, но и в "запоминании" результатов в выбранной стратегической сетке. Пусть Y С Y будет конечным подмножеством и p(Y,T) - щах min ||у - у\\2. уег

Тогда на практике для достаточно малого /?, решение на множестве Y вместо Y будет достаточно хорошей аппроксимацией для исходной задачи.

Для доказательства сходимости методов дискретизации, необходимо чтобы каждая предельная точка последовательности "решений" хп* задач P(Yn) была решением задачи SIP Р°, где "решение" P(Yn) - это такая точка, к которой в соответствии с доказательством его сходимости, сходится соответствующий алгоритм P(Yn)~ Что касается решения аппроксимирующей задачи P(Yn), то здесь подходят не все методы математического программирования, так как часто во многих из них требуется решение подзадач, которые имеют такое же число ограничений как и исходная задача.

Для улучшения эффективности метода дискретизации важно, чтобы информация о решении задачи, полученная на одном уровне передавалась на следующий уровень, что означает, что приближенное решение хп* задачи P(Yn) может быть использовано в качестве начальной точки для решения Такая начальная точка может быть недопустимой для P(Yn+1), так как задача F^i^-j-i) включает дополнительные или различные с P{Yn) ограничения. Поэтому многие методы, которые нуждаются в допустимой стартовой точке и, следовательно, в двух-фазовой процедуре решения P(Yn+1), слишком дороги для этих целей.

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

Методы, в которых бесконечное множество ограничений

9(*,у)< 0, y£Y° задачи Р° локально заменено в точке xq конечным множеством ограничений gj(x) :=g(x,yJ(x)) < О, j = 1,п(д70), где у3(х) - локальные максимумы д(х, •) относительно F0, называются методами, основанными на локальной редукции (в [46] их называют непрерывными методами).

Их основная идея заключается в следующем: пусть задана допустимая точка хо € 1Zk для задачи конечной оптимизации, тогда существует окрестность этой точки, где допустимое множество может быть описано активными в точке xQ ограничениями (обычно их > к). Тогда если х§ это (локальное) решение задачи, то оно также является (локальным) решением задачи в которой все ограничения, неактивные в #0? уничтожены и наоборот. На самом деле, в случае задач полубесконечной оптимизации обычно это не выполняется, т. е. допустимое множество задачи SIP не может быть локально представлено только посредством (обычно конечного множества) активных ограничений (см. [69]). Тем не менее, при определенных предположениях, для хо £ Лк (необязательно допустимой) существует конечное число заданных неявных неравенств и область, где допустимое множество, заданное этими ограничениями, совпадает с допустимым множеством исходной задачи SIP. Поэтому при определенных предположениях задача SIP может быть локально сведена к конечной задаче, по крайней мере, концептуально. Впоследствии такая конечная задача может быть решена методом Ньютона [46], методами последовательного квадратичного программирования (Sequential Quadratic Programming methods), например, методом Вилсона [51, 75], методом модифицированных функций Лагранжа и другими. Чтобы найти эти ограничения надо применять методы, которые способны вести глобальный поиск максимумов функции д(хп,у) на F0, не делая много итераций. Подход, основанный на локальной редукции был предложен Хеттишем и Ионгеном [49] и после был развит другими авторами.

К методам, основанным на последовательной аппроксимации относятся и полунепрерывные методы, Они также могут работать и с уже дискретизированными задачами полубесконечной оптимизации, поэтому многие из них дают базис методам дискретизации. Основная идея таких методов выглядит следующим образом: пусть на га-шаге задано конечное подмножество Yn С YQ и пусть хп будет решением задачи P(Yn) на множестве Необходимо определить точки у1,., ут € У0, для которых д(хп, у) достигает своего локального максимума и выбрать

Yn+i CYnU {у1,уг} в соответствие с некоторыми заданными правилами. Следует отметить, что такие методы обычно используются для линейных и выпуклых задач и очень популярны для линейных задач Чебышевской аппроксимации. Подробнее о полунепрерывных методах можно найти в [50, 46].

К классу полунепрерывных методов относятся и неявные методы обмена, в которых Yn-\ С Yni и где обмен точек происходит неявно с помощью симплекс-метода.

К методам, в которых Yn О Ki-i относится общий стохастический метод внешних аппроксимаций, описание которого можно найти ниже.

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

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

Методы дискретизации численно очень дороги, и их стоимость возрастает на каждой итерации в связи с увеличением требуемой точности. Время для проверки допустимости точки по отношению к P(Y„) также сильно увеличивается с ростом мощности множества Yn. Поэтому на практике могут использоваться только сетки с ограниченным числом узлом. Типичными являются сетки с 50.000 - 100.000 точками для задач с 100 переменными.

Таким образом, методы дискретизации сильно проигрывают, когда множество Y0 высокой размерности, т. е. если F0 С V}, I > 2, так как число активных ограничений стремится разрастись. В этом случае эти методы неэффективны. Хотя в общем, методы дискретизации с подходящими стратегиями уточнения сеток превосходят методы обмена вследствие простоты дискретизации и трудности поиска максимума д(х, у) на К0. Они обладают тем преимуществом, что работают исключительно с конечными подмножествами Y°.

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

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

Как и методы дискретизации, полунепрерывные методы могут быть использованы на первой фазе и при некоторых предположениях связываться с методом, основанным на локальной редукции, у которого обычно хорошая сходимость к локальным экстремумам. ([69]). Такие комбинации называют двухфазовыми или гибридными методами. Двухфазовый метод с техникой дискретизации и методом, основанным на локальной редукции, до сих пор остается наиболее реальным и эффективным подходом к решению малых и небольших задач S3P.

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

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

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

Для невыпуклых задач полубесконечной оптимизации, в основном, существуют два вида алгоритмов, которые являются прототипами для конструирования других. Первый - из класса возможных направлений представленный В. Ф. Демьяновым [36]. Второй - это класс внешних аппроксимаций [22, 37, 34, 76] развитый в работах Левитина и Поляка [22], Ивза и Зангвилла [37], Бланкеншипа и Фалька [34]. В обоих направлениях мало практических реализаций предложенных алгоритмов: в [67] авторы использовали идеи Демьянова для случая когда все С Я1, в то время как в [34] был представлен алгоритм для выпуклого случая.

В случае, когда функции /(х) и д(х, у) в задаче предполагаются непрерывно дифференцируемыми и выпуклыми по х на выпуклом компакте Х° для любого у £ У"0, то задача Р° называется выпуклой задачей полубесконечной оптимизации. Отметим, что вогнутости по у не предполагается. Среди методов, предназначенных для решения таких задач следует отметить методы "отсекающих плоскостей", которые изначально были предназначены для решения конечных выпуклых задач. Среди них, метод Келли (Kelley-Cheney-Goldstem) [35,62], который является достаточно надежным методом для решения линейных и выпуклых задач SEP и дает высокую точность решений для задач с числом переменных более тысячи. Метод имеет и ряд недостатков как теоретического, так и практического характера. Генерация алгоритмом последовательности недопустимых точек представляет собой наибольший недостаток. Сходимость к оптимальному решению можно гарантировать, только если допустимая область выпуклая, хотя при помощи метода Келли был решен и ряд невыпуклых задач. Методы "отсекающих плоскостей" чувствительны к ограничениям точности численного решения подзадач, которые возникают из-за того, что последовательно вводимые отсекающие плоскости в окрестности точки оптимума почти параллельны. Метод Келли и другие методы "отсекающих плоскостей", например, метод Veinott-EIzinga [38] и мете« Moore были очень распространены и модифицированы также и для выпуклых задач полубесконечной оптимизации.

В [70, 72] Тихачке и Шварц представили методы для выпуклых задач полубесконечной оптимизации, которые комбинируют адаптивно определенную схему дискретизации с подходом возможных направлений, известным из конечномерной оптимизации.

Каплан и Тихачке в [55, 61, 56, 59, 60] предлагают несколько вариантов численного подхода к выпуклым некорректным полубесконечным задачам. Они объединяют техники метода штрафов с дискретизацией и итеративной ргох-регуляризацией.

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

1,2,., Как было сказано ранее, данный метод относится к группе методов, основанных на последовательной аппроксимации.

Первыми работами, посвященными этим методам, были [35, 62], где методы были представлены в форме методов "отсекающих плоскостей" (cutting plane methods). В 1966 году Левитин и Поляк ([22]) представили методы внешних аппроксимаций в более абстрактной форме.

Основное отличие предложенных ранее методов сведения бесконечного числа ограничений к конечному состояло в выборе метода поиска критических ограничений. В первых работах, посвященных этим методам, авторы столкнулись с проблемой разрастания множества ограничений. С ростом п очень быстро задачи P(Yn), п = 1,2,. становились такими же сложными, как и исходная задача Р°, тем самым обеспечивался монотонный рост мощности множеств Yni п — 1,2,.,

Y, С У2 С .

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

Далее, после некоторого перерыва в связи с возникшей проблемой, развитие данного метода получило в работах [37, 53, 74, 73, 63], в которых для ограничения скорости и прерывания монотонности роста мощности множеств Yni п = 1,2,. были предложены схемы отсеивания некоторых ограничений. Так от методов с монотонным ростом мощности множеств ограничений состоялся переход к методам с адаптивным формированием множеств активных ограничений для аппроксимирующих задач. В [42] авторы обобщили разрозненные алгоритмы и систематизировали их, используя для формирования множеств Yn, п = 1,2,. следующие правила:

Добавление Точек.

При заданной точке хп последовательное получение точек у", € F0 осуществляется до тех пор пока перестанут выполнятся необходимые условия оптимальности в точке хп следующей задачи:

SIP.Pn : f(x) nun д(х,у)< 0 VyeYn U {у?,

Добавление точек у",., к множеству Yn для формирования множества Yn.

Отбрасывание точек.

Отсеиваивание некоторых точек из Yn для получения множества AYn С Y^ такого, что ограничения д(х,у) <0Vy£ AYn не нарушаются в точке хп в задаче SIP.Pn. Затем отбрасывание некоторых множеств из {ДЗ^, г = 1,., п} для получения и AY;-, Jn c{l,.,n}.

В [77, 78] для подбора множеств ограничений использовалась схема пассивного случайного поиска. Основным новшеством предложенной схемы была зависимость между значением квазиоптимальной функцией и числом экспериментов случайного поиска активных ограничений. Такая связь ограничивает число экспериментов рандомизации, выполняемых в каждой точке. Вообще, использование только пассивного случайного поиска не очень эффективно, вследствие того, что точки, "выброшенные" в схеме, не обязательно будут критическими. На основании этого в [76] была предложена модифицированная схема активизированного случайного поиска КЯ.АСТГУ, и сформулированы Предположения А1 и А2 о существовании решения аппроксимирующих задач и о свойствах непрерывности квазиоптимальной функции. Была доказана теорема о том, что для любой задачи оптимизации с бесконечным числом ограничений и любой квазиоптимальной функции, удовлетворяющей Предположениям А1 и А2, траектория общего стохастического метода внешних аппроксимаций 8МЕТН.АСТ1У с вероятностью единица сходится к квазиоптимальному множеству исходной задачи.

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

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

К задачам полубесконечной оптимизации сводятся многие стационарные краевые задачи механики с ограничениями, среди них задача упруго-пластического кручения стержня [7, 31, 9], которая может быть представлена как задача выпуклой условной минимизации в функциональных пространствах, в которых целевой функционал / задается в виде многомерного интеграла, а выпуклое замкнутое множество ограничений К - с помощью операторных неравенств: ппп/М (1) / Ф(аг, у)йу, и с Пп п

К = {х £ Н | д(х, у) < 0 п.в. в О, Н(х, у) < 0 п.в. на Г = 00}, пространство Н - Гильбертово.

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

Основной подход к решению задач минимизации функционалов в бесконечномерных пространствах с ограничениями заключается в их проектировании в конечномерные пространства с последующим переходом к пределу конечномерных решений [7, б, 8, 18]. Целевой функционал J (или форма («/'(-г), х) в случае дифференцируемости) аппроксимируется функцией конечного числа переменных с использованием численных методов, таких как метод конечных разностей, метод Ритца, метод конечных элементов или других классических методов численного анализа.

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

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

В оптимизации к методам, использующим конечно-разностный подход, можно отнести метод локальных вариаций, впервые предложенный в [30]. В [1, 3, 2, 21, 31] метод применялся для решения задач механики сплошной среды и задач оптимизации движения управляемых объектов. Допустимая область заменяется сеткой и вместо решения непрерывной вариационной задачи решается дискретная (конечномерная) задача, в которой искомая функция заменяется ломаной с вершинами в узлах разбиения. Решение задачи строится как предел последовательных приближений. Численное исследование задачи упруго-пластического кручения стержня (1) данным методом можно найти в [31].

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

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

Метод конечных элементов (МКЭ) остается одним из наиболее популярных и продвинутых в теории и практике. В механике деформируемого твердого тела МКЭ, основанный на принципе виртуальной работы, можно рассматривать как вариант метода Галеркина и также условно отнести к методу взвешенных невязок. Область Л условно разбивается на конечные элементы и при построении метода конечных элементов рассматривается как совокупность этих элементов. Непрерывные функции представляющие физические величины, такие как температура, давление или перемещение, заменяются аппроксимирующими функциями, которые выбираются гладкими в каждом элементе, но во всей области являются кусочно-гладкими. Приближенное решение представляется в каждом элементе с помощью интерполяционных функций с неизвестными параметрами аппроксимаций, которыми могут быть, например, значения величин в узловых точках. Интерполяционные функции, называемые также базисными функциями, выбираются так, чтобы как только определены неизвестные параметры, распределения физических величин во всем теле определялись однозначно. При негладких входных данных задачи, а также в случае областей сложной формы, МКЭ часто сходится быстрее, чем метод конечных разностей. Метод конечных элементов используют для сведения бесконечномерной задачи к конечномерной благодаря возможности замены интегральных функционалов суммой интегралов по подобластям. Последние интегралы легко могут быть вычислены приближенно за счет удачного выбора базисных функций и хорошей триангуляции. Для численного решения сложных как по характеру ограничений, так и по виду функционала J задач типа (1), возможно комбинирование МКЭ с методом штрафов, где штрафование используется для сведения задач условной оптимизации к безусловной [7, 28].

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

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

Что касается практического построения аппроксимаций множества К, то это одна из основных трудностей решения задач условной оптимизации в функциональных пространствах. Нелинейность ограничений в задаче (1) затрудняет их учет в общем виде с помощью проектирования или выбора соответствующего базиса, а построение базиса под конкретную задачу довольно сложно. Учитывать аппроксимированные ограничения также непросто. Поэтому для сведения подобных задач условной оптимизации к безусловной иногда применяют метод штрафов [64, 7, 8, 43, 28]. Например, аппроксимируется оштрафованный функционал «7С, т. е. неквадратичная (из-за наличия штрафа) задача безусловной минимизации.

Необходимость практической реализации описанных численных методов привела к идее итеративной аппроксимации в схемах условной и безусловной минимизации, которой посвящены работы [64, 7, 8, 43, 28, 58, 57, 54, 18]. В [7] для сведения бесконечномерных задач к конечномерным применяют внутренние и внешние аппроксимации. Здесь также используется метод штрафов для решения аппроксимированных задач с ограничениями. Декомпозицию исходной задачи предлагается производить путем прибавления дополнительных функций и "искусственных ограничений", которые потом снимаются с помощью штрафа. Другая интересная идея заключается в замене ограничения более простым с точки зрения численной реализации. В [7] приближенную конечномерную задачу упруго-пластического кручения стержня предлагается решать методами релаксации, штрафа и двойст венност и.

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

В [28] для решения вариационных задач с операторными ограничениями была предложена схема итеративного комбинирования метода интегрального штрафа типа сглаженной "срезки", аппроксимации задачи по методу конечных элементов 1-го порядка (кусочно-линейный базис) и метода скорейшего градиентного спуска (МИКЭПГГ). Главным отличеим от техники предложенной в [64] является использование неортогонального базиса. Полученное с помощью МИКЭ1ПГ приближение полезно использовать в качестве начального приближения для более совершенных алгоритмов.

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

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

Для сведения экстремальной постановки (1) к выпуклой задаче SIP предлагается исходное бесконечномерное пространство аппроксимировать по схеме Ритца на базе ортогональных рядов Фурье. Далее полученную выпуклую задачу полубесконечной оптимизации численно решать предлагаемыми алгоритмами.

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

В соответствии с изложенным формулируется цель настоящей работы:

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

Для достижения указанной цели были поставлены следующие задачи:

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

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

Исследовать теоретическую и практическую сходимость построенных алгоритмов.

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

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

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

Заключение диссертации по теме «Дискретная математика и математическая кибернетика», Федосова, Алина Валерьевна

Заключение.

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

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

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Федосова, Алина Валерьевна, 1999 год

1. Баничук Н.В., Крылов И. А., Петров В. М., Черноусько Ф. Л. Алгоритм метода локальных вариаций для решения вариационных задач с одной независимой переменной. Алгоритмы и алгоритмические языки. М.: ВЦ АН СССР, 1969. Вып. 4.

2. Баничук Н.В., Петров В. М., Черноусько Ф. Л. Метод локальных вариаций для вариационных задач с неаддитивными функционалами // Ж. вычисл. матем. и матем. физ., 1969. Т. 9. N 3.

3. Баничук Н.В., Петров В. М., Черноусько Ф. Л. Численное решение вариационных и краевых задач методом локальных вариаций // Ж. вычисл. матем. и матем. физ., 1966. Т. 6. N 6.

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

5. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. М.: Мир, 1985.

6. Главачек Й., Гаслингер Я., Нечас И., Ловишек Я. Решение вариационных неравенств. М.: Мир, 1986.

7. Гловински Р., Лионе Ж. Л., Тремольер Р. Численное исследование вариационных неравенств. М.: Мир, 1979.

8. Гроссман К., Каплан А.А. О решении конечномерных задач, возникающих при аппроксимации вариационных неравенств. // Оптимизация. Новосибирск, 1983. В. 32. С. 5-20.

9. Дюво Г., Лионе Ж. Л. Неравенства в механике и физике. М.: Наука, 1980.

10. Завриев С. К. Комбинированный метод штрафов и стохастического градиента для поиска максимина // Ж. вычисл. матем. и матем. физ., 1979, Т. 19. N 2. С. 329-342.

11. Завриев С. К. Стохастические градиентные методы решения минимаксных задач. М.: МГУ, 1984.

12. Завриев С. К., Новикова Н. М., Федосова А. В. Об учете ограничений равенств в алгоритме внешних аппроксимаций решения задач полубесконечной оптимизации. Деп. в ВИНИТИ РАН, 1999. N 3282-B99.

13. Завриев С. К., Новикова Н. М., Федосова А. В. Стохастический алгоритм решения выпуклых задач полубесконечной оптимизации с ограничениями равенствами и неравенствами // Вестник Моск. ун-та. Сер. 15. Вычисл. матем. и киберн» (в печати).

14. Завриев С. К., ПеруноваЮ. Н. Об использовании конечных разностей в методе мультистарТа для решения некоторого класса задач глобальной оптимизации // Вестник Моск. ун-та. Сер, 15. Вычисл. матем. и киберн, 1997. N. 3.

15. Завриев С. К., Федосова А. В. Алгоритм метода внешних аппроксимаций для решения выпуклых задач полубесконечной оптимизации. Деп. в ВИНИТИ РАН, 1999. N 3281-В99.

16. Каплан А. Об устойчивости методов решения задач выпуклого программирования и вариационных неравенств // Модели и методы оптимизации. Новосибирск: Наука, 1988. С. 132-159.

17. Каплан А., Тихачке Р. Исследование итерационных процессов решения некорректных выпуклых вариационных задач. Доклады АН СССР, 1990. Т. 315. С. 275-278.

18. Крабе В. Теория приближений и их приложений. М., 1978.

19. Крылов й. А., Черноусысо Ф.Л. Решение задач оптимального управления методом локальных вариаций //Ж. вычисл. матем. и матем. физ., 1966. Т. 6. N 2.

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

21. Михалевич В. С., Гупал А. М., Норкин В. И. Методы невыцуклой оптимизации. М.: Наука, 1987.

22. Морозов В. В., Сухарев А. Г., Федоров В. В. Исследование операций в задачах и упражнениях. М.: Высшая школа, 1986.

23. Неве Ж. Математические основы теории вероятностей. М.: Мир, 1969.

24. Новикова Н. М. Стохастический квазиградиентный метод поиска минимакса ff Ж. вычисл. матем. и матем. физ., 1977, Т. 17. N 1. С. 91-99.

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

26. Станюкова И. В. Исследование итеративной схемы метода конечных элементов, штрафов и градиентного спуска для решения одного класса вариационных задач, Автореф. дис. . канд. физ.-матем. наук. М.: МГУ, 1998.

27. Федоров В. В. Методы поиска максимина. М.: Наука, 1977.

28. Черноусько Ф. Л. Метод локальных вариаций для численного решения вариационных задач.// Ж. вычисл. матем. и матем. физ., 1965. Т. 5. N 4.

29. Черноусько Ф. Л., Баничук Н. В. Вариационные задачи механики и управления. М.: Наука, 1973.

30. Эрроу К. Дж., Гурвиц Л., Удзава X. Исследования по линейному и нелинейному программированию. М.: ЙЛ, 1962.

31. Anderson Е. Л., Philpott А. В., editors. Infinite Programming ff Lecture Notes In Econom. and Math. Systems. Springer. BerlinHeidelberg -New York-Tokyo, 1985. V. 259.

32. Blankenship J. W., Falk J. E. Infinitely Constrained Optimization Problems // The George Washington University. Institute for Management Science and Engineering, 1974. Serial No T-301.

33. Cheney E. W., Goldstein A. A. Newton's method for convex programming and tchebycheff approximation // Numer. Mathematics, 1959. N. 1. P. 253-268.

34. Demianov V. F. On the solution of Certain Min-Max Problems // Kibernetica, 1966. N. 2. C. 47-53.

35. Eaves B. C., Zangwill W. I. Generalized Cutting Plane Algorithms // SIAM Journal on Control and Optimization, 1971. V. 9. P. 529-542.

36. Elzinga X, Moore T. G. A central cutting plane algorithm for the convex programming problem // Math. Programming, 1975. N 8, P. 134-145.

37. Fedosova A. V. Acerca de la inmunidad a las perturbaciones en el método de descenso por el gradiente // Revista Integración. Temas de Matematicas, Universidad Industrial de Santander, Colombia, 1996. V.14, N. 1, P. 19-30.

38. Fedosova A. V., Zavriev S. K. A Stochastic Algorithm for Solving Convex Semi-Infinite Programming Problems. Abstracts The 2nd Moscow International Conference On Operations Research (Moscow, November 17-20, 1998), 14.

39. Fiacco A. V,, Kortanek K. O. Semi-infinite Programming and Applications // Lecture Notes in Economics and Mathematical Systems. Springer-Verlag, New York, 1983. V. 215.

40. Gonzaga G., Polak E. On Constraint Dropping Schemes and Optimality Functions for a Class of Outer Approximations Algorithms // SIAM Journal on Control and Optimization, 1979. V. 17. P. 477-493.

41. Grossmann C., Kaplan A. On the solution of discretized obstacle problems by an Adapted Penalty Method // Computing., 1985. V. 35. N 3-4. P. 295-306.

42. Gustafson S. A. On semi-infinite programming in numerical analysis // Semi-infinite programming (Springer-Verlag, Berlin, Heidelberg, New York), 1979. P. 137-153.

43. Gustafson S. A., Kortanek K. 0. A comprehensive approach to air quality planning: Abatemen. monitoring networks and time interpolation // Mathematical models for planning and controlling air quality, 1982. P.75-91.

44. Hettich R. A comparison of some numerical methods for semi-infinite programming // Lecture Notes in Contr. and Inform. Sei., 1979. V. 15. P. 112-125.

45. Hettich R. An implementation of a discretization method for semiinfinite programming // Math. Progr., 1986. N. 34. P.354-361.

46. Hettich R. Semi-Infinite Programming // Lecture Notes in Contr. and Inform. Sei. Springer. Berlin-Heidelb erg-New York, 1979. V. 15.

47. Hettich R., Jongen H. Semi-infinite programming: conditions of optimality and applications // Springer Lecture Notes in Contr. and Inform. Sei., 1978. V. 7. P. 1-11.

48. Hettich R., Kortanek K. O. Semi-infinite Programming: Theory, Methods, and Applications // SIAM Review, 1993. V. 35. N. 3. P. 380-429.

49. Hettich R., Van Honstede W. On quadratically convergent methods for semi-infinite programming // Lecture Notes in Contr. and Inform. Sei., 1979. V. 15. P. 97-111.

50. Hettich R., Zencke P. Numerische Methoden der Approximation und semi-infiniten Optimierung. Teubner, Stuttgart. 1982.

51. Hogan W. W. Application of a general convergence theory for outer approximations algorithms // Math. Progr., 1973. N. 5, P. 151-168.

52. Kaplan A., Tichatschke R. A note on the paper Multi-Step- -Prox-Regularization Methods for Solving Convex Variational Problems // Optimization, 1996. V. 37. N 4. P. 149-152.

53. Kaplan A., Tichatschke R. A regularized penalty method for solving convex semi-infinite programs // Optimization, 1992. N. 26. P. 215228.

54. Kaplan A., Tichatschke R. Iterative processes for solving incorrect convex variational problems // J. Global Optim., 1993. N. 3. P. 243255.

55. Kaplan A., Tichatschke R. Multi-Step-Prox-Regularization Methods for Solving Convex Variational Problems // Optimization, 1995. V. 33. N 4. P. 287-319.

56. Kaplan A., Tichatschke R. Prox-regularization and Solution of III-Pozed Elliptic Variational Inequalities. // Applications of Mathematics, 1997. V. 42. N 1,2.

57. Kaplan A., Tichatschke R. Regularized penalty methods for semiinfinite programming problems. In B. Brosowski, F. Deutsch, and J. Guddat, editors, Approximation & Optimization. Peter Lang. Frankfurt, 1993. P. 341-356.

58. Kaplan A., Tichatschke R. Stable Methods for Ill-Posed Variational Problems. Akademie Verlag. Berlin, 1994.

59. Kaplan A., Tichatschke R. Variational inequalities and convex semiinfinite programming problems // Optimization, 1992. N. 26. P. 187214.

60. Kelley J. E. The cutting-plane method for solving convex programs // J. Soc. Indust. Appl. Math., 1960. V.8. P. 703-712.

61. Mayne D. Q., Polak E., Trahan R. An Outer Approximations algorithm for Computer-Aided Design Problems // Jour, of Optim. Theory and Appl., 1979. V. 28. N. 3. P. 331-352.

62. Polak E. On the mathematical foundations of nondifferent!able optimization in engineering design // SIAM Rev., 1987. V. 29. P. 21-89.

63. Polak E. Semi-infinite optimization in engineering design // Semiinfinite programming and applications. (Springer-Verlag, Berlin, Heidelberg, New York, Tokyo), 1983. P. 236-248.

64. Polak E., Mayne D. Q. An Algorithm for Optimization Problems with Functional Inequality Constraints // IEEE Transactions on Automatic Control., 1976. V. AC-21. P. 184-193.

65. Reemtsen R. Discretization methods for the solution of semi-infinite programming problems // Jour, of Optim. Theory and AppL, 1991. V. 71. N. 1. P. 85-103.

66. Reemtsen R., Gorner S. Numerical Methods for Semi-infinite Programming: A Survey. "Semi-infinite Programming" R. Reemtsen and J.-J. Ruckmann Eds., 1998. P. 195-275.

67. Tichatschke R. Semi-infinite programming problems // Banach Center Publ., 1985. N. 14. P. 543-554.

68. Tichatschke R., Kirsten H. About the efficiency of a method of feasible directions for solving variational inequalities // Lecture Notes in Economics and Mathematical Systems. Springer-Verlag, New York, 1986. V. 294.

69. Tichatschke R., Schwartz B. Methods of feasible directions for semiinfinite programming problems. Wiss. Inform. TH Karl-Marx-Stadt. 1982. N. 33. Part I. P. 1-15. Part II. P. 16-23.

70. Topkis D. M. A note on cutting plane methods without nested constraints // Operations Res. Center. Univ. of Calif., 1969. Report No 69-36.

71. Topkis D. M. Cutting plane methods without nested constraints // Oper. Res., 1970. P. 404-413.

72. Van Honstede W. An approximation method for semi-infinite programs // Lecture Notes in Contr. and Inform. Sei., 1979. V. 15. P. 126-136.

73. Volkov Y. VM Zavriev S. K. A General Stochastic Outer Approximations Methods // SIAM Journal on Control and Optimization, 1997. V. 35. P. 1387-1421.

74. Wardi Y, A Stochastic Algorithm for Optimization Problems with Continua of Inequalities // Journal of Optimization Theory and Applications, 1988. V, 56. P. 285-311.

75. Wardi Y. Stochastic Approximation Algorithm for Minimax Problems // Journal of Optimization Theory and Applications, 1990. V. 64. P. 615-640.