36219

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

Доклад

Математика и математический анализ

Задача линейного программирования ЛП – функции критериев qkx и ограничений fix линейны; если хотя бы одна из этих функций нелинейна то имеем задачу нелинейного программирования НЛП. Задача выпуклого программирования – функции критериев qkx и ограничений fix выпуклые. Задача линейного целочисленного программирования – функции критериев qkx и ограничений fix линейны контролируемые входные переменные хj – целые числа. Оценка приращения функции Лемма 6.

Русский

2013-09-21

119 KB

4 чел.

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

Классификация моделей оптимального синтеза

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

В общем случае задачу оптимального параметрического синтеза можно представить в виде

,

где qi – критерии задачи; – вектор неконтролируемых параметров;  – вектор контролируемых входных параметров; D  En – область допустимых решений задачи (ОДР). (Значок вектора в дальнейшем будем употреблять лишь в тех случаях, когда это необходимо чтобы избежать недоразумений.)  Часто ОДР задается в виде системы неравенств

D = {xEn | j fj(x,) 0}.

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

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

1. По степени полноты исходной информации

1.1. Оптимизация в условиях определенности (детерминированная задача) – отсутствуют неконтролируемые параметры: = 0. Ответ задачи – оптимальное значение вектора контролируемых входных параметров xopt.

1.2. Оптимизация в условиях риска (задача стохастического программирования) – вектор параметров полагается случайной величиной с известным законом распределения. Ответ задачи – значение вектора контролируемых входных параметров xopt, который является оптимальным либо с некоторой заданной вероятностью, либо в среднем, т.е. в смысле оптимальности математического ожидания критерия q(x, ).

1.3. Оптимизация в условиях неопределенности  – известны границы изменения компонент вектора , но характер их поведения внутри диапазона неизвестен. Ответ задачи – величина гарантированного эффекта в худшем случае.

1.4. Оптимизация в условиях активного противодействия (игра) – параметрами j управляет некий противник, стремящийся придать им такие значения, которые максимально ухудшают эффективность наших действий. Ответ задачи – стратегия поведения, максимизирующего величину гарантированного эффекта в худшем случае.

2. По свойствам контролируемых входных параметров и функций от них, входящих в критерии и ограничения и, соответственно, по применяемым численным методам решения (при = 0). Схема иерархии моделей приведена на рис. 5.1.

Приведем определения основных задач из данной схемы.

Непрерывные модели – контролируемые входные переменные хj принимают произвольные вещественные значения; дискретные модели – контролируемые входные переменные хj принимают значения из некоторого дискретного (конечного или счетного) множества.

програм

Задача безусловной оптимизации – на значения контролируемых входных переменных хj не наложено ограничений: D = En; при D  En (строгое включение) имеем задачу условной оптимизации.

Задача линейного программирования (ЛП) – функции критериев qk(x) и ограничений fi(x) линейны; если хотя бы одна из этих функций нелинейна, то имеем задачу нелинейного программирования (НЛП).

Задача выпуклого программирования – функции критериев qk(x) и ограничений fi(x) выпуклые.

Задача линейного целочисленного программирования – функции критериев qk(x) и ограничений fi(x) линейны, контролируемые входные переменные хj – целые числа.

Задача динамического программирования – многошаговые процессы специального вида – с отсутствием последействия.

3. По определенности цели

3.1.  Однокритериальные: q(x) – скаляр

3.2.  Многокритериальные: – вектор.

6.3. Методы релаксации 

Идея метода. Пусть имеем задачу:

.

Методы релаксации образуют целый класс численных методов оптимизации. Их суть заключается в следующем. Начиная с некоторой точки х0 строится последовательность х1, х2 ,…, где ,  – некоторый скаляр, – вектор (направление поиска). Вектор поиска указывает направление движения, скаляр указывает расстояние, на которое нужно продвинуться. В каждом конкретном методе этого класса  и  определяются по-своему, но всегда при этом должно выполняться условие релаксации:

