Ви є тут

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

Автор: 
Заботин Игорь Ярославич
Тип роботи: 
Докторская
Рік: 
2009
Артикул:
322331
179 грн
Додати в кошик

Вміст

2
Содержание
Введение 4
1 Общие процедуры решения задачи математического программирования и отыскания точки выпуклого множества. Их реализации 22
1.1 Общие процедуры аппроксимации с частичным погружением допустимого множества для задачи математического программирования ........... 22
1.2 Общая процедура аппроксимации с полным погружением допустимого множества для задачи математического программирования............... 31
1.3 Две общие схемы отыскания точки выпуклого множества и их реализации 36
2 Методы условной минимизации гладких псевдовыпуклых функций с
реализациями на основе процедур аппроксимации 47
2.1 Метод условной минимизациии гладких псевдовыпуклых функций .... 47
2.2 Некоторые реализации метода из § 2.1 ........................... 58
2.3 Метод типа условного градиента для задачи псевдовы пук лого программирования .......................................................... 63
2.4 Реализации метода из § 2.3 на основе частичного погружения допустимого множества .......................................................... 70
2.5 Метод проекционного типа в псевдовыпуклом программировании и его реализации на основе процедур аппроксимации множеств................ 77
2.6 Метод второго порядка........................................... 88
3 Алгоритмы с параметризованными направлениями для условной минимизации гладких псевдовыпуклых функций 96
3.1 Вспомогательные результаты...................................... 97
3.2 Метод типа условного градиента с параметрическим заданием подходящих направлений ....................................................101
3.3 Реализация метода типа условного градиента с параметрическим заданием подходящих направлений на основе процедур аппроксимации .... 114
3.4 Проекционные алгоритмы с параметризованными направлениями спуска 120
3.5 Проекционные алгоритмы с параметризованными направлениями, использующие аппроксимацию допустимого множества......................132
з
3.6 Алгоритм второго порядка с параметризованными направлениями .... 138
3.7 Алгоритм второго порядка с параметризованными направлениями, использующий частичное погружение допустимого множества.................. 148
3.8 Вариант метода возможных направлений Зойтендейка с параметризованными направлениями для задачи псевдовыпуклого программирования . . 152
3.9 Вариант метода линеаризации с параметризованными направлениями итерационного перехода.....................................................164
4 Методы условной минимизации негладких псевдовыпуклых функций 174
4.1 Релаксационные алгоритмы условной минимизации негладких строго псевдовыпуклых функций......................................................174
4.2 Алгоритмы отыскания условного дискретного минимакса.................181
4.3 Вариант параметризованного метода центров...........................189
5 Алгоритмы безусловной минимизации псевдовыпуклых функций и исследование их устойчивости 197
5.1 Обший метод безусловной минимизации гладких псевдовыпуклых функций 197
5.2 Одношаговыс и многошаговые алгоритмы, как реализации общего метода безусловной минимизации.................................................206
5.3 Методы спуска по группам переменных ................................213
5.4 Общая схема исследования устойчивости алгоритмов безусловной минимизации гладких псевдовыпуклых функций..................................220
5.5 Исследование устойчивости некоторых одношаговых алгоритмов..........226
5.6 Исследование устойчивости некоторых многошаговых алгоритмов .... 235
6 Методы решения специальных и прикладных задач псевдовыпуклого
программирования 241
6.1 Методы спуска по группам переменных для одного класса задач условной минимизации.............................................................241
6.2 Метод условной минимизации функции максимума специального вида . . 251
6.3 Субградиентиый метод отыскания седловых точек.......................256
6.4 Использование предложенных методов при решении некоторых прикладных задач...............................................................260
Заключение 268
Список литературы
274
4
Введение
В связи с постоянно возникающими на практике оптимизационными задачами нелинейное программирование остается актуальным направлением исследований специалистов, работающих в области математической кибернетики и вычислительной математики. Большинство работ по нелинейному программированию относится к наиболее изученному его разделу выпуклого программирования. Различные подходы к построению методов выпуклого программирования и исследованию их сходимости предложены в [2, 8, 11, 16, 17, 21, 22, 23, 24, 26, 28, 34, 36, 38, 42, 45, 47, 48, 53, 54, 55, 58, 124, 133, 134, 140, 141, 143, 161, 167, 168, 173, 176, 178, 179, 185, 194, 200, 201, 205, 207], и этот перечень работ далеко не полон. К настоящему времени разработано значительное число методов минимизации как гладких, так и негладких выпуклых функций,,}! сложилась определенная их классификация. Можно привести примеры довольно больших классов методов выпуклого программирования, исследованных, в частности, в указанных выше работах. Это методы возможных направлений, методы типа линеаризации, штрафных и барьерных функций, методы центров, модифицированных функций Лагранжа и др. Большую группу методов минимизации неднфференцнруемых выпуклых функций образуют основанные на идеях метода обобщенного градиентного спуска [207] так называемые субгра-диентньте методы (напр., [42, 57. 73, 151, 169, 174, 181, 202, 207]), связанные с методами фейеровских приближений (напр., [26, 54]), методами отсечений (напр., [6, 169]). Близкими к этой группе являются £ - субградиентные методы, предложенные сначала в виде алгоритмов типа наискорейшего спуска для минимаксных задач (см., напр., [43]) и разработанные затем для минимизации как функций максимума, так и произвольных выпуклых функций (напр., [31, 42, 43, 68,131, 159, 173, 186, 200. 201, 207, 223, 224, 230. 231]). В отдельные группы методов выпуклого программирования можно выделить алгоритмы погружений - отсечений (напр., [6, 7, 9, 21, 62, 69, 133, 161, 207, 210, 220, 229]), а также основанные на идеях, подробно описанных в [23, 24, 195] , методы регуляризации и итеративной рстуляризации (напр., [25, 4G, 189, 19G]). Отметим, что в тесной связи с разработкой методов выпуклого программирования находились и находятся вопросы оценки их эффективности (напр., (7, 1G9, 170, 171, 193, 210]).
Однако, практикой востребованы и методы минимизации функций более общих, чем выпуклые. Исследованиям задач нелинейного программирования, не входящих в раздел выпуклого программирования, и построению методов их решения также посвящено не-
5
мало публикаций (напр., [18, 30, 49, 128, 129, 130, 152, 164, 171, 172, 177, 179, 183, 190, 191, 192, 195, 203, 204, 212, 213, 215, 216, 218, 225, 228]). Среди них есть работы по методам решения многоэкстремальных задач, методам регуляризации, квазшзынуклому программированию и др. В последнее время интенсивно исследуются задачи равновесного программирования (напр., [4, 5, 15, 35, 153, 154, 155)), продолжают строиться методы решения вариационных неравенств (напр., [12, 13, 142, 148, 156, 182, 221. 222]).
Из задач математического программирования более общих, чем задача выпуклого программирования, ближе других к последней стоит задача исевдовыпуклого программирования. Понятие псевдовыпуклости для дифференцируемых функций было предложено еще в 1965 году О. Мангасарианом ([2261). В 1974 году в работе Заботина Я. И. и Кораблева Л. И. ([127]) введено определение недифференцируемых псевдовыпуклых функций и изучены некоторые их свойства. Хотя задача исевдовыпуклого программирования сформулирована уже давно и методам ее решения также уделено определенное внимание (см., напр., [11, 29, 98, 105. 126, 127, 135, 157, 158, 214, 217, 226, 227, 232]), раздел псевдовыпуклого программирования изучен еще далеко не полно. При разработке и исследовании методов минимизации псевдовыпуклых функций возникают определенные трудности, связанные со спецификой задачи. Заметим, что нсевдовыпуклые функции, действительно, близки к выпуклым по многим важным свойствам. Например, их лебеговы множества также являются выпуклыми, всякий локальный минимум совпадает с глобальным, множество точек минимума выпукло. Однако, хорошо изученный и развитый аппарат выпуклого анализа, на котором основаны построение методов выпуклого программирования и методика обоснования их сходимости, обычно не удается непосредственно использовать для разработки и обоснования методов исевдовыпуклого программирования.
Поскольку класс псевдовыпуклых функций (их примеры можно найти, в частности, в [11, 158]) существенно шире класса выпуклых функций, и псевдовыпуклые экстремальные задачи возникают на практике (иапр., [158]), то дальнейшие исследования по численным методам псевдовыпуклого программирования полезны как с тео[>етической, так и с практической точки зрения. Данная диссертационная работа относится к исследованиям в области псевдовыпуклого программирования. Она посвящена построению методов условной и безусловной минимизации гладких и негладких псевдовыпуклых функций на основе параметризации направлений итерационного перехода и аппроксимации множеств. При этом разрабатываемые методы учитывают специфику как дифференцируемых, так и недифференинруемых псевдовыпуклых функций. Заметим, что за счет схожести обсуждаемых разделов математического программирования многие идеи могут быть естественным образом перенесены из выпуклого в псевдовыпуклое программирование. Однако, целью работы является не формальное обобщение и распространение известных алгоритмов выпуклого программирования на псевдовыпуклый случай, а разработка новых подходов к построению конструктивных методов псевдовыпуклого программирования с легко реализуемыми алгоритмами, а также новых методик
б
исследования сходимости этих методов.
Несмотря на большое число работ по методам нелинейного программирования, и сейчас еще численная реализация многих из них вызывает значительные сложности. Одной из причин трудной реализуемости методов является то, что в них при построении итерационных точек приходится решать вспомогательные задачи, которые сами по себе немногим легче исходной задачи минимизации. В качестве примеров могут служить различные варианты метода условного градиента, проекционные алгоритмы, варианты метода Ньютона и ряд других алгоритмов выпуклого программирования, где для нахождения направлений итерационного перехода необходимо решать задачи условной минимизации вспомогательных функций с использованием всех или части ограничений исходной задачи. При задании допустимых множеств нелинейными неравенствами это требует больших вычислительных затрат. Кроме того, во многих методах (в том числе и только что упомянутых) размерности этих вспомогательных задач, т. е. число переменных и ограничений в них, совпадают с размерностями исходной задачи, а иногда и превышают их, что сказывается при решении такими методами задач большой размерности. Даже в тех методах, где, несмотря на общий вид ограничений, вспомогательные задачи построения итерационных точек явно упрощаются по сравнению с исходной задачей (метод возможных направлений Зойтендейка [22, 134, 143] , метод линеаризации [184, 185] , методы отсечений [21] и т. д.), число переменных (а часто и ограничений) и этих подзадачах не уменьшается по отношению к исходной задаче.
Уже эти замечания доказывают актуальность исследований в области псевдовыпук-лого, а значит, и выпуклого программирования, направленных на разработку методов с реализуемыми алгоритмами, в которых вспомогательные задачи, несмотря на размерности исходной задачи и общий вид ограничений, остаются относительно простыми (во всяком случае решаются за конечное число шагов и могут при желании иметь меньшее, чем основная задача, количество переменных и ограничений). Построению именно таких методов псевдовынуклого программирования посвящены проведенные ниже исследования.
Основные подходы, реализованные в предлагаемых здесь методах, заключаются в следующем. Во-первых, за счет разработанных автором принципов и процедур аппроксимации допустимого множества или его части многогранным множеством вспомогательные задачи построения направлений итерационного перехода в реализациях этих методов решаются за конечное число шагов, несмотря на общий вид ограничений. Во-вторых, параметрическое представление направлений перехода в строящихся методах позволяет вспомогательным задачам поиска этих направлений иметь меньшее число переменных, чем исходная задача математического программирования. Среди предлагаемых ниже методов и их реализаций есть те, в которых используется только один из названных подходов - аппроксимация или параметризация, а есть такие, где оба подхода применяются одновременно.
Коротко обсудим эти подходы. Сразу отмстим, что в настоящей работе процедуры
7
аппроксимации множеств применяются с иными, чем в известных методах погружений - отсечений, целями. Р1дея аппроксимации множеств, в частности на основе операций погружений и отсечений, используется в математическом программировании довольно давно. В том или ином виде она применяется для решения задач выпуклого программирования, многоэкстремальных задач, задач целочисленного программирования и лр. (кроме названных выше работ, см. также [3, 24, 34, 61, 63, 64, 66, 66, 69, 70, 149, 150, 169, 175, 184, 185]). Так в методе опорных множеств [21] для задачи выпуклого программирования и в некоторых других методах погружений (напр., [9, 21, 66, 133, 220]) аппроксимация допустимого множества исходной задачи использована с целью упрощения подзадач отыскания итерационных точек следующим образом. Строится последовательность вложенных друг в друга множеств, как правило многогранников, содержащих допустимую область, и точки хк минимума на них целевой функции принимаются за приближенные решения задачи выпуклого программирования. Каждое из аппроксимирующих множеств получается из предыдущего путем отсечения найденной точки хк.
В данной работе при построении методов условной минимизации гладких и негладких нсевдовыпуклых функций также используются погружающие множества. Однако, разработанные здесь процедуры аппроксимации допустимого множества D или его подмножеств Dk применяются в предложенных методах только для нахождения некоторых вспомогательных направлений $*, а не самих приближений хк. В отличие от упомянутых известных методов погружений - отсечений последовательности {.г>} строятся здесь принадлежащими D. Переход к очередной точке хк+\ для каждого к = 0,1,... осуществляется так, что значение /о(ж*м) целевой функции в ней не превосходит значения /о(т) во вспомогательной точке vk — хк + ßksk> что позволяет еще распоряжаться выбором шагов ßk и способами построения самой итерационной точки хк+\- При этом размерности аппроксимирующих множеств Мк, использующихся для отыскания направлений s*, могут отличаться от размерности dim D множества D, если Мк строятся для подмножеств Пк С Z), имеющих меньшую, чем D, размерность. Заметим, что разработанные принципы аппроксимации позволили также сделать реализуемыми некоторые известные методы выпуклого программирования, которые трудноприменимы для задач с ограничениями общего вида.
Используемый в диссертации для предлагаемых методов псевдовыпуклого программирования подход параметризации направлений sk заключается в следующем. Векторы sk строятся в виде линейных комбинаций градиентов целевой функции и активных в точках хк ограничений. Коэффициенты комбинаций отыскиваются, как правило, с помощью решения вспомогательных задач линейного или квадратичного программирования. В случае, когда количество активных ограничений невелико по сравнению с числом п переменных исходной задачи, размерность вспомогательных задач ниже, чем 71, и меньше размерностей традиционных задач выбора направлений в методах выпуклого программирования. Отметим, что задачи поиска коэффициентов могут решаться
8
с привлечением разработанных процедур аппроксимации допустимых множеств этих вспомогательных задач, что делает предлагаемые способы построения параметризованных направлений реализуемыми.
Диссертация состоит из шести глав. Опишем последовательно содержание каждой из них.
Первая глава посвящена разработке и обоснованию тех процедур аппроксимации, которые будут применяться далее при построении направлений итерационнного перехода в предлагаемых методах условной минимизации гладких и негладких псевдовынуклых функций. Эти процедуры строятся в виде общих схем решения задачи математического программирования с использованием операций погружения и отсечения множеств на основе идей уже упомянутых методов погружения. Поскольку предлагаемые схемы могут использоваться как для указанных задач выбора направлений, так и для общих задач математического программирования, то результаты первой главы имеют не только вспомогательный характер, но и определенное самостоятельное значение.
В § 1.1 разработаны общие методы решения задачи
(0-1)
где функция д(х) непрерывна в п - мерном евклидовом пространстве /?^, а множество (7 задано пересечением конечного числа выпуклых замкнутых множеств С /?„,
о о
7 6 с непустой внутренностью в3-, причем, возможен, в частности, случай С= 0- Пер-
вый метод (процедура тг1) вырабатывает последовательность приближенных решений е А/Д (7. г = 0,1,где АА - вложенные друг в друга вообще говоря неограниченные множества, содержащие хотя бы одно решение задачи (0.1). Аппроксимирующее множество М,+1 строится на основе предыдущего Л/, с использованием вспомогательных
о _
точек уу путем отсечения от М, точки у* конечным числом обобщенно - опор-
ных гиперплоскостей. Обсуждаются реализации этой схемы, проводится сравнение ее с известными методами погружения, обосновывается сходимость. Приводится итерационный процесс решения задачи (0.1), обобщающий первую процедуру на случай, когда множества Gj принадлежат некоторому линейному многообразию меньшей, чем гг, размерности.
В п.4 § 1.1 приводятся две постановки задачи минимизации д(х) на множестве (7 с заранее заданной точностью. Доказывается, что предложенными процедурами отсечений в обоих случаях такая задача решается за конечное число шагов. При этом предлагаются простые практические критерии остановки работы процедур. Один из таких способов приближенного решения задачи (0.1) с наперед заданной точностью будет применяться далее для различных вспомогательных функций д(х) и множеств (7 в реализациях предлагаемых методов нсевдовыпуклого программирования при построении направлений итерационного перехода.
В п.5 ^ 1.1 для приближенного решения задачи (0.1) строится еще одна аналогичная тг 1 процедура отсечений 7гь в которой точки уг выбираются принадлежащими допус-
9
тимой области G. Показывается, что процедурой 77[ можно строить за конечное число шагов подходящие для функции д(х) относительно G направления в стационарных неэкстремальных точках. Эта процедура может быть полезна, например, в случае, когда в задаче (0.1) целевая функция квазивыпукла.
Далее, в § 1.2 предлагается в виде процедуры 7г2 еще один общий метод решения задачи (0.1), близкий к процедуре 7Г], в котором итерационные точки i = 0,1,..., являются точками приближенного минимума на аппроксимирующих множествах А/,-вспомогательных функций Qi(x) = д(х) + а,/,(т). Для выбора чисел а* и функций /,(ж) имеются большие возможности. В лемме 1.4 обосновано, что любая предельная точка последовательности {} принадлежит множеству G, а в теоремах 1.1 - 1.4 доказана сходимость метода для различных способов задания последовательностей {с*,} и {/,-(:г)}. В замечаниях 1.7 - 1.10 показано, что при определенных способах выбора функций li(x) и других параметров процедуру тг2 можно интерпретировать как варианты некоторых известных методов, например, метода регуляризации, метода барьерных функций, штрафных функций.
В третьем параграфе гл. 1 на идеях §1.1 построены две общие схемы отсечений для нахождения точки множества G (см. процедуры 7Гз,тгз). Первая из них по сути также является методом решения задачи (0.1), где целевая функция имеет вид
9(z) = max (р, я-У), (0.2)
о
а Р - конечное множество обобщенно-опорных кСв точке у &G векторов. Эта процеду-
о
ра не требует знания вспомогательных точек ijj GGj, которые используются в дь д2 на-каждом шаге при построении отсекающих гиперплоскостей. Роль у* играет здесь точка у, а отсечения строятся в точках 2,- € (у, у,). Вторая из предложенных схем отличается от первой тем, что при нахождении точек % множество Р в (0.2) меняется от шага к шагу. В результате использования любой из процедур тгз, тг'3 будет найдена точка у, € G или построится последовательность {у,-}, у которой (см. лемму 1.5) любая предельная точка принадлежит G. В связи с этим Дз>^з действительно можно рассматривать как схемы отыскания точки выпуклого множества, однако подчеркнем, что ниже они будут применяться только как практические способы построения направлений спуска в предлагаемых методах минимизации. На основе замечаний 1.13, 1.14 и леммы 1.6 в п.2 данного параграфа приводятся примеры использования процедур тгз>Дз- ® виде алгоритмов ЯЛ - ЯЛ описываются и обосновываются (утверждения 1.1 - 1.4) некоторые реализации этих процедур для множеств G специального вида. Во всех реализациях удобно выбирать начальное погружающее множество Mq выпуклым многогранником, а отыскивать как точки минимума функции (0.2) на множествах М,-. Доказано, что для гладкой или негладкой псевдовыпуклой функции /(&•) алгоритмами Я\ - Я.\ можно построить за конечное число шагов подходящее в точке у 6 D направление, выбирая в процедурах тгз, тгз в качестве G лебегово множество
E(f,D,y) = {хе Д„ : i 6 Д f(x) < {(у)).
10
Все относящиеся к гл. 1 результаты получены без участия соавторов и опубликованы в работах (62, 66, 113, 115, 119, 120].
Гл. 2 посвящена разработке методов условной минимизации гладких псевдовыпук-лых функций с простыми реализациями на основе процедур аппроксимации, построенных в предыдущей главе. Как уже отмечено, во многих известных методах выпуклого программирования задачи построения подходящих направлений немногим проще исходной задачи, если ограничения определены нелинейными функциями. Предлагаемые в гл. 2 алгоритмы псевдовыпуклого программирования позволяют, несмотря на общий вид ограничений, отыскивать подходящие направления с помощью решения задач линейного или квадратичного программирования. Принципы построения направлений итерационного перехода, заложенные в этих алгоритмах, позволили также сделать реализуемыми в общем случае и некоторые известные методы выпуклого программирования -условного градиента, проекции градиента, Ньютона.
В §§ 2.1, 2.3, 2.5 предложены три метода решения задачи
гпт{/0(ж) | х в £>}, (0.3)
где множество D С Rn выпукло н замкнуто, dim D < п, а функция fo{x) псевдовыпукла и непрерывно дифференцируема. Первые два метода используют идеи метода условного градиента, а третий - метода проекции градиента. Предлагаемые методы объединены следующей общей схемой. На к - ом шаге методов выбираются множества Dk С Rn, удовлетворяющие введенным в тех же параграфах условиям Л, В или С (причем, до-пускается выполнение неравенств dim Dk < diinD), в множествах Dк отыскиваются
некоторые вспомогательные точки хк, направления s* = хк — хк используются для на-
хождения дополнительных точек v/c 6 Да очередное приближение хк+\ € D строится так, что
/o(s*+i) < /оМ- (0.4)
Методы отличаются друг от друга принципами выбора множеств Ок и способами задания точек хк <5 Dk. При этом множества Dk могут полностью или частично содержать область D, а могут и содержаться в ней. Если положить в методах
l)k ~ D, хк+\ = vk — хк -+■ fikskt
то при т.к = аг£гтпЦ/о(:г*),:г — хк^ \ х € Dk] первые два метода совпадают с методом условного градиента, а при хк = Pv(xk-vkf'0(xk)t Dk) третий метод является вариантом метода проекции градиента. Отметим, что в предложенном варианте метода проекции градиента традиционная операция проектирования вспомогательной точки (даже при ее выходе из D) может опускаться на некоторых итерациях, что полезно с практической точки зрения. Доказаны теоремы сходимости методов, получены оценки их скорости сходимости для всех случаев задания точек vk как с условием релаксации, гак и без него.
11
В §§ 2.2, 2.4, 2.5 предлагаются реализации этих методом, основанные на различных способах задания множеств Пк и на конечных процедурах тгь тг3 построения точек хк, в которых С = Г)к, у* — у = х*. При выборе в тгь 7г3 начального погружающего множества М0 в виде многогранника точки хк в таких реализациях будут находиться путем решения задач линейного или квадратичного программирования. В § 2.4 приводятся результаты численных экспериментов, проведенных с первыми двумя методами. На их основе реализации сравниваются между собой, а также с известными алгоритмами. Выявлены явные преимущества построенных алгоритмов с выбором Ик = Е{/о, £), ?д.), где ук € Ру перед методом условного градиента для ’’овражных” целевых функций. Заметим, что за счет условия (0.4) на этапе перехода от вспомогательной точки и* к приближению хк+1 предложенные методы можно комбинировать практически с любыми известными или новыми алгоритмами условной минимизации, в которых итерационные точки принадлежат допустимой области, причем, сходимость таких смешанных алгоритмов остается обоснованной в связи с теоремами 2.1, 2.3 - 2.5, 2.8, 2.10. Промежуточные точки ьк и условие (0.4) выбора приближений хк+\ будут использоваться далее почти во всех предлагаемых в диссертации методах, поэтому высказанное здесь замечание относительно построения на их основе всевозможных комбинированных алгоритмов будет иметь силу и в дальнейшем.
Для решения задачи (0.3) с сильно выпуклой функцией /о(т) в заключительном параграфе гл. 2 предлагается метод второго порядка, основанный на идеях метода Ньютона и алгоритмов из §§ 2.3. 2.5. В предлагаемом методе, в отличие от метода Ньютона, для построения на к-ом шаге подходящего направления эк = хк - хк, во-первых, можно использовать не все допустимое множество £), а лишь его часть, например, £>* = Е(/0,О,хк), и, во-вторых, вспомогательную задачу минимизации традиционной выпуклой квадратичной функции Ек(х) для нахождения точки хк можно решать не на множествах £) или £)*, а на содержащем их специально построенном множестве Л* более простого вила. С практической точки зрения аппроксимирующее множество Д* удобно строить как многогранное. Тогда задача выбора направления в методе является задачей квадратичного программирования, и может быть решена за конечное число шагов (см., напр., [22], с. 314). Отметим также, что на некоторых итерациях метода для отыскания направления вк достаточно решить только задачу безуслонпой минимизации Ек(х). Кроме того, в методе заложена возможность нахождения приближений х*+1 с использованием промежуточных точек ук = хк + (Зквк и условия (0.4). Доказана сходимость метода, получена оценка его скорости сходимости. Описаны реализации метода, в которых применяется конечная процедура отсечений из § 1.1 построения аппроксимирующих множеств Ак и, соответственно, точек хк.
Основные результаты гл. 2 опубликованы в работах, которые распределены но параграфам этой главы следующим образом. К §§ 3.2, 3.3 относятся [92, 93, 101], к §§ 3.4,
3.5 - [94, 101, 105, 107], к §§ 3.6, 3.7 - [95, 97], к § 3.8 - [93], и наконец, к § 3.9 - [106]. Все приведенные в гл. 2 результаты получены и опубликованы в названных работах
12
без участия соавторов.
Как уже подчеркивалось, размерности множеств Бк) используемых в методах главы 1, могут быть меньше размерности множества Б. Тогда задачи выбора направлений в этих методах имеют меньшую размерность, чем основная задача (0.3). Гл. 3 посвящена разработке таких алгоритмов условной минимизации, где принцип уменьшения размерности вспомогательных задач поиска направлений за счет специального выбора множеств Бк является основной идеей алгоритмов. Множества Бк в предлагаемых здесь методах выбираются из линейных многообразий, определяющихся градиентами целевой функции и активных в точке хк ограничений исходной задачи (0.3). Другими словами, в гл. 3 на примере методов условной минимизации гладких пссвдовыпуклых функций реализуется описанный выше подход параметризации направлений итерационного перехода, который позволяет для некоторых типов задач математического программирования снизить число переменных и ограничений в задачах построения приближений хк но отношению к некоторым известным методам.
Первый параграф гл. 3 носит вспомогательный характер. В нем исследуются некоторые свойства задачи (0.3), где
Б={хеНп: /](х) < 0, jeJ}, (0.5)
3 = {1, ...,т}, функции /^э:) псевдовыпуклы непрерывно дифференцируемы, а множество Б регулярно по Слейтеру. Эти свойства связаны со спецификой строящихся далее методов и особенностями обоснования их сходимости.
В § 3.2 ставится и исследуется задача построения в точке хк € Б подходящего направления в виде
** = 13 (0.6)
где 1к = ли{°ь ~ множество ек - активных в точке хк ограничений /}(х). Для
отыскания коэффициентов а,(я*) предлагается решать одну из трех вспомогательных
задач минимизации линейной функции ]Г) {/'0(хк), /[(ха.)} а* при некоторых ограниче-
4 '
ниях на переменные а,-. Изучаются свойства задач отыскания коэффициентов аДзд), и доказывается теорема оптимальности точки в терминах этих задач. Далее для решения задачи (0.3), (0.5) предлагается метод, в котором направления я*.. в точках хк строятся в виде (0.6), причем, вспомогательные задачи поиска коэффициентов аг{(эд) могут решаться приближенно. Точки находятся из условия (0.4) с привлечением дополнительных точек ук. При переходе от хк к ик по направлению вк допустимы различные способы задания шагов. Доказывается сходимость метода для всех видов шагов, приводятся оценки скорости сходимости.
Заметим, что допустимые области Ск вспомогательных задач поиска значений а,-(я*), вообще говоря, не являются многогранными при задании множества Б в общем виде, а значит, задачи выбора направления в точках хк могут быть достаточно сложны с практической точки зрения. Однако, в методе заложена возможность неточного реше-
13
ния указанных задач. В связи с этим, применяя уже использованные выше принципы аппроксимации множеств, можно для областей строить аппроксимирующие их множества в форме многогранников и, соответственно, ставить задачи поиска коэффициентов в (0.6) в виде задач линейного программирования. С учетом этого замечания
в § 3.3 приводится одна из возможных реализаций метода, в которой на каждой итерации при нахождении приближенного решения а,(з;Л), г € Д., вспомогательной задачи используются процедуры отсечений 7гI или 7Гз, описанные выше. Каждая из процедур гарантирует отыскание искомых значений а,(я*) за конечное число шагов, и при этом на каждом шаге процедуры независимо от вида О решается задача линейного программирования. В § 3.3 проводится сравнение предложенного метода псевдовыпуклого программирования с идейно близкими известными методами выпуклого программирования, отмечаются его преимущества для определенных типов задач (0.3). Приводятся также результаты численного сравнения на тестовых примерах некоторых алгоритмов метода между собой и с методом условного градиента.
Далее, во многих известных методах проекционного типа задачи поиска в итерационных точках направлений спуска немногим проще исходной задачи выпуклого программирования, поскольку размерности вспомогательных задач проектирования совпадают с размерностями исходной задачи, а сама операция проектирования вызывает большие трудности, когда допустимая область И определена нелинейными функциями. В связи с этим в §§ 3.4, 3.5 предлаг аются проекционные алгоритмы решения задачи псевдовыпуклого программирования, в которых, во-первых, задачи проектирования для построения подходящих направлений могут иметь меньшее по сравнению с исходной задачей число переменных и ограничений, и, во-вторых, несмотря на общий вид множества Г), проектирование вспомогательных точек может осуществляться на некоторые специально построенные многогранные множества. Уменьшение количества переменных и ограничений задач проектирования в предлагаемых алгоритмах происходит, как и выше, за счет параметрического способа (0.6) представления направлений перехода, а упрощение операции проектирования с применением многогранников - за счет уже использованных выше принципов и способов аппроксимации множеств. Итак, в § 3.4 приводятся и обосновываются два алгоритма для задачи (0.3), (0.5), в которых направления имеют вид (0.6), а коэффициенты аДх*) отыскиваются с помощью одной из двух задач проектирования градиента целевой функции на некоторое множество из линейного многообразия, определяемого векторами /’(х*), * € Д. Поскольку число неизвестных сх^Хк) в этих вспомогательных задачах зависит от количества активных в точке хк ограничений, то при тп < п такие задачи предпочтительнее традиционной задачи выбора направления, например, в методе проекции градиента. К тому же, при использовании в предложенных алгоритмах второй из вспомогательных задач проектирования число ограничений в ней также меньше, чем в упомянутом известном методе, а в случае Д = 0 она вообще не требует решения. На случай задания области £> нелинейными функциями в § 3.5 предлагаются модификации обсуждаемых алгоритмов, использующие заложенные
14
в проекционном методе параграфа 2.5 идеи аппроксимации множеств ДіВ модификациях направления (0.6) строятся путем проектирования градиента не на множества Дь, как в исходных алгоритмах, а на аппроксимирующие их многогранные множества Д*, что удобнее с практической точки зрения. Отметим, что все алгоритмы из §§ 3.4, 3.5 за счет построения дополнительных точек у* и условия (0.4) допускают возможность комбинирования их с другими релаксационными алгоритмами.
Использование параметризованных направлений для уменьшения размерностей задач их поиска возможно и в методах второго порядка. В §§ 3.6, 3.7 приводятся примеры построения таких методов. В § 3.6 для задачи (0.3), (0.5) с сильно выпуклой целевой функцией предлагается алгоритм, близкий к описанному выше в § 2.6 методу второго порядка. В этом алгоритме при построении направлений коэффициенты схг(хк) в (0.6) отыскиваются путем минимизации выпуклых квадратичных функций на некоторых множествах размерности которых определяются количеством активных в точках Хк ограничений. Несмотря на то, что эти вспомогательные задачи поиска коэффициентов в определенных случаях имеют меньшие, чем, например, в методе Ньютона, размерности, при задании множества В в общем виде они остаются достаточно сложны. В связи с этим в § 3.7 предлагается модификация алгоритма параграфа 3.6, позволяющая использовать в задачах выбора направления вместо множеств Вк аппроксимирующие их многогранные множества Д*.- из тех же линейных многообразий, что и Д. Тогда, несмотря на общий вид В, процедурами отсечений из § 1.1 удается получать искомые коэффициенты а,(я*) в комбинации (0.6) с помощью задач квадратичного программирования. В §§ 3.6, 3.7 приводятся обоснования сходимости алгоритма и его модификации, оценки скорости сходимости, а также реализации алгоритмов.
В § 3.8 предлагается еще один алгоритм решения задачи (0.3), (0.5) с параметризованными направлениями (0.0), который идейно близок к известному методу возможных направлений Зойтендейка. В отличие от методов с параметризацией из предыдущих параграфов главы этот алгоритм позволяет, независимо от вида ограничений (0.5), ставить задачи отыскания коэффициентов в (0.6) как задачи линейного программирования. Если размерность п пространства переменных исходной задачи превышает число га ограничений в ней, то предлагаемая задача выбора направления в построенном алгоритме выгодно отличается от традиционной задачи Зойтендейка по числу переменных и ограничений.
Использованный выше принцип параметризации может быть применен в алгоритмах, принадлежащих и другим классам методов. Один из таких примеров приведен в § 3.9. Здесь строится алгоритм псевдовыпуклого программирования, основанный на идеях метода линеаризации и близких к нему алгоритмов, в которых к построению направлений правлекаются задачи квадратичного программирования. В отличие от упомянутых методов предлагаемый алгоритм использует параметризованные направления вида (0.6), где коэффициенты аг(хк) находятся также путем решения задачи квадратичного программирования. Однако, применяемый здесь способ выбора направлений при
15
определенных условиях на размерности исходной задачи (0.3), (0.5) может быть предпочтительнее используемого в методах типа линеаризации. Заметим, что , как и другие методы гл. 2, 3, данный алгоритм позволяет за счет условия (0.4) комбинировать его с любыми релаксационными методами, не обосновывая заново сходимость смешанных алгоритмов.
Основные результаты третьей главы опубликованы. Распределение публикаций по параграфам выглядит следующим образом. К §§ 3.2, 3.3 относятся работы [92, 93, 101], к §§ 3.4, 3.5 - [94, 101, 105, 107], к §§ 3.6, 3.7 - [95, 97), к § 3.8 - [93], к § 3.9 - [106]. Все результаты гл. 3 получены и опубликованы в указанных работах без соавторства.
Глава 4 посвящена построению методов условной минимизации недифференцируемых псевдовыпуклых функций. Методы допускают операцию частичного или полного погружения допустимого множества в многогранники и параметрический способ представления направлений итерационного перехода с целью упрощения вспомогательных задач выбора направлений. Таким образом обосновывается возможность использования разработанных выше принципов аппроксимации и параметризации в негладком случае.
В § 4.1 строятся два релаксационных метода решения задачи (0.3) с негладкой строго лсевдовыпуклой функцией /о(я), в которых вспомогательные задачи близки к задачам построения подходящих направлений в алгоритмах минимизации гладких функций из §§ 2.1, 2.2. Близость заключается в том, что в предлагаемых методах целевые функции задач выбора направления могут быть линейными, а допустимые области £>* этих задач совпадают с. лебеговыми множествами £(/о, Д ж*)- Второй из этих методов отличается от первого тем, что применяется к задаче (0.3) с дополнительным требованием строгой выпуклости множества Д но, в то же время, имеет более широкие возможности в выборе подходящих направлений по сравнению с первым методом. Отметим, что в методах заложена возможность неточного решения задач выбора направления. В связи с этим в реализациях методов для отыскания этого приближенного решения предлагается использовать процедуру отсечений 7Г3 из § 1.3. При выборе в ней начального аппроксимирующего множества Мо в виде многогранника искомое направление спуска строится с помощью задач линейного программирования за конечное число шагов. В том же параграфе обсуждаются результаты численных экспериментов, проведенных с целью сравнения методов между собой.
Развитый в гл. 3 подход с параметризацией направлений для минимизации гладких функций распространяется далее на алгоритмы условной минимизации лсевдовыпуклой функции максимума. В § 4.2 ставится задача (0.3), (0.5), где /о (я) определена в виде функции максимума гладких псевдовыпуклых функций. Лля ее решения предлагается метод, в котором направление спуска на каждом шаге строится как линейная комбинация градиентов активных функций, задающих целевую функцию и ограничения (0.5). Коэффициенты комбинации находятся путем решения системы линейных неравенств или задачи линейного программирования. Показана сходимость метода, получены оценки скорости сходимости, описаны алгоритмы метода. За счет параметрического
16
представления направлений эти алгоритмы имеют определенные преимущества перед рядом известных методов нахождения дискретного минимакса в случае, когда общее число функций, определяющих исходную задачу, существенно меньше п.
Использованный в § 4.2 подход к решению задачи минимизации функции максимума можно перенести и на те методы, в которых минимаксными являются вспомогательные задачи построения итерационных точек или направлений перехода в итерационных точках. В последнем параграфе главы 4 на примере одного алгоритма решения задачи (0.3), (0.5) показывается, каким образом идея параметризации направлений может применяться и быть полезной с практической точки зрения в методах центров. В предлагаемом алгоритме на каждом шаге строится вспомогательная функция максимума Гк[х) на основе измененной целевой функции и функций ограничений исходной задачи (0.3), (0.5), и из текущей итерационной точки Хк производится переход в новую точку Ук с лучшим значением функции /ч(т). Используемое при этом направление имеет вид линейной комбинации активных в точке хк градиентов функции /'/•(я), а коэффициенты комбинации находятся с помощью решения системы линейных неравенств или задачи линейного программирования. Очередное приближение х.к+1 отыскивается из условия ^к(хк+1) < Рк{Ук)- После обоснования сходимости метода обсуждаются его реализации и возможные преимущества перед некоторыми методами центров для определенного типа задач.
Публикации, на основе которых написана гл. 4, распределяются по параграфам следующим образом. К § 4.1 относятся работы [60], [108] - [112), к ^ 4.2 — [87], [88], а к § 4.3 - [89] - [91]. Заметим, что § 4.3 диссертации написан по результатам совместной статьи [91], которая посвящена разработке варианта параметризованного метода центров для задачи выпуклого программирования. Князеву Е. А. в этой статье принадлежат леммы 2, 4 и первая часть доказательства теоремы сходимости, а Заботнну И. Я. - предлагаемый метод, лемма 3, теорема оптимальности точки, а также теоремы 2, 3 и вторая часть доказательства теоремы сходимости метода. Однако, заметим, что результаты данного параграфа диссертации носят более общий по сравнению с результатами статьи [91] характер, т. к., во-первых, они получены для задачи исевдовыпуклого программирования, и, во-вторых, сам предлагаемый здесь метод обобщает метод из работы [91].
Пятая глава диссертации посвящена построению методов безусловной минимизации гладких псевдовыпуклых функций и исследованию их устойчивости. Предлагаемые методы характерны тем, что в них переход от точки к точке, как и в алгоритмах гл. 3, 4, происходит в некоторых линейных многообразиях, порождаемых приближениями Хк и специально выбранными векторами. Таким образом, идея параметризации направлений, использованная выше в методах условной минимизации, применяется и в данной главе. Разработанная здесь схема решения упомянутой задачи позволяет строить на ее основе новые одношаговые и многошаговые алгоритмы минимизации псевдовыпуклых функций с указанной выше особенностью, распараллеливать процесс решения исходной задачи, получать различные смешанные алгоритмы без дополнительных обоснований
17
их сходимости. С помощью предложенной в гл. 5 методики исследуется устойчивость многих (как известных, так и новых) алгоритмов по отношению к ошибкам вычисления частных производных в итерационных точках.
В § 5.1 для задачи
тт{/0(х) ] х € Л„} (0.7)
с псевдовыпуклой непрерывно дифференцируемой целевой функцией строится и обосновывается общий метод, в котором переход от точек хь к промежуточным точкам Ьк происходит в некоторых линейных многообразиях М(х*), а затем приближение г€ Яп выбирается согласно условию
/о(я*+1) < /оМ. (0.8)
Размерности многообразий задаются на каждом шаге произвольно от 1 до п. За счет большой свободы в выборе множеств М(х1е), вспомогательных точек и приближений .7;*+] метод допускает значительное число реализаций, которые приводятся в § 5.2. Среди них - известные алгоритмы выпуклого программирования, их модификации и новые алгоритмы минимизации псевдовылуклых функций. К известным алгоритмам, которые являются реализациями предложенного метода, относятся методы наискорсй-шего спуска, покоординатного спуска, обобщенный метод градиентного спуска, метод изменения масштабов, метод Ньютона с регулировкой шага, квазиньютонопские алгоритмы, варианты метода сопряженных градиентов и многие другие. Для каждого из этих методов, а также для всех предлагаемых новых алгоритмов в § 5.2 доказывается выполнение тех или иных условий теорем 5.1 - 5.3 сходимости общего метода и теорем 5.4, 5.5, касающихся оценок его скорости сходимости. Тем самым для многих исследуемых в § 5.2 методов выпуклого программирования и новых алгоритмов обосновывается
возможность их использования для задачи псевдовыпуклого программирования (0.7) и доказываются оценки скорости сходимости для иссвдовыпуклых и сильно выпуклых функций. Таким образом, предложенный в § 5.1 подход к разработке методов решения задачи (0.7) позволяет строить новые одношаговые и многошаговые алгоритмы с практически произвольными процедурами обновления, модифицировать известные методы, расширяя их возможности в выборе направлений и шаговых множителей, а также по единой методике исследовать сходимость методов и получать оценки скорости сходимости. Кроме ТОГО, поскольку процесс отыскания приближения Хк+1 из условия (0.8) в методе не конкретизирован, то за счет чередования различных способов построения точек Ук и Хк+1 можно получать всевозможные смешанные алгоритмы на основе известных и новых методов без дополнительного обоснования их сходимости.
В отдельный параграф (§ 5.3) выделены еще два алгоритма решения задачи (0.7), которые идейно близки к общему методу из § 5.1, но формально в него не вкладываются и потому обосновываются по другой методике. Эти алгоритмы уместно отнести к классу методов спуска по группам переменных. В данный класс можно включить хорошо известный метод покоординатного спуска и его варианты, метод градиентного спуска
18
по быстрым переменным ([166, 167;) и некоторые другие, в том числе эвристические, алгоритмы. Отметим, что в алгоритмах спуска по быстрым и медленным переменным (напр., [166]) используется эвристический прием чередования переходов в подпространствах быстрых переменных с переходами по группам медленных переменных. Несмотря на определенную практическую пользу такого чередования при минимизации ”овражных” функций (см. [166]), у этих алгоритмов, кроме вопросов о критериях отбора групп переменных на каждом шаге, остаются открытыми вопросил об их сходимости и оценках скорости сходимости. И связи с этим могут оказаться полезными предлагаемые в § 5.3 критерии отбора групп переменных, участвующих в итерационных переходах строящихся здесь алгоритмов. Эти критерии, во - первых, просты для проверки, во -вторых, гарантируют сходимость методов указанного класса, и в - третьих, позволяют выбирать на каждом шаге число переменных, входящих в эти группы, любым от 1 до л, т. е. производить переход в подпространствах любой размерности. На базе этих критериев и строятся упомянутые алгоритмы спуска по группам переменных. В том же § 5.3 доказывается их сходимость, обосновываются опенки скорости сходимости, описываются реализации. Среди этих реализаций есть известные методы покоординатного спуска и спуска по быстрым переменным, которые благодаря теоремам сходимости 5.6 - 5.9 могут использоваться при решении более общих задач (0.7). Как и в упомянутом методе [166], в предлагаемых здесь сходящихся алгоритмах допустимо чередование шагов в подпространствах быстрых и медленных переменных, причем, размерности этих подпространств можно задавать заранее на каждой итерации. За счет условия (0.8) выбора точек 27*^1 алгоритмы допускают комбинирование с методами этого же или другого класса.
Следующие три параграфа главы посвящены исследованию устойчивости алгоритмов решения задачи (0.7) к ошибкам вычисления градиентов. Устойчивость в том или ином смысле методов выпуклого программирования изучается во многих работах (ссылки см. в тексте), но используемые там подходы в большинстве случаев опираются на то, что исследуемые методы применяются для минимизации выпуклых, а не псевдо-выпуклых функций. Предлагаемый здесь подход позволяет исследовать устойчивость в указанном смысле методов как выпуклого, так и псевдовыпуклого программирования. Этот подход основывается на разработанной в § 5.4 общей схеме решения задачи (0.7), в которой заложена возможность неточного вычисления градиентов целевой функции в итерационных точках. Поскольку сходимость и оценки скорости сходимости доказываются для схемы с учетом погрешностей вычислений, то тем самым обосновывается устойчивость тех алгоритмов, которые вкладываются в эту схему и в которых погрешности вычисления градиентов удовлетворяют тем же условиям, что и в общей схеме.
Предлагаемая схема близка к методу из § 5.1. Итерационные переходы в ней тоже осуществляются в некоторых линейных многообразиях М(Хк), но построенных с использованием неточно вычисленных градиентов. За счет определенной свободы в выборе многообразий М{хь) схема допускает различные реализации, среди которых - извсст-
19
ные и новые алгоритмы. В §§ 5.5, 5.6 для этих алгоритмов на основе сформулированного выше принципа исследуется их устойчивость в указанном смысле. При этом приходится доказывать, что каждый из алгоритмов является частным случаем общей схемы. В указанных параграфах исследованы на устойчивость метод обобщенного градиентного спуска, так называемый нелинейный метод ’197], методы покоординатного спуска и Ныотона, квазиньютоновские алгоритмы, метод многопараметрического поиска [205], а также многие другие известные и новые одиошаговые и многошаговые алгоритмы. Отметим, что для многих исследованных алгоритмов справедливы оценки скорости сходимости общей схемы, полученные с учетом погрешностей вычисления градиентов, для псевдовынуклых и сильно выпуклых функций.
Вес результаты гл. 5 опубликованы. К § 5.1 относится работа [98], к § 5.2 - [60, 96. 98, 99], к § 5.3 - [77, 78, 85], к § 5.4 - (99, 102, 103, 104], к § 5.5 - [99, 102, 103, 104], к § 5.6 - [96, 99, 102]. Все описанные в пятой главе результаты получены (и опубликованы в названных работах) без участия соавторов.
Заключительная 6-я глава диссертации посвящена разработке методов решения задач псевдовынуклого программирования специального вида, а также решению некоторых прикладных задач проектирования технических систем построенными в данной работе алгоритмами.
Зачастую практические оптимизационные задачи вида (0.3) обладают специфической структурой за счет особенностей задания целевой функции или допустимого множества. В гл. 6 приведены соответствующие примеры и ссылки. Одной из таких особенностей можно считать задание области I) в (0.3) в виде прямого произведения выпуклых замкнутых множеств Д, г = 1,...,т, из пространств 7?^., вообще говоря, различных размерностей. В § 6.1 строятся два метода минимизации гладкой исевдовыпуклой функции на множестве указанного вида. Методы характерны тем, что на каждом шаге итерационный переход при желании может производиться в них лишь по части переменных задачи. В связи с этим методы могут быть отнесены к алгоритмам спуска по группам переменных наряду с некоторыми известными алгоритмами выпуклого программирования (напр., (9, 37. 56]). В диссертации предлагается отличный от известных принцип выбора групп переменных, но которым производится спуск на каждом шаге. Формирование этих групп происходит в результате решения т вспомогательных задач минимизации некоторых функций F■:(x) на множествах Д. Построенные на основе предложенного принципа методы отличаются друг от друга тем, что спуск на к -ом шаге в выбранном подпространстве происходит либо по конкретным направлениям, либо с большой долей свободы, привлекая любые релаксационные процедуры. Заложенный в методах критерий выбора групп переменных гарантирует их сходимость, позволяет заранее задавать желательную размерность подпространств, в которых производится спуск, дает возможность построения различных реализаций. Среди них можно выделить вариант метода покоординатного спуска для задачи (0.3) с множеством V в виде параллелепипеда, алгоритм спуска по быстрым переменным, алгоритмы, в которых до-
20
пустимо чередование переходов по быстрым и медленным переменным. Отметим также, что предложенные методы можно комбинировать с другими алгоритмами, а решение упомянутых вспомогательных задач минимизации 1\к(х) на множествах Д можно проводить одновременно на многопроцессорных ЭВМ, что поможет сократить время построения направлений спуска.
В § 6.2 ставится еще одна экстремальная задача
специального вида. Функция Г(х) в (0.9) представляет собой функцию максимума, характерную тем, что каждая из составляющих ее непрерывных функций /»(ж,-), г = I,..., 771, зависит от переменных , не связанных с переменными остальных функ-
ций, а область Д как и в § 6.1. задана в виде прямого произведения выпуклых замкнутых множеств Д С Япг Изучаются свойства задачи (0.9). Доказывается, что для ее решения нет необходимости в последовательном решении всех частных задач
Если х* = (х;,...,х^) - решение задачи (0.9), то необязательно для каждого г = компонента х,- является решением соответствующей задачи (0.10). Для поставленной задачи (0.9) в том же параграфе строится и обосновывается метод, который также можно отнести к алгоритмам спуска по группам переменных. Переход из текущей итерационной точки хк = (х|, ...,х*п), хк € Д, производится в методе лишь по тем переменным X,, для которых соответствующие функции /,-(х*) являются активными в точке хк. Спуск по выбранным переменным х, производится в областях Д с привлечением любых, вообще говоря различных, сходящихся алгоритмов Л7г.
Далее, в работе [35) построен один метод субградиентного типа для задачи нахождения седловых точек выпукло - вогнутых функций при наличии ограничений. Сходимость метода доказана в [35] при так называемом условии устойчивости множества седловых точек, которое на практике не всегда выполняется. В связи с этим в § 6.3 предлагается идейно близкий к методу (35] алгоритм, который вырабатывает последовательность приближений, сходящуюся к решению лишь по функционалу, но без дополнительного предположения об устойчивости множества решений.
В заключительном параграфе главы 6 приводятся примеры использования некоторых из предложенных в диссертации методов для решения прикладных задач. В рамках договоров между Казанским государственным университетом и российскими предприятиями, связанными с проектированием технических систем, в течение ряда лет с участием автора ставились и решались оптимизационные задачи синтеза радиоэлектронных систем и их отдельных подсистем. Некоторые из задач описаны в § 6.4 и решены с применением разработанных здесь алгоритмов.
Результаты главы 6 полностью опубликованы. Они описаны в работах [78, 80, 84, 86], относящихся к § 6.1, в работах [75, 79), касающихся § 6.2, в статье [76], относящейся
тіп{7?(х) | х Є £>}
(0.9)
(0.10)
21
к § 6.3, и наконец, в работах [71, 74, 81, 83], относящихся к § 6.4. Нее представленные в §§ 6.1 - б.З результаты получены и опубликованы в названных работах без участия соавторов. Статьи, касающиеся решения прикладных задач из § 6.4, являются совместными. В связи с этим отметим, что прикладные оптимизационные задачи данного параграфа, относящиеся к проектированию радиоэлектронных систем, были предложены автору руководителем упомянутых договоров доцентом кафедры радиофизики КГУ Кобчиковым А. В. Их математические постановки, описанные в § 6.4 диссертации, разрабатывались авторами указанных статей совместно, а использованные при решении задач алгоритмы и результаты экспериментов, приведенные в том же § 6.4, принадлежат Заботину И. Я.
Заметим также, что в диссертации имеются ссылки и на некоторые другие совместные работы автора, например, [65, 67, 73, 82]. Однако, опубликованные в них результаты никак не представлены в диссертации и, соответственно, не выносятся на защиту, поэтому деление результатов между соавторами для таких работ здесь не производится.
Автор выражает благодарность участникам научного семинара кафедры экономической кибернетики КГУ, а также профессору И. В. Коннову за полезные обсуждения и замечания в ходе работы над диссертацией.
(
22
Глава 1
Общие процедуры решения задачи математического программирования и отыскания точки выпуклого множества. Их реализации
1.1 Общие процедуры аппроксимации с частичным . погружением допустимого множества для задачи математического программирования
В данном параграфе предлагаются общие процедуры решения задачи математического программирования, использующие идею погружения допустимого множества. В то же время их можно считать схемами отыскания точки выпуклого множества. Доказывается сходимость процедур. Обсуждаются их реализации. В основном результаты параграфа будут использованы в дальнейшем в качестве вспомогательных при построении методов исевдовыпуклого программирования.
Пусть I = {0,1,...}, J = {1,...,т}, С Яп, j е J, - выпуклые замкнутые
о
множества, внутренность Су множества Су непуста для всех д € ^/, С = П О,, (7 Ф

0, \'\/Т(х,Су) = {а £ Яп : (а. г - х) < 0 Уг е (”?,•} - конус обобщенно-опорных векторов для множества бу в точке х <~ Я,*, \¥1(х, £;) = {а € Я.п : а € И7(я, С>), |)о|| = 1}. Пусть у(х) - непрерывная достигающая на множестве С минимума функция, д* = 1шп^(з:), У* - Агдт\пд(х), Е{д, 7) = {х в Яп : д{х) < 7}, Е(д,С>'у) = {х е С :
хбО х<ЕО
Ф) < у}, Е(д,г) - {х € Яп : д(х) < .ф)}, Е(д,в!г) = {х € в : д(х) < ф)}, где 7 еЯи г € Яп-
23
1. Опишем сначала процедуры, которые могут служить методами решения задачи
mms(x). (1.1)
Процедура 7Г] = 7Ti(g(x), G). Строится выпуклое замкнутое множество М0 с ЯП1 со-
О
держащее хотя бы одну точку множества У*. Выбираются точки yJ Є Gj V7 Є ■/, задается число q Є [I, -гос), полагается і = 0.
1. Отыскивается точка у{ € Mif\E(g,g*). Если
Рі Є G, (1.2)
'го процесс заканчивается.
2. Полагается
А = (І Є J : & £ £?,}.
о
Для всех j Є Ji в интервале (уЯУі) находится такая точка zj £ Gj, что существует точка yj Є Gj, удовлетворяющая неравенству
Ші-ІЇ\\<я\\Уі-гІ\\- (1.3)
Для всех j <t Ji полагается z\ = yj =%.
3. Для всех j Є Ji выбирается конечное подмножество А\ С Wl(zj,Gj), полагается
Мі+1 = Мх р|{х Є Rn : {a,x — zj) <0 Va€ AJit j € Jt}, (1.4)
и следует переход к пункту 1 при і, увеличенном на единицу.
Отметим, что, несмотря на условие нсиустоты внутренности каждого из множеств Gj, j Є J, внутренность G может быть пустой.
Замечание 1.1 . Если при некотором і Є I выполняется включение (1-2), то очевидно, что % Є Y*. Если же в результате работы процедуры выработана последовательность {!/;}, і Є І, то, как показано ниже, любая ее предельная точка принадлежит множеству У*. Кроме того, если положить Tji = arg min g(z) Vi Є І, то последо-
хЄМі
вательность {yj}, і € І, сходится к множеству Ym. Таким, образом, процедура т\\ действительно может служить методом решения задачи (1.1). Отметим, что если
о о
Gl = ... = Gm = G, Gi=- 0, функция g(x) выпукла, у1 = ... = ут = у, и у Є G, то процедура 7гі близка к известным методам погружений В. II.Булатова (папр., [21]) для задачи выпуклого программирования.
Замечание 1.2 . В процедуре 7ч можно положить Mq = Г) Gj, где J' С J, в част-
j€J'
пости, М0 = Gjof где jo € J. Так как у і Є Mt С А/о Vt € І, то о множествах Jj при всех і <Е I будут отсутствовать индексы из J', и точки у3 Є Gj, j Є J', пи па одной итерации процедуры не понадобятся. В этом случае уК j € J', задавать не нужно. Такой способ выбора Мо удобен, например, когда П G, - выпуклый многогранник.
24
Если Mq = 7?п, то при достижении функцией в Яп своего минимального значения можно положить у0 = arg min д(х). При пыборе Л/0 = G процедура завершает работу на
Ян
О о
первом шаге. Если G ф Ъ и известна точка у € G’, то в 7гг удобно положить у} = у V? € J.
Замечание 1.3 . В упомянутых методах [21] для построения отсече)шя выбиралась точка Zi пересечения отрезка [y,yt] с границей множества G. В предложенной процедуре не нужно отыскивать точку пересечения отрезка с границей множества
Gj. Более того, для проверки условия (1.3) не требуется находить и точку у{. Это условие можно проверить, например, следующим образом. Если yi -г q(z\ — yf) <Е Gj или, если у{ +q(zj - рх) $ Gj, но \\% - у*\\ < q\\% - zj\\, то очевидно, что требования пункта 2 процедуры выполняются.
Способы построения элементов множества W{(zi,Gji) можно найти, в частности, в работах [122], [128], [198].
2. Исследуем сходимость описанной процедуры.
Пусть dim U - размерность множества U С Я,г, т. е. размерность его аффинной оболочки aff U. Если dim U = п, то внутренность множества V будем обозначать,
о
как и прежде, через V или int U. Если dim U < п, то относительную внутренность
множества U обозначим, как и принято (см., напр., [22] , с 160), через ri if.
Лемма 1.1 . Пусть множество U С Пп выпукло, dim V = n', 1 < п' < п, L -несущее подпространство множества U. Пусть и € ri U, множество Q С aff U ограничено, Q <£ ri U. Тогда найдется такое число 6 > 0, что для всех z € Q\ri U и всех а в LC\Wl(z, U) выполняется неравенство
{a, XL — z) < —6. (1.5)
Доказательство. Допустим, что утверждение леммы неверно. Выберем такую числовую последовательность {£/},/ € /, что <5/ > 0 V/ € /, и 6( -> 0, / ->■ оо. Тогда по предположению для каждого числа Si найдутся такие zt € Q\ri U и (ц € Lf)Wl(zi,U), что
(altu - zt) > -61.
Выделим из ограниченных последовательностей {z/} и {«*} сходящиеся подпоследовательности {zik} и {a/fc}, hei. Пусть, соответственно, z ий- их предельные точки. Так как (a[k,x — zik) < 0 Vx £ U, то, переходя в этом неравенстве к пределу по к —у оо, получим
<ä,x-z> < 0 Vx € U. (1.6)
Как уже отмечено, для всех к е I выполняются неравенства
0 > (atk,u- zih) > -6lk.
25
Перейдем в этих неравенствах к пределу по к -> эс. Тогда (a, u-z) = 0, причем ||5|| ф 0. Заметим, что в несущем подпространстве L найдется хотя бы одна точка х, для которой (а,х) ф 0, поскольку в противном случае вектор а принадлежал бы ортогональному дополнению подпространства L до всего пространства, что невозможно в силу выбора векторов ai £ L VI £ I. Таким образом, с учетом равенства af/U = и + L н включения и £ ri U можно выбрать вектор s £ L так, что {а, .*>) ф 0 и при этом и + s £ U и и - 5 £ U. Тогда согласно (1.6} (а, и + s) < (а, z) и (а,и - $) < (а, г). Отсюда с учетом, что (а,и) = (a, z), следует равенство (a, s) = 0, противоречащее выбору вектора s. Лемма доказана.
Из леммы 1.1 непосредственно вытекает
О
Следствие 1.1 . Пусть множество U С /?„ выпукло, и £ Ц, множество Q С Rn
о о
ограничено, Q U • Тогда найдется такое число 6 > 0, что для всех z £ Q\ JJ и всех а £ Wl(z,U) справедливо неравенство (1.5).
Пусть последовательность {%}, г £ /, построена процедурой щ. Для каждого j £ J положим
N* = {г £1 : j £ JJ.
Лемма 1.2 . Пусть последовательность {^}, г £ I, построена процедурой к\, и
{f*}? i € 1\ С I, - ее сходящаяся подпоследовательность. Тогда для каждого j £ ./
справедливо равенство
Jim N - fill =0. (1.7)
ie/i
Доказательство. Пусть j £ J. Положим
I[ = {i£h : i £ №}, I'{ = {i£ /, : ii №}.
Тогда I\ = J{ U /(', z\ Ф iji Vi £ /{, и z{ = Vi £ I". Если множество /[ конечно или пусто, то равенство (1.7) очевидно для выбранного j £ J. Поэтому будем считать, что 1[ состоит из бесконечного числа номеров. Отметим, что для всех г £ I
4 = Vi + tfV - ft). (is)
где уI £ [0,1), причем согласно пункту 2 процедуры у- > 0, если г £ и yj = 0 в противном случае.
Пусть номера i,p £ 1J таковы, что р > г. Поскольку Мр с А7,-, ур £ Мр, и любой элемент множества А\ является обобщенно-опорным для множества Мр в точке zj, то (а,ур - z{) < 0 Va £ А\. Отсюда с учетом (1.8)
Vi ~ УР> > 7i <«> Vi ~ Vj) Va £ A\.
26
По следствию к лемме 1.1 найдется такое число > 0, что («,у, — у*) > - у7) >
Уг е /[, а е А{. Следовательно, <а,&—£р> > Уа € /1*', а поскольку ||а|| = 1 Уа € Л],
то
НЕ- “ 5РН > VI, р е /;, р > г. (1.9)
’Гак как подпоследовательность {1/*}, г € /5, последовательности {у*}, г € Л, является сходящейся, то согласно (1.9) т/ —> 0, г —> оо, г € /!• Но, как уже замечено выше, т/ = О для всех г € /". Значит, т/ —У 0, г —> сю, г е /|, н из (1.8) с учетом ограниченности величин Ц?/-7 - |^[|, г € Л, следует утверждение леммы.
Лемма 1.3 . Пусть последовательность {т/*, }, г € /, построена процедурой тг\, и является ограниченной. Тогда любая предельная точка этой последовательности принадлежит множеству С.
Доказательство. Пусть {р*}, г € /, С /, ~ любая сходящаяся подпоследовательность последовательности Щ}, г € /, и у - ее П1»едельная точка. Покажем, что
27 е С;, (1.10)
тогда утверждение леммы будет доказано.
Отметим, что при каждом у 6 7 выбранной подпоследовательности {у*}, г <Е /ь соответствует последовательность {гг*}, г € /ь причем, по лемме 1.2 для всех у 6 .7 справедливо равенство (1.7). Согласно пункту 2 процедуры для каждой пары номеров г € 7* и у € 7 существует точка у- € (7,, совпадающая с у* при у £ 7* и удовлетворяющая неравенству (1.3) при у е .7г. Так как последовательность {у*}, г € /ь ограничена, то отсюда с учетом (1.3), (1.8) следует ограниченность последовательности {у*}> * € /ь для каждого у € 7. Выделим из каждой последовательности {у?}, г € /ь у е .7, сходящуюся подпоследовательность {у?}, г € Р С /1, и пусть - ее предельная точка. Заметим, что и3 € С7, V; € .7 в силу замкнутости множества (7,-. Положим
// = {г <= Р : г 6 А"}, 1{ = Р \ Т{ V у € .7.
Хотя бы одно из множеств 1{ или /2 для каждого у € 7 состоит из бесконечного числа номеров. Перейдем теперь при каждом фиксированном у € «7 к пределу в неравенствах (1.3) по г —» оо, г € 7/, с учетом (1.7), если 7? бесконечно, или в равенствах у* = р* но г -> оо, г € /3, если /2 бесконечно. Тогда получим равенства у = Uj Уу € .7, из которых следует включение (1.10). Лемма доказана.
Теорема 1.1 . Пусть последовательность {у*}, г € I, построена процедурой тг* с условием, что множество М0ПР(у,У*) ограничено. Тогда любил предельная точка этой последовательности принадлежит множеству У*, а если при этом
27(2/i) = тту(.т) Vi€ /, г€ л/|
то ося ?шслсс7ооашслькость {у,}, г 6 /, сходится к множеству Y
(1.11)
27
Доказательство. Пусть {ÿj, i G 1\ С /, любая сходящаяся подпоследовательность
последовательности {ÿj, г 6 /, и ÿ - ее предельная точка. По лемме 1.3 справедливо
включение (1.10). Так как д(у,J < #*, г G /, то lim </(Е) = #©) < д*. С другой стороны,
»<=/]
<7©) > .9* согласно (1.10). Таким образом, g (у) = g\ и первое утверждение теоремы доказано. Далее, пусть выполняется условие (1.11). Поскольку Мц.\ С A/,, г G /, то f)(Ui+1) > <?(Е)> * € Л а значит, с учетом ограниченности {yj, г € /. последовательность {<7©*)}, г 6 /, сходится. Тогда в силу уже доказанного первого утверждения последовательность ©©j)}, i G /, является минимизирующей, и по теореме 1 ([22] , с. 74) второе утверждение теоремы тоже доказано.
Замечание 1.4 . В пункте 2 процедуры при j € «Л точку z\ из интервала ©*,!/*)
О
можно выбирать и другими способами, например, так, чтобы z\ <f:Gj и при некотором QÎ е [1»?] выполнилось включение ÿi + gj(zj - 7/,) = ÿj E Gj. Нетрудно проверить, что утверждения леммы 1.3 и теоремы 1.1 останутся справедливыми и в этом случае.
3. Пусть L - подпространство пространства Rn размерности n\ 1 <п'< п, Д с Д,, - линейное многообразие, порожденное подпространством L и некоторой точкой из Rn. Пусть в приведенной выше постановке задачи (1.1) выпуклые замкнутые множества G j, j G таковы, что
Gj С Д, dim Gj = п\ ri G, ф 0 Vj € •/, G ф 0.
Опишем для такой задачи, как обобщение процедуры тгь еше один итерационный процесс, который в частном случае при )./[ = 1 будет использоваться далее в реализациях некоторых предлагаемых методов условной минимизации.
Пусть в процедуре 7Гi множество А/0 задается с дополнительным условием А/о С Д; точки таковы, что 6 ri Gj Vjf G J, а в пунктах 1—3 процедуры точки zj и множества А{ выбираются из условий zj £ ri Gj, А\ С Lf] W\zj, Gj). Процедуру 7t\ с такими изменениями обозначим через tFi = 7Г1©(ж),С?).
Сразу отметим, что при п! = п процедура к\ совпадает с процедурой эть т. к.
о
А = Rn, ri Gj =Gj, j G J. Коротко остановимся на свойствах последовательности {ЕЬ * € Л построенной процедурой 7гi. Пусть {ÿ,}, i G /] С /, - любая сходящаяся подпоследовательность этой последовательности. Повторяя с привлечением леммы 1.1 обоснование леммы 1.2, доказывается равенство (1.7) для каждого j G ./. На его основе, полностью повторив доказательство леммы 1.3 и теоремы 1.1 при условии ограниченности множества А/0 П E(g,g*), легко получаем для последовательности {pj, i € I, утверждения леммы 1.3 и теоремы 1.1. Таким образом, процедура лч может служить методом решения задачи (1.1) с приведенными выше особенностями в задании множества G. Кроме того, для процедуры tTj можно сделать замечания, аналогичные замечаниям
1.2 - 1.4 к исходной процедуре