МЕТОД ВОЗМОЖНЫХ НАПРАВЛЕНИЙ

Идея метода возможных направлений МВН заключается в том что в каждой очередной точке находится направление спуска такое что перемещение точки по этому направлению на некоторое расстояние не приводит к нарушению ограничений задачи. Направление определяемое вектором называется возможным направлением в точке если достаточно малое перемещение из в направлении не выводит точку за пределы допустимой области т. Очевидно если является внутренней точкой множества то любое направление в этой точке является возможным. Возможное...

2014-07-08

113.98 KB

74 чел.


Поделитесь работой в социальных сетях

Если эта работа Вам не подошла внизу страницы есть список похожих работ. Так же Вы можете воспользоваться кнопкой поиск


Лекция №13

МЕТОД ВОЗМОЖНЫХ НАПРАВЛЕНИЙ

Рассмотрим задачу выпуклого программирования

                                              (13.1)

где допустимая область  задается так

 (13.2)

Поскольку функции , ,..,  предполагаются выпуклыми, то в силу рассмотренных ранее свойств выпуклых функций задача (13.1)-(13.2) есть задача минимизации выпуклой функции на выпуклом множестве.

Введя в рассмотрение индексные множества

, ,

имеем

.    (13.3)

Для сокращения записей обозначим

,

Тогда ЗВП запишется в виде

.

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

Для описания метода возможных направлений введем ряд определений.

Определение 13.1. Направление, определяемое вектором , называется возможным направлением в точке , если достаточно малое перемещение из  в направлении  не выводит точку за пределы допустимой области, т.е., если существует такое число , что  для всех .

Очевидно, если  является внутренней точкой множества , то любое направление в этой точке является возможным.

Определение 13.2. Возможное направление, определяемое вектором , называется подходящим направлением в точке , если перемещение из точки  по этому направлению осуществляется с уменьшением значения функции, т.е., если .

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

Следствием введенных определений является утверждение: если в точке  подходящих направлений нет, то функция  достигает в этой точке своего минимума на множестве , т.е.

.

В самом деле. Пусть в точке  нет ни одного подходящего направления, т.е. для любого вектора  в точке  выполняется неравенство . Тогда при перемещении из точки  по любому из этих направлений функция  не убывает

.

Следовательно,  - точка локального минимума .

Вычислительные алгоритмы метода возможных направлений

Метод возможных направлений осуществляется следующим образом.

1. Точка начального приближения находится в допустимой области .

2. Последовательность точек , принадлежащих , строится так, чтобы выполнялись неравенства  . При этом, строя точку  так, чтобы выполнялось неравенство

, обнаруживаем, что либо  не ограничена, либо такой точки не существует, т.е. - оптимальная точка. В обоих случаях процесс решения задачи прекращается. Задача решена.

Процедура построения точки состоит из двух этапов:

а) в точкеопределяется подходящее направление ,

б) определяется длина шага  такая, что  принадлежит  и . Так как направление  подходящее, то при этом оказывается, что .

3. Выбор подходящих направлений  в точках  производится так, что обеспечивается сходимость значений  к , либо обнаруживается, что последовательность  не ограничена.

Методы возможных направлений можно рассматривать как градиентные методы с конечным шагом. Многие методы линейных и нелинейных задач математического программирования можно трактовать как методы возможных направлений. Они различаются лишь дополнительными требованиями к выбору начальной точки , направления  и длины шага . В частности к таким методам относится и симплекс- метод решения ЗЛП.


Построение начального приближения

  1.  Строим точку , где С – заданный вектор.
  2.  Располагая точкой , вычисляем значения функций

, .

Если значение функции , то точка  удовлетворяет -му линейному ограничению задачи, т.е. выполняется неравенство .