qk) > qk+1),

т. е. последовательность {qk)}монотонно убывает.

Согласно известной теореме математического анализа, если монотонно убывающая последовательность ограничена снизу, то она имеет предел. Однако этот предел не всегда может совпадать с минимумом q(x).

Пример 6.5. q(x) = х2; x0 = 1; sk = – 1; . Тогда ; ; ; …;

+  +  +  + … +  = 1 =    =  , хотя min q достигается при х = 0.

Вывод. Нужно специальным образом выбирать  и sk, чтобы последовательность сходилась к точке минимума.

В общем случае, когда функция q(x) достаточно сложна, и имеет несколько локальных минимумов, методы релаксации не позволяют найти точку глобального минимума. Однако они могут гарантировать сходимость к локальному минимуму, т. е. к такой точке, где  (норма градиента равна нулю). Выясним, какими свойствами должна обладать функция q(x), а также как надо выбирать  и sk, чтобы последовательность {xk} сходилась к точке минимума.

Оценка приращения функции

Лемма 6.1. Пусть функция q(x) удовлетворяет условию Липшица для градиентов

||q(x) – q(y) ||  L||xy||.

Тогда для любых х, s  En, > 0 выполняется неравенство:

q(x + s) – q(x)  2 L ||s||2 + (q(x))Ts.                           (6.6)

Следствие. Если (–q(х) )Ts > 0, т.е. вектор s составляет острый угол с направлением антиградиента, то при достаточно малом выполнено условие релаксации.

Теорема о сходимости методов релаксации. Следствие из леммы 6.1 определяет способ выбора направления sk, при котором выполняется условие релаксации, тем самым гарантируется монотонное убывание q(xk). Вопрос о выборе величины шага по результатам теоремы решить нельзя. Достаточно разумным кажется выбор k из условия достижения  q(xk + sk) = k. Это обеспечит максимальное уменьшение q(xk+1).

Однако точный поиск минимума функции даже одной переменной (в данном случае – переменной ) достаточно трудоемок. Как будет показано далее, для сходимости метода вполне достаточно на каждой итерации находить приближенный минимум, чтобы при некотором (0, 1) выполнялось неравенство

q(xk) – q(xk + sk)  [ q(xk) –  k ].                          (6.7)

Геометрический смысл соотношения (7) – на рис. 6.2.

Пояснения. На рис. 6.2 кривая ADE – изменение  функции q(x) в направлении s; точка A соответствует значению q(xk) (при = 0); точка Е соответствует значению q(xk+1) = q(xk + ksk); точка D – значению  k (минимум q(xk + sk)); длина отрезка AC равна величине q(xk) –  k; AB = [ q(xk) –  k ] – правая часть неравенства (6.7); AF = q(xk) – q(xk + sk) – левая часть (6.7). Неравенство (6.7) выполняется, если точка Е попадает между прямыми ВК и CD, т.е. уменьшение функции хотя и не максимально (нет точного попадания в точку D), но достаточно велико – больше длины отрезка АВ. Значение определяет допустимую точность нахождения минимума q(xk + sk): при = 1 минимум находится абсолютно точно.

Теорема 6.1. Пусть выполнены следующие условия.

1) Функция q(x) ограничена снизу, и ее градиент удовлетворяет условию Липшица (6.5).

2) Последовательность {xk} строится по формуле

xk+1 = xk + ksk.                                                 (6.8)

3) Существует > 0, что для любого k величина  (косинус угла между –q(xk) и sk) удовлетворяет неравенству  k, т.е. k не стремится к нулю при k  .

4) Шаг k выбирается из условия выполнения неравенства (6.7).

Тогда ||q(xk)|| 0

