Реферат: Методы оптимизации

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Кафедра математического анализа

Дипломная работа по математике

студентка 5 курса математического факультета

специальность 032100.01 – «Математика» с дополнительной

специальностью «Информатика»

МЕТОДЫ ОПТИМИЗАЦИИ

Научный руководитель: доцент, кандидат технических наук

Допущена к защите.

Зав. кафедрой математического анализа _________________________

«___» _______ 2010 г., протокол №__

Защищена «____» июня 2010 г.

Оценка __________________________

СОДЕРЖАНИЕ

Введение

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

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

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

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

На первоначальном этапе решения принимались без специального математического анализа, просто на основе опыта и здравого смысла.

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

Из всего выше сказанного можно сделать вывод об актуальности темы дипломной работы.

Объект исследования: методы оптимизации как раздел математики.

Предмет исследования: методы оптимизации первого порядка (градиентные методы) и второго порядка: методы Ньютона и Ньютона- Рафсона.

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

Задачи , решаемые в работе:

1. Изучить теорию нахождения безусловного и условного экстремумов функции нескольких переменных;

2. Рассмотреть задачи минимизации функции нескольких переменных;

3. Изучить численные методы решения задач поиска безусловного минимума функции.

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

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

Глава I . ЗАДАЧА ОТЫСКАНИЯ ЭКСТРЕМУМА ФУНКЦИИ

МНОГИХ ПЕРЕМЕННЫХ

§ 1. Функция многих переменных

Одной из важных задач анализа является задача оты­скания экстремума (наибольшего или наименьшего зна­чения) скалярной функции f (х) n -мерного векторного аргумента х при некоторых ограничениях. Эту задачу мы будем записывать следующим образом:

min f ( x ), (1)

(2)

Здесь X — некоторое подмножество n -мерного евклидова пространства Е_п . Будем называть X допустимым множеством задачи (1)—(2), а точки, принадлежащие X, — ее допустимыми точками. Заметим, что задачу мак­симизации функции f (х) тоже можно записать в виде (1)-(2), заменив f (х) на .

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

g ( x )=0,

где g ( x ) есть m -мерная вектор-функция, т<п.

Задача (1) - (2) является классической и рассмат­ривается во всех курсах анализа. Теория решения таких задач развивалась еще в трудах Эйлера, Лагранжа, Бернулли, Лейбница. Она не потеряла своего значения и в настоящее время, несмотря на то, что с тех пор раз­работаны более общие методы, включающие классические, как частый случай. Классическая теория содержит зна­чительную часть идей, лежащих в основе современных методов оптимизации.

1.1 Необходимое условие экстремума. Рассмотрим задачу безусловной минимизации, будем теперь счи­тать, что f (х) — скалярная функция векторного аргумента размерности п, т. е. X = E_n . Если - точка ее безусловного локального экстремума, в ^j будет достигаться экстре­мум функции

одной переменной x^j , которая получается из функции f ( x ), если зафиксировать все переменные, кроме x^j , положив х ⁱ = ⁱ для . Для функции же одной переменной

получена теорема 1.

Теорема 1. Для того чтобы функция f ( x ), опре­деленная на вещественной оси, имела безусловный локаль­ный экстремум в точке , необходимо, чтобы выполнялось условие

. (3)

Проведя это рассуждение для всех j = 1, ..., п, приходим к следующей теореме.

Теорема 2. Для того чтобы в точке функция f ( x ¹ , ..., х^п ) имела безусловный локальный экстремум, необходимо, чтобы все ее частные производные обращались в в нуль:

i = 1, 2, …n . . (4)

Условие стационарности (4) мы будем записывать еще в одной из следующих эквивалентных форм:

grad

где — n -мерный вектор с компонентами, i =l, ..., п, который принято называть градиен­том функции f (х) в точке .

Заметим, что необходимое условие экстремума (4) эквивалентно равенству нулю дифференциала функции f ( x ) в точке :

df ( ) = 0.

В самом деле, если выполнено условие (4), то для любых dx^l , i = l, ..., n , имеем

.

Справедливо и обратное утверждение, так как из послед­него равенства в силу произвольности независимых при­ращений dxⁱ ,i = l, ..., n , следует, что все частные производные в точке равны нулю:

i = l, ..., n .

Условия (4) образуют систему п уравнений для определения п компонент вектора . Эти уравнения могут иметь различную природу и допускать любое количество решений, в частности, не иметь ни одного. Как и выше, точки ,являющиеся решениями системы уравнений (4), будем называть стационарными, а условие (4) - необхо­димым условием экстремума первого порядка.

1.2 Необходимое условие второго порядка. Достаточные условия. После того как решение системы уравнений (4) будет найдено, необходимо еще определить характер стационарной точки . Для этого нужно исследовать пове­дение функции f ( x ) в окрестности стационарной точки . Снова воспользуемся разложением функции f (х) в ряд Тейлора, предполагая ее дважды непрерывно дифферен­цируемой по всем переменным х¹ , ...,х ⁿ . Тогда получим

(5)

Здесь через мы обозначили элементы матрицы вто­рых производных функции f ( x ) в стационарной точке , а через - какую-нибудь норму вектора , например, .Далее матрицу вторых производных мы будем обозначать так:

. (6)

Характер стационарной точки функции f ( x ) связан сознакоопределенностью квадратичной формы

. (7)

Напомним, что квадратичная форма называется неотрица­тельно определенной в точке , если

