Поиск глобального решения в задачах обратно-выпуклого программирования Яковлева Татьяна Владимировна

Данный автореферат диссертации должен поступить в библиотеки в ближайшее время
Уведомить о поступлении

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

Автореферат - 240 руб., доставка 1-3 часа, с 10-19 (Московское время), кроме воскресенья

Яковлева Татьяна Владимировна. Поиск глобального решения в задачах обратно-выпуклого программирования : Дис. ... канд. физ.-мат. наук : 05.13.01 : Иркутск, 2003 146 c. РГБ ОД, 61:04-1/413

Содержание к диссертации

Введение 3

1 Глобальный поиск в обратно-выпуклых задачах 20

Некоторые сведения об обратно-выпуклых задачах 21
Методы локального поиска 27

Специальный метод локального поиска 27
Модифицированный метод Розена 34

1.3 Условия глобальной оптимальности 43

Минимизирующие последовательности 47
Стратегия глобального поиска 51

1.6 Сходимость стратегии глобального поиска 55

2 Численное решение задач обратно-выпуклого программирования 61

Постановка задач 62
О методах локального поиска 63
Специальный алгоритм глобального поиска 68
Численное решение задач с ограничением типа нормы 70

Выбор начального приближения 70
Аппроксимация поверхности уровня 71
Результаты численного эксперимента 73

Численное решение задач с квадратичным ограничением общего вида . 76
Численное решение задач с другими нелинейными ограничениями ... 80
Анализ вычислительного эксперимента 83

3 Численное решение задачи о многомерном рюкзаке 85

Постановки задач 86
Практические приложения 90
О стратегии глобального поиска для задачи о рюкзаке 94
Построение аппроксимации поверхности уровня 96
Построение оценок 100
Численный эксперимент по решению задачи о рюкзаке 103

Алгоритм глобального поиска для решения задачи о рюкзаке . . 104
О решении линеаризованной задачи 105
Локальный поиск для задач о рюкзаке 107
Результаты численного эксперимента 109

Метод исключения координат 116
Численное решение задачи о многомерном рюкзаке 119

Заключение 127

Библиография 129

Приложение 143

Введение к работе

Слово "оптимизация" становится все более популярным и не всегда используется в своем изначальном математическом смысле. А последнее, как известно, означает выбор из множества допустимых альтернатив наилучшей. И такие задачи встречаются в неисчислимом множестве не только в науке, но и во всех прикладных областях человеческой деятельности, о чем свидетельствует, например, научно-техническая революция в XX веке. Экономика и экология, техника и строительство, управление электрическими, газовыми и тепловыми потоками и вообще управление динамическими системами без использования современных математических методов нередко приводят к деградации объектов и процессов управления, авариям и даже катастрофам. Известные аварии в Бхопале (Индия), Чернобыле (СССР), недавние электроэнергетические катастрофы в США и Италии — тому подтверждение.

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

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

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

Достаточно сложно привести полную классификацию задач невыпуклой или, как еще принято говорить, глобальной оптимизации. Тем не менее, в литературе [118]— [120] принято рассматривать следующие четыре класса задач.

1. Задачи выпуклой максимизации (или вогнутой минимизации): f(x) | max, х Є D, (CM) где /() — выпуклая функция на некотором открытом выпуклом множестве ) С Rⁿ, содержащем допустимое множество D.

2. Обратно-выпуклые задачи или задачи на дополнениях выпуклых множеств. Простейшей задачей подобного типа является следующая задача h(x) 4- пііп, х Є S, д(х) > 0, (RC) где д(-) — выпуклая функция на выпуклом открытом множестве О. С М^п, содержащем множество 5, h(-) — непрерывная функция на Rⁿ.

3. Задачи d.c. минимизации F(x) = д(х) - f(x) і min, х Є D, (DC) где /(), g(-) — выпуклые функции на некотором открытом выпуклом множестве fi С -К", D С Г2. Функцию F(-), представимую в виде разности двух выпуклых функций, в литературе принято называть d.c. функцией (the difference of two convex functions).

4. Экстремальные задачи с d.c. ограничениями, простейшей из которых является задача следующего вида h(x) I min, х Є S, F(x) > 0, (DCC) где F(x) = g(x) — f(x), x Є Q, a /(), g(-) являются выпуклыми функциями на выпуклом открытом множестве Q С JRⁿ, содержащем множество 5, h(-) — непрерывная функция на ШС¹.

