Определение длины шага в методе возможных направлений

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

2014-07-08

65.84 KB

1 чел.


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

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


Лекция №14

Определение длины шага в методе возможных направлений

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

Эту задачу удобно решать в два этапа:

1. На первом этапе определим  число . То есть определим значение , при котором луч  пересекает границу допустимой области R. Это достигается нахождением корней уравнений

 

и выбором из них наименьшего положительного.

2. Далее выбираем число .

Если минимум достигается в точке , не принадлежащей области R, то в качестве длины шага выбираем значение . Если же минимум достигается в точке , то в качестве длины шага выбираем значение .

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

Оценка погрешности приближенного решения

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

Как оценить близость полученной точки  к неизвестному решению  исходной задачи

,

где .

Алгоритм такого оценивания вытекает из следующей теоремы.

Теорема 14.1. Для любой точки  и любой функциивыпуклой на выпуклом множестве R  справедливо неравенство

,  ( 14.1   )

где

.

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

.

С другой стороны, для любой точки    выполняются условия :

,  и  

или . Тогда, если вместо ограничений  исходной задачи использовать в качестве ограничений только что полученные неравенства, то мы будем иметь «более пухлое множество», содержащее в себе. Но тогда

.

Обозначая , получим

.

Теорема 14.1 доказана.

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

Линеаризованную задачу получаем заменой минимизации функции

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

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

Пример 14.1. Решить задачу выпуклого программирования

где

,

Выполним одну итерацию рассмотренного метода возможных направлений.  В качестве начального приближения выберем точку =(2;0).

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

=ø;

.

Поставим задачу выбора наилучшего подходящего направления  в точке Х0 как задачу линейного программирования с нормализацией №3:

.

Здесь - искомый вектор; - вспомогательная переменная;  - градиенты соответствующих функций в точке , то есть векторы

.

Итак, имеем задачу в виде

Решим её симплекс-методом. Вначале, с целью уменьшения числа строк последующей симплекс-таблицы, перейдём к новым переменных по формулам

Далее, для  приведения задачи к канонической форме, введём дополнительные переменные, заменяя величину  с неопределённым знаком на разность двух неотрицательных переменных  и  преобразуем ограничения типа неравенств в ограничения- равенства.  В результате этих действий наша ЗЛП запишется так:

Дальнейший процесс решения ЗЛП отражён в следующих симплекс-таблицах:

С

0

0

1

-1

0

0

N

C

P

B

A1

A2

A3

A4

A5

A6

t

1

0

A5

12

6

6

1

-1

1

0

12

2

0

A6

1

0

1

1

-1

0

1

1

0

0

0

-1

1

0

0

1

0

A5

11

6

5

0

0

1

-1

2

1

A3

1

0

1

1

-1

0

1

1

0

1

0

0

0

1

Итак, задача решена за две итерации симплекс-метода и найден её оптимальный план , из которого получаем . Тогда вычисляем значения компонент вектора, указывающего наилучшее подходящее направление, а именно .

Таким образом, в результате решения задачи выбора в точке Х0=(2;0) подходящего направления найден вектор S0=(1;1). Построим луч, исходящий из точки Х0 по направлению найденного вектора : 

Определим длину шага  в этом направлении.

Для этого найдём вначале то значение , при котором луч  пересекает границу допустимой области R. То есть найдём положительные корни уравнений

,

а именно, уравнений

,

или . Отсюда найдутся корни

.

Таким образом, величина . Далее, определим значение , при котором функция  достигает минимума по . Для этого приравняем к нулю производную этой функции по  и найдём корень полученного уравнения:

Отсюда получим, что . Следовательно, искомое значение длины шага . Завершая итерацию, находим новую точку.

Первая итерация полностью выполнена.

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

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

2. Из какого условия вычисляется наибольшее значение длины шага?

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

4. Какое число окончательно выбирается в качестве длины шага?

5. С какой целью рассматривается задача оценивания погрешности приближённого решения ЗВП методом возможных направлений?

6. Какой алгоритм оценивания погрешности приближённого решения ЗВП можно предложить на основании доказанной аппроксимационной теоремы?

7. Поясните геометрический смысл аппроксимационной теоремы.

8.  Как осуществляется линеаризация исходной задачи при формировании задачи оценивания погрешности приближённого решения ЗВП методом возможных направлений?

9. Остаётся ли справедливым неравенство ( 14.1) , если точка окажется точкой минимума функции  в допустимой области  R?

PAGE  151



 

Другие похожие работы, которые могут вас заинтересовать.
2243. МЕТОД ВОЗМОЖНЫХ НАПРАВЛЕНИЙ 113.98 KB
  Идея метода возможных направлений МВН заключается в том что в каждой очередной точке находится направление спуска такое что перемещение точки по этому направлению на некоторое расстояние не приводит к нарушению ограничений задачи. Направление определяемое вектором называется возможным направлением в точке если достаточно малое перемещение из в направлении не выводит точку за пределы допустимой области т. Очевидно если является внутренней точкой множества то любое направление в этой точке является возможным. Возможное...