(8)

и положительно определенной, если

(9)

для любых векторов .

Соответственно, симметричная матрица вторых произ­водных f "(х) называется неотрицательно определенной в точке , если выполнено (8), и положительно опре­деленной, если выполнено (9). Неположительно опреде­ленным и отрицательно определенным квадратичным фор­мам и матрицам соответствуют противоположные знаки в неравенствах (8), (9).

Таким образом, с учетом разложения (5), приходим к следующей формулировке условий второго порядка экстремальности функции f ( x ¹ , ..., х^п ).

Теорема 3. Для того чтобы дважды непрерывно дифференцируемая функция п переменных f ( x ) имела в ста­ционарной точке безусловный локальный минимум (мак­симум), необходимо, чтобы матрица ее вторых производных была неотрицательно (неположительно) определенной, и достаточно, чтобы она была положительно (отрица­тельно) определенной .

Проверка знакоопределенности матриц может быть осу­ществлена, например, с помощью критерия Сильвестра . Согласно этому критерию, необходимым и достаточным условием положительной определенности квадратичной формы (х, Ах), где А = { a_ij } — симметричная матрица, является выполнение п неравенств:

, , …,

Необходимым и достаточным условием отрицательной опре­деленности квадратичной формы (х, Ах) является выпол­нение цепочки следующих п неравенств:

, , …,

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

Пример. Определить экстремаль­ные значения функции

Из необходимых условий (2.1) имеем

Поэтому , - стационарная точка. Коэффици­енты квадратичной формы (7), вычисленные в ней, равны

Тогда, согласно теореме 3, имеем следующие случаи:

1) а>0, b >0 - функция f (х) имеет в точке = {0, 0}^T минимум;

экстремума нет

4) а<0, b<0 - функция f (х) имеет в точке ={0, 0}^T максимум. Отметим, что случаи 1) и 4) соответствуют поверхности, являющейся эллиптическим параболоидом, а случаи 2) и 3) - гиперболическому параболоиду, имеющему стационар­ную точку типа «седло».

Замечание: Здесь и далее {x ¹ , ..., х^п }^T – вектор-столбец.

§ 2. Относительный экстремум. Метод множителей Лагранжа

2.1 Метод исключения. Рассмотрим теперь задачу на относительный экстремум. Как мы видели в § 1, решение задачи об отыскании экстремумов функции п переменных f (х) на всем пространстве Е_п может быть сведено с по­мощью необходимых условий к решению системы уравнений (4), в результате чего определяются стационарные точки функции f ( x ). Оказывается, что аналогичное сведе­ние возможно и для задачи отыскания экстремумов функ­ции f ( x ) при наличии ограничений типа равенств

g_i ( x ) = 0, i = 1, 2, ..., т. (10)

Условия (10) принято еще называть уравнениями связи .

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

Определение . Допустимая точка доставляет относительный локальный минимум функции f (х), если можно указать такое число , что для всех х, удов­летворяющих уравнениям связи (10) и условию ||х - ||<, имеет место неравенство

.

Рассмотрим случай, когда уравнения связи (10) могут быть разрешены относительно части переменных. Будем предполагать, что функции g_i ( x ), i =l,..., т ,имеют в окрестности рассматриваемой допустимой точки непре­рывные частные производные по всем аргументам до вто­рого порядка включительно и, кроме того, ранг матрицы Якоби для функций g_i ( x ), i = l, ...,m , рассматриваемой в точке ,равен т .Не нарушая общности, предположим, что отличен от нуля определитель (якобиан), составленный из частных производных по первым т аргументам, т. е.

(11)

Тогда по теореме о неявных функциях в некоторой окре­стности точки система уравнений (10) разрешима отно­сительно х¹ , ..., х^т ,т. е. представима в виде

j = 1, 2, …, m , (12)

где - непрерывно дифференцируемые в рассматриваемой окрестности функции. Переменные х^т+1 ,..., х^п естественно назвать «независимыми», в отличие от «зави­симых»— x ¹ , ..., х^т . Подставляя выражения (12) в функ­цию f ( x ), получим задачу отыскания безусловного экстре­мума функции п — т переменных

.

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

2.2 Метод множителей Лагранжа. Как мы видели в за­мечании к теореме 2, в точке , доставляющей безу­словный экстремум функции, ее полный дифференциал равен нулю, т. е.

(13)

где dx^j ,j =1, ..., m , — дифференциалы «зависимых» пере­менных, связанные с дифференциалами «независимых» пере­менных dx^k , k = m +1, ..., n , следующим образом:

i = l, …, m . (14)

Метод Лагранжа состоит из следующих этапов:

1) составляется функция п+т переменных, которая называется функцией Лагранжа:

(15)

2) вычисляются и приравниваются нулю ее частные производные по х и :

j = 1, 2, …, n , (16)

i = 1, 2, …, m ,

3) решается система (16) п+т уравнений относи­тельно п+т неизвестных x ¹ , ..., х^п , ₁ , ..., _т .

Система уравнений (16) представляет собой необхо­димые условия первого порядка в задаче на относитель­ный экстремум, а ее решения ¹ , ...,^п принято называть условно-стационарными точками. Как и в случае задач на безусловный экстремум, необходимые условия первого порядка не определяют характера условно-стационарной точки. Для выяснения этого вопроса следует привлечьпроизводные более высоких порядков функций f (х) и g ( x ).