Нетрудно видеть, что при д(х) = 0 задача d.c. минимизации (DC) обращается и задачу выпуклой максимизации (СМ), так что последняя является частным случаем (DC). Аналогично задача с d.c. ограничениями (DCC) при f(x) = 0 обращается в задачу (RC) на дополнении выпуклого множества, которая, таким образом, оказывается частным случаем (DCC). Итак, можно сказать, что простейшие задачи d.c. программирования (DC) и (DCC) являются основными согласно предложенной классификации.

Для решения невыпуклых задач, в основном, применяются, исключая стохастику и эвристику, следующие методы: отсечений [8, 9, 106, 151]; ветвей и границ [120, 122, 136, 151]; внешней и внутренней аппроксимации [8, 122, 151].

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

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

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

Однако, как известно, принцип Лагранжа в самой общей его форме, даже с использованием производных, которых в современной литературе введено достаточное количество [22], не дает условий, достаточных для глобальной оптимальности. И, как следствие, в невыпуклых задачах с использованием традиционных численных методов оптимизации [2, 9,14, 17], [50]-[56], [82] можно гарантировать сходимость, вообще говоря, лишь к стационарной точке или в лучшем случае к локальному экстремуму и то не во всех случаях.

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

Одним из первых оригинальных результатов в этом направлении было необходимое условие локальной оптимальности, полученное Рокафелларом Р. [58] для задачи (СМ). Оно имеет следующий вид: если z Є Argmax(f, X), то df(z) С N(z/X), где df (z) = {x* Є lRⁿ : f (x) — f (z) > (x*, x — z) Vx Є IRⁿ) — субдифференциал выпуклой функции / () в точке z, а. N (z/X) = {х* Є JRⁿ : (х*,х - z) < 0 Vx Є М^п} — конус опорных векторов к множеству X в точке z.

Далее, несомненным достижением явилось полученное J.B. Hiriart-Urruty необходимое и достаточное условие глобальной оптимальности [115, 116] для задачи выпуклой максимизации (СМ). Развив предварительно технику є - субдифференциалов [114], ему удалось получить следующее условие z Є Arg тах(/,Х) <=> df(z) С N_e(z/X) Me > 0, где d_ef(z) - бг-субдифферециал функции /, a N(z/X) - множество е-опорных функционалов по множеству X в точке z.

Другой подход к характеризации глобального решения был развит в работах А.С. Стрекаловского [60]—[66], [144]—[146]. Предложенные им условия оптимальности характеризуют глобальное решение задач типа (CM)-(DCC), используя поверхность уровня функции, задающей невыпуклость в задаче, а также классическую идею линеаризации.

Полученное в 1987 г. условие оптимальности для задачи выпуклой максимизации (СМ) основано на использовании поверхности уровня выпуклых функций и (при выполнении некоторых условий регулярности) имеет следующий вид: z Є Argmax(f, D) <* df(y) С N(y/D) Vy : f(y) = f(z). (1)

В случае дифференцируемости функции /() условие (1) принимает вид: zArgma.x(f,D) & (Vf(y),x-y)<0Wy:f(y) = f(z), Vz D. (2)

Легко заметить, что при у = z из условия (2) следует классическое условие локальной оптимальности: (Vf(z),x-z)

Отметим, что проверка условия оптимальности (2) сводится к решению серии, так называемых, линеаризованных задач (V/(y),s)tmax, х Є D, (PL) зависящих от параметра у, лежащего на поверхности уровня функции /(-)i задающей невыпуклость в задаче (СМ). При этом в случае выпуклости множества D задача (PL) оказывается выпуклой, и для ее решения применимы известные методы выпуклого программирования [4, 11, 12, 13, 27, 28, 33, 34, 50, 51, 53, 54, 56, 82]. Таким образом, данный подход принимает во внимание богатый численный опыт решения выпуклых задач.

Позже А.С. Стрекаловским были получены условия оптимальности для обратно-выпуклых задач [62, 64, 144] и задач d.c. программирования [66, 146]. Подчеркнем, что условия оптимальности для задачи выпуклой максимизации (СМ) являются частным случаем условий для задачи d.c. минимизации (DC), а из необходимых и достаточных условий для задач с d.c. ограничениями (DCC) вытекают условия глобальной оптимальности для задач на дополнениях выпуклых множеств (RC). Это гармоничное взаимоотношение между постановками задач и условиями глобальной оптимальности, думается, подчеркивает естественность предложенного подхода.

