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

• Автор: Цэвээндоржийн Идэр
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1996
• Место защиты: Иркутск
• Количество страниц: 103 с.

1 Теория методов решения задач обратно-выпуклого программирования

1.1 Необходимые и достаточные условия глобальной оптимальности

1.2 Минимизирующие последовательности

1.3 Теоретический метод глобального спуска в задаче (РИ)

2 Алгоритм глобальной оптимизации для задачи с квадратичным обратно - выпуклым огранц^ени^ц,

2.1 Построение алгоритЗвд, решения задачи (РК)

2.2 Сходимость .й-алгоритма

2.3 Пример разрешающего набора для одной частной задачи

3 Численные эксперименты

3.1 Численное решение й-алгоритмом одной квадратичной тестовой задачи

3.1.1 Постановка тестовой задачи

3.1.2 Метод локального спуска
3.1.3 К решению задачи (ЬР3)
3.1.4 К решению линеаризованной задачи
3.1.5 Численные результаты и их анализ
3.2 К решению задачи о рюкзаке Д-апгоритмом
3.2.1 Постановка задачи и переход от целочисленной к непрерывной
задаче
3.2.2 Метод локального подъема в задаче о рюкзаке
3.2.3 О связи задач (Ра), {РК)
3.2.4 Метод решения ”линеаризованной задачи”в задаче {Ру)
3.3 Численное решение задачи о рюкзаке Д-алгоритмом
Список литературы

В последние два десятилетия проблемы глобальной оптимизации приобретают все большее и большое значение. Это связано, во-первых, с бурным ростом интереса к многоэкстремальным задачам со стороны экономистов, экологов и специалистов, занимающихся проблемами обработки информации, во-вторых, с тем, что с появлением быстродействующих ЭВМ стало возможным эффективное решение многих важных прикладных задач, которое ранее из-за своей сложности представлялось недоступным [1, 15, 44, 46].
Многие задачи оптимизации встречающиеся в экономике и технике, описываются в виде:
/(ж) -> min, х £ D = {х / gi(x) <0, i = 1 ,га}. (1)
Если в задаче (1) все фигурирующие при ее описании функции /(•), выпуклы, то такая задача называется выпуклой и к настоящему времени разработано и исследовано большое число методов ее решения (см. напр, литературу в [15]).
Однако большинство реальных задач не может быть адекватно описано с помощью моделей выпуклого программирования из-за многоэкстремальности целевой функции или невыпуклости допустимого множества D.
Нахождение глобального решения в таких задачах в общем случае является чрезвычайно сложным. В теории оптимизации направление, связанное с поиском глобальных экстремумов, развито недостаточно в частности из-за большой сложности этой проблемы.
Поэтому методы поиска глобального экстремума являются в настоящее время предметом интенсивных исследований.
Известные методы поиска делятся на детерминированные и стохастические, которые, в свою очередь, могут быть эвристическими или строго обоснованными. Простейший и наиболее широко используемый метод ’’мультистарт”состоит в проведении ряда оптимизационных расчетов при различных начальных условиях. В этом методе начальные точки выбираются из определенной сетки или же генерируются случайным образом и осуществляется локальный поиск из каждой такой точки по отдельности. [-30,36]
К сожалению, в сложных прикладных задачах поиск локального экстремума сам по себе трудоемок, так что возможности комбинирования его со случайным выбором

xs = рг/ п(ж5 + ashs),
где рг/п(р)-проекция точки р на множестве П, а число обретение задачи одномерной минимизации:
Фз(а) = f(xs + ah3) —> min, а > 0. (3.1)
В данном случае (при заданной функции /(•)), нетрудно видеть, что число
{hs, у - Xs)
ЗІІ2
решает задачу (3.1).
2. Если
то полагать
3. Если
||лg(xs) > о,
д(х3) < 0,
то полагать
т5+1 :=рвГ + {1-р3)х% где /?8 решение уравнения
д(рх* + ( 1-/3)0
относительно /3 на отрезке [0,1].
Из структуры функции д(-) и из неравенств
д(х*) < 0, д(х3) >
вытекает, что существует решение данного уравнения на отрезке [0,1] и оно имеет вид
А = - А€|0.1[,
(6 (ж — х“), х — хв)

(Сxs, xs —Xs) А 2 • g(xs)
,{C{xs — xs), xs — х‘) J (C{xs — Xs), Xs — Xs) • В) Случай g(xs) = 0.
1. Положить
(f (x°), g'(x*)),
I Ip'Mil2
При таком выборе As, если (/' (xs) ,g' (О) > 0, то направление /' (О — Ag' (ж£)будет ортогональным с g‘ (xs) т.е.
{/'(*')-W(**),$V)>