Если число , то в точке  не выполняется условие  и, следовательно, точка  не удовлетворяет -му линейному ограничению задачи.

  1.  Введем в рассмотрение неотрицательные числа , положив  для тех индексов , для которых  и  положив  для тех индексов, для которых .
  2.  Вводим дополнительную переменную , увеличивая тем самым размерность вектора неизвестных на единицу, и в (n+1)-мерном пространстве  формируем следующую задачу:

(13.4)

Таким образом, получим в (n+1)-мерном пространстве задачу минимизации линейной функции на множестве, задаваемом линейными ограничениями, т.е. задачу линейного программирования, которая решается за конечное число шагов симплекс-методом. При этом в качестве начального опорного плана можно выбрать точку

.

В качестве  можно взять.

Решая вспомогательную задачу (13.4) симплекс-методом, за конечное число шагов получим оптимальный план, в котором . Тогда первые n компонент этого опорного плана определят точку , которая будет удовлетворять всем линейным ограничениям исходной задачи, т.е.

.

  1.  Вычисляем . Задаем неотрицательные числа  и полагаем  для тех индексов , для которых  и  для тех индексов, для которых .
  2.  Вводим дополнительную переменную  и формулируем еще одну вспомогательную задачу, следующим образом:

   (13.5)

Это есть задача выпуклого программирования, для которой известна начальная точка с координатами

Если выбрать в качестве , тогда начальная точка будет . Очевидно, если в ходе решения ЗВП (13.5) на каком-то шаге получим , то есть вектор , то соответствующий вектор  определит искомую точку , которая будет являться начальной точкой исходной задачи.

Теорема 13.1. Если  непусто и регулярно по Слейтеру, то, применяя для решения задачи (13.5) метод возможных направлений, получим  за конечное число шагов.

Д о к а з а т е л ь с т в о. Допустим, что задача (13.5) решается методом возможных направлений без требования . В силу условия Слейтера существует точка   такая, что  для всех , тогда ограничения ,  допускают существование точки с компонентой . Так как  минимизируется, то последовательность значений минимизируемой функции  будет сходиться к значению . При этом, даже если оптимальное значение является пределом сходящейся последовательности,  становится неположительным за конечное число шагов. Следовательно, при условии  оптимальное значение  достигается за конечное число шагов.

Замечание. Вместо того, чтобы последовательно удовлетворять сначала линейным, а затем нелинейным ограничениям, можно, избегая пунктов 5 и 6 и имея точку , сразу решить задачу

(13.6)

где  для тех индексов , для которых .

Задача (13.6) является задачей выпуклого  программирования, для которой за нулевое приближение можно взять точку

Однако, решение задачи (13.6) является более сложным, чем решение задач, которые рассматривались на шагах 5 и 6.

Определение подходящего направления

Для описания алгоритма выбора наилучшего направления поиска очередной точки минимизирующей последовательности введём ряд важных понятий.

Определение 13.3. Ограничение  (  ) называется

активным в фиксированной точке , если

 (  ).

Введём в рассмотрение множества индексов активных ограничений

в фиксированной точке :  - индексное множество активных нелинейных ограничений;  - индексное множество активных линейных ограничений;

; .

Введем в рассмотрение множество n-мерных векторов  в точке  и построим множество

Множество представляет собой конус возможных направлений в точке . Если  - внутренняя точка множества R, то множество  пусто, т.е. в этой точке  нет активных ограничений, и на выбор вектора S не накладывается никаких ограничений.

Введем искусственную переменную  и определим множество (n+1)-мерных векторов  следующим образом:

.

Задачу выбора подходящего направления сформулируем как задачу линейного программирования:

.          (13.7)

Очевидно, что при  множества и  совпадают. Если , то из ограничения  следует, что  и направление  будет подходящим. В этом случае , т.е.  не направлено по касательной к нелинейным границам. При этом, чем больше , тем больше отличается от нуля , т.е. тем больший угол образуется между  и внешней нормалью . Если, то точка  оказывается точкой минимума функции .