В работах А.С. Стрекаловского и его учеников [65, 70, 145] на основе условий глобальной оптимальности (2) предложены алгоритмы глобального поиска для задачи выпуклой максимизации (СМ), а также приведены результаты его тестирования на некоторых прикладных задачах.

Впоследствии подобные алгоритмы были предложены и для задач обратно-выпуклого программирования [45, 77, 147], и, наконец, для общих задач d.c. оптимизации (66)-(69]. [71]-(75], [88, 146]. ^, При этом необходимо отметить, что, насколько известно [8,45, 77, 99,111, 112, 113,

123, 124, 100, 131, 132, ПО, 140, 147, 150, 152|, огромное количество работ посвящено решению обратно-выпуклой задачи вида h(x) і min, xeS, g{x) > 0. (RC)

Когда функция h(-) и множество S выпуклы, основные трудности ее решения связывают с ограничением д(х) > 0, которое и создает базовую невыпуклость в задаче {RC).

Напомним кратко несколько практических задач, которые могут быть сформулированы в виде задачи обратно-выпуклого программирования (RC).

1. Задача целочисленного программирования. W Это весьма многочисленный класс задач, возникающих на практике [3, 50J, на- пример, задачи планирования производства [84], размещение предприятий и распределение капиталовложений [10]. В качестве примера здесь рассмотрим задачу транспортного обслуживания [44].

Пусть из некоторого пункта необходимо доставить Ь человек. Транспортное агентство располагает автобусами п типов, вместимостью а; (г = 1,...,п) человек. В зависимости от типа автобуса установлены тарифы на проезд с*. Необходимо определить, какого типа автобусы и в каком количестве следует использовать так, чтобы суммарные издержки были минимальными.

Щ- Пусть Хі — количество автобусов г-го типа. Тогда получаем следующую задачу целочисленного программирования: > (с, х) і min, (а,х) >Ь, где Z₊ — множество неотрицательных целых чисел.

Применяя следующее представление для каждой переменной: *t = X)ytj2^J, од,-Є {0,1}, і =1,...,п, где целое число Ki — верхняя граница величины log₂x,-, и учитывая, что в свою очередь, булевое ограничение у^ Є {0,1} эквивалентно ограничениям у^ — y_tj > 0

О < Vij < 1» получаем задачу (4) в виде h(y) |min, yeSnU, yfj-Vij>0, j = l,...K_it і = 1,...,n, где Л(у) = Х>5>«2'', S^Lg^*» I >|>₀2'>Л, i=l j=0 [ t=l j=0 J

П = {у Є JRⁿ | 0 < yij < 1, j = 1,... *Г<, і = 1,... ,n}.

2. Задача о дополнительности.

Рассмотрим задачу квадратичного программирования следующего вида: {Qx, х) + (с, х) і min, Ax>b, х>0.

Если квадратная матрица Q положительно определена, то целевая функция в задаче (5) выпукла, и условия Куна-Таккера являются достаточными условиями оптимальности в задаче (5). Поэтому, в данном случае для решения задачи (5) достаточно найти точку, удовлетворяющую условиям (2Qx - А^ТХ + с, х) = О, (Ах - 6, Л) = О, А > О, х е Rⁿ, А Є R^m.

После введения обозначений

, М =

2Q -А^т \ с¹ -Ь перепишем условия Куна-Таккера следующим образом: (Mz + q,z) = О, у = Mz + q, или < Mz + q > О, z > О (У, z) = О, у>0, z>0.

Полученная задача (6) называется задачей о дополнительности [5, 119, 120, 135]. Очевидно, что условия (у, z) = 0, у > 0, z > 0 эквивалентны ограничениям ^2 тіп{у_г-, Zi) < 0, у > 0, z > 0, первое из которых является обратно-выпуклым, поскольку функция J2 min{yi,Zi} вогнутая функция.

3. Задача размещения.

Рассмотрим следующую задачу [1]: n m '

И а>цХц 4 min, i=lj=l

Еіу=^ Xij > О, і = 1,...,л, j = 1,...,m, >

И/і(Уі)<В, Vi>Zxij, і = 1,...,n, t=l i=l где a^ — транспортные затраты на перевозку единицы продукции из г-ого пункта производства в j'-ый пункт потребления, х^ - объем перевозок, Уі - объем производства в г-ом пункте, /Ду,-) - функциональная зависимость стоимости производства одной единицы продукции от объема производства в г'-ом пункте производства, Ь,- -объем потребления в j'-ом пункте и В - общая сумма средств на производственных пунктах.

Можно показать, что если стоимость продукции убывает при возрастании объема производства, то функции /, {уї) являются вогнутыми, что отражает экономическую реальность. Именно эти слагаемые и создают специфику ограничения /іІУі) < В — его обратную выпуклость, что приводит к обратно-выпуклой задаче.