Заметим, что требова­ние неравенства нулю якобиана (11) является су­щественным.

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

Рис. 1

Пусть

п = 2, т = 2, f (х) = х ² ,

,

.

Допустимая точка должна одновременно удовлетворять уравнениям g ₁ ( x ) = 0 , g ₂ ( x ) = 0 и является единственной: х¹ = 0, x ² = 0. Очевидно, что точка ¹ =0, ² =0 и будет решением задачи на относительный минимум функции f (х) = x ² при ограничениях g ₁ ( x ) = g ₂ ( x ) = 0. Составим для этой задачи функцию Лагранжа:

Метод множителей Лагранжа приводит к уравнениям

Этим уравнениям точка относительного минимума ¹ =0, ² =0не удовлетворяет ни при каких значениях ₁ , ₂ ,т. е. в данном случае метод множителей Лагранжа не работает.

Пример 2. Пусть

п = 2, т = 2, f (х) = х ² min,

g ( x )= х ² -( x ¹ )² .

Функция Лагранжа для этой задачи имеет вид

Соответственно, правило множителей Лагранжа приво­дит к уравнениям

решением которых будет ,¹ =0, ² =0. Чтобы понять, доставляет точка =0 относительный минимум функции f (х) илинет, надо выяснить характер поведения квадратичной формы

на прямой

.

При , как функция одной переменной , эта форма положительно определена. Значит, в точке =0 имеем относительный минимум.

2.3 Седловая точка функции Лагранжа. Рассмотрим функцию двух переменных z = Ф(х, у) ,где х, y —скаляры или векторы.

Определение. Назовем пару {х*, y *} седловой точкой функции Ф (х, у), если для любых х, y справедливо неравенство

(17)

Очевидно, что неравенство (17) эквивалентно выражению

Снова рассмотрим задачу отыскания относительного экстремума функции f ( x ) при ограничениях g ( x ) = 0 . Не­обходимые условия экстремума (3.10) можно записать в виде

(18)

т. е. пара является стационарной точкой функции Лагранжа

Однако в этой точке функция не может достигать максимума или минимума по х и одновременно. В самом деле, пусть в точке достигается максимум функции по х и . Так как условия связи в точке выполнены, то Пусть, далее, в некоторой точке нарушено одно из ограничений, например Тогда в силу линейности функции L по мы можем за счет выбора добиться бесконечно большого значения L (число имеет знак, противоположный знаку g_k ( x )). Следовательно, в точке функция Лагранжа не может иметь максимума по . Аналогично можно показать, что в точке не может одновременно достигаться мини­мум функции Лагранжа по х и .

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

Следовательно,

где

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

то точка , по определению, является седловой точ­кой функции Лагранжа.

Пример 3. Исследуем на экстремум функцию

.

Решение. Координаты x , y , z критической точки гладкой функции u должны удовлетворять системе:

или

Отсюда получаем пять критических точек:

, , , , .

Исследуем поведение функции u в стационарных точках с помощью достаточного условия экстремума:

Отсюда получаем . Так как является отрицательно определенной квадратичной формой, то в точке функция u имеет строгий локальный максимум.

Для анализа квадратичной формы

Применим критерий Сильвестра. Матрица этой формы:

.

Её главные миноры:

2>0;

Распределение знаков этих миноров показывает, что данная квадратичная форма знакопеременная, следовательно, в точке М₁ функция u не имеет экстремума: точка М₁ есть седловая точка функции u .

Точно так же устанавливается, что точки М₂ , М₃ , М₄ также седловые точки функции u .

Глава II . ЧИСЛЕННЫЕ МЕТОДЫ ОТЫСКАНИЯ БЕЗУСЛОВНОГО ЭКСТРЕМУМА

§ 1. Методы первого порядка (градиентные методы)

Как известно из курсов анализа, градиент скалярной функции f (х) в некоторой точке x_k направлен в сторону наискорейшего возрастания функции и ортогонален линии уровня (поверх­ности постоянного значения функции f ( x ), проходящей через точку х _k ). Вектор, противоположный градиенту f '( x_k ) , антиградиент, направлен в сторону наискорейшего убывания функции f ( x ). Выбирая в качестве направления спуска р _k в антиградиент функции f (х) в точке x_k , мы приходим к итерационному процессу вида

k =1, 2, … n .

В координатной форме этот процесс записывается следу­ющим образом:

i =1, 2, … n .

Все итерационные процессы, в которых направление дви­жения на каждом шаге совпадает с антиградиентом (гра­диентом) функции, называются градиентными методами и отличаются друг от друга способами выбора шага Рассмотрим некоторые из них.

1.1 Метод градиентного спуска с постоянным шагом

Постановка задачи

Пусть дана функция f (х) , ограниченная снизу на множестве Rⁿ и имеющая непрерывные частные производные во всех его точках.

Требуется найти локальный минимум функции f (х) на множестве допустимых решений X = Rⁿ , т.е. найти такую точку , что

Стратегия поиска

Стратегия решения задачи состоит в построении последовательности точек {х _k } , k = 0,1,..., таких, что k = 0,1,... . Точки последовательности {х _k } вычисляются по правилу

(1)

где точка х₀ задается пользователем; - градиент функции f ( x ) , вычисленный в точке х _k ; величина шага задается пользователем и остается постоянной до тех пор, пока функция убывает в точках последовательности, что контролируется путем проверки выполнения условия или

Рис. 2

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