Замечание. Данная теорема показывает, что минимум q(xk + sk) не нужно находить очень точно, на сходимость это практически не влияет. Например, q(x) = x2; x0 = –1;  0 = 0.8; q(x0) = 1; q(x1) = (–1+ 0.8)2 = 0.04. Следовательно,   = 1 – 0.04 = 0.96 1, т.е. функция достаточно сильно уменьшилась. С другой стороны * = 1 и отличается от 0 = 0.8 на 20%, т.е. точность нахождения невелика. Это говорит о том, что значение k можно искать достаточно простым методом – например, параболической интерполяцией без итерационного уточнения.

6.4. Алгоритм градиентного метода

В градиентном методе в качестве направления поиска s используется антиградиент целевой функции: sk = – q(xk). Программа, реализующая этот метод, содержит головную программу, функцию argmin вычисления оптимальной длины шага k одномерного поиска/ Используемые имена массивов (векторов) будем обозначать большими жирными буквами, скалярные величины – маленькими обычными.

begin read(X);   eps:= 0.0001;

         repeat G := grad(X);  gn := || G ||;

                    S :=  G;            { Определение направления S }

                    if  gn > eps  then

                    begin := argmin(X, S);  {Поиск минимума q в направлении S}

                              X := X + *S;   

                    end;

         until  gn <= eps;

         writeln(X, fun(X) );

end.

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

s0 = – q(x0);    sk = – q(xk) + k sk – 1.                        (6.11)

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

1) ;               2) ;

3) ;           4) .

Здесь qk = q(xk). Практически не отличаясь по вычислительной сложности от обычного градиентного алгоритма, методы сопряженных градиентов позволяют найти минимум достаточно сложных функций и имеют весьма высокую скорость сходимости. В частности, доказано, что задача минимизации квадратичной функции от n переменных при условии точного нахождения минимумаq(xk +sk) может быть решена ими за число итераций, не больше n.


 

А также другие работы, которые могут Вас заинтересовать

84431. Оценка эффективности привлечения заемного капитала при инвестировании бизнес-центра «Первая Башня» 395.95 KB
  Целью курсовой работы является определение целесообразности приобретения инвестором доходной недвижимости. Для этого определяется предполагаемая доходность объекта и целесообразность привлечения заемного капитала.
84434. Методические указания: Основы управления персоналом 221 KB
  Целью курсовой работы является дальнейшее углубление и специализация знаний и навыков студентов в управлении персоналом в поэлементном, функциональном и объектном разрезах в условиях практического решения реальных проблем.
84436. МЕТОД РАСЧЕТА ЭКОНОМИЧЕСКОЙ ДОБАВЛЕННОЙ СТОИМОСТИ (EVA) 56.72 KB
  Управление факторами влияющими на стоимость компании. Это объяснялось тем что существующие до этого времени методы оценки деятельности фирмы уже не могли удовлетворять растущим требованиям менеджеров поскольку не позволяли оценивать деятельность компании в долгосрочном периоде.
84437. БИЗНЕС-ПЛАН ФИРМЫ «ФОТОС» 369.5 KB
  Результатом настоящего проекта будет являться открытие нового фотосалона и реализация фото-продукции и фото-услуг. Данный фотосалон будет выгодно отличаться от конкурентов наличием новейшего оборудования, позволяющем печатать на множестве различных твердых материалов...
84438. Многофункциональные аварийно-спасательные суда 3.63 MB
  Многофункциональное аварийно-спасательное судно - предназначено для борьбы с аварийными разливами нефти и спасательных операций. Его характерной особенностью является «косой» дизайн с асимметричным корпусом и несколькими винторулевыми колонками, что позволяет судну работать на переднем и заднем ходу...
84439. Усилитель звуковых частот (УЗЧ) 1.56 MB
  Усилители низкой частоты наиболее широко применяются для усиления сигналов, несущих звуковую информацию, в этих случаях они называются, также, усилителями звуковой частоты, кроме этого УНЧ используются для усиления информационного сигнала в различных сферах: измерительной технике...