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.


 

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

78670. Инновационная стратегия фирмы 33.5 KB
  Инновационная стратегия фирмы. Обычно к таким стратегиям относят. Стратегия непрерывного совершенствования кайзен продукции. Инновационная стратегия целенаправленная деятельность по определению приоритетов перспективного развития организации и их достижению в результате которой обеспечивается новое качество производства и управления.
78671. Прогрессивные формы организации инновационной деятельности :бизнес-инкубаторы, технопарки, технополисы 31 KB
  Инновационная деятельность это процесс направленный на реализацию результатов законченных научных исследований и разработку иных научно технических достижений интеллектуального продукта. Отличительные черты: комплексность по научнопроизводственному циклу научные учреждения вузы промышленные предприятия компактность расположения ограниченность площади расположение в экологически чистых районах. Технополис – научнотехнический комплекс соединяющий научнотехническую деятельность с наукоемким производством с хорошо развитой...
78672. Экономическая безопасность государства и механизм ее реализации 43 KB
  Проблемы обеспечения экономической безопасности страны стабильного экономического развития государства и общества стоят перед многими странами мира. Современное социально-экономическое положение России обусловливает чрезвычайную актуальность целенаправленной деятельности государства в сфере обеспечения экономической безопасности страны российского общества и каждого гражданина в отдельности. Например США разрабатывают доктрину концепцию и стратегию своей национальной безопасности где особое место уделено вопросам экономической...
78673. Предпринимательство как вид экономической деятельности. Виды предпринимательства 35 KB
  Виды предпринимательства. Рыночная экономика экономика свободного предпринимательства. В зависимости от содержания и направленности предпринимательской деятельности объекта приложения капитала и получения конкретных результатов связи предпринимательской деятельности с основными стадиями воспроизводственного процесса различают следующие виды предпринимательства. Коммерческое торговое предпринимательство Принцип организации торгового предпринимательства несколько отличается от производственного так как предприниматель выступает...
78674. Инфраструктурное обеспечение предпринимательской деятельности 25 KB
  система общих условий воспроизводства предпринимательского типа представляющая собой совокупность техникотехнологических организационноэкономических и социальных взаимосвязей тех элементов инфраструктуры которые обеспечивают обслуживание процесса предпринимательства на уровне макро мезо и микроэкономики. являются научность и системность в формировании и развитии предпринимательства и его инфраструктуры а также постепенность и многообразие моделей инфраструктурного обеспечения предпринимательства. Прежде всего нужна трансформация...
78675. Виды и формы предпринимательской деятельности 39 KB
  Рыночная экономика экономика свободного предпринимательства. В зависимости от содержания и направленности предпринимательской деятельности объекта приложения капитала и получения конкретных результатов связи предпринимательской деятельности с основными стадиями воспроизводственного процесса различают следующие виды предпринимательства: 1. Коммерческое торговое предпринимательство Принцип организации торгового предпринимательства несколько отличается от производственного так как предприниматель выступает непосредственно в роли...
78676. Государственное регулирование предпринимательской деятельности 28.5 KB
  Целью государственного регулирования предпринимательской деятельности является создание определенных условий обеспечивающих нормальное функционирование экономики в целом и стабильное участие предпринимателей страны в международном разделении труда и получение от этого оптимальных выгод. В обобщенном виде в задачи государственного регулирования входят: разработка принятие и контроль за законодательством обеспечивающим правовую основу и защиту интересов предпринимателей; повышение эффективности государственного регулирования и снижение...
78677. Малое предпринимательство, его фин-экон и организационные особенности 41.5 KB
  В современных условиях роль малого бизнеса в рыночной экономике растет. Функции малого бизнеса: Экономические функции малого бизнеса: Придает рыночной системе необходимую гибкость активизация структурных сдвигов процессов разгосударствления и приватизации. Социальные функции малого бизнеса: Обеспечивает рост занятости. Но все перечисленные достоинства малого бизнеса проявляются отнюдь не автоматически.
78678. Среднее и крупное предпринимательство 30.5 KB
  Формы взаимодействия малого среднего и крупного бизнеса в рамках сетевой экономики В современной развитой рыночной экономике малый бизнес оказывается подчинен крупному бизнесу через систему подрядов и субподрядов. Крупному бизнесу как правило обеспечивает гарантию возврата кредита и обеспечивает устойчивые долгосрочные отношения с подрядчиком или субподрядчиком . С помощью франчайзинга малый бизнес получает возможность стабилизировать внешнюю среду обеспечить конкурентные преимущества. Крупный бизнес расширяет сферу контроля над рынком и...