Геометрическая интерпретация метода для п =2приведена на рис. 2.

Процедура решения задачи

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

2. Провести анализ точки х _k с целью установить, является ли точка х_к найденным приближением решения задачи. Процедура анализа определяется на­личием у функции f (х) непрерывных вторых производных. Если , то следует провести проверку выполнения достаточных условий минимума: матрица Гессе Если то точка х _k есть найденное приближение искомойточки х_* . Если , то следует провести проверку функции f (х) на выпук­лость в Q -окрестности точки х _k , используя критерий выпуклости для функций : функция f ( x ) выпукла (строго выпукла) в том и только в том случае, если . Если функция f ( x ) выпукла (строго вы­пукла), то х _k есть найденное приближение точки х_* .

Определение: Матрицей Гессе Н(х) дважды непрерывно дифференцируемой в точке х функции f ( x ) называется матрица частных производных второго порядка, вычисленной в данной точке:

,

где

Определители , , …, называются угловыми минорами.

Пример 1.1. Найти локальный минимум функции

□ I. Определение точки х _k , в которой выполнен по крайней мере один из критериев окончания расчетов.

1. Зададим х₀ , , , М : х₀ = (0,5; 1)^T , = 0,1; = 0,15 ; М = 10. Найдем градиент функции в произвольной точке

2. Положим к = 0.

3⁰ . Вычислим : = (3;2,5)^Т .

4⁰ . Вычислим : = 3,9 > 0,1. Переходим к шагу 5.

5⁰ . Проверим условие : k = 0 < 10 = M . Переходим к шагу 6.

6⁰ . Зададим = 0,5 .

7⁰ . Вычислим х₁ : х₁ = (0,5; 1)^T -0,5(3; 2,5)^T = (-1; -0,25)^T ; f (х₁ ) = 2,31.

8⁰ . Сравним f (х₁ ) с f (х₀ ) = 2. Имеем f (х₁ ) > f (х₀ ) . Вывод: условие для k = 0 не выполняется. Зададим = 0,25, переходим к по­вторению шагов 7, 8.

7⁰¹ . Вычислим х₁ : х₁ = (0,5; 1)^T -0,25(3; 2,5)^T = (-0,25; 0,375)^T ; f (х₁ ) = 0,171.

8⁰¹ . Сравним f (х₁ ) и f (х₀ ) . Вывод: f ( x ₁ ) < f ( x ₀ ). Переходим к шагу 9.

9⁰ . Вычислим и :

=0,976 > 0,15; = 1,829 > 0,15.

Вывод: полагаем k =1 и переходим к шагу 3.

3¹ . Вычислим : = (-0,625;0,51)^Т .

4¹ . Вычислим := 0,81. Переходим к шагу 5.

5¹ . Проверим условие : k = 1 < 10 = M . Переходим к шагу 6.

6¹ . Зададим = 0,25.

7¹ . Вычислим х₂ : х₂ = (-0,25; 0,375)^T - 0,25 (-0,625; 0,5)^T = (-0,094; 0,25)^T ; f (х₂ ) = 0,056.

8¹ . Сравним f (х₂ ) с f (х₁ ) . Вывод: f (х₂ ) < f (х₁ ). Переходим к шагу 9.

9¹ . Вычислим и :

= 0,2 > 0,15;= 0,115 < 0,15.

Вывод: полагаем k = 2 и переходим к шагу 3.

3² . Вычислим : = (-0,126; 0,406)^Т .

4² . Вычислим : = 0,425 > 0,1. Переходим к шагу 5.

5² . Проверим условие : k = 2 < 10 = М , переходим к шагу 6.

6² . Зададим =0,25.

7² . Вычислим х₃ : х₃ = (-0,094; 0,25)^T -0,25(-0,126; 0,406)^T = (-0,063;0,15)^T ; f (х₃ ) = 0,021.

8² . Сравним f (х₃ ) и f (х₂ ) . Вывод: f (х₃ ) < f (х₂ ) .Переходим к шагу 9.

9² . Вычислим и :

= 0,105 < 0,15; = 0,035 < 0,15.

Вывод: полагаем k = 3 и переходим к шагу 3.

3³ . Вычислим : = (-0,102;0,237)^T .

4³ . Вычислим : = 0,257 > 0,1 . Переходим к шагу 5.

5³ . Проверим условие : k = 3<10 = М, переходим к шагу 6.

6³ . Зададим = 0,25.

7³ . Вычислим х₄ : х₄ = (-0,063; 0,15)^T - 0,25(-0,102; 0,237)^T = (-0,038; 0,091)^Т ; f (х₄ ) = 0,0076.

8³ . Сравним f (х₄ ) и f (х₃ ) : f (х₄ ) < f (х₃ ) .

9³ . Вычислим и :

= 0,064 < 0,15; = 0,015 < 0,15.

Условия , выполнены при k = 2,3. Расчет окончен. Найдена точка х₄ = (-0,038; 0,091)^Т ; f ( x ₄ ) = 0,0076.

На рис. 3 полученные точки соединены пунктирной линией.

II. Анализ точки х₄ .

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

Рис. 3