11433. Определение направлений современных глянцевых изданий и перспектив их развития 1.18 MB
  Влияние на молодых женщин и девушек развлекательных СМИ к которым относятся глянцевые журналы в настоящее время значительно. Валентинов в одной из статей окрестил современные глянцевые журналы для женщин Библией для девушек. Так называемые глянцевые журналы mgzine среди печатных СМИ являются аналогом модных развлекательных телеканалов. Все это имеет отношение и к производству и потреблению глянцевых журналов когда все более усиливается давление на аудиторию со стороны производителей рекламы.
390. Исследование электрического поля при замыкании на землю. Напряжение прикосновения и шага 77.44 KB
  Напряжение прикосновения и шага Цель работы Изучить закономерность распределения потенциалов вблизи заземлителя при стекании электрического тока в землю исследовать основные параметры напряжения прикосновения и шага и научиться определять опасные зоны. Определить величину напряжения прикосновения и шага и их зависимость от расстояния от человека до места утечки тока в землю. Изучить способы уменьшения опасности поражения напряжением шага и прикосновения. Если человек прикоснется к этому корпусу то он окажется под напряжением...
19416. Программное обеспечение для автоматической коррекции шага спиральной нарезки металлопленочных резисторов 628.55 KB
  Блок схема АСУТП лазерной подгонки в номинальное значение цилиндрических металлических резисторов. Электромагнит цанг ЭМЦ разводит цанги в которые электромагнит загрузки ЭМЗ из накопителя загружает резистор после чего коммутатор К подключает резистор находящийся в цангах к Rэ магазина сопротивления образуя делитель с выхода которого аналоговое значение Uпз поступает на вход аналого-цифрового преобразователя АЦП. Её основные функции сводятся к следующим: Внесение случайной погрешности по равномерному закону распределения...
14446. ХАРАКТЕРИСТИКА КОММУНИКАТИВНЫХ БАРЬЕРОВ И ВОЗМОЖНЫХ СПОСОБОВ ИХ ПРЕОДОЛЕНИЯ 608.46 KB
  Новизна работы заключается в том что теоретически мы объясняем происхождение барьеров через теорию речевых актов Дж. Практическая значимость определяется тем что мы смогли применить приемы и правила преодоления коммуникативных барьеров с целью совершенствовать навыки их преодоления при проведении ряда занятий с ребятами изучающими иностранный язык а затем увидеть результат в ходе встречи и коммуникации с носителем иностранного языка. Ричардс: коммуникация имеет место когда одно человеческое сознание так действует на окружающую его среду...
20904. Описание, история эксперимента и подготовка оборудования для определения длины световой волны с помощью колец Ньютона 902.03 KB
  Описание история эксперимента и подготовка оборудования для определения длины световой волны с помощью колец Ньютона. Для того чтобы выполнить поставленную цель мне потребуется получить Кольца Ньютона представляющие собой концентрические чередующиеся темные и светлые окружности которые можно наблюдать при отражении перпендикулярно падающего света от границ тонкой воздушной прослойки которая заключена между выпуклой поверхностью плосковыпуклой линзы и плоской стеклянной пластинкой. Цель работы: Определить длину волны с помощью...
13675. Нахождение возможных путей совершенствования учета производственных запасов 91.08 KB
  ля успешного решения задач учёта семян и кормов сельскохозяйственное предприятие должно правильно организовать складское хозяйство; располагать рациональной системой первичных и сводных документов и правильно организованным документооборотом; рационально организовать синтетический и аналитический учёт товарно-материальных ценностей; обеспечить систематический контроль за поступлением, расходованием и сохранностью запасов путём учёта их по местам хранения и материально ответственным лицам
21182. Расчет на прочность балки с жесткозаделанным левым и свободно опертым правым концом, нагруженной на части длины равномерной нагрузкой 537.53 KB
  Методом начальныхпараметров получены выражения для вычисления прогиба угла поворота изгибающегомомента и перерезывающей силы точек оси балки. Изучение изгиба балки представляет собойбольшую и сложную задачу в которой немалую роль занимает этап исследованияизогнутой оси балки и определение прогибов в наиболее характерных точках. Напряжения возникающие в разных сечениях балки зависят от величины изгибающего момента М и перерезывающей силы Q в соответствующих сечениях.
11583. Классификация возможных угроз, требующих действий подразделений гражданской обороны России 613.74 KB
  Региональные войны – это войны более крупного масштаба которые будут проводиться с целями: разгрома основных военных сил России на территории военных действий ТВД захвата значительной части территории ослабления военно-политического руководства и содействия территориальному распаду России ослабления международной позиции России окончательного размывания и распада СНГ и системы межгосударственных отношений. Наиболее характерными чертами будут: скрытность подготовки и внезапность развязывания агрессии; массированное применение...
3535. Мягкий зубной налет, бляшка, их значение, определение. Индекс гигиены по Федорову-Володкиной, по Пахомову, Грина-Вермиллиона, OHI-S, Синлес-Лоу. Определение, подсчет, показатели нормы 27.18 KB
  Минерализованные отложения: а пелликула а наддесневой зубной камень б зубная бляшка б поддесневой зубной камень в мягкий зубной налет г пищевые остатки детрит Пелликула зуба это приобретенная тонкая органическая пленка которая сменяет...
© "REFLEADER" http://refleader.ru/
Все права на сайт и размещенные работы
защищены законом об авторском праве.