Безусловная минимизация функций многих переменных

Выпуклые множества и выпуклые функции.

Пусть Е^п - п-мерное евклидово пространство арифметических векторов . Множество U Ì Е^п называется выпуклым, если вместе с любыми двумя точками оно содержит и отрезок, соединяющий эти точки, т. е.

для всех                                (9.1)

Пример 9.1. Показать, что множество точек  пло­скости  выпукло.

Пусть и , a  - точка отрез­ка, соединяющего точки  и . Покажем, что x Î U. Имеем:

Используя неравенства (т.к. , а также , получим: , т.е. x Î U

Рис.9.1.

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

Проверка условия (2.1) в большинстве случаев требует громозд­ких выкладок, поэтому на практике при исследовании выпуклости множеств в пространствах Е² и Е³ часто используют геометриче­ские иллюстрации, подобные рис. 9.1.

Функция f( x), заданная на выпуклом множестве U, назы­вается выпуклой на этом множестве, если для любых точек  и произвольного числа  справедливо неравенство

                                    (9.2)

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

Если f(х) - дважды дифференцируемая на выпуклом множестве U функция и матрица ее вторых производных (гессиан) положительно определена при всех x Î U, то функция f(х) является выпуклой на множестве U.

это утверждение можно сформулировать в более удобном для про­верки виде:

Если все угловые миноры матрицы, f" (х) положительны при хÎ U, то функция f(х) выпукла на множестве U.

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

Пример 9.2. Выяснить, является ли функция  выпуклой в пространстве Е².

Запишем матрицу вторых производных.

 

Найдя угловые миноры этой матрицы ,

убеждаемся, что  при всех х, т. е. функция f(х) выпукла.

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

Если положить то получим симметрическую матрицу , с помощью которой можно представить квадратичную функ­цию в виде

                                                  (9.3)

где ,  - векторы-столбцы.

Градиент и матрица вторых производных функции (9.3) равны

.

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

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

а) Найти матрицу Q и вектор r в представлении (2.3) функции f(x).

б) Найти градиент f’( x).

в) Выяснить, является ли функция f(х) выпуклой.

В данном случае , поэтому:

Используя найденные матрицу Q и векторr, запишем:

Найдем угловые миноры  матрицы :

Так как  то функция f( x) выпукла.

Постановка задачи минимизации функции п переменных  на множестве U Ì Е^п не отличается от постановки в одномерном случае. Если U = Е^п, то говорят о безусловной минимизации функции f( x).

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

Градиентные методы

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

                                         (9.4)

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

                                      (9.5)

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

Существует много различных способов выбора a_k, нонаиболее распространены два: первый называется методом с дроблением шага и связан с проверкой на каждой итерации некоторого неравенства (см. ниже неравенство (9.6)); во втором при переходе из точки x_k, в точку x^(k+1) функция минимизируется по a - метод наискорейшего спуска. Соответствующие итерационные процессы рассматриваются далее.

9.2.2. Градиентные методы с дроблением шага. Методы с постоянным шагом. Рассмотрим процесс (9.4). Первая проблема, с которой мы сталкиваемся при его реализации - это выбор шага a_k. Достаточно малый шаг a_k  обеспечит убывание функции, т. е. выполнение неравенства:

                                          (9.6)

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

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

Геометрически градиентный спуск с дроблением шага изображен на рис. 2.2. Здесь изображены линии уровня функции f( x), имеющей минимум в точке х_*, причем и некоторая зигзагообразная траектория , ортогональная в каждой точке соответствующим линиям уровня и приводящая из началь­ной точки х₀ в точку минимума х_*. Ломаная  аппроксимирует так называемую градиентную кривую, которая удовлетворяет дифференциальному уравнению

                                                       (2.7)

 

Рис.9.2. Схема градиентного спуска

Это уравнение, в свою очередь, получается из дискретного соотношения (9.4) при α → 0, а сама итерационная схема (9.4) может рассматриваться как схема метода Эйлера для решения дифференциального уравнения 9.7).

Заметим, что процедура проверки неравенства (9.6) на каждой итерации является довольно трудоемкой. Если известны некоторые параметры, характеризующие функцию f(х), можно использовать вариант метода (9.4) с постоян­ным на всех итерациях шагом, при котором функция f(х) заведомо монотонно убывает. Пусть, например, сущест­вует константа R такая, что неравенство

                                            (9.8)

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

                                                        (9.9)

Если известна равномерная по х оценка М сверху мак­симального собственного числа матрицы f’(х), выполнение неравенства (2.6) обеспечивается выбором шага по формуле

                                                 (9.10)

При спуске с постоянным шагом трудоемкость каждой итерации минимальна (нужно вычислять только градиент f ’( x_k )). Однако значения постоянных R, М обычно заранее неизвестны.

9.2.3.Алгоритм метода градиентного спуска с дроблением шага. Пусть f(х) - выпуклая дифферен­цируемая во всем пространстве Е^п функция и требуется найти ее точку минимума х*. Выбрав произвольное начальное приближение  построим последовательность

                                      (9.11)

где величины  (параметрические шаги) выбираются достаточно малыми для того, чтобы выполнялось условие:

                                     (9.12)

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

или