4. Иерархические системы управления (Многоуровневое программирование).

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

Рассмотрим простейшую из подобных игр: центр (I игрок) — один производитель (II игрок) (69]. Каждый из участников имеет свой критерий эффективности и связанные ресурсы, но преимущество хода у I игрока.

При выборе "центром" управления х игрок II выбирает свое управление у с целью оптимизировать свой критерий эффективности д(у) на множестве ограничений Y(x) С Ш.^п, зависящим от х. Например, может быть, что Y(x) = {yeRⁿ\ G{x, у) < 0, у Є Р}, где Р С Rⁿ, G : М^т+п -> JR — непрерывная функция.

Итак, ответом игрока II на решение х игрока I будет вектор у = у{х), являющийся решением задачи g(v) t max, v Є Y(x). (7)

Естественно предположить, что у лица, принимающего решение на верхнем уровне, имеется свой взгляд на оценку принятия решений, следовательно, свой критерий эффективности, который оценивает и свою стратегию, и стратегию игрока II. Поэтому возникает следующая задача: f(x, у) I min, (х, у) Є S С ffC yeY(x), yeSol(7)

При этом даже в простейшем случае, когда все данные задач (7) и (8) линейны: f(x,v) = (^с,^х) + (di,y), д(у) = (d₂,y), S = {(х,у) : А_хх + B_lyl,xe JR%}, > Y(x) = {v : A₂x + B₂v 2,y<= Щ}, взаимосвязи между верхней и нижней "властью" создают невыпуклости, которые не могут быть преодолены стандартными методами нелинейного программирования. Действительно, обозначим через V(x) оптимальное значение нижней подзадачи V(x) = sup{g(v) : v Є Y(x)}.

Тогда включение у Є Sol(7) равносильно неравенству

9(v)>V(x), yeY(x). (9)

Довольно часто целевая функция игрока II вогнута, как в линейном случае. Тогда и функция оптимального значения У(«) тоже оказывается вогнутой [151]. При этом ограничение-неравенство в (9) оказывается обратно-выпуклым относительно х. #

В работах [96, 97] показано, что при описании задачи инженерного дизайна участвуют обратно-выпуклые ограничения. В [111] описано, как проблема расширения потока по сетям формалиризуется в виде задачи линейного программирования с одним дополнительным обратно-выпуклым ограничением. Другие интересные практические применения решения исследуемой задачи можно найти в работах [149, 153], где рассмотрена проблема огранения ценных камней, и в статье [31], посвященной формализации экономической задачи о переоборудовании предприятия.

Можно привести дополнительное количество примеров практических задач, если учесть, что задачи выпуклой максимизации (СМ) и задачи d.c. минимизации (DC) могут быть сведены к обратно-выпуклым задачам. Так задача f(x) t max, х Є D, очевидно, может быть сведена к следующей задаче [г] Є 1R): п t max, х Є D, f(x) — n > 0; а задача d.c. минимизации f(x) — g(x) \. min, x Є D, приводит к обратно-выпуклой задаче (п Є М) f(x) — 771 min, х Є D, д(х) — т) > 0, где функции /() и

Первая работа, посвященная обратно-выпуклым задачам, насколько нам известно, вышла в 1966 г. [140], где Ж.Б. Розеном была рассмотрена одна задача оптимального управления, для которой в качестве вспомогательной рассматривалась задача обратно-выпуклого программирования (RC) (хотя сам термин "обратно-выпуклая задача" (reverse convex problem) введен был позднее P.P. Мейером в [131]). Для решения задачи (RC) Ж.Б. Розеном была произведена последовательная линеаризация обратно-выпуклого ограничения в точках у^к, и затем рассматривались выпуклые задачи (PL(y^k)) h(x) і min, х Є S, д(у^к) + {^д(у^к),х-у^к)>о.