Присутствие в задаче (13.7) ограничения  объясняется следующим образом. Когда речь идёт о выборе направления, нас интересует именно направление, которое задаётся некоторым вектором произвольной длины. Но при решении ЗЛП (13.7) величина  может оказаться неограниченной. Чтобы этого избежать следует наложить на длину S некоторые ограничения. Поэтому в постановке задачи (13.7) должно присутствовать так называемое условие нормализации. Таким условием может быть одно из следующих ограничений:

№1..

№2.

№3.если   или   если  

№4.

Признак оптимальности в задаче выбора наилучшего подходящего направления устанавливается следующей теоремой.

Теорема 13.2. Точка  является точкой минимума  на , регулярном по Слейтеру тогда и только тогда, когда  для всех , удовлетворяющих неравенству .

Д о к а з а т е л ь с т в о.Если в решении  задачи выбора направления (13.7) окажется, что , то соответствующее направление  будет подходящим, и точка  не может быть точкой минимума функции .

Пусть теперь  для всех , удовлетворяющих условиям

(13.8)

(13.9)

(13.10)

Будем считать для сокращения записей, что в (13.10) содержатся также и прямые ограничения на переменные задачи .

Введя в рассмотрение  - мерные вектора ,  неравенство  можно записать в виде

В силу теоремы Фаркаша, устанавливающей равносильность условий

,

найдется такой вектор , , что имеют место равенства

(13.11)

(13.12)

Если , т.е. , то из (13.11)

,                  (13.13)

Умножая скалярно равенство (13.13) на некоторый произвольный вектор , принадлежащий множеству  получим

.

Но в множестве  выполняются условия  и  для любого . Следовательно,  для любого , а значит в точке  нет подходящего направления и она является точкой минимума функции  на .

Если , то из условия  и равенства (13.12) следует существование по крайней мере одного , . Тогда умножая (13.11) на  

                            (13.14)

Но из регулярности по Слейеру следует существование точки  такой, что  для всех . Тогда, полагая , в силу теоремы 12.5  имеем

т.к. , а . Таким образом, хотя бы одно из слагаемых в (13.14) строго меньше нуля а все остальные неположительны. Поэтому левая часть равенства (13.14) не может быть равна нулю, т.е. случай  невозможен. Теорема доказана.

Контрольные вопросы

1. В чем заключается основная  идея метода возможных направлений?

2. Какое направление  называется возможным в допустимой точке?

3. Поясните понятие подходящего направления в допустимой точке.

4. Какие ограничения называются активными в фиксированной точке?

5. Какой метод решения задачи выпуклого программирования называется методом возможных направлений?

6. Приведите алгоритм построения начального приближения в методе возможных направлений.

7. Опишите процедуру построения очередной точки минимизирующей последовательности в методе возможных направлений.

8. Дайте определение конуса возможных направлений в точке.

9. Опишите постановку вспомогательной задачи для выбора наилучшего подходящего направления в допустимой точке.

10. Сформулируйте признак оптимальности в задаче выбора наилучшего подходящего направления в допустимой точке.

PAGE  142



 

Другие похожие работы, которые могут вас заинтересовать.
2242. Определение длины шага в методе возможных направлений 65.84 KB
  Очевиден геометрический смысл доказанной теоремы. Её можно рассматривать как теорему об аппроксимации. А именно, на основании этой теоремы можно утверждать, что если мы начинаем итерационный процесс в допустимой точке, то наибольшее уменьшение минимизируемой функции не может быть больше уменьшения минимизируемой функции в линеаризованной задаче.
14446. ХАРАКТЕРИСТИКА КОММУНИКАТИВНЫХ БАРЬЕРОВ И ВОЗМОЖНЫХ СПОСОБОВ ИХ ПРЕОДОЛЕНИЯ 608.46 KB
  Новизна работы заключается в том что теоретически мы объясняем происхождение барьеров через теорию речевых актов Дж. Практическая значимость определяется тем что мы смогли применить приемы и правила преодоления коммуникативных барьеров с целью совершенствовать навыки их преодоления при проведении ряда занятий с ребятами изучающими иностранный язык а затем увидеть результат в ходе встречи и коммуникации с носителем иностранного языка. Ричардс: коммуникация имеет место когда одно человеческое сознание так действует на окружающую его среду...