Матрица постоянна и является положительно определенной (т.е. H > 0) , так как оба ее угловых минора = 4 и = 7 положительны. Следовательно, точка х₄ =(-0,038; 0,091)^T есть найденное приближение точки локального минимума х_* = (0,0)^T , а значение f ( x ₄ ) =0,0076 есть найденное приближение значения f ( x _* ) =0. Заметим, что условие H > 0, есть одновременно условие строгой выпуклости функции . Следовательно, х₄ = (-0,038; 0,091)^T , f ( x ₄ ) =0,0076 есть найден­ные приближения точки глобального минимума f ( x ) и ее наименьшего значе­ния на R ² . ■

1.2 Метод наискорейшего градиентного спуска

Стратегия поиска

Стратегия решения задачи состоит в построении последовательности точек {х _k }, k = 0,1,..., таких, что k = 0,1,.... Точки последовательности {х _k } вычисляются по правилу

(2)

где точка х₀ задается пользователем; величина шага определяется для каждого значения k из условия

(3)

Решение задачи (3) может осуществляться с использованием необходи­мого условия минимума с последующей проверкой достаточного условия минимума . Такой путь может быть использован либо при достаточно простой минимизируемой функции , либо при предварительной аппроксимации достаточно сложной функции полиномом P ( ) (как правило, второй или третьей степени), и тогда условие замещается условием , а условие условием .

Построение последовательности {х _k }, k = 0,1,..., заканчивается в точке х _k , для которой , где - заданное число, или, если , М -предельное число итераций, или при двукратном одновременном выполнении неравенств , , где - малое положительное число. Вопрос о том, может ли точка х _k рассматриваться как найденное при­ближение искомой точки локального минимума х_* , решается путем дополни­тельного исследования.

Рис. 4

Геометрическая интерпретация метода для п = 2приведена на рис. 4.

Пример 1. 2. Найти локальный минимум функции

.

□ I. Определение точки х _k , в которой выполнен по крайней мере один из критериев окончания расчетов.

1. Зададим х₀ , , , М : х₀ = (0,5; 1)^T , = 0,1; = 0,15 ; М = 10. Найдем градиент функции в произвольной точке

2. Положим k = 0.

3⁰ . Вычислим : = (3;2,5)^Т .

4⁰ . Вычислим : = 3,9 > 0,1. Переходим к шагу 5.

5⁰ . Проверим условие : k = 0 < 10 = M . Переходим к шагу 6.

6° . Следующая точка находится по формуле

= (0,5; 1)^T - (3; 2,5)^г = (0,5 - 3; 1 - 2,5).

Подставим полученные выражения 0,5 - 3, 1 - 2,5для коор­динат в f ( x ) :

Найдем минимум функции по с помощью необходимых условий безусловного экстремума:

.

Отсюда . Так как = 63,25 > 0, найденное значение шага обеспечивает минимум функции по .

7⁰ . Найдем : х₁ = (0,5; 1)^Т - 0,24(3; 2,5)^Т = (-0,22; 0,4)^Т .

8°. Вычислим и :

= 0,937 >0,15; = 1,83 > 0,15.

Вывод: полагаем k = 1 и переходим к шагу 3.

3¹ . Вычислим : = (-0,48;0,58)^T .

4¹ . Вычислим = 0,752 > 0,1.

5¹ . Проверим условие : k = 1 < 10 = М .

6¹ . Определим : = 0,546(см. п. 6⁰ ).

7¹ . Найдем :

х₂ =(-0,22; 0,4)^T - 0,546 (- 0,48; 0,58)^T = (0,04; 0,08)^T .

8¹ . Вычислим и :

= 0,41 > 0,15; = 0,156 > 0,15.

Полагаем k = 2 и переходим к шагу 3.

3² . Вычислим : = (0,24;0,2)^T .

4² . Вычислим : = 0,312 > 0,1.

5² . Проверим условие : k = 2 < 10 = M .

6² . Определим : =0,24 (см. п. 6⁰ ).

7² . Найдем :

х₃ =(0,04; 0,08)^T - 0,24 (0,24; 0,2)^T = (-0,0176; 0,032)^T .

8² . Вычислим и :

= 0,0749 < 0,15; = 0,0116 < 0,15.

Полагаем k =3 и переходим к шагу 3.

3³ . Вычислим : = (-0,012;-0,0816)^T .

4³ . Вычислим : = 0,082 < 0,1. Расчет окончен. Найденаточка х₃ =(-0,0176;0,032)^T , f (х₃ ) = 0,00127.

II. Анализ точки х₃ .

В примере 1.1 (гл.2 §1) было показано, что функция f ( x ) является строго выпуклой и, следовательно, точка х₃ является найденным приближением точки глобаль­ного минимума х_* . ■

1.3 Метод покоординатного спуска

Стратегия поиска

Стратегия решения задачи состоит в построении последовательности точек {х _k }, k = 0,1,..., таких, что k = 0,1,... . Точки последовательности {х _k }вычисляются по циклам в соответствии с правилом

. (4)

где j - номер цикла вычислений; j = 0,1,2,...; k - номер итерации внутри цикла, k = 0,1,... ,n - 1; е _{k +1} , k = 0,l,..., n - 1 -единичный вектор, (k +1) -я проекция ко­торого равна 1; точка х₀₀ задается пользователем, величина шага выбирается из условия

или .