При этом точка y^kJrl последовательности {y^h} строилась как точное решение задачи (PL(y^k)). Сходимость метода устанавливается теоремой [131, 140], говорящей о том, что если точка у* является предельной для последовательности {у^к}, то она является решением линеаризованной задачи (PL(y*)). Кроме того, в точке у* выполнены необходимые условия Куна-Таккера для исходной задачи (RC).

Отметим, что эта теорема доказана в предположении компактности допустимого множества, а также точного решения вспомогательной задачи (PL(y^k)). Кроме того, не очень понятно какой приближенный критерий останова использовать, и что получаем в случае выполнения этого критерия. Поэтому нами была предложена модификация метода Ж.Б. Розена (см. п. 1.2), в которой допустимое множество не обязательно является компактом, и вспомогательная задача решается приближенно. Удалось доказать теорему сходимости и разработать новый критерий останова. Эффективность предложенного метода проверена численным экспериментом (см. п. 2.2).

В работе [8] В.П. Булатова (1977 г.) задача {RC) была названа задачей минимизации "на дыре", и к ее решению был предложен итеративный процесс последовательной линеаризации "плохого" ограничения д{х) > 0, аналогичный процессу Ж.Б. Розена. Отличие состояло в том, что линеаризация производилась в другой точке у^к = у^к + Xkd^k, где d^k — направляющий вектор со свойством Vh(y^k)d^k < 0, а Ajt — некоторое число. Доказана сходимость метода к точке Куна-Таккера в предположении компактности допустимого множества задачи.

Глубокие исследования в этой области провели Р.Ж. Хиллестад, СИ. Якобсен и П.П. Бенсел [99, 111, 112, 113]. Р.Ж. Хиллестадом в [111] рассмотрена задача линейного программирования с одним дополнительным обратно-выпуклым ограничением (ЛЗОВП — линейная задача обратно-выпуклого программирования) и к решению этой задачи предложен один метод, основанный на переборе вершин многогранника. В [99] П.П. Бенсел и СИ. Якобсен исследовали также ЛЗОВП и получили для нее специфичные необходимые и достаточные условия локального решения. На основе полученных условий предложили алгоритм решения данной задачи, но его практическое применение встречает серьезные трудности, хотя и доказана сходимость за конечное число шагов. Далее в [112, 113] Р.Ж. Хиллестад и СИ. Якобсен для решения рассматриваемой задачи развили идею комбинирования метода отсечений и перебора вершин многогранника, а также доказали, что выпуклой оболочкой допустимого множества ЛЗОВП является выпуклый многогранник. Ими был предложен алгоритм глобального поиска, в основе которого лежит метод отсечений. В настоящий момент исследование и решение ЛЗОВП продолжается С. Якобсеном и К. Мо-ширвазири [123, 124, 132].

Исследования задачи обратно-выпуклого программирования связаны также с именем X. Туя. [150,152]. Для ее решения им и его учениками разработано семейство методов отсечения, основанное на введенной X. Туем двойственности задач вогнутой минимизации (выпуклой максимизации) и обратно-выпуклого программирования и на идее ранее примененного для задачи вогнутой минимизации метода отсечений для задачи вогнутого программирования. Одним из недостатков метода отсечений в этом случае является отсутствие гарантии нахождения глобального решения. Другим существенными недостатками методов отсечения являются рост числа ограничений на каждом шаге алгоритма и тот факт, что отсекающие плоскости становятся почти параллельными через определенное количество шагов. Неэффективность метода отсечения обсуждалась в работах [100, 101, 102, 110] и подтверждена численными экспериментами в [ПО].

В данной работе для решения задач обратно-выпуклого программирования предложен другой подход, который основан на необходимых и достаточных условиях глобального минимума, полученных А.С. Стрекаловским в [64]. Однако, до работ [45, 147J было не совсем ясно, является ли условие глобальной оптимальности (УГО) конструктивным для построения численных методов решения задачи (RC). Чтобы ответить на этот вопрос, заметим, что проверка УГО сводится к рассмотрению семейства задач, называемых линеаризованными: (Vg{y),x) t max, х Є S, h(x) < h(z), (LQ) где параметр у Є JRⁿ "бегает" по поверхности уровня функции п | д(у) = 0}, (10) а также к последующей проверке условия {Vg{y),x-y)

