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.


 

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

41092. Загальний опис Visual IFPS/Plus 581 KB
  Інтерактивна система планування фінансів Interctive Finncil Plnning System скорочено IFPS була оригінально розроблена на початку 70х років ХХ ст. Система IFPS набула надзвичайного поширення. З того часу система під назвою Visul IFPS Plus постійно вдосконалювалася.
41093. Система підтримки прийняття рішень PLEXSYS 40 KB
  Система підтримки прийняття рішень PLEXSYS Загальне описання ГСППР PLEXSYS Одним із найперспективніших напрямів розвитку СППР є створення групових систем підтримки прийняття рішень ГСППР. Дослідження галузі ГСППР дають змогу переглядати ролі й обов’язки в групових діях пов’язаних із оцінюванням ситуації виявленням і генеруванням ідей діалектикою обговорення а також розв’язанням інших завдань які приводять до прийняття групових рішень. ГСППР об’єднують комунікації обчислення і технологію підтримки рішень з тим щоб допомогти деякій...
41094. Архітектура СППР та суміжні питання 50 KB
  Архітектура СППР та суміжні питання Архітектура СППР визначається характером взаємодії основних її складових інтерфейсу користувача; бази та сховища даних документів і правил; моделей і аналітичних інструментів; інфраструктури комунікацій і мереж а також елементів цих частин. Ефективне поєднання всіх елементів СППР дає змогу уникнути ряду труднощів щодо побудови СППР і підвищити продуктивність комп’ютерної системи за рахунок: особливої інтеграції бази даних СППР з іншими внутрішніми і зовнішніми базами даних; скорочення тривалості...
41095. Компоненти користувацького інтерфейсу 655 KB
  Призначення та загальні ознакикористувацького інтерфейсу Важливість та ефективністькористувацького інтерфейсу СППР Комп’ютерні системи підтримки прийняття рішень призначені для розв’язування завдань користувачами а тому невіддільною складовою їх роботи має бути точне дотримання вимог щодо деяких параметрів здобутих від користувачів урахування їх побажань за проектування системи. При цьому якщо система функціонує коректно але подає результати у спосіб який є незручним для користувача то роботу такої системи не можна вважати задовільною...
41096. НЕОБХОДИМОСТЬ ДЕНЕГ, ИХ ВОЗНИКНОВЕНИЕ И СУЩНОСТЬ 656.5 KB
  Деньги возникают при определенных условиях осуществления производства и экономических отношений в обществе и способствуют дальнейшему их развитию.
41097. СИСТЕМА БЕЗНАЛИЧНЫХ РАСЧЕТОВ 627.73 KB
  Сущность принципы организации и значение безналичных расчетов. Аккредитивная форма расчетов ее сущность и сфера применения. Денежные средства на расчетных и других аналогичных счетах в банках отражаются посредством записи остатков оборотов по лицевым счетам вследствие безналичных расчетов.
41098. Коммерческие банки. Сущность и организационная основа деятельности коммерческих банков 103.42 KB
  Принципы деятельности коммерческого банка. Функции коммерческого банка Банки одно из центральных звеньев системы рыночных структур. Основное назначение банка –посредничество в перемещении денежных средств от кредиторов к заемщикам и от продавцов к покупателям. Наряду с банками перемещение денежных средств на рынках осуществляют и другие финансовые и кредитнофинансовые учреждения: инвестиционные фонды страховые компании брокерские дилерские фирмы и т.
41099. Управление заемным капиталом 1.25 MB
  Обеспечение своевременных расчетов по полученным кредитам На второй стадии анализа определяются основные формы привлечения заемных средств анализируются в динамике удельный вес сформированных финансового кредита товарного кредита и текущих обязательств по расчетам в общей сумме заемных средств используемых предприятием. Эти формы дифференцируются в разрезе финансового кредита; товарного коммерческого кредита; прочих форм. К числу важнейших из этих условий относятся; а срок предоставления кредита; б ставка процента за кредит;...