Если выбранное условие при текущем не выполняется, шаг уменьшается вдвое и точка вычисляется заново. Легко видеть, чтопри фиксированном j за одну итерацию с номером k изменяется только одна проекция точки х _jk , имеющая номер k + 1, а в течение всего цикла с номером j , т.е. начиная с k = 0 и кончая k = п -1, изменяются все п проекций точки х _{j 0} . После этого точке х _{j п} присваивается номер х _{j + 0,1} , и она берется за на­чальную точку для вычислений в j + 1 цикле. Расчет заканчивается в точке х _jk при выполнении по крайней мере одного из трех критериев окончания счета: , или , или двукратного выполнения неравенств , .

Полученные в результате вычислений точки могут быть записаны как эле­менты последовательности {х _l }, где - порядковый номер точки, т.е.

Геометрическая интерпретация метода для п = 2 приведена на рис. 5.

Рис. 5

Пример 1.3. Найти локальный минимум функции

.

□ I. Определение точки x_jk , в которой выполнен по крайней мере один из критериев окончания расчетов.

1. Зададим х₀₀ , М : х₀₀ = (0,5; 1)^Т , ; М =10. Найдем градиент функции в произвольной точке

2. Зададим j = 0.

3⁰ . Проверим выполнение условия : j = 0<10 = М .

4⁰ . Зададим k = 0.

5⁰ . Проверим выполнение условия : k = 0<1 = n -1.

6⁰ . Вычислим : = (3; 2,5)^T .

7⁰ . Проверим условие : = 3,8 > 0,1.

8⁰ . Зададим = 0,5 .

9⁰ . Вычислим , где

, .

Отсюда х₀₁ = (-1;1)^T .

10⁰ . Проверим условие : = 2-2 = 0. Вы­вод: полагаем = 0,25 и переходим к шагу 9.

9⁰¹ . Вычислим х₀₁ с шагом = 0,25: х₀₁ = (-0,25; 1)^T .

10⁰¹ . Проверим условие :

= 0,875 - 2 = -1,125 < 0.

11⁰ . Проверим условия , :

= 0,75 > 0,15; = 1,125 > 0,15.

Полагаем k =1 и переходим к шагу 5.

5¹ . Проверим условие : k = 1 = n -1.

6¹ . Вычислим : = (0; 1,75)^T .

7¹ . Проверим условие : = 1,75 > 0,1.

8¹ . Зададим =0,5.

9¹ . Вычислим , где ;

.

Отсюда х₀₂ = (-0,25; 0,125)^Т .

10¹ . Проверим условие :

= 0,109 - 0,875 = - 0,766 < 0.

11¹ . Проверим условия , :

= 0,875 > 0,15, = 0,766 > 0,15.

Полагаем k = 2, переходим к шагу 5.

5² . Проверим условие : k = 2 > n -1. Зададим j = 1, х₁₀ = х₀₂ , пе­реходим к шагу 3.

3¹ . Проверим условие : j = 1 < 10 = М .

4¹ . Зададим k = 0.

5² . Проверим условие : k = 0 < 1 = п- 1.

6² . Вычислим : = = (-0,875; 0,00)^T .

7² . Проверим условие : = 0,875 > 0,1.

8² . Зададим = 0,25.

9² . Вычислим : x ₁₁ = (-0,03;0,125)^T

10² . Проверим условие :

= 0,01-0,109 = -0,099 < 0.

11² . Проверим условия , :

= 0,22 > 0,15, = 0,099 < 0,15.

Полагаем k =1 и переходим к шагу 5.

5³ . Проверим условие : k = 1 = n -1.

6³ . Вычислим : = (0,005; 0,22)^T .

7³ . Проверим условия : = 0,22 > 0,1.

8³ . Зададим =0,25.

9³ . Вычислим : x ₁₂ =(-0,03; 0,07)^T .

10³ . Проверим условие :

= 0,0046 -0,01 = -0,0054 < 0.

11³ . Проверим условия , :

= 0,055 < 0,15, = 0,0054 < 0,15.

Зададим k = 2 и переходим к шагу 5.

5⁴ . Проверим условие : k = 2 > п- 1.

Полагаем j = 2, х₂₀ = х₁₂ и переходим к шагу 3.

3² . Проверим условие : j = 2 < 10 = М.

4² . Зададим k =0.

5⁴ . Проверим условие :k = 0 <1 = n -1.

6⁴ . Вычислим : = = (-0,05; 0,11)^T .

7⁴ . Проверим условие : = 0,12 > 0,1.

8⁴ . Зададим = 0,25.

9⁴ . Вычислим : х₂₁ = (- 0,02; 0,07)^Т .

10⁴ . Проверим условие : 0,0043-0,046 = -0,0003 < 0, пе­рейдем к шагу 11.

11⁴ . Проверим условия , :

= 0,01 < 0,15 ,= 0,0003 < 0,15.

Условия , выполнены в двух последовательных циклах с номерами j = 2 и j -1 = 1. Расчет окончен, найдена точка х₂₁ = (- 0,02; 0,07)^Т ; f (х₂₁ ) = 0,0043 .

На рис. 6 полученные точки соединены пунктирной линией.

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

Рис. 6

II. Анализ точки х₂₁ .

В примере 1.1 (гл.2 §1) было показано, что функция f (х) строго выпукла, имеет единственный минимум и, следовательно, точка х₂₁ = = (-0,02; 0,07)^Т является найденным приближением точки глобального минимума. ■

Во всех рас­смотренных выше градиентных методах последовательность точек { x_k } сходится к стационарной точке функции f ( x ) при достаточно общих предложениях относительно свойств этой функции. В частности, справедлива теорема:

