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.


 

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

46636. Правила оформлення наукової роботи: структура, нумерація, ілюстративний матеріал, загальні правила цитування й покликання на використані джерела, оформлення бібліографічного опису 23.5 KB
  Правила оформлення наукової роботи: структура нумерація ілюстративний матеріал загальні правила цитування й покликання на використані джерела оформлення бібліографічного опису. Структура наукової роботи досить своєрідна. Після нього повинен бути зміст на якому вказується структура наукової роботи. Власне наукова робота починається із вступу в якому вказується актуальність теми мету дослідження завдання роботи теоретичне та практичне значення дослідження тощо.
46637. Традиційні формули звертання в діловому та науковому стилях 23.5 KB
  Традиційні формули звертання в діловому та науковому стилях. Звертання найяскравіший і часто вживаний вид мовленнєвого етикету. Вибір звертання значною мірою залежить від тональності спілкування. В офіційному здебільшого усному спілкуванні послуговуються цим звертанням у поєднанні з прізвищем або назвою особи за фахом чи родом діяльності напр.
46639. Quite and rather 23.5 KB
  Мы часто употребляем quite в позитивных ситуациях, а rather в негативных: She is quite intelligent but rather lazy. Когда мы употребляем rather с позитивными словами
46640. ОСНОВНЫЕ ИТОГИ СОЦИАЛЬНО–ЭКОНОМИЧЕСКОГО РАЗВИТИЯ СССР К ИСХОДУ 30–Х ГОДОВ 23.6 KB
  На наш взгляд в оценке итогов развития страны к началу 40х годов следует учитывать два объективных обстоятельства: вопервых конечный результат вовторых средства и методы с помощью которых он был достигнут. Бесспорно то что в конце 30хгодов были созданы основные конструкции социалистического общества. К исходу 30х годов наша страна вышла с пятого места в1913году на второе место в мире после США по объемам валовой промышленной продукции.
46641. Прогнозирование возможной радиационной обстановки и ее оценка 23.62 KB
  Полученные размеры ОЯП и зон РЗ ВП наносят на карту или схему местности с учетом принятого или фактического направления ветра. Методика прогнозирования и оценки зон РЗ местности при ЯВ. На 1 этапе определяют размеры зон Р3 изображают их на карте схеме местности в соответствующих цветах и находят в какую зону по РЗ попал рассматриваемый объект. На 3 этапе разрабатывают текст оповещения населения об опасности РЗ местности и принимают решения по работе персонала объекта.
46642. Образование единых централизованных государств 23.65 KB
  Экспансия государства была в основе своей экспансией сельского хозяйства которое при всей своей первобытности обнаруживало превосходство над кочевниками Юга и Востока. Жадная требовательность государства и скудость крестьянской базы под господствующими классами порождали самые ожесточенные формы эксплуатации. Национальный гнет в России был несравненно грубее чем в соседних государствах не только по западную но и по восточную границу. Если в национально однородных государствах буржуазная революция развивала могучие центробежные тенденции...