УГО, очевидно, сохраняет алгоритмическое свойство классических условий оптимальности, заключающееся в следующем. Если нарушено неравенство (11), то есть возможность построить точку, лучшую, чем исследуемая. Можно сказать, что обратно-выпуклая задача (RC) "стоит" семейства линеаризованных задач (LQ), зависящих от параметров, поэтому задача (RC) — несравнимо более трудная, чем выпуклая задача f(x) I min, хе D, (12) где функция /() выпукла и дифференцируема, а множество D выпукло, поскольку задача (12) "стоит", если так можно сказать, лишь одной линеаризованной задачи (V/(z), х) і min, хе D. (10)

К тому же нетрудно заметить, что линеаризованная задача (LQ) является более трудной, нежели линеаризованная задача (10),при условии, что множества D и S будут приблизительно одинаковой структуры и сложности.

Алгоритмы глобального поиска, разработанные на основе УГО, для решения обратно-выпуклых задач были предложены в [45, 147].

В последние четыре десятилетия предметом интенсивного исследования также является перспективный и бурно развивающийся раздел оптимизации — дискретная оптимизация. Здесь разработано большое количество интересных методов поиска решения, которые получили широкое распространение (см., например, [3, 7, 23, 37, 38, 39, 83, 120]). Количество и разнообразие публикаций в этом направлении резко возросло. Существенно расширился и круг специалистов, занимающихся практическими приложениями в этой области. Можно перечислить большое количество разнообразных задач планирования экономики, управления и организации производства, проектирования техники, которые сводятся к выбору лучших в каком-то смысле значений дискретных параметров из некоторого допустимого множества [3, 7, 23, 83, 120]. Заметим, что формально математические модели, отвечающие этим разнообразным по своему содержанию задачам, мало отличаются между собой.

К точным методам в дискретной оптимизации традиционно относятся методы полного перебора, методы ветвей и границ, методы отсечений. Кроме того, в последние время возникают новые подходы к решению дискретных задач. Среди них можно выделить метод регулярных разбиений, предложенный А.А. Колоколовым [26, 38, 39], на основе которого создан метод перебора L-классов для решения задач целочисленного программирования (ЦП). Данный подход основан на лексикографическом упорядочении элементов L-разбиения релаксационного многогранника Q исходной дискретной задачи и заключается в последовательном переборе и исключении L-классов с помощью решения линейных подзадач. В частности, разработаны алгоритмы перебора L-классов для задачи о многомерном рюкзаке [30], а также задач ^. ЦП с интервальными исходными данными [21].

Разработка точных и приближенных алгоритмов с гарантированными оценками точности для решения задач комбинаторной оптимизации, таких как дискретные задачи размещения [20, 42], задачи двухуровневого программирования [57, 126], задачи календарного планирования [18, 43], и упаковки [15, 16, 29], очень интенсивно проводится в Новосибирском научном центре по следующим направлениям: исследование комбинаторной сложности и построение эффективных алгоритмов, например, алгоритмов муравьиной колонии (Ant colony algorithms), основу которых составляют вероятностью жадные алгоритмы, использующие в своей работе накопленную статистическую информацию о процессе поиска [19, 95]; разработка методов локального поиска и построение метаэвристик; . - применение Лагранжевых релаксаций для исследуемых задач.

В данной работе рассматривается также одна задача дискретной оптимизации - задача о многомерном рюкзаке (multiconstraint (multidimentsional) 0-1 knapsack problem) (с, x) t max, (a*,x)<0j, j = 1,...,m, \ (MKP) xe {0,l}ⁿ. Известно [103, 129, 130, 138], что она является ЛГР-трудной даже при га = 1.

Используя возможность представления задачи (МКР) в виде задачи обратно-выпуклого программирования [45, 120], для ее решения применяется стратегия гло- бального поиска, основанная на условиях глобальной оптимальности (УГО). Частный случай задачи (МКР) при т = 1 — задача о рюкзаке — рассмотрен в работе [45], где на впервые основе УГО проведены ее теоретические и численные исследования.