,                                                (9.13)

 где e - заданное достаточно малое число, после чего полагают .

Если при некотором k условие (9.12) нарушается, то шаг  в (9.11) уменьшают (дробят) в заданное число раз до выполнения неравен­ства (9.12) и продолжают вычисления.

Пример 9.4. Минимизироватьфункцию   методом градиентного спуска, завершив вычис­ления при

Выбрав начальное приближение  и = 1, построим последовательность (9.11), записывая результаты вычислений в таб­лице 9.1.

 

Таблица 9.1

k							Примечание
0	0	0	1	1	1	1
	-1	-1	3, 145	-	-		Условие (9.12) нарушено. Умень­шаем  в 2 ра­за
	0	0	1	1	1	0, 5
	-0, 5	-0, 5	1, 118	-	-		Условие (9.12) на­рушено. Уменьшаем  в 2 раза
	0	0	1	1	1	0, 25
1	-0, 25	-0, 25	0, 794	0, 106	-0, 393	0, 25	Условие (9.12) выполнено
2	-0, 277	-0, 152	0, 774	0, 098	0, 045	0, 25	То же
3	-0, 301	-0, 163	0, 772	0, 026	-0, 023	-	Точность дос­тигнута

Итак, х* » (-0, 301, -0, 163), f* » 0, 772.

Для квадратичной функции (9.3) формула (9.11) принимает вид:

                                   (9.14)

9.2.4. Метод наискорейшего спуска. Как показано выше, можно выбрать некоторую посто­янную для всех итераций величину шага, обеспечивающую убывание функции f(х) от итерации к итерации. Однако обычно шаг при этом оказывается очень малым, что при­водит к необходимости проводить большое количество итераций для достижения точки минимума. Поэтому методы спуска с переменным шагом являются более эко­номными. Процесс, на каждой итерации которого шаг α _k выбирается из условия минимума функции f( x) в направ­лении движения, т. е.

                            (9.15)

называется методом наискорейшего спуска. В этом вари­анте градиентного спуска на каждой итерации требуется решать задачу одномерной минимизации (9.15). Разумеется, этот способ выбора α _k, сложнее, чем рассмотренные ранее.

 

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

Геометрическая интерпретация метода наискорейшего спуска представлена на рис. 9.3.

В этом методе, в отличие от обычного градиентного спуска, направление движения из точки х^(k), касается линии уровня в точке х^(k+1). Последовательность точек , ... зигзагообразно приближается к точке мини­мума х*, причем звенья этого зигзага ортогональны между собой. В самом деле, шаг α выбирается из условия мини­мизации по α функции

,

и поэтому

.

 

Таким образом, направления спуска на двух последова­тельных итерациях взаимно ортогональны (рис. 9.4).

Рис.9.4.

 

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

Пример 9.5. Решить пример 2.4 методом наискорейшего спуска.

Шаг 8. Положим , тогда .

Для нахождения точки минимума функции используем метод перебора:

a	0, 18	0, 20	0, 22	0, 24	0, 26
	0, 7949	0, 7903	0, 7892	0, 7916	0, 7973

 

т.e. , откуда .

Шаг 2.

Минимизируем :

a	0, 28	0, 30	0, 32	0, 34	0, 36
	0, 77401	0, 77384	0, 77380	0, 77387	0, 77408

 

т.e. , откуда = (-0, 22, -0, 22) - 0, 32 (0, 204, -0, 236) = (-0, 2853, -0, 1445).

Шаг 3.

Минимизируем :

a	0, 20	0, 22	0, 24	0, 26	0, 28
	0, 77273	0, 77241	0, 77240	0, 77241	0, 77244

т.e. , = (-0, 3045, -0, 1619), , поэтому требуемая точность достигнута и х* » (-0, 305, -0, 162), f* » 0, 772

Если f( x) - квадратичная функция (2.3), то величинаα _k может быть найдена в явном виде

                                                  (9.16)

Таким образом, для квадратичной функций метод наискорейшего спуска состоит в построении последовательности  по формулам (9.14), (9.16).

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

Пусть - начальное приближение. Вычислим частную производ­ную по первой координате  и примем

,

где е₁={l, 0, ..., 0} - единичный вектор оси х_8.

Следующая итерации состоит в вычислении точки х⁽²⁾по формуле

,

где е₂ = {0, 1, 0, ..., 0} - единичный вектор оси х₂ и т. д. Таким образом, в методе покоординатного спуска мы спускаемся по ломаной, состоящей из отрезков прямых, параллельных координатным осям (рис. 2.7).

 

Рис.9.7. Метод покоординатного спуска

Спуск по всем п координатам составляет одну «внеш­нюю» итерацию. Пусть k - номер очередной внешней ите­рации, a s - номер той координаты, по которой произво­дится спуск. Тогда рекуррентная формула, определяю­щая следующее приближение к точке минимума, запишется в следующем виде:

или, в координатной форме,

После s = n счетчик числа больших итераций k увели­чивается на единицу, а s принимает значение, равное единице.

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

то мы получаем координатный аналог метода наискорей­шего спуска, называемый обычно методом Гаусса (или Гаусса— Зейделя).

⇐ Предыдущая123456789Следующая ⇒

Поделиться: