Минимизация функций нескольких переменных. Метод покоординатного спуска

Российский Государственный  Университет Нефти и Газа им. И.М. Губкина

Кафедра прикладной математики и компьютерного моделирования

 

 

 

               

                    Курсовая работа

 

По дисциплине: Методы оптимизации

       На тему: Минимизация функций нескольких                переменных. Метод покоординатного спуска.

 

 

 

 

 

 

 

                                                 Выполнила: студентка группы АМ-10-06

                                                         Бакалдина Екатерина

                                                  Проверила: старший преподаватель

                                                                  Панюшева Людмила Николаевна

 

 

 

                                                Москва 2013

 

Содержание

Введение 3-4

Общая постановка методов решения минимизации ф-ии нескольких переменных. ………5

Метод циклического покоординатного спуска. Алгоритм. 6

Пример 7-8

Сходимость метода 8

Ускоряющий шаг 9

Заключение 10

Список используемой литературы…………………………………………………………….11

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 

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

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

Возьмем пример: человек вышел утром  из дому, чтобы ехать на работу. По ходу дела ему приходится принять  целый ряд решений: брать ли с  собой зонтик? В каком месте  перейти улицу? Каким видом транспорта воспользоваться? И так далее. Разумеется, все эти решения человек принимает  без специальных расчетов, просто опираясь на имеющийся у него опыт и на здравый смысл. Для обоснования  таких решений никакая наука  не нужна, да вряд ли понадобится и  в дальнейшем.

Однако возьмем другой пример. Допусти, организуется работа городского транспорта. В нашем распоряжении имеется  какое-то количество транспортных средств. Необходимо принять ряд решений, например: какое количество и каких  транспортных средств направить  по тому или другому маршруту? Как изменять частоту следования машин в зависимости от времени суток? Где поместить остановки? И так далее.

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

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

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

 

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

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

Рассмотрим общую постановку методов  решения минимизации функции  нескольких переменных f, не использующие вычисление производных. Эти методы заключаются в следующем. При заданном векторе x определяется допустимое направление d. Затем, отправляясь из точки x, функция f минимизируется вдоль направления d одним из этих методов.

Предполагается, что задача линейного  поиска заключается в минимизации  f(x+λd) при условии, что λЄL, где L обычно задается в форме L=E₁, L={λ: λ≥0} или L={λ: a≤λ≤b}. Для простоты будем предполагать, что точка минимума λ҄ существует. Однако в реальных задачах это предположение может не выполняться. Оптимальное значение целевой функции в задаче линейного поиска может быть неограниченным или оптимальное значение функции конечное, но не достигается ни при каком λ. В первом случае целевая функция исходной задачи неограниченна и вычисления прекращаются. Во втором случае можно выбрать такое λ, что f(х + λd) будет достаточно близким к inf{f(х + λd): λЄL}.

В своей курсовой работе я рассмотрю метод циклического покоординатного спуска.

Метод циклического покоординатного спуска

В этом методе в качестве направлений поиска используются координатные векторы. Точнее, метод осуществляет поиск вдоль направлений d₁, ...,d_n, где d_j - вектор, все компоненты которого, за исключением j-й, равны нулю. Таким образом, при поиске по направлению d_j меняется только переменная x_j, в то время как все остальные переменные остаются зафиксированными.

Алгоритм  циклического покоординатного спуска

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

Для остановки алгоритма могут быть использованы несколько критериев. В приведенном ниже алгоритме процесс останавливается, если ||х_k+1— х_k|| < Ɛ. Ясно, что можно применить и любой другой критерий остановки.

Начальный этап.

Выбрать число Ɛ>0, которое будет использоваться для остановки алгоритма, и взять в качестве d₁, ...,d_n координатные направления. Выбрать начальную точку x₁, положить у₁=x₁, k=j=1 и перейти к основному этапу.

Основной этап.

     Шаг 1. Положить λ_j равным оптимальному решению задачи минимизации f(y_j + λd_j) при условии λЄE₁. Положить у_j+1= у_j + λ_jd_j. Если

j < n, то заменить j на j+1 и вернуться к шагу 1. Если j=n, то перейти к шагу 2.

Шаг 2. Положить x_k+1= у_n+1. Если ||х_k+1— х_k|| < Ɛ, то остановиться. В противном случае положить у₁= x_k+1, j=1, заменить k на k+1 и перейти к шагу 1.

 

 

 

 

 

 

ПРИМЕР. Рассмотрим следующую задачу:

минимизировать (x₁ — 2)⁴ + (x₁ — 2х₂)².

