Условная и безусловная оптимизация. Теорема Куна-Таккера

                                , i=1, …, n.

Эти условия  образуют систему n нелинейных уравнений, среди решений которой находятся точки минимума. Вектор f’(х), составленный из первых производных функции по каждой переменной, т.е.

                                  

 

                               

называют градиентом скалярной  функции f(x). Как видно, в точке минимума градиент равен нулю.

Решение систем нелинейных уравнений - задача весьма сложная и трудоемкая. Вследствие этого на практике используют второй подход к минимизации функций, составляющий основу прямых методов. Суть их состоит в построении последовательности векторов х [0], х [1], …, х [n], таких, что f(х[0])> f(х [1])> f(х [n])>… В качестве начальной точки x[0] может быть выбрана произвольная точка, однако стремятся использовать всю имеющуюся информацию о поведении функции f(x), чтобы точка x[0] располагалась как можно ближе к точке минимума. Переход (итерация) от точки х [k] к точке х [k+1], k= 0, 1, 2, ..., состоит из двух этапов:

1. выбор направления движения из точки х [k];
2. определение шага вдоль этого направления.

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

Математически методы спуска описываются соотношением

x[k+1] = x[k] + a_kp[k], k = 0, 1, 2, ...,

где p[k] - вектор, определяющий направление спуска; a_k - длина шага. В координатной форме:

                                     

Различные методы спуска отличаются друг от друга способами  выбора двух параметров - направления  спуска и длины шага вдоль этого  направления. На практике применяются  только методы, обладающие сходимостью. Они позволяют за конечное число  шагов получить точку минимума или  подойти к точке, достаточно близкой  к точке минимума. Качество сходящихся итерационных методов оценивают  по скорости сходимости.

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

                                            

или функции

                                       .

Здесь k - номер  итерации; e, g - заданные величины точности решения задачи.

Методы поиска точки минимума называются детерминированными, если оба элемента перехода от х[k] к x[k+l] (направление движения и величина шага) выбираются однозначно по доступной в точке х [k] информации. Если же при переходе используется какой-либо случайный механизм, то алгоритм поиска называется случайным поиском минимума.

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

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

Качество  численного метода характеризуется  многими факторами: скоростью сходимости, временем выполнения одной итерации, объемом памяти ЭВМ, необходимым  для реализации метода, классом решаемых задач и т. д. Решаемые задачи также  весьма разнообразны: они могут иметь  высокую и малую размерность, быть унимодальными (обладающими одним  экстремумом) и многоэкстремальными  и т. д. Один и тот же метод, эффективный  для решения задач одного типа, может оказаться совершенно неприемлемым для задач другого типа. Очевидно, что разумное сочетание разнообразных  методов, учет их свойств позволят с  наибольшей эффективностью решать поставленные задачи. Многометодный способ решения  весьма удобен в диалоговом режиме работы с ЭВМ. Для успешной работы в таком режиме очень полезно  знать основные свойства, специфику  методов оптимизации. Это обеспечивает способность правильно ориентироваться  в различных ситуациях, возникающих  в процессе расчетов, и наилучшим  образом решить задачу.

 

 

 

 

 

 

 

                                  Условная оптимизация.

 

 

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

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

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

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

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

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

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

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

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

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

На первом этапе решения задачи, называемом условной оптимизацией, определяются функция Беллмана и оптимальные  управления для всех возможных состояний  на каждом шаге, начиная с последнего в соответствии с алгоритмом обратной прогонки. На последнем, n-м шаге оптимальное управление *_n определяется функцией Беллмана: F(S) = max {W_n (S, x_n )}, в соответствии с которой максимум выбирается из всех возможных значений x_n ,причем x_n €X.  
Дальнейшие вычисления производятся согласно рекуррентному соотношению, связывающему функцию Беллмана на каждом шаге с этой же функцией, но вычисленной на предыдущем шаге. В общем виде это уравнение имеет вид F_n(S) = max {W_n (S, x_n ) + F_k+1) (Sⁿ(S, x_k )} x_k € X.  
Этот максимум (или минимум) определяется по всем возможным для k и S значениям переменной управления X.

Постановка задачи условной оптимизации

Задача  условной  оптимизации   состоит   в   минимизации   функции

, f)

где , а определяется явными ограничениями

, при  ,

а также неявными ограничениями

, при  .

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                                          Заключение.

 

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

Отличие методов условной и безусловной оптимизации по наличию или отсутствию ограничений. Рассматривается теорема Куна-Таккера, как способ решения для задач как безусловной, так и условной оптимизации и показывают множество численных методов.

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

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

                                                       

 

 

 

 

                         

 

 

 

 

 

 

                                 Список литературы:

 

 

1. Банди Б.  Методы оптимизации. Вводный курс. - М.: Радио и связь.

2. Банди Б.  Основы линейного программирования. - М.: Радио и связь.

3. Химмельблау  Д. Прикладное нелинейное программирование. - М.: Мир.

4. Кузнецов  Ю.Н., Кузубов В.И., Волощенко А.Б.  Математическое

программирование. - М.: Высшая школа.

5. Мышкис  А.Д. Математика для ВТУЗов. Специальные  курсы – СПб.:

Издательство  ‘Лань’.

6. Понтрягин  Л.С., Болтянский В.Г., Гамкрелидзе  Р.В., Мищенко Е.Ф.

Математическая  теория оптимальных процессов. –  Издательство «Наука» гл. ред.

физико-математической литературы, 3 изд.

7. Интриллигатор  М. Математические методы оптимизации  и экономическая

теория. –  М.: Айрис-Пресс.

8. Методы оптимизации - http://www.sbras.ru/rus/textbooks/akhmerov/mo_unicode/2.html

9. А.Г.Трифонов. "Постановка задачи оптимизации и численные методы ее решения" Методы безусловной оптимизации - http://matlab.exponenta.ru/optimiz/book_2/2_1.php

10. Задача - условная оптимизация

http://www.ngpedia.ru/id24585p2.html

11. Основные понятия теории оптимизации - http://www.studfiles.ru/dir/cat14/subj93/file10846/view103031.html

12. Методы безусловной оптимизации -

http://www.vevivi.ru/best/Metody-optimizatsii-funktsii-mnogikh-peremennykh-ref172141.html

13. Множители Лагранжа -

http://rudocs.exdat.com/docs/index-59900.html#2751894

14. Теорема Куна- Таккера - http://www.math.nsc.ru/LBRT/k5/MO-2009/lec8-FIT-part1.pdf

15. Теорема  Куна- Таккера - http://modality.ru/gos4/node27.php

16. Теоремма Куна-Таккера - http://www.nsu.ru/ef/tsy/ec_cs/micro2/temp/KuhnTuck.pdf

17. Пантелеев А.В., Т.А.Летова. Методы оптимизации в примерах и задачах: Учебное пособие.

18 . Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. Пособие.

19 . Курицкий Б.Я. Поиcк оптимальных решений средствами Excel 7.0. – СПб.

20.Методы условной оптмизации -  http://window.edu.ru/resource/198/56198