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

На правах рукописи

Морозова Елена Юрьевна СЮ3054012

ГЛОБАЛЬНАЯ МИНИМИЗАЦИЯ КВАЗИВОГНУТЫХ ФУНКЦИЙ НА ВЫПУКЛЫХ МНОЖЕСТВАХ

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата фшико-матбматических наук

Санкт-Петербург 2007

003054012

Работа выполнена на кафедре прикладной математики Петербургского государственного университета путей сообщения.

Научный руководитель доктор физико-математических наук,

профессор Жигалко Евгений Фаддеевич

Официальные оппоненты: доктор физико-математических наук,

профессор Демьянович Юрий Казимирович;

доктор физико-математических наук, профессор Шапорев Сергей Дмитриевич

Ведущая организация: Санкт-Петербургский государственный

университет гражданской авиации

Защита состоится 14 марта 2007 г. в 15 часов на заседании диссертационного совета К 212.223.01 при ГОУ ВПО «Санкт-Петербургский государственный архитектурно-строительный университет» по адресу: 190005, Санкт-Петербург, 2-я Красноармейская ул., д. 4, ауд! 505 А.

Телефакс: (812) 316-58-72.

С диссертацией можно ознакомиться в библиотеке ГОУ ВПО «Санкт-Петербургский государственный архитектурно-строительный университет»

Автореферат разослан « февраля 2007 г.

Ученый секретарь диссертационного совета

В.А. Фролькис

Общая характеристика работы

Актуальность темы исследования. Активные исследования последнего времени привели к появлению разнообразных методов нахождения глобальных решений нелинейных оптимизационных задач с ограничениями. Рсиниоиразные важные практические приложения в экономике, промышленности и других областях приводят к необходимости отыскания глобального минимума квазивогнутой функции на замкнутом выпуклом множестве. Так, например, к формулировке задач такого типа приводят задачи с эффектом масштаба (economies of scale) и задачи фиксированных расходов (fixed charge problems). В связи с задачами минимизации эксплутационных расходов при организации железнодорожных перевозок также возникает необходимость в решении задачи квазивогнутого программирования. Несмотря на существование различных методов глобальной минимизации вогнутых функций на выпуклых множествах, возможности применения этих методов для решения конкретных задач ограничены предположениями о принадлежности некоторым специальным классам как оптимизируемых функций, так и допустимых множеств. Таким образом, разработка новых эффективных методов минимизации квазивохнутых функций на выпуклых множествах остается актуальной задачей прикладной математики.

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

Задачи диссертационного исследования.

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

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

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

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

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

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

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

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

Основные положения, выносимые на защиту.

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

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

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

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

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

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

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

Апробация работы. Результаты диссертации докладывались на научных семинарах кафедры прикладной математики ПГУПС, на Третьем Всероссийском симпозиуме по прикладной и промышленной математике (Сочи, 2002), на Восьмой международной научно-практической конференции «ИНФОТРАНС - 2003» (СПб, 2003), на Четвертом (весенняя сессия - Петрозаводск, 2003), (осенняя сессия -Сочи, 2003), Шестом (весенняя сессия - СПб, 2005), (осенняя сессия - Сочи, 2005), и Седьмом (Кисловодск, 2006) Всероссийских симпозиумах по прикладной и промышленной математике.

Публикации. По теме диссертации опубликовано 12 работ.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Работа изложена на 135 страницах машинописного текста, содержит 32 рисунка, 3 таблицы и 137 библиографических ссылок на литературу.

Содержание работы

Во введении обоснована актуальность темы, сформулированы цели и основные задачи исследований, приведен обзор литературб1 по теме работы, приведены сведения о научной новизне, основных результатах, выносимых на защиту, их апробации и публикации.

В первой главе предлагается новый рекурсивный алгоритм прямого поиска минимума негладкой функции нескольких переменных.

В разделе 1 рассматривается задача

/(x)-»mm, xeS, (1)

где / - непрерывная функция на множестве S, a S - п-мерный симплекс в пространстве Я",т.е. S = c0m>(vo,y,,...,vll),me v0,v,,...,vn -аффиннонезависимые

точки в пространстве R".

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

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

Пусть D - ограниченное замкнутое выпуклое подмножество пространства R". Функция / : D -> R называется строго унимодальной на множестве D, если для любого отрезка Дс£> # Л rg min {/(эф: е Д} = 1, где символ «#» означает мощность множества.

Заметим, что если функция строго унимодальна, то и на любом замкнутом выпуклом подмножестве D'czD #Argmm{f(x),x е £>'} = 1. Отметим также, что класс строго унимодальных функций содержит класс строго выпуклых функций (на множестве D).

Пусть / - непрерывная функция в замкнутой ограниченной области D

пространства R". Зафиксируем вектор единичной нормы е и для каждого вещественного числа t рассмотрим гиперплоскость

Г/={хеГ|{е,л-) = /}. (2)

Семейство {у, |-оо </<«>} покрывает все пространство Л" и поскольку Б -замкнутая ограниченная область, то найдутся значения / и такие, что для каждого получим £>, = /) п * 0, а для каждого I £ [/тш, /п1ал ] I) = 0.

Имеет место представление

и о, (3)

««С™ Л®.) ' К '

Множество Д( называется сечением множества Д гиперплоскостью у!. Поскольку множество лежит в гиперплоскости у0 то его можно рассматривать как множество в пространстве, размерность которого на единицу меньше, чем исходное пространство. Рассмотрим функцию

^(/) = тт{/(*)|*еД}. (4)

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

Предложение 1.1. Предположим, что / (х) - непрерывная функция в области Д тогда - непрерывная функция на отрезке [г^,^] и имеет место равенство

тт{/(*)|* е д} = тш^*)11 е[^п**]} • (5)

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

Предложение 1.2. Если множество Д выпукло, а /- выпуклая функция на Д то функция ^ выпукла на отрезке [гтш, гтгх ].

Предложение 1.3. Если множество Д выпукло, а/- строго унимодальная функция на Д то функция Г строго унимодальна на отрезке [/1;11П,/П1ах]

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

область, ограниченная исходным симплексом & и п -1 -мерными симплексами и 5,1 • В результате ее выполнения строятся симплексы и , такие, что

сот^.Л'^ссот^Д1} и точка = , где

х°+1 - arg min {/(x) | x e S°+l }. x'+, =argmin{/(x)|^6 5(1+1}. Точка x,+1 рассматривается как аппроксимация точки минимума х . Имеет место следующий результат.

Теорема 1.1. Если f - непрерывная строго унимодальная функция на п-мер-ном симплексе S, х' = arg min / eS, xk - аппроксимация точки минимума, полу-

г h •

чрнная ппг.пр 1г-и итрппцт/ пт/глнипрп амщр nn^QptimuQ^ м при Ir—Urr,^ X . X ■ Предложенный алгоритм реализован в среде пакета MatLab. В качестве одной из тестовых задач приводится контрпример для известного метода Нелде-ра-Мида безусловной минимизации функции многих переменных. Известен класс строго выпуклых функций двух переменных, для которых симплексы, генерируемые алгоритмом Нелдера-Мида со специального вида начальным симплексом сходятся к точке, не являющейся точкой минимума. Показана сходимость предлагаемого алгоритма для функций этого класса к точке минимума.

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

" ' " р

минимизации негладких функций вида /(х,у)= Jj*~а*| + Zl-У~Ьк\ , 0</><1

для случая, когда числа к — \,...,т и все числа Ьк, к = \,...,п представляют собой выборки различного объема из равномерного распределения на отрезке [ОД].

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

В разделе 2 главы 1 рассматривается модификация алгоритма из раздела 1 для решения задачи безусловной минимизации вида

/0)->mm, xeR", (6)

где / :R"->R - ограниченная снизу непрерывная строго унимодальная функция.

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

f(x) -> min, х е S* > (7)

