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.


 

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

13427. НАСТРОЮВАННЯ ІНТЕРФЕЙСУ ОС WINDOWS 2000 439 KB
  ЛАБОРАТОРНА РОБОТА № 4 НАСТРОЮВАННЯ ІНТЕРФЕЙСУ ОС WINDOWS 2000 1. Мета роботи Ознайомитися з можливостями настроювання інтерфейсу операційної системи Windows 2000 за допомогою програм папки Панель управління та придбати практичні навички у настроюванні елементів інтер
13428. РОБОТА У ФАЙЛОВОМУ МЕНЕДЖЕРІ WINDOWS COMMANDER 358 KB
  ЛАБОРАТОРНА РОБОТА № 5 РОБОТА У ФАЙЛОВОМУ МЕНЕДЖЕРІ WINDOWS COMMANDER 1. Мета роботи Ознайомитися з можливостями програми WINDOWS COMMANDER та придбати навички для її використання у повсякденній діяльності. 2. Задачі роботи 2.1. Освоїти роботу з файловим менеджером WINDOWS COMMAND...
13429. ПРОГРАМА АРХІВАЦІЇ WINRAR 477 KB
  ЛАБОРАТОРНА РОБОТА № 6 ПРОГРАМА АРХІВАЦІЇ WINRAR 1. Мета роботи Навчитися виконувати архівацію файлів документів і програм за допомогою програми архівації WinRAR. 2. Задачі роботи 2.1. Освоїти роботу з програмою архівації WinRAR. 2.2. Придбати практичні навички по архіва...
13430. ОБСЛУГОВУВАННЯ ДИСКІВ ПК ЗА ДОПОМОГОЮ СЛУЖБОВИХ ДОДАТКІВ 437 KB
  ЛАБОРАТОРНА РОБОТА № 7 ОБСЛУГОВУВАННЯ ДИСКІВ ПК ЗА ДОПОМОГОЮ СЛУЖБОВИХ ДОДАТКІВ 1. Мета роботи Навчитися виконувати обслуговування дисків за допомогою службових додатків ОС Windows 2000. 2. Задачі роботи Придбати практичні навички роботи із службовими дода...
13431. ФОРМУВАННЯ ТАБЛИЦЬ В ТАБЛИЧНОМУ ПРОЦЕССОРІ MICROSOFT EXCEL 1.81 MB
  МЕТОДИЧНІ ВКАЗІВКИ ДО ЛАБОРАТОРНОЇ РОБОТИ №1 ФОРМУВАННЯ ТАБЛИЦЬ В ТАБЛИЧНОМУ ПРОЦЕССОРІ MICROSOFT EXCEL 1. Мета заняття Оволодіти практичними навичками роботи в процесі формування електронних таблиць ЕТ та здійснення в них розрахунків. 2. Завдання роботи Оволо...
13432. ПОВЯЗУВАННЯ ТАБЛИЦЬ MICROSOFT EXCEL 494 KB
  МЕТОДИЧНІ ВКАЗІВКИ ДО ЛАБОРАТОРНОЇ РОБОТИ №2 ПОВЯЗУВАННЯ ТАБЛИЦЬ MICROSOFT EXCEL 1. Мета заняття Навчитись працювати і придбати практичні навички роботи з декількома пов'язаними таблицями. 2. Завдання роботи Оволодіти прийомами пов'язування електронних таблиц
13433. ВБУДОВАНІ ФУНКЦІЇ MS EXCEL та ОФОРМЛЕННЯ РОБОЧИХ АРКУШІВ 180 KB
  МЕТОДИЧНІ ВКАЗІВКИ ДО ЛАБОРАТОРНОЇ РОБОТИ №3 ВБУДОВАНІ ФУНКЦІЇ MS EXCEL та ОФОРМЛЕННЯ РОБОЧИХ АРКУШІВ 1. Мета та завдання роботи Придбання навичок роботи з вбудованими функціями Microsoft Excel та оволодіння можливостями оформлення робочих аркушів. 2. Зміст робот
13434. СПОСОБИ ОФОРМЛЕННЯ ДІАГРАМ 350 KB
  МЕТОДИЧНІ ВКАЗІВКИ ДО ЛАБОРАТОРНОЇ РОБОТИ №4 СПОСОБИ ОФОРМЛЕННЯ ДІАГРАМ 1. Мета роботи Метою даної роботи є отримання практичних навичок при побудові редагуванні і оформленні діаграм в табличному процесорі Microsoft Excel. 2. Зміст роботи 2.1 Завантажити оболонку ...
13435. УПРАВЛІННЯ ДАННИМИ В MICROSOFT EXCEL 130.5 KB
  МЕТОДИЧНІ ВКАЗІВКИ ДО ЛАБОРАТОРНОЇ РОБОТИ № 5 УПРАВЛІННЯ ДАННИМИ В MICROSOFT EXCEL 1. Мета заняття Оволодіти навичками роботи з базами даних в Microsoft Excel. 2. Завдання роботи Навчитись: 2.1. Створювати бази даних. 2.2. Створювати форми даних і працювати в них із запи...