13675. Нахождение возможных путей совершенствования учета производственных запасов 91.08 KB
  ля успешного решения задач учёта семян и кормов сельскохозяйственное предприятие должно правильно организовать складское хозяйство; располагать рациональной системой первичных и сводных документов и правильно организованным документооборотом; рационально организовать синтетический и аналитический учёт товарно-материальных ценностей; обеспечить систематический контроль за поступлением, расходованием и сохранностью запасов путём учёта их по местам хранения и материально ответственным лицам
11583. Классификация возможных угроз, требующих действий подразделений гражданской обороны России 613.74 KB
  Региональные войны – это войны более крупного масштаба которые будут проводиться с целями: разгрома основных военных сил России на территории военных действий ТВД захвата значительной части территории ослабления военно-политического руководства и содействия территориальному распаду России ослабления международной позиции России окончательного размывания и распада СНГ и системы межгосударственных отношений. Наиболее характерными чертами будут: скрытность подготовки и внезапность развязывания агрессии; массированное применение...
17426. Развитие кубизма как одно из направлений в искусстве 374.08 KB
  Его представители – Пабло Пикассо Жорж Брак Фернан Леже Робер Делоне – исповедовали настоящую страсть к эксперименту поиску новых выразительных средств и приемов. Считается что появление кубизма стало результатом влияния на мировосприятие его основоположников Пикассо и Брака привезенной тогда в Европу африканской...
13725. Разработка направлений повышения конкурентоспособности ООО «РОХО» 264.26 KB
  Сущность и содержание конкурентоспособности предприятия. Методы анализа конкурентоспособности предприятия. Факторы конкурентоспособности предприятия. Краткая характеристика предприятия.
18837. ИССЛЕДОВАНИЕ ИДЕЙНО-ХУДОЖЕСТВЕННЫХ НАПРАВЛЕНИЙ КОЛЛЕКЦИИ 10.2 MB
  Общаясь с клиентом мастер в своем воображении рисует всевозможные творческие решения и подбирает варианты максимально подходящие именно для этого человека. А при этом мастерство и творческое воображение парикмахера-модельера - главное условие для создания яркого и неповторимого образа. Для того чтобы создать реальную жизненную прическу показать в ней характерное и типичное необходимо все время наблюдать отбирая главное наиболее важное для воссоздания замысла.
859. Анализ основных направлений современной налоговой политики РФ 38.27 KB
  Элементы цели и типы налоговой политики. Анализ основных направлений современной налоговой политики РФ. Основные направления налоговой политики Российской Федерации на перспективу. Меры в области налоговой политики планируемые к реализации в 2014 году и плановом периоде 2015 и 2016 годов.
11433. Определение направлений современных глянцевых изданий и перспектив их развития 1.18 MB
  Влияние на молодых женщин и девушек развлекательных СМИ к которым относятся глянцевые журналы в настоящее время значительно. Валентинов в одной из статей окрестил современные глянцевые журналы для женщин Библией для девушек. Так называемые глянцевые журналы mgzine среди печатных СМИ являются аналогом модных развлекательных телеканалов. Все это имеет отношение и к производству и потреблению глянцевых журналов когда все более усиливается давление на аудиторию со стороны производителей рекламы.
3613. Разработка основных направлений развития логистической системы Республики Беларусь 92.73 KB
  Географическое положение Беларуси предопределяет ее роль в качестве транзитного государства. Находясь на перекрестке основных транспортных маршрутов, связывающих государства Западной Европы с двумя мощными региональными рынками – Россией и странами Юго-Восточной Азии
© "REFLEADER" http://refleader.ru/
Все права на сайт и размещенные работы
защищены законом об авторском праве.