Содержание к диссертации
Введение
ГЛАВА 1. Минимизация негладкой функции нескольких переменных 25
1.1. Алгоритм бисекции для нахождения минимума непрерывной строго унимодальной функции на симплексе 25
1.1.1. Постановка задачи 25
1.1.2. Декомпозиция множеств и функций по сечениям 26
1.1.3. Описание алгоритма 29
1.1.4. Обоснование алгоритма 34
1.1.5. Результаты численных экспериментов 36
1.1.5.1. Примеры минимизации негладких функций . 36
1.1.5.2. Контрпример для алгоритма Нелдера-Мида 37
1.1.5.3. Пример минимизации функции Денниса-Вуда . 42
1.2. Алгоритм безусловной минимизации непрерывной
строго унимодальной функции 45
1.2.1. Постановка задачи и описание алгоритма 45
1.2.2. Примеры работы алгоритма 49
1.2.2.1. Контрпример для алгоритма Нелдера-Мида 49
1.2.2.2. Пример минимизации негладкой функции 49
1.2.2.3. Пример минимизации функции Денниса-Вуда . 52
ГЛАВА 2. Метод статистических испытаний для решения задачи минимизации квазивогнутой функции на выпуклом многогранном множестве 54
2.1. Общие свойства задач квазивогнутого программирования 54
2.2. Постановка задачи и основные утверждения 55
2.3. Моделирование равномерного распределения на выпуклой оболочке конечного подмножества векторов евклидова пространства 56
2.4. Описание основного алгоритма и его обоснование 60
2.5. Вычислительные эксперименты. Примеры 65
2.5.1. Пример минимизации вогнутой функции 65
2.5.2. Математическая модель задачи минимизации эксплуатационных расходов при организации вагонопотоков 67
2.5.3. Пример минимизации квазивогнутой функции 71
2.5.4. Определение диаметра выпуклого многогранного множества 73
ГЛАВА 3. Методы решения задачи транспортного типа с квазивогнутой функцией стоимости 79
3.1. Свойства транспортного многогранника 19
3.2. Метод статистических испытаний для решения задачи транспортного типа с квазивогнутой функцией стоимости 84
3.2.1. Модификация алгоритма минимизации квазивогнутой функции на выпуклом многогранном множестве 84
3.2.2. Постановка задачи и описание алгоритма 87
3.2.3. Решение задачи при вырожденном опорном плане 88
3.2.4. Тестовая задача нахождения диаметра многогранника бистохастических матриц 89
3.3. Детерминированный метод поиска глобального минимума квазивогнутой функции на транспортном многограннике 91
ГЛАВА 4. Алгоритм глобальной минимизации квазивогнутой функции на выпуклом множестве 97
4.1. Общие замечания 97
4.2. Постановка задачи и краткое описание структуры алгоритма 97
4.3. Описание предварительного этапа 99
4.4. Описание и обоснование процедуры построения многогранника, содержащего выпуклое множество 102
4.5. Пошаговое описание алгоритма 105
4.6. Результаты вычислительных экспериментов 110
4.6.1. Пример минимизации вогнутой функции на выпуклом множестве, задаваемом нелинейными ограничениями 110
4.6.2. Пример минимизации вогнутой функции на выпуклом множестве, задаваемом нелинейными и линейными ограничениями 117
4.6.3. Пример минимизации вогнутой функции, когда оптимальное решение достигается в точке, лежащей
на границе только одного из ограничений 117
Заключение 121
Литература
- Декомпозиция множеств и функций по сечениям
- Моделирование равномерного распределения на выпуклой оболочке конечного подмножества векторов евклидова пространства
- Модификация алгоритма минимизации квазивогнутой функции на выпуклом многогранном множестве
- Постановка задачи и краткое описание структуры алгоритма
Введение к работе
Актуальность темы исследования. Работа посвящена разработке новых методов минимизации негладких функций и глобальной минимизации квазивогнутых функций на выпуклых множествах различной структуры. Разнообразные важные практические приложения в экономике, промышленности, транспорте и других областях приводят к формулировке задач такого типа. Несмотря на существование большого количества различных методов оптимизации, возможности применения этих методов для решения конкретных задач ограничены предположениями о принадлежности к некоторым специальным классам как оптимизируемых функций, так и допустимых множеств. Актуальность темы определяется необходимостью совершенствования математического аппарата в области минимизации негладких функций, а также невыпуклых функций.
Цель диссертационной работы. Целью настоящей диссертационной работы является разработка и обоснование новых и эффективных методов глобальной минимизации некоторых специальных классов негладких функций на выпуклых множествах.
Задачи диссертационного исследования.
Разработать и обосновать метод нахождения минимума негладкой выпуклой функции многих переменных на симплексе.
Разработать и обосновать метод нахождения глобального минимума квазивогнутой функции на выпуклом многогранном множестве.
Разработать и обосновать метод решения задачи транспортного типа с квазивогнутой функцией стоимости.
Разработать и обосновать метод глобальной минимизации квазивогнутой функции на произвольном выпуклом множестве.
Объектом исследования являются задачи глобальной оптимизации негладких функций нескольких переменных.
Предметом исследования являются алгоритмы решения задач нелинейной оптимизации для некоторых специальных классов функций.
Общая методология исследования базируется на основных положениях выпуклого анализа, теории оптимизации, на принципах моделирования.
Научная новизна. В работе получены следующие результаты: 1. Предложен новый алгоритм нахождения минимума функции многих переменных на симплексе. Алгоритм относится к классу методов прямого поиска, использующих лишь информацию о значениях функции в произвольных точках. Алгоритм реализован в виде рекурсивной процедуры и является обобщением хорошо известного в одномерной оптимизации
метода половинного деления. Доказана сходимость алгоритма к точке минимума для класса непрерывных строго унимодальных функций. Алгоритм позволяет гарантированно находить точку минимума негладких функций, что выделяет его среди известных алгоритмов.
Предложена модификация алгоритма бисекции для нахождения минимума функции нескольких переменных на симплексе для задачи безусловной минимизации непрерывной строго унимодальной функции. Метод сходится для обозначенного класса функций, не накладывает дополнительных ограничений на дифференцируемость функции и позволяет гарантированно находить точку минимума негладких функций в отсутствие ограничений.
Предложен новый метод глобальной минимизации квазивогнутой функции на выпуклом многогранном множестве. Итерационная процедура алгоритма включает в себя три основных элемента: нахождение точки локального минимума, нахождение допустимой области с меньшим значением целевой функции и усечение исходной области опорными гиперплоскостями к поверхности текущего уровня целевой функции. Для улучшения найденного локально-оптимального решения используется метод статистических испытаний. Предложенный метод допускает обобщение на случай кусочно-вогнутых разрывных сепарабельных функций, что проиллюстрировано численными примерами.
Предложена модификация метода глобальной минимизации квазивогнутой функции на полиэдре для решения задачи транспортного типа с квазивогнутой функцией стоимости. Вместо усечения исходного множества опорными гиперплоскостями для нахождения крайней точки на грани транспортного многогранника с меньшим значением целевой функции решается последовательность задач по нахождению начального базисного плана в транспортной задаче с запретами. Предложен алгоритм решения задачи в случае, когда транспортный многогранник является вырожденным. В предложенном методе не накладывается дополнительных ограничений на вид целевой функции, что позволяет рассматривать более широкий класс целевых функций, в частности, разрывных квазивогнутых функций.
Предложен метод минимизации квазивогнутой функции на замкнутом выпуклом ограниченном множестве, основанный на аппроксимации допустимой области снизу и сверху выпуклыми множествами. Для получения нижней границы решается последовательность задач минимизации выпуклой функции при линейных ограничениях. Предложенный метод позволяет гарантированно находить минимум негладкой квазивогнутой функции на замкнутом выпуклом ограниченном множестве, когда ограничения,
определяющие допустимое множество, могут быть нелинейными, т.е. допустимое множество не является полиэдром.
Достоверность и научная обоснованность результатов диссертации обеспечивается использованием современных математических методов при разработке и обосновании предлагаемых алгоритмов, тщательным тестированием вычислительных программ, сопоставлением полученных результатов с результатами других теоретических исследований.
Практическая значимость результатов исследования заключается в возможности использования полученных результатов в ряде прикладных областей экономики, промышленности, транспорта и других задачах, приводящих к минимизации вогнутой функции на выпуклом множестве.
Апробация работы. Результаты диссертации обсуждались на научных семинарах кафедры прикладной математики ПГУПС и докладывались на:
Третьем Всероссийском симпозиуме по прикладной и промышленной математике (Сочи, 2002);
Восьмой международной научно-практической конференции "ИНФОТРАНС - 2003" (Санкт-Петербург, 2003);
Четвертом (весенняя сессия - Петрозаводск, 2003), (осенняя сессия -Сочи, 2003) Всероссийском симпозиуме по прикладной и промышленной математике;
Шестом (весенняя сессия - Санкт-Петербург, 2005), (осенняя сессия -Сочи, 2005) Всероссийском симпозиуме по прикладной и промышленной математике;
Седьмом (Кисловодск, 2006) Всероссийском симпозиуме по прикладной и промышленной математике;
на международной конференции The 2007 International Conference of Applied and Engineering Mathematics (Лондон, 2007).
Публикации. По теме диссертации опубликовано 13 работ.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Работа изложена на 135 страницах машинописного текста, содержит 32 рисунка, 3 таблицы и список литературы из 137 наименований.
Декомпозиция множеств и функций по сечениям
Будем рассматривать задачу /(x)-»min, XGS, (1.1) где f:S- R - непрерывная строго унимодальная функция на множестве S, a S -w-мерный симплекс в пространстве R", т.е. S = conv(v0,vv...,vn), где v0,v,,...,v„ - аффинно независимые точки в пространстве R". Будем использовать следующее определение строгой унимодальности функции. Пусть D - ограниченное замкнутое выпуклое подмножество пространства R". Функция f:D- R называется строго унимодальной на множестве D, если для любого отрезка AcD #Argm\n{f(x]xeA}=\, где символ «#» означает мощность множества. Заметим, что если функция строго унимодальна, то и на любом замкнутом выпуклом подмножестве D cD #Argmm[f(x]ixGD }=l.
Отметим следующее свойство строго унимодальных функций. Лемма 1.1. Пусть f - непрерывная строго унимодальная функция на множестве D, отрезок [xl,x2\czD. Если Xі е\щхх,х2\ и f\xx) f(x3), то
Доказательство (от противного). Предположим, что /(X3) /(JC2). Тогда существует х" elnX[x\x1\=avgmax\f(x ixE[xi,x2\j и существуют такие положительные числа ? ,, 52, что на отрезке \х — , дг J функция / возрастает, а на отрезке [x ,j +J2J - убывает, при этом в силу непрерывности функции / f\x -8Х)=f[x +S2), т. е. точки х -д1 и х +S2 являются точками минимума функции/на отрезке [х -5х,х" +S2\, что противоречит определению строгой унимодальности.
Пусть D - замкнутая ограниченная область в пространстве R", f непрерывная функция в области D. Зафиксируем вектор единичной нормы е и для каждого вещественного числа t рассмотрим гиперплоскость rt = {xERn\(e,x) = t}. (1.2)
Семейство \yt -оо t оо} покрывает все пространство R" и поскольку D -замкнутая ограниченная область, то найдутся значения /min и tmaii такие, что для каждого te[tmin,tmJ получим D, = Dnyt 0, а для каждого te[tmin,tmJ Д = 0. Имеет место представление
D= U D,. (1.3)
Множество Д называется сечением множества Z) гиперплоскостью /,. Поскольку множество Dt лежит в гиперплоскости у,, то его можно рассматривать как множество в пространстве, размерность которого на единицу меньше, чем исходное пространство. Рассмотрим функцию F(t) = mm{f(x)\xeDl}. (1.4) Предложение 1.1. Предположим, что f(x) - непрерывная функция в области D, тогда F(t) - непрерывная функция на отрезке [?min,/max] и имеет место равенство mm{f(x)\xED} = mm{F(t)\te[tmin,tmj}. (1.5) Доказательство. Поскольку / - непрерывная функция, а множество D замкнуто и ограничено, то функция / равномерно непрерывна в области D. Поэтому для произвольного є 0 найдется такое 8 0, что a f(S) = sup{\f(x)-f(y)\\x,yED,\\x-y\\ S} s. (1.6) Пусть \\t2 - f, д. Покажем, что при этом будет выполняться неравенство F(f2)-F(/,) . (1.7) Пусть х{ = arg min I f (x) \x є D , x2= arg min j /(x) x є Z} }, причем /(x[) /(x2). Рассмотрим w = x,+(/2-ґ,)е. Поскольку X,GZ), TO при достаточно малых 8 ueD. Поскольку (x, + (t2 x)e,e) = tx +12 x =t2, то и єyt и, следовательно, ueDh. Поскольку и-х, = ґ2 x\ 8, то \f{u)-f[xA s. Из последнего неравенства и предположения получим /(х2) /(м) : + /(х1) : + /(х2), то \f(x2)-f(xA , т.е. выполняется неравенство (1.7).
Моделирование равномерного распределения на выпуклой оболочке конечного подмножества векторов евклидова пространства
В задаче минимизации эксплутационных расходов в зависимости от объёма грузовых железнодорожных перевозок при организации вагонопотоков возникает необходимость в решении задачи нелинейного программирования, в которой целевая функция является сепарабельной, при этом её слагаемые -кусочно-вогнутые, строго возрастающие на R+, с точками разрыва первого рода, функции, а ограничения задачи представляют собой выпуклое многогранное множество [138].
С математической точки зрения задачи квазивогнутого программирования включают в себя две основных особенности. Во-первых, среди решений такой задачи (если оно существует) обязательно найдется крайняя точка множества допустимых планов задачи, во-вторых, точка локального минимума в этой задаче не обязательно совпадает с точкой глобального минимума.
Предлагаемый метод фактически является методом последовательного улучшения плана, который включает в себя три основных элемента: нахождение точки локального минимума, нахождение допустимой области с меньшим значением целевой функции и усечение исходной области опорными гиперплоскостями к поверхности текущего уровня целевой функции. Для улучшения найденного локально-оптимального решения используется метод статистических испытаний. 2.2. Постановка задачи и основные утверждения Рассматривается задача математического программирования следующего вида: F(jc)- min, (2.1) при ограничениях Ах = Ь X: , xeR", (2.2) х 0 где F(x) - квазивогнутая функция, beRm, А - матрица размера тхп.
Относительно матрицы А и вектора Ъ системы (2.2) будем предполагать, что они содержат только неотрицательные элементы. В этом случае допустимое множество X задачи (если оно не пусто) ограничено и представляет собой выпуклый многогранник. Отметим также, что когда речь идёт о канонической форме записи совокупности линейных ограничений, т.е. о форме (2.2), то, не нарушая общности, можно считать, что гапк(А) = т п.
Предлагаемый алгоритм решения задачи (2.1) - (2.2) основан на следующих утверждениях. Лемма 2.1. Пусть DczR" - выпуклое множество, F:D- R квазивогнутая функция и отрезок [лг ,х2]с). Тогда minJF(x)лгєГх1, 2 mmjFfx L/Mx2}}. Доказательство. Пусть 0 / 1, х = (і)xl + tx2, с = тіп (х ), (д:2]. Рассмотрим множество Xе = {XED\F(X) C). Поскольку F - квазивогнутая функция, то это множество выпукло, а т.к. Xі еХс, хг є Xе, то отрезок [х1, х1 \ с Xе, в частности, F[x ) с, что и требовалось доказать. Теорема 2.1. Пусть DczR" - ограниченное замкнутое выпуклое множество, F:D- R - непрерывная квазивогнутая функция. Тогда min F(x)x Є } = min F(X)JC Є ExtrD}. Доказательство. По теореме Вейерштрасса множество argminF(x)A;GD не пусто. Пусть х єargminF(X)JCЄZ), d = d im(D). По теореме Каратеодори найдутся точки x\...,xk eExtrD и неотрицательные числа а1,...,« , а =1, такие, что x"= aV, причем k d + \. Положим c = minF(A;1j,...,F(x J, Xе = {XED\F(X) CJ. Поскольку F - квазивогнутая функция, то это множество Xе выпукло. Очевидно, х\...,хк еХс. Следовательно, F\x ) c, что и требовалось доказать. Замечание 2.1. Требование ограниченности в условии теоремы существенно, как показывает следующий пример. Пусть л = 2, В = \{х,у1х 0,у — , F(x,y) = y. В этом случае ExtrD = Нх,уІх 0,у = — , arg mm {F(x)\xeD} = 0.
Модификация алгоритма минимизации квазивогнутой функции на выпуклом многогранном множестве
Рассматривается задача математического программирования вида: F(x)- mm, (3.5) Х:\" , , (3.6) 0,..., 0 где F(x) - квазивогнутая функция, X - выпуклое многогранное множество.
Алгоритм нахождения точки глобального минимума квазивогнутой функции на выпуклом многогранном множестве включает следующие основные элементы (рис. 3.1):
1. Нахождение точки локального минимума z, при этом F(z) = т;
2. Статистическое моделирование направлений поиска области в допустимом множестве с меньшим значением целевой функции (нахождение соседних с z вершин \zJ;j = 1,...,/]); моделирование случайной точки zc, имеющей равномерное распределение на выпуклой оболочке convjz1,... }; нахождение точки wc пересечения луча h = {z = z + t(zc -z), t Q} с выпуклым множеством X (wc=z mm, max = max( -zl eX}), при этом F{w) = m m) ,
3. Усечение исходного множества опорной гиперплоскостью к поверхности текущего уровня целевой функции F{x) = т.
Непосредственное применение этого алгоритма для решения задач транспортного типа приводит к принципиальным трудностям, поскольку в результате такого усечения возникает задача, которая уже не является задачей транспортного типа (в системе ограничений появляется дополнительное ограничение, определяемое опорной гиперплоскостью). Решать же транспортную задачу как общую задачу крайне невыгодно из-за ее высокой размерности (задачаимеет тхп переменных).
В связи с этой проблемой предлагается модификация предложенного во второй главе алгоритма. Вместо усечения исходного множества опорными гиперплоскостями можно использовать следующий способ нахождения вершины с меньшим значением целевой функции. Пусть wc - точка с меньшим значением целевой функции, полученная в п. 2 и лежащая на грани выпуклого множества X. В соответствии с процедурой нахождения этой точки в момент совпадения точек z и wc, некоторые из координат точки z обращаются в нуль. Допустим, что это координаты w ,...,w t. Тогда грань, на которой лежит точка wc, задается ограничениями: -86. axxxx+... + aXnxn=bx с): mil /ил л т х, =х, =... = х, = 0 атХх.+... + ах=Ьн (3.7) хі 0,і = \,...п
Грань Г(м с) можно рассматривать как выпуклое многогранное множество вида (3.6) в пространстве R" k векторов ( , / є {1,...,и}\ {/ ,,...,z J). Заметим, что крайние точки грани T(wc) являются и крайними точками множества X. Поскольку F квазивогнутая функция, то, согласно основной теореме, найдется крайняя точка на грани T(wc), в которой значение целевой функции не больше, чем в точке wc. Пусть и - произвольная крайняя точка грани T(wc). Рассмотрим луч р = \w = и + t(wc - и), t 0). Для любого t точка W удовлетворяет равенствам системы ограничений (3.7). Обозначим t -максимальное значение /, при котором w удовлетворяет также и неравенствам. В силу квазивогнутости по крайней мере в одной из точек и, W значение целевой функции не больше, чем в точке wc. При этом точка W лежит на грани меньшей размерности, чем точка wc. Если точка w не является крайней, то к ней следует повторить эту процедуру и т.д. до тех пор, пока не будет найдена крайняя точка множества X с меньшим значением, чем в точке wc. Таким образом, модификация алгоритма заключается в замене шага 3 описанной выше процедурой. Для программной реализации этой процедуры достаточно иметь программу, включающую в себя процедуры нахождения начальной базисной точки множества типа (3.7), которая хорошо известна, а также достаточно простую процедуру нахождения точки пересечения луча и грани многогранного множества.
Постановка задачи и краткое описание структуры алгоритма
В этой главе будем рассматривать задачу минимизации квазивогнутой функции на замкнутом выпуклом ограниченном множестве, когда ограничения, определяющие допустимое множество, могут быть нелинейными, т.е. допустимое множество не является полиэдром.
Существуют различные способы аналитического задания выпуклого множества в пространстве R" [126]. В математическом программировании допустимое множество X обычно задается в виде X = {xeRn\gi(x) 0,i = l,...m}, (4.1) где gt(x) - заданные выпуклые функции на пространстве R". Если рассмотреть функцию g(x) = max{gi(x),i = l,...,m], (4.2) то множество X можно записать в виде X = {xeRn\g(x) 0} (4.3) Поэтому, не нарушая общности, можно считать, что т = 1. Рассматривается задача /( )-» min, g(x) 0, (4.4) где, f(x) - квазивогнутая функция на пространстве Rn, g(x) - выпуклая функция, определенная на R". Будем предполагать, что множество X = їх є R" \ g(x) OJ ограничено. Предлагаемый алгоритм включает следующие этапы.
1. Предварительный этап.
На этом этапе решается задача построения симплекса Q, вписанного в множество X и построения оценки сверху для значения задачи (4.4). При этом требуется задание внутренней точки д;0 множества X (предполагаем, что размерность множества X равна п, а поверхности уровня функции g ограничены). 2. Итерационная процедура. Включает следующие шаги. 1) Построение выпуклого множества Р, содержащего множество X. 2) Сужение исследуемой области. 3) Получение новой оценки снизу для значения задачи (4.4). 4) Получение новой оценки сверху для значения задачи (4.4). 5) Проверка условий (18) остановки алгоритма. В случае невыполнения условия - переход к следующему шагу. 6) модификация многогранника Q. Отметим следующее. Выпуклый многогранник Q называется вписанным в выпуклое множество X, если все его вершины (нульмерные грани) лежат на границе дХ множества X.
Выпуклый многогранник Р называется описанным вокруг выпуклого множества X (размерности п), если: 1) сР; 2) для любой грани у многогранника Р размерности п -1 выполняется условие у п Р Ф 0. Основные элементы этапа: Нахождение внутренней точки х. Построение симплекса S0 с вершиной в точке х так, чтобы все его вершины оказались внутри множества X. Нахождение центра тяжести хс симплекса S0. Построение лучей, исходящих из хс и проходящих через вершины симплекса S0 до пересечения с границей множества X.
Построение симплекса Q, вписанного в множество Основная техническая трудность в реализации предварительного этапа заключается в нахождении внутренней точки х для множества X. Существуют различные алгоритмы для решения этой задачи [123]. На практике эффективным оказывается следующий предлагаемый алгоритм для нахождения точки л:0. Предположим для простоты, что функции g(x), определяющие допустимое множество X, являются гладкими. В случае негладкой функции g(x) можно использовать методы, предложенные в [117], [118].
Алгоритм нахождения внутренней точки х выпуклого множества X. Шаг 1. Задание начальной точки х из области определения g(x). Пусть g(x) = g.
Если g(x) 0, то х - искомая точка. Алгоритм останавливаем. В противном случае переходим к шагу 2. Шаг 2. Находим антиградиент функции g(x) в точке х и полагаем \gV)\ Построим луч l = x+te (t 0). (4.5) Находим f№=max{//n(g( ) = g) 0}. (4.6) Задача определения tmax эквивалентна задаче нахождения нуля функции F(t) = g(x+te)-g0. (4.7) Для решения этой задачи можно использовать один из методов поиска нуля функции одной переменной, например, хорошо известный метод бисекции. ШагЗ. Рассмотрим задачу g(x) - min, х є[0, х + tmsKe]. (4.8) Находим минимум функции на отрезке каким-либо из известных методов одномерной минимизации. Пусть х1- найденная точка минимума. Если g(xl) 0, то х1 - искомая точка, алгоритм останавливаем. В противном случае полагаем g =g(xl), х = х1, и переходим к шагу 2. Построение симплекса S0 с вершиной в точке х. Для построения симплекса S0 можно воспользоваться следующим алгоритмом. Пусть \е1,...,е"} - канонический базис пространства R". Поскольку х - внутренняя точка множества X, для которой g(x) 0, то несложно найти такие значения р 0, i = \,...,n, для которых g(х + р е ) 0. Обозначим s = х + р е , i = \,...,n. Тогда convlx,s\s2,...,s"\ - искомый симплекс S0 (рис. 4.1).