где Sl =co«v{i'0i,vl',...v'} и v0,v],...,vn -аффинно независимые точки в пространстве

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

X4"' ={argmm/(x)|xG5M} к точке х" -{argmin/(x)|х е S"}, k<=N, начиная

с некоторой начальной точки х° eS°, х" = {arg min /(x)]*eS''}, -произвольный

стартовый симплекс. Симплексы S1 строятся с использованием операций

отражения и сдвига таким образом, что хк~' emt причем на каждой итерации с номером к выполняется условие

/* = /(**)</(**"') = /*-,> к BN. (8)

Итерационный процесс останавливается, когда точка хк становится внутренней точкой симплекса Sk.

Построенная последовательность симплексов S°,S' ,...,S*,... удовлетворяет следующей теореме.

Теорема 1.2. Для любого начального симплекса S° и любой ограниченной снизу непрерывной строго унимодальной функции f на пространстве R" найдется такойномер к., что х' ={argmin/(х)|jcei'jeint5i-.

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

В качестве примера эффективности алгоритма для минимизации негладких функций рассмотрим следующий вариант функции Дснниса-Вуда:

/(*) = |max jx - с, f ,||л: - с2 f}, (9)

где с, = (l,-l), с2 = -с,. Эта функция является непрерывной и строго выпуклой, но ее градиент является разрывным всюду на линии х1=х2.

На рис. 1 а) показаны линии уровня функции, последовательность симплексов и точки минимума функции на каждом из них. Точка х5 (0,0) eintS5 и является решением задачи. На рис. 1 б) представлены значения функции на каждом цикле (симплексе) и на каждой итерации.

Во второй главе рассматривается задача математического программирования следующего вида:

f(x) -> min, (10)

при ограничениях

\Ах = Ъ

где /(х) - квазивогнутая функция, beR'",A- матрица размера m v-n-

Xmin = 0; Ymin = 0; finin = 1

1

ч.

• •

• •

0 20 40 60 80 100 120 140 160 180

Итерации

Рис. 1. Последовательность симплексов и сходимость к точке минимума (а) и значения функции /(*) = - с,||~,||х-с,||'] на каждой итерации (б)

Относительно матрицы А и вектора Ь системы (И) будем предполагать, что они содержат только неотрицательные элементы. В этом случае допустимое множество X задачи (если оно не пусто) ограничено и представляет собой выпуклый многогранник. Отметим также, что когда речь идёт о канонической форме записи совокупности линейных ограничений, т.е. о форме (11), то, не нарушая общности, можно считать, что гапк(А) = т<п.

Функция / (д:), определенная на выпуклом множестве X, называется квазивогнутой, если для каждого вещественного числа с множество {х: f{x) > с, х е X] выпукло.

Предлагаемый алгоритм решения задачи (10) - (11) основан на том факте, что еслидопустимоемножествовзадаче(10)-(11)не пусто, то точка глобального минимума функции F(x) на множестве (11) находится среди крайних точек этого множества. Крайняя точка, в которой значение целевой функции не превосходит ее значений в соседних точках, называется точкой локального минимума функции f(x). Основной проблемой при решении задачи (10) - (11) является то обстоятельство, что для квазивогнутой функции, заданной на выпуклом множестве, точка локального минимума не обязательно является и точкой глобального минимума функции на этом множестве.

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

1. Нахождение точки локального минимума z°, при этом /(z°) = m°;

2. Статистическое моделирование направлений поиска области в допустимом множестве с меньшим значением целевой функции (нахождение соседних с 2° вершин |z-';7 = l,...,/J); моделирование случайной точки гс, имеющей равномерное распределение на выпуклой оболочке conv{z',...,z'}; нахождение точки wc пересечения луча h = {z' = z° + t(zc - z°), t > 0} с выпуклым множеством X (wc = z'"" > 'щи = max{f:z' e X)), при этом /(#) = т<т°У,

3. Усечение исходного множества опорной гиперплоскостью у к поверхности текущего уровня целевой функции f(x) = m .

4. Применение шагов 1.-3. к усеченному множеству.

Корректность работы алгоритма основывается на следующем утверждении.

Теорема 2.2. Обозначим через zM крайнюю точку локального минимума,

найденную после завершения работы алгоритма, а через X' множество точек глобального минимума функции fix). Вероятность события j zM е X J стремится к единице при неограниченном возрастании М.

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

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

Рис. 2. Графическая иллюстрация метода

В третьей главе предлагается модификация алгоритма из главы 2 для решения транспортной задачи с квазивогнутой функцией стоимости следующего вида:

/(х)->тт, (12)

хе/Г*",

Я '

1Х=а.''=1>-/и>

X:

м

YJxlJ=bJ'j='í>•■■n>

х~ > 0, г = 1 ,..т, ] = 1,...п

(13)

где /(х) - произвольная квазивогнутая функция в пространстве Лтх° вещественных матриц размера т х п. Множество в пространстве вещественных матриц размера тхп, определяемое ограничениями (13) называется классическим транспортным многогранником порядка.

Непосредственное применение этого алгоритма для решения задач транспортного типа приводит к принципиальным трудностям, поскольку в результате такого усечения возникает задача, которая уже не является задачей транспортного типа (в системе ограничений появляется дополнительное ограничение, опре-

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

Алгоритм решения задачи (12) - (13) аналогичен алгоритму решения общей задачи квазивогнутого программирования (10) - (11) из главы 2 с предлагаемой модификацией. Основные шаги алгоритма для невырожденного случая следующие.

1. Нахождение крайней точки в транспортном многограннике (13), которая является точкой локального минимума для функции/. Начальный базисный (опорный) план транспортной Задачи может быть найден каким-либо известным методом.

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

3. Представление точки, найденной в п. 2 в виде выпуклой комбинации крайних

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

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

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

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

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

Рассматривается задача

/(*)-»• min, g(x)< О, (15)

где, /(х) - квазивогнутая функция на пространстве R", g(x) - выпуклая функция, определенная на R". '

Будем предполагать, что множество X = {х е R" \ g(x) < о] ограничено.

ПпТТУГТИМ ЧТГ» Or-y (—Р I'tf Р Н О— ПТ.ТШШПТ.ТР нилгултошп If nurtwoivm^

, , - j - , - - х. —----г " — -----J----

причем вершины множества Q лежат на границе множества X и пусть найдены числа

т = шт{/(лг)|л-еР}, (16)

M=mm{f{x)\xzQ}. (17)

Если обозначим через т" =min{/(x)| хе X} - искомое значение шобаль-ного минимума, то т<т <М, поэтому если для заданного числа е >0 выполняется неравенство

М-т<£ (18)

и хЕ = argmin{F(x) | х е g}, то план х£ можно считать f-решением задачи (15).

При таком подходе важно, с одной стороны, уметь находить ииДс другой стороны, в случае нарушения неравенства (18) нужно иметь процедуры расширения множества О и уменьшения множества Р, которые гарантировали бы выполнение неравенства (18) после достаточного числа итераций.

Предлагаемый алгоритм состоит из двух этапов.

На первом этапе решается задача построения симплекса Q. вписанного в множество X и построения оценки сверху М (17) для значения задачи (15).

Второй этап представляет собой итерационную процедуру, включающую следующие шаги:

1) Построение выпуклого множества Р, содержащего множество X.

2) Сужение исследуемой области.

3) Получение новой оценки снизу для значения задачи (15).

4) Получение новой оценки сверху для значения задачи (15).

5) Проверка условий (18) остановки алгоритма. В случае невыполнения условия - переход к следующему шагу.

6) модификация многогранника Q.

Наибольшую сложность представляет процедура построения множества Р, содержащего выпуклое множество X. Опишем этот шаг подробно.

Пусть в результате выполнения первого этапа имеется симплекс Q, вписанный в множество X и оценка сверху М для значения задачи (15).

Обозначим через Vl,...,V"+1 - вершины симплекса Q, у°,у\.,.,у" - грани симплекса Q. Пусть у0 - центр тяжести симплекса Q.

Для каждого t > 1 рассмотрим симплекс

= сот[У° + /(К' - У0),...,У°+((УЛ - Г0)]. (19)

Размерность симплекса Я, равна п -1. Заметим, что если > , то

сопу{К0,5„}ЗСО«У{Г°,5ч}. (20)

Определим

и = (21)

и пусть V е 5, г\Х (рис. 3).

Р1

Рис. 3. Построение многогранника Р, содержащего множество X Рассмотрим функцию

F(i) = min{g(x)|xe5,},rae <¿1. (22)

Для построения опорной гиперплоскости к множеству X необходимо ' вычислять значения функции F (г). Для решения этой задачи используется алгоритм, предложенный в разделе 1 главы 1.

Задача определения t^ сводится к задаче нахождения корня функции F(t), т.е. к задаче F(i) = 0. Как показано в предложении 1.2 главы 1, функция F (г) является выпуклой и для нахождения ее корня t^ может быть использован любой из известных алгоритмов нахождения нуля функции одной переменной. В результате реализации этой процедуры получаем точку

F = argmin{g(x)|x65w}, (23)

находим вершины

Обозначим множество вершин Р1,через р(у"*') ■

Проделав аналогичную процедуру для всех остальных граней ух.....у"

симплекса £), построим множества р(у'),..., р(у") ■ Положим

Тогда в качестве оценки снизу для значения задачи (15) можно взять величину (16).

Доказательство сходимости алгоритма основано на следующих фактах.

Если Рк, <2* - многогранники, построенные на к-й итерации алгоритма, Хк - часть множества X, оставшаяся на к итерации, то справедливы соотношения: Ок с!1 с:Р\ причем X' = А^т\п{[(х\х еХ}сХ1. Тогда расстояние Ха-усдорфа 0 при к -» оо. Поэтому для непрерывной функциии/, начи-

ная с некоторого к, будут выполняться неравенства (18).

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

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

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

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

(25)

Основные результаты

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

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

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

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

Основные результаты опубликованы в следующих работах:

1. Морозова Е.Ю. Рекурсивный алгоритм прямого поиска минимума функции нескольких переменных // Обозрение прикладной и промышленной математики. - 2006. - Т. 13. - Вып. 5. - С. 783-796.

2. Баушев А.Н., Морозова Е.Ю. Метод статистических испытаний в задаче квазивогнутого программирования // Обозрение прикп. и промышл. матем. — 2004. -Т. 11.-Вып. 1.-С. 34-40.

3. Морозова Е.Ю. Об алгоритме безусловной минимизации негладкой функции нескольких переменных // Обозрение прикладной и промышленной математики. - 2006. - Т. 13. - Вып. 3. - С. 524-525.

4. Баушев А.Н., Морозова Е.Ю. Об алгоритме бисекции для нахождения минимума выпуклой функции на симплексе // Обозрение прикладной и промышленной математики. - 2005. - Т. 12. - Вып. 3. - С. 699-700.

5. Баушев А.Н., Морозова Е.Ю. О задаче минимизации квазивогнутой функции при выпуклых ограничениях. // Обозрение прикл. и промышл. матем. - 2005.-Т. 12.-Вып. 1.-С. 109-110.

6. Баушев А.Н., Морозова Е Ю. Об алгоритме поиска глобального мини-

мума квазивогнутой функции на транспортном многограннике. // Обозрение прикл. и промышл. матем.- 2005. - Т. 12.-Вып. 1.-С. 110.

7. Морозова Е.Ю. Об алгоритме решения транспортной задачи с квазивогнутой функцией стоимости // Известия ПГУПС. - 2005. - Вып. 1. - С. 194-199.

8. Баушев А.Н., Морозова Е.Ю., Осьминин А.Т. О математической модели минимизации эксплуатационных затрат при организации вагонопотоков // Вестник ПГУПС. - 2004. - Вып. 2. - С. 39-43.

9. Морозова Е.Ю. Об определении диаметра конечного множества точек в евклидовом пространстве // Известия ПГУПС. - 2004. - Вып. 1. - С. 126-130.

10. Баушев А.Н., Морозова Е.Ю. О транспортной задаче с квазивогнутой функцией стоимости//Обозрение прикл. и промышл. матем. - 2004. - Т. 11. -Вып. 1.-С. 96.

11. Баушев А.Н., Елисеев С.Ю., Морозова Е.Ю., Осьминин А.Т., Рящиков A.C. О задаче математического программирования, возникающей в проблеме минимизации эксплутационных затрат при организации вагонопотоков // Аннотации докладов восьмой международной научно-практической конференции «ИНФОТРАНС - 2003». - СПб., 2003. - С. 46.

12. Баушев А.Н., Елисеев С.Ю., Морозова Е.Ю., Осьминин А.Т., Рящиков A.C. О задаче квазивогнутого программирования и ее применении к проблеме оптимизации железнодорожных перевозок // Обозрение прикладной и промышленной математики. - 2003. - Т. 10. - Вып. 3. - С. 603-604.

Подписано к печати 31.01.2007. Формат 60x84 1/16. Бум. офсетная Уел печ л. 1,25 Тираж 100 экз Заказ 7.

Санкт-Петербургский государственный архитектурно-строительный университет 190005, Санкт-Петербург, 2-я Красноармейская, 4

Отпечатано на ризографе. 190005, Санкт-Петербург, 2-я Красноармейская, 5.

Введение

Основные обозначения и определения.

ГЛАВА 1. Минимизация негладкой функции нескольких переменных

1.1. Алгоритм бисекции для нахождения минимума непрерывной строго унимодальной функции на симплексе

1.1.1. Постановка задачи.

1.1.2. Декомпозиция множеств и функций по сечениям.

1.1.3. Описание алгоритма.

1.1.4. Обоснование алгоритма.

1.1.5. Результаты численных экспериментов.

1.1.5.1. Примеры минимизации негладких функций

1.1.5.2. Контрпример для алгоритма Нелдера-Мида.

1.1.5.3. Пример минимизации функции Денниса-Вуда

1.2. Алгоритм безусловной минимизации непрерывной строго унимодальной функции.

1.2.1. Постановка задачи и описание алгоритма.

1.2.2. Примеры работы алгоритма.

1.2.2.1. Контрпример для алгоритма Нелдера-Мида.

1.2.2.2. Пример минимизации негладкой функции.

1.2.2.3. Пример минимизации функции Денниса-Вуда

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

2.1. Общие свойства задач квазивогнутого программирования

2.2. Постановка задачи и основные утверждения.

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

2.4. Описание основного алгоритма и его обоснование.

2.5. Вычислительные эксперименты. Примеры.

2.5.1. Пример минимизации вогнутой функции.

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

2.5.3. Пример минимизации квазивогнутой функции.

2.5.4. Определение диаметра выпуклого многогранного множества.

ГЛАВА 3. Методы решения задачи транспортного типа с квазивогнутой функцией стоимости

3.1. Свойства транспортного многогранника.

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

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

3.2.2. Постановка задачи и описание алгоритма.

3.2.3. Решение задачи при вырожденном опорном плане.

3.2.4. Тестовая задача нахождения диаметра многогранника бистохастических матриц.

3.3. Детерминированный метод поиска глобального минимума квазивогнутой функции на транспортном многограннике.

ГЛАВА 4. Алгоритм глобальной минимизации квазивогнутой функции на выпуклом множестве

4.1. Общие замечания.

4.2. Постановка задачи и краткое описание структуры алгоритма

4.3. Описание предварительного этапа.

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

4.5. Пошаговое описание алгоритма.

4.6. Результаты вычислительных экспериментов.

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

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

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

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

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

->min, xeDczR", (1) где /(х) - вещественнозначная вогнутая функция и D - выпуклое компактное множество, R" - n-мерное евклидово пространство.

Разнообразные важные практические приложения в экономике, промышленности и других областях приводят к необходимости отыскания глобального минимума вогнутой функции на замкнутом выпуклом множестве. Так, например, к формулировке задач такого типа приводят задачи с эффектом масштаба (economies of scale) [59], [90], [91] и задачи фиксированных расходов (fixed charge problems) [36], [76]. В связи с задачами минимизации эксплутационных расходов в зависимости от объёма грузовых железнодорожных перевозок при организации вагонопотоков также возникает необходимость в решении задачи вогнутого программирования [113], [137]. Кроме того, несколько важных задач оптимизации могут быть сформулированы как задачи вогнутой минимизации. Известно [86], что задача целочисленного программирования ноль-единица эквивалентна задаче минимизации квадратичной вогнутой функции при линейных ограничениях. Задача о назначениях с квадратичной целевой функцией может быть сформулирована как задача (1) [64], [11]. Фриз [30] привел 3-мерную задачу о назначениях к задаче билинейного программирования и затем к специальной задаче вогнутого программирования. В общем случае, задачи билинейного программирования эквивалентны задачам вогнутой минимизации [61]. Другая важная задача, линейная задача о дополнительности может быть приведена к вогнутой задаче [69], [115], [132], линейные минимаксные задачи со связанными переменными и линейные многошаговые биматричные игры также приводимы к задаче (1) [26], [57]. Поскольку рассмотренные выше примеры охватывают широкий диапазон случаев, задача глобальной вогнутой минимизации (1) представляет, очевидно, значительный интерес.

С точки зрения вычислительной сложности задача (1) остается NP-сложной задачей даже для таких частных случаев как минимизация квадратичной вогнутой функции на гиперкубе (см. например [70], [31], [37]), в отличие от задачи минимизации выпуклой (квадратичной) функции, которая может быть решена алгоритмами в полиномиально ограниченное время [19], [62].

Все известные методы глобальной оптимизации можно разделить на две категории: детерминированные и стохастические. Детерминированные методы получают глобальное решение посредством исчерпывающего поиска на всем допустимом множестве. Большинство стохастических методов оценивают значение функции цели в случайных точках допустимого множества с последующей обработкой выборки. Как следствие, стохастические методы не гарантируют успех. Описание методов стохастической глобальной оптимизации можно найти в [4], [22], [88].

Самые важные детерминированные подходы вогнутого программирования используют методы перечисления, методы отсечения, симплициальные, прямоугольные и конические методы ветвей и границ, решение аппроксимационных подзадач, методы билинейного программирования или различных комбинаций этих методов. Также специальные методы были предложены для задач, где целевая функция имеет специальную структуру (квадратичная, сепарабельная, факторизуемая и т.д.) [2], [3], [59] или допустимое множество имеет специальную структуру (единичный гиперкуб, сетевые ограничения [1], [34], [35], [48], квадратичные ограничения [1] - [3] и т.д.). Обзоры детерминированных методов можно найти в [15], [33], [25], [29], [45], [56], [80], [81], [87], [105], [120], [130].

Важным свойством задачи (1) является тот факт, что глобальный оптимум, если он существует, достигается в какой-либо крайней точке допустимой области [131]. Поэтому в том случае, когда рассматриваемое выпуклое множество ограничений имеет конечное число крайних точек, т.е. является полиэдральным множеством, задачу можно в принципе решить перебором крайних точек. Однако этот подход оказывается неприемлимым для задач большой размерности. Методы полного перебора крайних точек представлены в [24], [68]. Обзоры и сравнение методов перечисления представлены в [23], [71]. Аспекты эффективности вычислений при использовании алгоритмов упорядочивания крайний точек обсуждались в [17].

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

Зварт в [111] показал расходимость конусного алгоритма, описанного Туем. В этой же статье Зварт привел контрпример для метода Риттера [89], в котором для усечения допустимого множества использовалась последовательность отсекающих плоскостей. Зварт привел пример, в котором потребовалась бесконечная последовательность отсекающих плоскостей.

В [8] и [110] были предложены модификации метода Туя. Алгоритм из [110] является конечным и сходится быстро для задач, имеющих небольшое число локальных минимумов или когда глобальный оптимум существенно отличается от других оптимумов. В [58] приведено доказательство алгоритма типа Туя для общей задачи вогнутой минимизации. В [32] Гловер предложил новый класс отсечений (выпуклые отсечения), обобщив класс осекающих плоскостей Туя.

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

В 1969 году Фолк и Соланд в [27] представили первый алгоритм ветвей и границ для решения задачи глобальной минимизации невыпуклой сепарабельной функции на выпуклом ограниченном множестве. В алгоритме целевая функция заменялась на ее выпуклую огибающую и решалась последовательность подзадач, в каждой из которых целевая функция была линейной или выпуклой. Эти задачи соответствовали последовательным разбиениям допустимого множества, и определяли нижнюю и верхнюю границы для решения задачи. Этот алгоритм был расширен позднее Соландом [93] для задач с сепарабельными невыпуклыми ограничениями.

В [43] Хорст рассмотрел более общую задачу невыпуклого программирования. Отличие подхода, предложенного в [43] по сравнению с [27] состоит в использовании разбиений на компакты общего вида вместо прямоугольных разбиений и не требует использования выпуклых огибающих. Хорст показал, что каждая предельная точка последовательности точек, генерируемой алгоритмом, решает задачу. Хорст использовал идеи конического метода ветвей и границ. Различные модификации алгоритмов для решения этого класса можно найти в [41], [46], [47], [51]. Особый класс задач -минимизация при линейных ограничениях суммы вогнутой функции, определенной на пространстве размерности р и линейной функции, определенной на пространстве размерности q, где q намного больше, чем р рассмотрен в [49], [50].

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

МакКормик в [73] показал, что подход "выпуклых огибающих" может быть применен для факторизуемых функций. Детальное описание факторизуемых функций может быть найдено в [74].

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

Несмотря на существование достаточно большого числа разнообразных методов глобальной минимизации вогнутых функций на выпуклых множествах, возможности применения этих методов для решения конкретных задач ограничены предположениями о принадлежности некоторым специальным классам как оптимизируемых функций, так и допустимых множеств [49], [80], [133]. В работе предлагаются новые методы решения задач вогнутого программирования, не накладывающие дополнительных ограничений на дифференцируемость целевой функции и позволяющие применять их для более общего класса функций - негладких и даже разрывных квазивогнутых функций. Один из предлагаемых в данной работе методов глобальной минимизации квазивогнутой функции на произвольном выпуклом множестве базируется на последовательном применении алгоритма нахождения минимума выпуклой функции на симплексе для вычисления оценок снизу и сверху оптимального значения задачи вогнутой минимизации. Описание этого алгоритма представлено в первой главе. Также представлена модификация этого алгоритма для случая минимизации строго унимодальной функции нескольких переменных в отсутствие ограничении. В настоящее время разработано множество численных методов для решения задачи нахождения минимума функции / Традиционные методы на основе анализа производных различного порядка являются достаточно быстрыми и точными, однако, их применение часто оказывается неэффективным или вовсе невозможным в случае решения задач оптимизации для негладких функций. Предложенный в первой главе алгоритм относится к классу методов прямого поиска, основной особенностью которых является то, что они не требуют вычисления производной целевой функции. Направление минимизации полностью определяется последовательными вычислениями значений функции, что позволяет использовать эти методы для негладких функций. Такие ситуации часто встречаются в практически важных задачах оптимизации, что предопределяет широкое применение этих методов при решении важных прикладных оптимизационных задач. Методы прямого поиска наиболее известны как методы безусловной оптимизации, однако, существуют модификации этих методов и для задач с ограничениями [65], [66]. Ниже приведен краткий обзор методов прямого поиска минимума функции в отсутствие ограничений.

В настоящее время одним из наиболее популярных методов прямого поиска минимума функции является метод Нелдера-Мида [79], являющийся развитием метода Спендли, Хекста и Химсворта [94]. Идея метода состоит в сравнении значений функции в {п +1) вершинах симплекса и перемещении симплекса в направлении оптимальной точки с помощью итерационной процедуры, использующей три основных операции: отражения, растяжения и сжатия. Теоретическое исследование этого метода в настоящее время далеко от завершения. Так, в [63] получен ряд результатов о сходимости, в частности, доказано, что оригинальный метод Нелдера-Мида сходится для строго выпуклых функций одной переменной, кроме того, доказано, что в случае двух переменных диаметр симплекса сходится к нулю. Однако, вопрос о сходимости алгоритма к единственной точке даже для строго выпуклых квадратичных функций двух переменных (например, для таких функций, как f(x,y) = x2 + уг) остается открытым. МакКиннон [72] сконструировал семейство функций в R2, для которого алгоритм Нелдера-Мида со специальным выбором начальной конфигурации симплекса сходится к точке, не являющейся точкой минимума, даже в случае, когда семейство параметризовано так, что функции являются строго выпуклыми и имеют непрерывные производные до третьего порядка. При этом происходит эффект внутреннего сжатия, когда симплексы, генерируемые алгоритмом Нелдера Мида стягиваются к прямой линии, ортогональной направлению наискорейшего спуска и не содержащей точки минимума (см. раздел 6.2). Подобного рода примеры представлены также в [96]. Тем не менее, метод Неледра-Мида продолжает активно использоваться на практике (реализация этого метода имеется в пакете Matlab, приложение Optimization Toolbox), что, в свою очередь, способствует появлению его многочисленных модификаций [14], [60], [78], [85], [99], [106].

Более ясной представляется ситуация с теоретическим обоснованием другого класса методов прямого поиска - методов поиска по шаблону, включающих такие классические алгоритмы прямого поиска, как алгоритмы координатного поиска [98], алгоритм эволюционного действия, предложенный Боксом [16], алгоритм поиска по образцу Хука и Дживса [40] и сравнительно недавно предложенные методы мультинаправленного поиска [20], [97]. Методы поиска по шаблону основаны на выборе некоего набора точек, называемых шаблоном, который расширяется или сжимается, в зависимости о того, имеет или нет какая-либо точка данного шаблона меньшее значение целевой функции, чем текущая точка. Поиск заканчивается после того, как будет достигнут минимальный размер рассматриваемого шаблона. Методы прямого поиска считались эвристическими и не имеющими строго математического анализа до появления в 1991 году работы Торзон [97], в которой методы мультинаправленного поиска рассматривались в контексте параллельных вычислений и сопровождались анализом сходимости, основанным на предположении о непрерывной дифференцируемости минимизируемой функции. Исследования последних 15 лет привели к появлению целого ряда публикаций, посвященных теоретическому исследованию класса методов поиска по шаблону [6], [20], [65], [66], [67], [98]. Основным результатом этих исследований является доказательство глобальной сходимости методов к стационарной точке в случае, когда целевая функция является гладкой. Остается открытой проблема эффективности этих методов при решении задач большой размерности. Реализации методов поиска по шаблону содержатся в последних версиях пакета MatLab (приложение Direct Search Toolbox). Известно, что для функций, которые являются негладкими, либо дифференцируемыми всюду, но не имеющими непрерывных производных, алгоритмы поиска по шаблону могут приводить к ошибочным результатам. В [97] проведено исследование причин возникновения таких ошибок, а также проведен анализ локальной сходимости методов, объясняющий причины возможной медленной асимптотической сходимости.

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

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

Задачи диссертационного исследования.

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

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

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

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

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

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

Основные положения, выносимые на защиту.

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

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

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

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

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

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

Научная новизна полученных результатов.

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

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

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

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

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

Апробация работы. Результаты диссертации докладывались на научных семинарах кафедры прикладной математики ПГУПС, на Третьем Всероссийском симпозиуме по прикладной и промышленной математике (Сочи, 2002), на Восьмой международной научно-практической конференции "ИНФОТРАНС - 2003" (СПб, 2003), на Четвертом (весенняя сессия -Петрозаводск, 2003), (осенняя сессия - Сочи, 2003), Шестом (весенняя сессия -СПб, 2005), (осенняя сессия - Сочи, 2005), и Седьмом (Кисловодск, 2006), Всероссийских симпозиумах по прикладной и промышленной математике.

Основные результаты опубликованы в следующих работах:

1. Морозова ЕЛО. Рекурсивный алгоритм прямого поиска минимума функции нескольких переменных // Обозрение прикладной и промышленной математики. - 2006. - Т. 13. - Вып. 5. - С. 783-796.

2. Баушев А.Н., Морозова ЕЛО. Метод статистических испытаний в задаче квазивогнутого программирования // Обозрение прикл. и промышл. матем. -2004.-Т. 11.-Вып. 1.-С. 34-40.

3. Морозова Е.Ю. Об алгоритме безусловной минимизации негладкой функции нескольких переменных // Обозрение прикладной и промышленной математики. - 2006. - Т. 13. - Вып. 3. - С. 524-525.

4. Баушев А.Н., Морозова Е.Ю. Об алгоритме бисекции для нахождения минимума выпуклой функции на симплексе // Обозрение прикладной и промышленной математики. - 2005. - Т. 12. - Вып. 3. - С. 699-700.

5. Баушев А.Н., Морозова Е.Ю. О задаче минимизации квазивогнутой функции при выпуклых ограничениях. // Обозрение прикл. и промышл. матем. - 2005.-Т. 12.-Вып. 1.-С. 109-110.

6. Баушев А.Н., Морозова Е.Ю. Об алгоритме поиска глобального минимума квазивогнутой функции на транспортном многограннике. // Обозрение прикл. и промышл. матем. - 2005. - Т. 12. - Вып. 1. - С. 110.

7. Морозова Е.Ю. Об алгоритме решения транспортной задачи с квазивогнутой функцией стоимости // Известия ПГУПС. - 2005. - Вып. 1. - С. 194-199.

8. Баушев А.Н., Морозова Е.Ю., Осьминин А.Т. О математической модели минимизации эксплуатационных затрат при организации вагонопотоков // Вестник ПГУПС. - 2004. - Вып. 2. - С. 39-43.

9. Морозова Е.Ю. Об определении диаметра конечного множества точек в евклидовом пространстве // Известия ПГУПС. - 2004. - Вып. 1. - С. 126-130.

Ю.Баушев А.Н., Морозова Е.Ю. О транспортной задаче с квазивогнутой функцией стоимости // Обозрение прикл. и промышл. матем. - 2004. - Т. 11.-Вып. 1.- С. 96.

11.Баушев А.Н., Елисеев С.Ю., Морозова Е.Ю., Осьминин А.Т., Рящиков А.С. О задаче математического программирования, возникающей в проблеме минимизации эксплутационных затрат при организации вагонопотоков //

Аннотации докладов восьмой международной научно-практической конференции "ИНФОТРАНС - 2003". - СПб., 2003. - С. 46.

12. Баушев А.Н., Елисеев С.Ю., Морозова Е.Ю., Осьминин А.Т., Рящиков А.С. О задаче квазивогнутого программирования и ее применении к проблеме оптимизации железнодорожных перевозок // Обозрение прикладной и промышленной математики. - 2003. - Т. 10. - Вып. 3. - С. 603-604.

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

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Работа изложена на 135 страницах машинописного текста, содержит 32 рисунка, 3 таблицы и 137 библиографических ссылок на литературу.

Результаты работы алгоритма по итерациям Таблица 4.1. шага, к пк Г- X Новые верш, множества и / Pk э X Вершины множества M к m Af*

0 F1 (4.1865,1.8271) F2 (4.9202, 0.8899) F5 (3.6779,0.1779) f3.6779' [o.l779, - - - -Inf -1.6653

1 F4 (4.6000,1.9596) f5.0000") (4.1217, 2.5705) (5.488 1, 0.8252)

Г5 (3.0888,0.5893) "Г6 (5.0000,0.0000) [o.oooo, •(4.0288, 3.6378) «(2.4522,-1.4751) «(6.2819, 0.7347) «(2.4714,-1.4492) 3 2 -3.1449 -2.5000

3.5689, 0.0309)

2 ♦F7 (4.3330,0.0447) F8 (3.0404,0.4000) К9 (3.5036,1.3270) ♦F10 (4.9800,0.4466) f5.0000' [o.oooo, ( 2.8697, 0.5 192) (4.1 65 1 , 2.0728) ( 2.7545, 0.4823) «(3.6476, 0.1 370) «(5.0384,-0.0503) ♦(4.9405,0.8876) «(5.0227,-0.0297) 4 2 -2.5697 -2.5000

5.0090,-0.0 1 1 8)

3 *F" (4.6657 0.0112) F'2 (4.0033 0.1004) ♦Г" (4.9950 0.2233) Vй (4.9550 0.6690) f5.0000" [o.oooo, «( 4.3339, 0.0334 ) (3.6706, 0.1 680) ( 4.3339, 0.033 1) «(5.0053,-0.0070) «(4.9852, 0.4429) (4.9253,0.8893) (4.9856,0.4426) 4 2 -2.5163 -2.5000

4.3332,0.04 19)

4 V" (4.4990,0.0252) *У16 (4.8328,0.0028) V" (4.9888,0.3350) *F'"(4.9988,0.1113) (5.00004) [o.oooo J (4.6670,0.0083) «(5.0022,-0.0029 ) «(4.6669,0.0083) (4.98 1 3, 0.4457 ) (4.9964,0.2220) «(5.00 1 3,-0.00 1 7 ) «("4.9963.0.2220"» 4 2 -2.5040 -2.5000

4.6660, 0.0 1 05)

5 *F" (4.9166,0.0007) *F2° (4.9997,0.0551) Г21 (4.9972,0.1671) V" (4.7490,0.0063) '5.0000' ,0.0000J (4.8332, 0.002 1) «(5.0005,-0.0007) «(4.8332, 0.002 1 ) (4.9953 , 0.2230) «(4.999 1 , 0.1 1 09 ) «(5.0003,-0.0004) (4.9991,0.1 1 09) 4 2 -2.5010 -2.5000

4.8329, 0.0026)

6 *F23 (4.9579,0.0002) *F24 (4.9999,0.0263) F"(4.8754,0.0015) F26 (4.9993.0.0832) '5.0000") ,0.0000J (4.9 1 67, 0 .0005) «(5.0001,-0.0002) «(4.9 1 67, 0.0 005 ) (4.99 88, 0.1 1 1 2) « (4.9998, 0.0550) • (5.000 I ,-0.000 l) (4.9998,0.0550) 4 2 -2.5002 -2.5000

4.9 1 66, 0.0007 )

7 V" (4.9358,0.0004) F2'(4.9797,0.0000) F29 (4.9998,0.0409) F3° (5.0000,0.0104) '5.0000") ,0.0000J (4.95 79, 0.0 00 1) (5.0000,-0.000 0 ) (4.95 79, 0.000 1) (4.9997, 0.05 5 0 ) (5.0000, 0.0 263 ) (5.0000,-0.00 00 ) (5.000 0,0.026 3 ) 0 0 -2.5000 -2.5000

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

В качестве тестовой рассмотрим задачу из [80]. f(x,y) = -(х- 20)2 - {у - ю)2 -> min, (4.37) при ограничениях:

X:

2у-х-20<0, х2 +(<у-10)-500<0, -х<0,

-у< о.

4.38)

Для нахождения оптимального решения х* = (0,0), /(х')=-500 и выполнения критерия остановки Мк -тк <0.0001 алгоритму потребовалось 4 итерации. Рис. 4.9 иллюстрирует процесс разбиения симплексов на всех итерациях и сходимость алгоритма к точке минимума. График, представленный на рис. 4.10 показывает поведение оценок снизу и сверху для значения задачи в течение четырех итераций. Максимальное число симплексов, остающихся после отбраковки, равно 2.

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

Рассмотрим задачу из [104], когда оптимальное решение достигается в точке, лежащей на границе только одного из ограничений, определяющих допустимое множество: х„х2) = -129х,2 + 242х,х2 - 129х22 + 1258х, - 1242х2 min, (4.39)

Рис. 4.9. Сходимость алгоритма к точке минимума х* (0,0)

-500 юоо

1500

2000

2500

3000

3500 м шшмшвтш»,

1*. к тК

VW*

Итерации, к

Рис. 4.10. Поведение оценок снизу и сверху для значения задачи в течение четырех итераций при ограничениях:

X:

-х1-Х2-2< О,

-4хх+Х2 - 8<0,

16xj2 ~Ъ2хх +25*2 -384 <0.

4.40)

Для нахождения оптимального решения х* =(-1,2),/(х;*) = -4871 и для выполнения критерия остановки Мк -тк <0.0001 алгоритму потребовалось 11 итераций. Рис. 4.11 иллюстрирует процесс разбиения симплексов на всех итерациях и сходимость алгоритма к точке минимума. График, представленный на рис. 4.12 показывает поведение оценок снизу и сверху для значения задачи в течение всех итераций. Максимальное число симплексов, остающихся после отбраковки, равно 3. 3

-6 -4 -2 0 2 4 6 8 10 12

Xl ./ ч

Рис. 4.11. Сходимость алгоритма к точке минимума х (-1,2) х ю

-0.5

-1

-1.5

-2

-2.5

X Мк в,»« х-. т iii1 lIU

8 9 10 11

Итерации, к

Рис. 4.12. Поведение оценок снизу и сверху для значения задачи в течение всех итеоапий

Заключение.

Сформулируем основные результаты, полученные в работе.

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

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

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

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

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

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

Основное содержание диссертации изложено в работах [112], [113], [127], [128], [129].

1. Al-Khayyal F. A. Global optimization of concave functions subject to quadratic constraints: An application in nonlinear bilevel programming // Annals of Operations Research. 1992. - Vol. 34. - P. 125-147.

2. Al-Khayyal F. A. and Falk J. E. Jointly constrained biconvex programming // Mathematics of Operations Research. 1983. - Vol. 8. - № 2. May. - P. 273-286.

3. Al-Khayyal F. A. and Larsen C. Global optimization of a quadratic function subject to a bounded mixed integer constraint set // Annals of Operations Research. 1990.-Vol. 25.-P. 169-180.

4. Ali M., Torn A., Viitanen S. Stochastic Global Optimization: Problem, Classes and Solution Techniques // J. of Global Optimization. 1999. - Vol. 14. p. 437-447.

5. Arrow, Kenneth J., and Alian C. Enthoven. Quasi-Concave Programming // Econometrica. 1961. - Vol. 29. - P. 779-800.

6. Aude C. Dennis J.E. Analysis of Generalized Pattern Searches // SIAM J. Optim. 2003. - Vol. 13. - №3. - P. 889-903.

7. Avriel M. Nonlinear Programming: Analysis and Methods. Prentice-Hall Inc., Englewood Cliffs. NJ, 1976.

8. Bali S. Minimization of a concave function on a bounded convex polyhedron. Ph. D. dissertation, Univ. California. Los Angeles, 1973.

9. Ban Vu Thien. A finite Algorithm for Globally Minimizing a Concave Function under Linear Constraints and its Applications. Preprint Series. №4. Hannoy: Institute of Mathematics, 1983.

10. Barber C.B., Dobkin D.P., Huhdanpaa H.T. The Quickhull Algorithm for Convex Hulls // ACM Transactions on Mathematical Software. 1996. -Vol. 22. - №. 4, Dec. - P. 469-483.

11. Bazara M. S. and Sherali H. D. On the use of exact and heuristic culling plane methods for the quadratic assignment problem // J. Oper. Res. Soc. -1982.-Vol. 15.-P. 991-1003.

12. Benson H. P. On the convergence of two branch and bound algorithms for nonconvex programming problems // JOTA. 1982. - Vol. 36. - P. 129-134.

13. Benson H. P. On the convergence of two branch-and-bound algorithms for nonconvex programming problems // Journal of Optimization Theory and Applications. 36(1), January 1982. Technical Note.

14. Bertsekas D.P. Nonlinear programming, 2th edition. Athena Scientific. Belmont, 1999.

15. Bomze I.M., Csendes Т., Horst, R., Pardalos P.M., eds. Developments in Global Optimization. London, Kluwer, 1997.

16. Box G. E. P. Evolutionary operation: A method for increasing industrial productivity //Appl. Statist. 1957. - Vol. 6. - P. 81-101.

17. Burdet С A. Generating all the faces of a polyhedron, SIAM J. Appl. Math., 26, 1974, pp.72-89.

18. Calvete, H. I. and Gale, C. On the quasiconcave bilevel programming problem // Journal of Optimization Theory and Applications. 1998. - Vol. 98,- P. 613-622.

19. Chung S. J. and Murty K. G. Polynomially bounded ellipsoid algorithms for convex quadratic programming, in Nonlinear Programming 4, 0. L. Mangasarian, R. R. Meyer and S. M. Robinson, eds. Academic Press. New York, 1981.-P. 439-485.

20. Dennis J.E. and Torczon V.J. Direct search methods on parallel machines // SIAM J. Optim. 1991. - Vol. 1. - P. 448-474.

21. Dennis J. E., Woods Jr. and D. J. Optimization on microcomputers: The Nelder-Mead simplex algorithm, in New Computing Environments:

22. Microcomputers in Large-Scale Computing, A. Wouk, ed., SIAM. -Philadelphia, 1987. P. 116-122.

23. Dixon L.C.W., Szego G.P. (eds). Towards Global Optimization 2. North-Holland, 1978.

24. Dyer M. E. The complexity of vertex enumeration methods // Math. Oper. Res. 1983. - Vol. 8. - P. 381-402.

25. Dyer M. E. and Proll L. G. An algorithm for determining all extreme points of a convex polytope // Math Progr. 1977. - 12. - P. 81.

26. Evtushenko Yu. G., Potapov M. A., Korotkich V. V. Recent Advances in Global Optimization. Prinston, Princeton University Press, 1992. - P. 274297.

27. Falk I. E. A linear max-min problem // Math. Progr. 1973. - Vol. 5. - P. 169-188.

28. Falk I. E. and Soland R. M. An algorithm for separable nonconvex programming problems // Management Sci. 1969. - Vol. 15. - P. 550-569.

29. Floudas C. A. and Pardalos P. M. A Collection of Test Problems for Constrained Global Optimization Algorithms // Lecture Notes in Computer Science. Springer-Verlag, 1990. Vol. 455.

30. Floudas C.A., Pardalos P.M. (eds). Recent Advances in Global Optimization. Prinston, USA, Printon University Press, 1992.

31. Frieze A. M. A bilinear programrningjormulation of the 1-dimensional assignment problem // Math. Progr. 1974. - Vol. 7. - P. 376-379.

32. Garey M. R., Johnson D. S. and Stockmeyer L. Some simplified NP-complete problems // Theoret. Сотр. Sci. 1976. - Vol. 1. - P. 237-268.

33. Glover F. Convexity cuts and cut search // Oper. Res. 1973. - Vol. 21. - P. 123-134.

34. Gray P., Hart W.E., Painton L., Phillips C., Trahan M., Wagner J. A Survey of Global Optimization Methods. Sandia National Laboratories, 1998.

35. Guisewite G.M., Pardalos P.M. Algorithms for the single-source uncapacitated minimum concave-cost network flow problem // Journal of Global Optim. 1991. - Vol.3. - P. 245-266.

36. Guisewite G.M., Pardalos P.M. A polynomial time solvable concave network flow problem // Network. 1993. - Vol. 23. - P. 143-147.

37. Hadley G. Nonlinear and Dynamic Programming. Addison-Wesley, Reading, MA, 1964.

38. Hammer P L. (TvANESCU). Some network flow problems solved with pseudo-boolean programming // Oper. Res. 1965. - Vol. 13. - P. 388-399.

39. Hoffman K. L. A method for globally minimizing concave functions over convex sets // Mathematical Programming. 1981. - Vol. 20. - P. 22-32.

40. Hoffman K. L. A successive underestimating method for concave minimization problems: Ph.D. thesis. Giorge Washington Univ., Washington, DC, 1975.

41. Hooke R. and Jeeves T. A. "Direct search" solution of numerical and statistical problems // J. Assoc. Comput. Mach. 1961. - Vol. 8. - P. 212229.

42. Horst R. A general class of branch-and-bound methods in global optimization with some new approaches for concave minimization // Journal of Optimization Theory and Applications. 1986. - Vol. 51. - № 2. November. -P. 271-291.

43. Horst R. A note on functions, whose local minimum are global // JOTA. -1982.-Vol. 36.-P. 457-463.

44. Horst R. An algorithm for nonconvex programming problems // Math. Progr. 1976.-Vol. 10.-P. 312-321.

45. Horst R, Muu L.D., Nast M. Branch-and-Bound Decomposition Approach for Solving Quasiconvex-Concave Programs // Journal of optimization theory and applications. 1994. - Vol. 82. - № 2. - P. 267-293.

46. Horst R., and Pardalos P.M., Editors. Handbook of Global Optimization, Klewer Academic Publishers, Dordrecht, Netherlands, 1995.

47. Horst R., Phong T.Q., Thoai N.V. and De Vries J. On solving a d.c. programming problem by a sequence of linear programs // Journal of Global Optim.-1991.-Vol.1.-P. 183-204.

48. Horst R. and Thoai N. V. A decomposition approach for the global minimization of biconcave functions over polytopes // Journal of Optimization Theory and Applications. 1996. - Vol. 88. - P. 561-583.

49. Horst R. and Thoai N. V. An integer concave minimization approach for the minimum concave cost capacitated flow problem on networks. // OR Spektrum. 1998. - Vol. 20. - P. 47-53.

50. Horst R. and Thoai N. V. Conical algorithm for the global minimization of linearly constrained decomposable concave minimization problems // Journal of Optimization Theory and Applications. 1992. - Vol. 74. - № 3. September. - P. 469-486.

51. Horst R. and Thoai N. V. Constraint decomposition algorithms in global optimization // Journal of Global Optimization. 1994. - Vol. 5. - P. 333— 348.

52. Horst R., Thoai N. V, and Benson H. P. Concave minimization via conical partitions and polyhedral outer approximation // Mathematical Programming. 1991.-Vol. 50.-P. 259-274.

53. Horst R. and Thoai N. V, and J. de Vries. A new simplicial cover technique in constrained global optimization // Journal of Global Optimization. 1992. - Vol. 2.-P. 1-19.

54. Horst R. and Thoai N. V, and J. de Vries. On geometry and convergence of a class of simplicial covers // Optimization. 1992. - Vol. 25. - P. 53-64.

55. Horst R., Tuy H. Global Optimization, Deterministic Approaches, 3rd Edn. -Springer, Berlin Heidelberg New York, Verlag, 1996.

56. Horst R., Tuy H. On the convergence of global methods in multiextremal optimization // Journal of Optimization Theory and Applications. 1987. -Vol. 54. - № 2. August. - P. 253- 271.

57. Huyer W., A. Neumaier. Global Optimization by Multilevel Coordinate Search // J. of Global Optimization. 1999. - Vol. 14. - P. 331-355.

58. Ivanilov Y. I. and Mukhamediev В. M. An algorithm for solving the linear max-min problem // Izv Akad, Nauk SSSR, Tekhn. Kibernitika. 1976. - № 6.-P. 3-10.

59. Jacobsen S. E. Convergence of a Tuy-type algorithm for concave minimization subject to linear inequality constraints // Appl. Math. Opt. -1982.-Vol. 7.-P. 1-9.

60. Kalantari B. and Rosen J. B. Algoritnm for large-scale global minimization of linearly constrained concave quadratic functions // Math, of Oper. Research. 1987. - Vol. 12. - P. 544-561.

61. Kelly C.T. Iterative Methods for Optimization. SIAM, Philadelphia, PA, 1999.

62. Konno H. A cutting plane algorithm for solving bilinear programs // Math. Progr. 1976. - Vol. 11. - P. 14-27.

63. Kozlov M. K., Tarasov S. P. and Khachian L. G. Polynomial solvability of convex quadratic programming // Soviet Math. Dokl. 1979. - Vol. 20. - P. 1108-1111.

64. Lagarias J.C., Reeds J.A., Wright M.H. and Wright P.E. Convergence properties of the Nelder Mead simplex algorithm in low dimensions // SIAM

65. J. Optim. 1998. - Vol. 9. - P. 112-147.

66. Lawler E. L. The quadratic assignment problem // Manag. Sci. 1963. - Vol. 9.-P. 586-599.

67. Lewis, Robert Michael and Virginia Torczon. Pattern Search Algorithms for Bound Constrained Minimization // SIAM J. Optim. 1999. - Vol. 9. - № 4. -P. 1082-1099.

68. Lewis, Robert Michael and Virginia Torczon. Pattern Search Methods for Linearly Constrained Minimization // SIAM J. Optim. 2000. - Vol. 10, № 3. -P. 917-941.

69. Lewis R. M., Torczon V., and Trosset M. W. Direct search methods: Then and now // J. Comput. Appl. Math. 2000. - Vol. 124. - P. 191-207.

70. Manas M. and Nedoma J. Finding a vertices of a convex polyhedral set // Numer. Math. 1974. - Vol. 9. - P. 35-39.

71. Mangasarian O. L. Characterization of linear complementarity problems as linear programs // Math. Progr. Study. 1978. - Vol. 7. - P. 74-87.

72. Mangasarian O. L. and Shiau Т. H. A variable complexity norm maximization problem // Computer Science Dept., Univ. Wisconsin Tech. Report 568, Univ. Wisconsin, Madison, 1984.

73. Matheissand Т. H., Rubin D. S. A survey and comparison of methods for finding all vertices of convex polyhedral sets // Math. Oper. Res. 1980. -Vol. 5.-P. 167-185.

74. McKinnon K.I.M. Convergence of the Nelder-Mead simplex method to a non-stationary point // SIAM J. Optim. 1998. - Vol. 9. - P. 148-158.

75. McCormick G. P. Computability of global solutions to factorable nonconvex programs: Part I — Convex underestimating problems // Mathematical Programming. 1976. - Vol. 10. - P. 147-175.

76. McCormick G. P. Nonlinear Programming, Theory, Algorithms, and Applications. John Wiley & Sons, 1983.

77. Migdalas A., Pardalos P.M. and Storoy S. Parallel Computing in Optimization. Kluwer Academic Publishers, 1997.

78. Murty K. Solving the fixed charge problem by ranking the extreme points // Oper. Res. 1969. - Vol. 16. - P. 268-279.

79. Muu L. D. and Oettli W. Combined branch-and-bound and cutting plane methods for solving a class of nonlinear programming problems // Journal of Global Optimization. 1993. -3. - P. 377-391.

80. Nazareth L. and Tseng P. Gilding the lily: A variant of the Nelder-Mead algorithm based on golden-section search // Comput. Optim. Appl. 2002. -Vol. 22. - P. 133-144.

81. Nelder J.A. and Mead R. A simplex method for function minimization // Computer Journal. 1965. - 7. - P. 308-313.

82. Pardalos P.M., Rosen J.B. Constrained Global Optimization: Algorithms and Applications // Berlin, Springer Verlag, Lecture Notes in Computer Science Vol. 268, 1987.

83. Pinter J.D. Global Optimization in Action. London, Kluwer, 1996.

84. A. T. Phillips and J. B. Rosen. A parallel algorithm for constrained concave quadratic global minimization. Journal of Optimization Theory and Applications. 1988. - Vol. 42. - P. 421^148.

85. A. T. Phillips and J. B. Rosen. Guaranteed s -approximate solution for indefinite quadratic global minimization // Naval Research Logistics. 1990. -Vol. 37.-P. 499-514.

86. Powell M. J. D. An efficient method for finding the minimum of a function of several variables without calculating derivatives // Comput. J. 1964. - Vol. 7.-P. 155-162.

87. Price C. J., Coope I. D. and Byatt D. A convergent variant of the Nelder-Mead algorithm // J. Optim. Theory Appl. 2002. - Vol. 113. - P. 5-19.

88. Raghavachari M. On connections between zero-one integer programming and concave programming under linear constraints // Oper. Res. 1969. -Vol. 17.-P. 680-684.

89. Ratchek H., Rokne J. New Computer Methods for Global Optimization. -Chichester, Ellis Horwood, 1988.

90. Rinnoy Kan A.H.G., Timmer G.T. Stochastic Global Optimization Methods // Mathematical programming. 1987. - Vol. 39. - P. 27-78.

91. Ritter K. A method for solving maximum problems with a nonconcave quadratic objective function // Z. Wahrsch. Verw. Geb. 1966. - Vol. 4. - P. 340-351.

92. Rosen J.B. Parametric Global minimization for large-scale problems // Technical Report 83-11, Computer science department. University of Minnesota, 1983.

93. Rosen J.B. and Pardalos P.M. Global Minimization of large-scale constrained concave quadratic problems by separable programming // Math. Programming. 1986. - Vol. 34. - P. 163-174.

94. Rosenbrock H. H. An automatic method for finding the greatest or least value of a function // Comput. J. 1960. - Vol. 3. - P. 175-184.

95. Soland R.M. An algorithm for separable nunconvex programming problems II: nonconvex constraints // Manag. Sci.- 1971. Vol. 17. - P. 759-773.

96. Spendley W., Hext G.R. and Himsworth F.R. Sequential applications of simplex designs in optimization and evolutionary operation // Technometrics. 1962.-Vol. 4.-P. 441-461.

97. Thoai N.V. and Tuy H. Convergent algorithms for minimizing a concave function // Math. Oper. Res. 1980. - Vol. 5. - P. 556-566.

98. Torczon V. Multi-Directional Search: A Direct Search Algorithm for Parallel Machines: Ph.D. thesis, Department of Mathematical Sciences, Rice

99. University, Houston, TX, 1989; available as Tech. Rep. 90-07, Department of Computational and Applied Mathematics, Rice University, Houston, TX,1990.

100. Torczon V. On the convergence of the multidirectional search algorithm // SIAMJ. Optim.- 1991. -Vol. l.P. 123-145.

101. Torczon V. On the convergence of Pattern Search Algorithms // SIAM J. Optim. 1997. - Vol. 7. - № 1. - P. 1-25.

102. Tseng P. Fortified-descend simplicial search method: a general approach // SIAMJ. Optim.-2000.-Vol. 10. P. 269-288.

103. Tuy H. Concave minimization under linear constraints with special structure // Optimization. 1985. - Vol. 16.3 - P. 335-352.

104. Tuy H. Effect of the subdivision strategy on convergence and efficiency of some global optimization algorithms // Journal of Global Optimization.1991.-Vol. 1. № l.-P. 23-36.

105. Tuy H. Global minimization of the difference of two convex functions // Mathematical Programming Study. 1987. - Vol. 30. - P. 150-183.

106. Tuy H., Migdalas A., and V'arbrand P. A quasiconcave minimization method for solving linear two-level programs // Journal of Global Optimization. -1994.-Vol. 4.-P. 243-263.

107. Tuy H, Thieu T.V. and Thoai NG.Q. A conical algorithm for globally minimizing a concave function over a closed convex set. // Preprint Series. -Vol. 10.-№3. Hanoi: Institute of Mathematics,1985.

108. Torn A., Zilinskas A. Global Optimization. Berlin, Springer Verlag, 1989.

109. Walters F.H., Parker L.R., Morgan S.L., and Deming S.N. Sequential Simplex Optimization. CRC Press, Boca Raton, FL, 1991.

110. Zangwill W. I. A note on functions whose local minima are global // JOTA. -1976.-Vol. 18.-P. 556-559.

111. Zangwill W. I. Minimizing a function without calculating derivatives // Comput. J. 1967. - Vol. 10. - P. 293-296.

112. Zangwill W.L. Minimum concave cost flows in certain networks // Management Science. 1968. - Vol. 14. - №7. - P. 429-450.

113. Zwart P.B. Global maximization of a convex function with linear inequality constraints // Oper. Res. 1974. - Vol. 22. - P. 602-609.

114. Zwart P.B. Nonlinear programming: Conterexamples to two global optimization algorithms. // Oper. Res. 1973. - Vol. 21. - P. 1260-1266.

115. Баушев A.H., Морозова Е.Ю. Метод статистических испытаний в задаче квазивогнутого программирования // Обозрение прикл. и промышл. матем. 2004. - Т. 11. - Вып. 1. - С. 34-40.

116. Баушев А.Н., Морозова Е.Ю., Осьминин А.Т. О математической модели минимизации эксплуатационных затрат при организации вагонопотоков // Вестник ПГУПС. 2004. - Вып. 2. - С. 39-43.

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

118. Буй Тхе Там, By Тхиен Бан. Минимизация вогнутой функции при линейных ограничениях // Экон. и матем. мет. 1985. - Т. XXI. - Вып. 4. -С. 709-714.

119. Дамбраускас А.П. Симплексный поиск. М.: Энергия, 1979. - 176 с.

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

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

122. Емеличев В.А., Ковалев М.М., Кравцов М.К. Многогранники. Графы. Оптимизация. М: Наука, 1981. - 344 с.

123. Жиглявский А.А., Жилинскас А.Г. Методы поиска глобального экстремум. М.: Наука, 1991. - 248 с.121.3айченко Ю.П. Исследование операций. Киев. Вища школа, 1975. -320 с.

124. Канторович JI. В., Гавурин М К. Применение математических методов в вопросах анализа грузопотоков // Проблемы повышения эффективности работы транспорта. М.: Издательство АН СССР, 1949. - С. 110-138.

125. Карманов В.Г. Математическое программирование. М.: Физматлит, 2001.-264 с.

126. Кендалл М., Моран П. Геометрические вероятности М.: Наука, 1972. -192 с.

127. Лейхтвейс К. Выпуклые множества. М.: Наука, 1985. - 352 с.

128. Магарил-Ильяев Г.Г., Тихомиров В.М. Выпуклый анализ и его приложения. М.: Эдиториал УРСС, 2000. - 176 с.

129. Морозова Е.Ю. Об алгоритме решения транспортной задачи с квазивогнутой функцией стоимости // Известия ПГУПС. 2005. - Вып. 1.-С. 194-199.

130. Морозова Е.Ю. Об определении диаметра конечного множества точек в евклидовом пространстве // Известия ПГУПС. 2004. - Вып. 1. - С. 126-130.

131. Морозова Е.Ю. Рекурсивный алгоритм прямого поиска минимума функции нескольких переменных. // Обозрение прикл. и промышл. матем. 2006.-Т. 13.-Вып. 5.-С. 783-796.

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

133. Рокафеллар Р.Т. Выпуклый анализ/Пер. с англ. М.: Мир, 1973. - 470 с.

134. Тхоаи Н. В., Туй X. Решение линейной задачи о дополнительности, используя вогнутое программирование // Журнал вычислит, матем. и матем. физики. 1983. - Т. 23. - Вып. 3. - С. 602-608.

135. Уткин C.JL, Хачатуров В.Р., Туй Хоанг. О конусных алгоритмах для решения задачи вогнутого программирования и некоторых ее обобщений // Ж. вычисл. матем. и матем. физики. 1988. - Т. 28. - С. 992-999.

136. Фихтенгольц Г.М. Основы математического анализа. Т. 1. М.: ФИЗМАТЛИТ, 2002. - 416 с.

137. Хадвигер Г. Лекции об объеме, площади поверхности и изопериметрии. -М.: Наука, 1985.-416 с.

138. Хоанг Туй. Вогнутое программирование при линейных ограничениях. // Докл. АН СССР. 1964. - Т. 159. - № 1. - С. 32-35.

139. Шульга A.M., Смехова Н.Г. Себестоимость железнодорожных перевозок. М: Транспорт, 1985. - 280 с.