Теорема. Если функция f ( x ) ограничена снизу , ее градиент удовлетворяет условию Липшица () и выбор значения производится одним из описанных выше спосо­бов, то, какова бы ни была начальная точка х₀ :

при .

При практической реализации схемы

k =1, 2, … n .

итерации прекращаются, если для всех i , i = 1, 2, ..., n , выпол­нены условия типа

,

где - некоторое заданное число, характеризующее точ­ность нахождения минимума.

В условиях теоремы градиентный метод обеспечи­вает сходимость по функции либо к точной нижней грани (если функция f (х) не имеет минимума; рис. 7), либо к значению функции в некоторой стационарной точке, являющейся пределом последовательности {х_к }. Нетрудно придумать примеры, когда в этой точке реализуется седло, а не минимум. На практике ме­тоды градиентного спуска уверенно обходят седловые точки и находят минимумы целевой функции (в общем случае — локальные).

Рис. 7

§ 2. Методы второго порядка

2.1 Метод Ньютона

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

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

Стратегия поиска

Стратегия метода Ньютона [ NewtonI. ] состоит в построении последова­тельности точек {х _k }, k = 0,1,..., таких, что k = 0,1,.... Точки последовательности вычисляются по правилу

(5)

где х₀ задается пользователем; величина шага определяется для каждого значения k по формуле

.(6)

Выбор по формуле (6) гарантирует выполнение требования при условии, что . Формула (6) получена из следующих соображений:

1. Функция f (х) аппроксимируется в каждой точке последовательности {х ^k } квадратичной функцией .

2. Направление определяется из необходимого условия экстремума пер­вого порядка: Таким образом, при выполнении требования последовательность является последовательностью точек минимумов квадратич­ных функций F_k , k = 0,1,... (рис. 8). Чтобы обеспечить выполнение требования , k = 0,1,..., даже в тех случаях, когда для каких-либо значений матрица Гессе не окажется положительно определенной, рекомендуется для соответствующих значений k вычислить точку по методу градиентного спуска с выбором величины шага из условия .

Рис. 8

Построение последовательности {х _k } заканчивается в точке х _k , для кото­рой где - заданное малое положительное число, или при (М - предельное число итераций), или при двукратном одновременном выполне­нии двух неравенств , где - малое положительное число. Вопрос о том, может ли точка х _k рассматриваться как най­денное приближение искомой точки минимума, решается путем проведения дополнительного исследования, которое описано ниже.

Сходимость

Утверждение. Пусть f ( x ) дважды непрерывно дифференцируемая сильновыпуклая функция с константой l > 0 на Rⁿ и удовлетворяет условию

,

где L > 0, а начальная точка такова, что , т.е.

,

где . . Тогда последовательность { x^k } сходится к точке минимума с квадратичной скоростью .

Замечание 1. Сходимость метода Ньютона доказана лишь для сильно выпуклых функ­ций и для достаточно хорошего начального приближения, определяемого услови­ем , практическое использование которого крайне затруднено, так как по­стоянные l и L , как правило, неизвестны или требуют трудоемкого исследования для их определения. Поэтому при практическом использовании метода Ньютона следует:

а) анализировать матрицу Н(х _k )на выполнение условия Н(х _k ) < 0 и заменять формулу на формулу в случае его невыполнения;

б) производить анализ точки х _k с целью выяснения, является ли она най­денным приближением искомой точки х_* .

Замечание 2. При решении задачи поиска безусловного максимума формула (6) не изменяется, так как в этом случае Н(х _k ) < 0.

Процедура решения задачи

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

2. Так как , то осуществить проверку выполнения достаточных

условий минимума > 0. Если условие выполнено, то точка х _k может рас­сматриваться как найденное приближение точки минимума х_* . Проверку вы­полнения достаточных условий минимума можно заменить проверкой функции f ( x ) на выпуклость.

Пример 2.1. Найти локальный минимум функции

.

□ I. Определение точки х _k , в которой выполняется по крайней мере один критерий окончания расчетов.

1. Зададим х₀ , М : х₀ = (0,5; 1)^Т , ; М =10. Найдем градиент функции в произвольной точке и матрицу Гессе .

2. Положим k = 0.

3⁰ . Вычислим : = (3; 2,5)^Т .

4⁰ . Проверим выполнение условия : = 3,9 > 0,1.

Переходим к шагу 5.

5⁰ . Проверим выполнение условия : k = 0 < 10. Переходим к шагу 6.

6⁰ . Вычислим : .

7⁰ . Вычислим :.

8⁰ . Проверим выполнение условия >0. Так как , , то согласно критерию Сильвестра > 0.

9⁰ . Определим .

10⁰ . Вычислим .

11⁰ . Проверим выполнение условий , :

= 1,12 > 0,15; = 2>0,15.

Полагаем k = 1, переходим к шагу 3.

3¹ . Вычислим := (0,0)^T .

4¹ . Проверим выполнение условия := 0 <0,1. Расчет окончен. Заметим, что в точке х₁ выполняется необходимое условие первого по­рядка, поэтому она является стационарной точкой.

II. Анализ точки х₁ .

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

Найденная точка х₁ =(0,0)^T есть точка локального и одновременно глобального минимума f (х) .

Рис. 9

На рис. 9 траектория спуска изображена сплошной линией. ■

2.2 Метод Ньютона-Рафсона

Стратегия поиска