Заметим, что  оптимальным решением этой задачи является точка (2, 1), в которой значение функции равно нулю. В таблице приведены результаты вычислений по методу циклического покоординатного спуска для начальной точки (0, 3). Заметим, что на каждой итерации векторы y₂ и у₃ получены посредством одномерной минимизации по направлениям (1, 0) и (0, 1) соответственно. Заметим также, что заметное убывание функции получено в течение первых нескольких итераций, тогда как на последних итерациях процесс явно замедляется. После семи итераций получена точка (2.22, 1.11), значение функции в которой равно 0.0023.

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

 

 

 

Таблица 8.6

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

к	хк /(X*)	/	«*/	У;	А,	У/ + 1 _»
1	(0.00,3.00)	1	(1.0,0.0)	(0.00,3.00)	3.13	(3.13,3.00)
	52.00	2	(0.0,1.0)	(3.13,3.00)	-1.44	(3.13,1.56)
2	(3.13,1.56)	1	(1.0,0.0)	(3.13,1.56)	-0.50	(2.63,1.56)
	1.63	2	(0.0,1.0)	(?.63,1.56)	-0.25	(2.63,1.31)
3	(2.63,1.31)	1	(1.0,0.0)	(2.63,1.31)	-0.19	(2.44,1.31)
	0.16	2	(0.0,1.0)	(2.44,1.31)	-0.09	(2.44,1.22)
4	(2.44,1.22)	1	(1.0,0.0)	(2.44,1.22)	-0.09	(2.35,1.22)
	0.04	2	(0.0,1.0)	(2.35,1.22)	-0.05	(2.35,1.17)
5	(2.35,1.17)	1	(1.0, 0.0)	(2.35,1.17)	-0.06	(2.29,1.17)
	0.015	2	(0.0,1.0)	(2.29,1.17)	-0.03	(2.29,1.14)
6	(2.29,1.14)	1	(1.0,0.0)	(2.29,1.14)	-0.04	(2.25,1.14)
	0.007	2	(0.0,1.0)	(2.25,1.14)	-0.02	(2.25,1.12)
7	(2.25,1.12)	1	(1.0,0.0)	(2.25,1.12)	-0.03	(2.22,1.12) ‘
	0.004	2	(0.0,1.0)	(2.22,1.12)	-0.01	(2.22,1.11)

 

 

Сходимость циклического покоординатного спуска

Теорема:

Пусть задана дифференцируемая функция f: Е_n -> E₁. Рассмотрим задачу минимизации f(х) при условии, что хЄЕ_п, и алгоритм, отображение которого А определено следующим образом. Вектор уЄА(х), если он получается последовательной минимизацией функции f вдоль направлений d₁, ...,d_n, начиная из точки х. Направления поиска

d₁, ...,d_n, могут зависеть от х, а норма каждого из них равна 1. Предположим, что выполняются следующие условия:

1. Существует Ɛ > 0, такое, что det [D (х)]  ≥ Ɛ для каждого xЄE_n. Здесь

D (х)  — матрица порядка nХn, столбцами которой являются построенные алгоритмом направления, а det [D (х)]  — определитель D (х).

2. Минимум функции f вдоль любой прямой в Е_п единствен.

Возьмем начальную  точку x₁ и предположим, что алгоритм

строит последовательность {х_k} в соответствии со следующим правилом. Если f(х_k) = 0, то алгоритм останавливается в х_k. В противном случае

х_k+1= А(х_k), полагается равным 1 и процедура повторяется. Тогда если последовательность {х_k} содержится в компактном множестве пространства Е_n, то каждая предельная точка х построенной таким образом последовательности {х_k} удовлетворяет равенству f(х) = 0.

 

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

1. Минимум f вдоль любого направления в Е_n единствен.
2. Последовательность точек, генерируемых алгоритмом, содержится в компактном множестве пространства Е_n.

Заметим, что направлениями  поиска, используемыми на каждой итерации, являются координатные векторы, так что матрица  направлений D = 1. Очевидно, что предположение (1) теоремы выполняется.

 

Ускоряющий шаг

Мы установили, что метод циклического покоординатного  спуска при минимизации дифференцируемой функции сходится к точке с  нулевым значением градиента. В  отсутствие дифференцируемости метод может остановиться в неоптимальной точке. Как показано на рисунке 2(a) ниже, поиск вдоль любой координатной оси в точке х₂ не приводит к улучшению целевой функции и в результате метод преждевременно останавливается. Это объясняется наличием оврага, вызванного недифференцируемостью f. Как показано на рисунке 2(b), эта трудность может быть преодолена поиском вдоль направления х₂—х₁.

Поиск вдоль направления х_k+1—х_k часто используется в процедурах циклического покоординатного спуска, даже если функция дифференцируема. Обычно эмпирическим путем устанавливается, что такой шаг делается на каждой р-й итерации. Эта модификация метода циклического покоординатного спуска часто ускоряет сходимость, в частности когда последовательность точек образует зигзагообразную траекторию вдоль дна оврага. Такой шаг обычно называют ускоряющим шагом.