Перейдем к описанию содержания диссертации.

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

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

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

Вторая глава посвящена построению алгоритмов глобальной оптимизации, основанных на результатах первой главы, для задач с линейной целевой функцией и обратно-выпуклым ограничением, заданным не только квадратичными функциями, но и другими нелинейными выпуклыми функциями. Основной целью проведенных исследований было построение алгоритмов, комбинирующих разработанные в первой главе численные методы локального поиска для задачи (RC) и вычислительные процедуры, вытекающие из необходимых и достаточных условий глобальной оптимальности. При этом удалось построить достаточно простую аппроксимацию поверхности уровня д{х) = 0, учитывающую свойства целевой функции, функции, задающей обратно-выпуклое ограничение, и структуру допустимого множества. Приведены также специальные алгоритмы глобального поиска (АГП), разработанные на основе Э?-стратегии из главы 1 с учетом специфики рассматриваемых задач.

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

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

В третьей главе настоящей диссертации рассматривается задача о многомерном рюкзаке (МКР), а также (в качестве вспомогательной) ее частный случай при т = 1 — задача о рюкзаке. Эти задачи сводятся к непрерывным задачам обратно-выпуклого программирования, что дает возможность применить к ним стратегию глобаль- ного поиска, представленную в главе 1.

Решение задачи (МКР) предложенным подходом открывает новую возможность решения задач целочисленного программирования. В первых двух параграфах главы 3 приводятся постановки задач и рассматриваются некоторые практические приложения задач о рюкзаке. Далее для задачи о рюкзаке, как для более простой при исследовании, аналитически строится достаточно простая аппроксимация поверхности уровня, состоящая из 2п+1 точки. В п. 3.5 описывается построение новых оценок сверху на значение задачи о рюкзаке, как это и принято во многочисленных методах решения дискретных задач, причем принцип их построения отличается от построения оценок на основе так называемой LP-релаксации задачи. Далее представлен АГП, разработанный по общей схеме 3?-стратегии с учетом специфики задачи о рюкзаке, приведен новый алгоритм локального поиска и метод исключения координат, позволяющий, если это возможно, снизить размерность исходной задачи.

Проведен успешный численный эксперимент по решению тестовых задач о рюкзаке, который показал, что оценки сверху, полученные в процессе работы АГП точнее оценок, построенных на основе LP-релаксации задачи. Наконец (п. 3.8), на основе метода, разработанного для задачи о рюкзаке в предыдущих параграфах, построен и реализован алгоритм для более общего случая — для задачи о многомерном рюкзаке. В основе алгоритма лежит частичная декомпозиция этой сложной комбинаторной задачи на задачи о рюкзаке с одним ограничением. И в заключение приведен численный эксперимент по решению задачи (МКР).

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

Основные результаты диссертационной работы заключаются в следующем:

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

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

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

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

Основные результаты диссертации опубликованы в работах [46, 47], [71]-(81], [89]-[93], [148] и докладывались на Международной конференции "Распределенные системы: Оптимизация и приложения в экономике и науках об окружающей среде (DSO'2000)" (Екатеринбург, май 2000 г.); Байкальской международной конференции "Методы оптимизации и их приложения" (Иркутск, июнь 2001 г.); Международной конференции "Дискретный анализ и исследование операций" (Новосибирск, июнь 2000 г.); Российской конференции "Дискретный анализ и исследование операций" (Новосибирск, июнь 2002 г.); Международной конференции по оптимизации и оптимальному управлению (Улан-Батор, Монголия, август 2002 г.); Франко-Германо-Польской конференции по оптимизации (Котбус, Германия, сентябрь, 2002 г.); Ляпуновских чтениях и презентации информационных технологий (Иркутск, ноябрь 2002 г.); Второй Восточно-Сибирской зональной межвузовской конференции по математике и проблемам ее преподавания в вузе (Иркутск, март 2003 г.); Всероссийской конференции "Проблемы оптимизации и экономические приложения" (Омск, июль 2003 г.).

Результаты работы обсуждалсь на семинарах лаборатории Методов глобальной оптимизации и на объединенном семинаре Института динамики систем и теории управления СО РАН.

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

Поиск глобального решения в задачах обратно-выпуклого программирования Яковлева Татьяна Владимировна

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