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

• Заботин, Игорь Ярославич
• доктор физико-математических наук
• 2009

Оглавление диссертации доктор физико-математических наук Заботин, Игорь Ярославич

Введение

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

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

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

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

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

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

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

§ 2.1.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

0.9)

I х1 е А-}.

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

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

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

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

Заключение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Список литературы диссертационного исследования доктор физико-математических наук Заботин, Игорь Ярославич, 2009 год

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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