WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 || 3 |

Предлагаемый алгоритм состоит в последовательном решении задач условной оптимизации вида f (x) min, x Sk, (7) k k k k где S = conv{v0,v1,…vn} и v0,v1,...,vn - аффинно независимые точки в пространстве Rn. Каждая из задач (7) решается с помощью алгоритма, предложенного в разделе 1 главы 1. При этом осуществляется k -1 k -последовательный переход от точки x ={arg min f (x)| x S } к точке k k x ={arg min f (x)| x S }, k N, начиная с некоторой начальной точки 0 x0 S0, x ={arg min f (x)| x S }, S0 - произвольный стартовый симплекс.

k Симплексы S строятся с использованием операций отражения и сдвига k -1 k таким образом, что x int S, причем на каждой итерации с номером k выполняется условие fk = f (xk ) < f (xk-1) = fk-1, k N. (8) Итерационный процесс останавливается, когда точка xk становится k внутренней точкой симплекса S.

0 1 k Построенная последовательность симплексов S,S,…,S,… удовлетворяет следующей теореме.

Теорема 1.2. Для любого начального симплекса S0 и любой ограниченной n снизу непрерывной строго унимодальной функции f на пространстве R * n k* найдется такой номер k, что x ={argmin f (x)| x R }intS.

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

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

1 2 f (x) = max{x - c, x - c }, (9) 1 где c = (1,-1), c = -c. Эта функция является непрерывной и строго 1 2 выпуклой, но ее градиент является разрывным всюду на линии x = x.

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

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

f (x) min, (10) при ограничениях Ax = b X :, x Rn, (11) x где f (x) - квазивогнутая функция, b Rm, A - матрица размера m n.

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

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

1.S1 xS0.xxxа) Sx-0.SSxo -v So -1.--2 -1.5 -1 -0.5 0 0.5 1 1.5 x Xmin = 0; Ymin = 0; fmin = 4.б) 3.2.1.0 20 40 60 80 100 120 140 160 Итерации Рис. 1. Последовательность симплексов и сходимость к точке минимума (а) 1 2 и значения функции f (x) = max{x - c, x - c } на каждой итерации (б) 1 y Значения функции В разделе 4 приводится описание основного алгоритма и его обоснование.

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

1. Нахождение точки локального минимума z0, при этом f (z0) = m0 ;

2. Статистическое моделирование направлений поиска области в допустимом множестве с меньшим значением целевой функции (нахождение j соседних с z0 вершин z ; j =1,...,l ); моделирование случайной точки zc, { } имеющей равномерное распределение на выпуклой оболочке conv{z1,..., zl}; нахождение точки wc пересечения луча max h = {zt = z0 + t(zc - z0), t 0} с выпуклым множеством X ( wc = zt, tmax = max{t : zt X}), при этом f (wc) = m < m0 );

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

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

wc X zf x > m( ) zc zf x = m( ) zf x = m ( ) Рис. 2. Графическая иллюстрация метода Корректность работы алгоритма основывается на следующем утверждении.

Теорема 2.2. Обозначим через zM крайнюю точку локального минимума, * найденную после завершения работы алгоритма, а через X множество точек глобального минимума функции f (x). Вероятность события * zM X стремится к единице при неограниченном возрастании M.

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

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

f (x) min, (12) x Rmn, n x = ai, i =1,...m, ij j=X :, (13) m x = bj, j =1,...n, ij i= xij 0, i =1,...m, j =1,...n где f (x) - произвольная квазивогнутая функция в пространстве Rmn вещественных матриц размера m n. Множество в пространстве вещественных матриц размера m n, определяемое ограничениями (13) называется классическим транспортным многогранником порядка m n.

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

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

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

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

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

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

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

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

Рассматривается задача f (x) min, g(x) 0, (15) где, f (x) - квазивогнутая функция на пространстве Rn, g(x) - выпуклая функция, определенная на Rn.

Будем предполагать, что множество X = x Rn | g(x) 0 ограничено.

{ } Допустим, что Q X P, где P и Q – выпуклые многогранные множества, причем вершины множества Q лежат на границе множества X и пусть найдены числа m = min f x | x P, (16) { ( ) } M = min f x | xQ. (17) { ( ) } Если обозначим через m* = min f (x) | x X - искомое значение { } глобального минимума, то m m* M, поэтому если для заданного числа > 0 выполняется неравенство M - m < (18) и x = arg min F(x) | xQ, то план x можно считать -решением задачи { } (15).

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

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

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

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

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

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

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

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

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

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

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

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

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

Для каждого t >1 рассмотрим симплекс 0 0 0 n St = conv V + t(V1 -V ),...,V + t(V -V ). (19) { } Размерность симплекса St равна n -1. Заметим, что если t1 t2, то (20) conv V,S conv V,S.

{ t1} { t2} Определим tmax = max t | St X (21) { } и пусть V St X (рис. 3).

max PStmax VV 3 X V3 VV PРис. 3. Построение многогранника P, содержащего множество X Рассмотрим функцию F t = min g x | x St, где t 1. (22) ( ) { ( ) } Для построения опорной гиперплоскости к множеству X необходимо вычислять значения функции F t. Для решения этой задачи используется ( ) алгоритм, предложенный в разделе 1 главы 1.

Задача определения tmax сводится к задаче нахождения корня функции F t, т.е. к задаче F t = 0. Как показано в предложении 1.2 главы 1, ( ) ( ) функция F t является выпуклой и для нахождения ее корня tmax может быть ( ) использован любой из известных алгоритмов нахождения нуля функции одной переменной. В результате реализации этой процедуры получаем точку V = arg min g x | x St, (23) ( ) { } max находим вершины 0 i Pi = V + tmax V -V, i =1,...,n. (24) ( ) n+Обозначим множество вершин P1,..., Pn через p( ).

1 n Проделав аналогичную процедуру для всех остальных граней,..., 1 n симплекса Q, построим множества p( ),..., p( ). Положим n+1 i P = conv p( ). (25) i=Тогда в качестве оценки снизу для значения задачи (15) можно взять величину (16).

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

k k Если P, Q - многогранники, построенные на k-й итерации алгоритма, k X – часть множества X, оставшаяся на k итерации, то справедливы k k k * k соотношения: Q X P, причем X = Arg min{f (x)x X} X. Тогда k k расстояние Хаусдорфа h(Q, P ) 0 при k. Поэтому для непрерывной функциии f, начиная с некоторого k, будут выполняться неравенства (18).

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

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

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

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

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

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

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

допустимое множество не является полиэдром.

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

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

Pages:     | 1 || 3 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»