Стратегия метода Ньютона-Рафсона [Newton-Raphson] состоит в построении последова­тельности точек {х _k }, k = 0,1,..., таких, что k = 0,1,.... Точки последовательности вычисляются по правилу

(7)

где х₀ задается пользователем; величина шага определяется из условия

.(8)

Задача (7.5) может решаться либо аналитически с использованием необхо­димого условия минимума с последующей проверкой достаточного условия , либо численно как задача

(9)

где интервал [a , b ]задается пользователем.

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

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

Построение последовательности {х _k } заканчивается в точке х _k , для кото­рой , где - заданное число, или при (М - предельное чис­ло итераций), или при двукратном одновременном выполнении двух неравенств , , где - малое положительное число.

Вопрос о том, может ли точка х _k рассматриваться как найденное приближение искомой точки минимума, решается путем проведения дополнительного иссле­дования, которое описано ниже.

Сходимость

Утверждение. Пусть функция f ( x ) дважды непрерывно дифференцируема и сильно выпукла на Rⁿ , а ее матрица Гессе Н(х) удовлетворяет условию Липшица

.

Тогда последовательность {х _k } сходится независимо от выбора начальной тонки х₀ к точке минимума х_* с квадратичной скоростью

,

где т - оценка наименьшего собственного значения матрицы .

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

а) анализировать матрицу Гессе на выполнение условия >0,k = 0,1,..., и заменять формулу на форму­лу метода градиентного спуска в случае его невыполнения;

б) производить анализ точки х _k с целью выяснения, является ли она най­денным приближением искомой точки х_* .

Процедура решения задачи

1. Используя алгоритм Ньютона-Рафсона, построить точку х _k , в которой выполняется по крайней мере один критерий окончания расчетов.

2. Так как , то осуществить проверку выполнения достаточных

условий минимума >0. Если условие выполнено, то точка х _k может рас­сматриваться как найденное приближение точки минимума х_* . Проверку вы­полнения достаточных условий минимума можно заменить проверкой функции f ( x ) на выпуклость.

Пример 2.2. Найти локальный минимум функции

.

□ I. Определение точки х _k , в которой выполняется по крайней мере один критерий окончания расчетов.

1. Зададим х₀ , М : х₀ = (0,5; 1)^Т , ; М =10. Найдем градиент функции в произвольной точке и матрицу Гессе .

2. Положим k = 0.

3⁰ . Вычислим : = (3; 2,5)^Т .

4⁰ . Проверим выполнение условия : = 3,9 > 0,1.

Переходим к шагу 5.

5⁰ . Проверим выполнение условия : k =0 < 10. Переходим к шагу 6.

6⁰ . Вычислим : .

7⁰ . Вычислим :.

8⁰ . Проверим выполнение условия >0. Так как , , то согласно критерию Сильвестра > 0.

Поэтому найдем .

9⁰ . Определим: .

10⁰ . Определим из условия .

Получаем

.

Из условия находим = 1. При этом , т.е. найденная величина шага обеспечивает минимум функции .

11°. Вычислим :.

12°. Проверим выполнение условий , :

= 1,12 > 0,15; = 2 > 0,15.

Положим k =1 и перейдем к шагу 3.

3¹ . Вычислим : .

4¹ . Проверим выполнение условия : = 0 < 0,1. Расчет

окончен: х_* = х₁ .

II. Анализ точки х₁ .

Точка х_* = (0;0)^T - точка локального и одновременно глобального миниму­ма f ( x ) .

На рис. 9траектория спуска изображена штрихпунктирной линией. ■

Заключение

В результате проделанной работы можно сделать следующие выводы:

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

2. Многие алго­ритмы решения задач с ограничениями включают миними­зацию без ограничений как некоторый этап.

3. Различные методы спуска отличаются друг от друга способами выбора направления спуска и длины шага вдоль этого направления.

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

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

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

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

Литература

1. Моисеев Н.Н., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. – М. Наука, 1978.

2. Кудрявцев Л.Д. Курс математического анализа (в двух томах): Учебник для студентов университетов и втузов. – М.: Высшая школа, 1981.

3. Измаилов А.Ф., Солодов М.В. Численные методы оптимизации: Учеб. пособие. – М.: Физматлит, 2005.

4. Виноградова И.А., Олехник С.Н., Садовничий В.А. Задачи и упражнения по математическому анализу: Пособие для университетов. – М.: Дрофа, 2001.

5. Пантелеев А.В., Методы оптимизации в примерах и задачах: Учеб. Пособие. – М.: Высш. школа, 2005.

6. Васильев Ф.П. Численные методы решения экстремальных задач. - М.: Наука, 1980.

7. Сухарев А.Г., Тимохов А.В., Федоров В.В. Курс методов оптимизации. - М.: Наука, 1986.

8. Поляк Б.Т. Введение в оптимизацию. - М.: Наука, 1983.

9. Сеа Ж. Оптимизация. Теория и алгоритмы. - М.: Мир, 1973.

10. Зангвилл У. Нелинейное программирование. Единый подход. - М.: Сов. радио,1973.

11. Банди Б. Методы оптимизации (вводный курс). - М.: Радио и связь,1988.

12. Компьютерное методическое пособие по методам параметрической оптимизации. МГТУ им. Баумана, 1997.

13. http://sapr.mgsu.ru/biblio/optimiz/opt.htm.

14. http://math.nsc.ru/LBRT/k5/Plyasunov/opt-2.html.

15. http://www.matmetod.ru/metods_optimize.