Тема-01-08



Тема 1.8. Многомерная оптимизация

Перейти к Теме 1.7 Теме 1.9 Огл.

1.8.1. Постановка задачи и основные определения

1.8.2. Методы спуска

1.8.3. Метод градиентного спуска с дроблением шага

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

1.8.5. Проблема оврагов. Метод покоординатного спуска

1.8.6. Тестовые задания по теме «Многомерная оптимизация»

1.8.1. Постановка задачи и основные определения

Задача, требующая нахождения оптимального значения функции m переменных f(Х)=f(x1, x2, …, xm), называется задачей многомерной оптимизации. Так же, как и для случая одномерной оптимизации, задача нахождения максимума функции сводится к задаче нахождения минимума путем замены целевой функции f на -f.

Пусть функция f(Х) = f(x1, x2, …, xm) определена на некотором множестве ХRm. Если Х=Rm (т.е. ограничения на переменные x1, x2, …, xm отсутствуют), принято говорить о задаче безусловной минимизации. В противном случае, когда Х Rm, говорят о задаче условной минимизации.

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

В постановке задачи безусловной оптимизации для f(Х)=f(x1, x2, …, xm) требуется найти хотя бы одну точку минимума Х* и вычислить f*=f(Х*). Точка Х*Rm называется точкой глобального минимума функции fна множестве Х, если для всех ХRm выполняется неравенство f(Х*)f(Х). В этом случае значение f(Х*) называется минимальным значением функции fна Rm.

Точка Х*Rm называется точкой локального минимума функции f, если существует такая — окрестность U этой точки (>0), что для всех ХХU выполняется неравенство f(X*)f(X).

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

Рассмотрим функцию нескольких переменных и введем для нее основные определения.

Множество точек, для которых целевая функция принимает постоянное значение f(x1, x2, …, xm) = c, называется поверхностью уровня. Для функции двух переменных (m = 2) это множество называется линией уровня.

Функция f(x1,x2) задает в трехмерном пространстве некоторую поверхность U=f(x1,x2) (рис. 1.8.1-1), низшая точка которой и дает решение задачи минимизации. Для того чтобы изобразить рельеф этой поверхности, проведем несколько плоскостей (U = const): U=c1, U=c2, U=c3 . Проекции на плоскость Ох1х2 линий пересечений этих плоскостей с поверхностью и даютлинии уровня.

Рис. 1.8.1-1

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

или .

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

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

Равенство нулю градиента в точке Х является необходимым условием того, чтобы внутренняя для множества Хi (i = 1, 2,…m) точка Х была точкой локального минимума дифференцируемой функции f. Точка Х, для которой выполняется равенство f’(X) = 0, называетсястационарной точкой функции.

Это равенство представляет собой систему из m нелинейных уравнений относительно компонент х1, х2, …, хm, вектора X, где m – количество переменных.

Для функции двух переменных Q(x, y)это условие имеет вид:

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

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

Для функции двух переменных Q(x, y) матрица Гессе имеет вид:

,

а достаточное условие существования минимума:

Алгоритм решения задачи оптимизации функции двух переменных Q(x,y) аналитическим (классическим) методом следующий:

Составляется и решается система уравнений

из которой находятся (x*, y*).

Проверяются достаточные условия существования минимума

.

Если (x*, y*) – единственное решение и в этой точке выполняются достаточные условия, то это точка минимума. Если хотя бы в одном из неравенств получается знак “<”, то минимума не существует. В случае появления знака “=” необходимо исследовать производные высших порядков.

Пример 1.8.1-1. Найти точку локального минимума функции.

f(x,y) = x2 + y2 – 4x + 100 – 8y.

Следовательно, в точке x*=2 и y*=4 функция имеет локальный минимум.

Пример 1.8.1-2. Найти точку локального минимума функцииf(x,y)= x2+y2–4x+10xy–8y.

Следовательно, функция не имеет точки локального минимума.

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

1.8.2. Методы спуска

Большинство итерационных методов, применяемых для решения задач безусловной минимизации функции нескольких переменных, относятся к классу методов спуска. Это такие методы, для которых каждая итерация (шаг) приводит к уменьшению значения целевой функции: f(xk+1)k), для всех k0.

Структура типичного алгоритма метода спуска для функции двух переменных Q(x,y) состоит в следующем:

Задается начальная точка (x0, y0), принадлежащая области допустимых значений функции.

На текущей k-й итерации (k=0,1, …n) определяется вектор задающий направление спуска, причем такой, чтобы для всех достаточно малых значений >0 (где — коэффициент, являющийся шагом поиска) выполнялось неравенство:

f(xk + pk, yk+ sk) < f(xk,yk).

Вычисляется шаг поиска — k, для которого выполняется условие п.2, и за очередное приближение к точке минимума принимается точка:

(xk+ pk, yk+ sk), где xk+ pk = xk+1, аyk+ sk = yk+1.

Проверяется выполнение критерия окончания итераций. Если критерий метода выполняется, то полагают (x*,y*)(xk+1,yk+1). В противном случае осуществляется переход к п.2 и выполняется следующая итерация.

Последовательность точек х1, х2, …, хk,получаемую методом спуска, называют траекторий спуска.

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

Для использования градиентного метода оптимизации необходимо определить правило выбора шага (k) на каждой итерации и правило прекращения итерационного процесса.

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

Алгоритм метода градиентного спуска приведен на рис. 1.8.2-1.

По способу выбора шага спуска среди градиентных методов наиболее известными являются метод градиентного спуска с дроблением шага (ГДШ) и метод наискорейшего спуска (НС).

Рис. 1.8.2-1. Алгоритм метода градиентного спуска

1.8.3. Метод градиентного спуска с дроблением шага

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

(1.8.3-1)

Выбор шага в методе ГДШ заключается в следующем.

Задается начальное значение шага k = 0 (как правило, 0=0,5). Проверяется условие сходимости, приведенное выше. Если условие сходимости выполняется, то шаг спуска для данной итерации выбран, а если оно не выполняется, то принимают новый шаг k = k/2, и снова проверяют условие сходимости (и т.д.).

Алгоритм метода ГДШ можно описать следующей последовательностью действий:

При k = 0 задаемся начальной точкой спуска (xk, yk), требуемой точностью и начальным шагом 0(пусть 0 =0,5).

Вычисляем значения

(1.8.3-2)

Вычисляем новые значения переменных

(1.8.3-3)

Проверяем условие сходимости:

(1.8.3-4)

Если условие выполняется, то полагаем величину шага равной k, в противном случае k = k/2 и переходим к п.3.

Проверка окончания процесса итераций (необходимого условия существования минимума):

(1.8.3-5)

Если условие выполнено, то минимум найден, а если нет — вычисление координат следующей точки (k=k+1) и передача управления п.2.

Рис. 1.8.3-1. Траектория спуска ГДШ

Алгоритм выбора шага в градиентном методе дробления шага приведен на рис. 1.8.3-2.

Рис. 1.8.3-2. Схема алгоритма выбора шага в градиентном методе дробления шага

Пример 1.8.3-1. Найти минимум функции Q(x,y) методом ГДШ.

Пусть Q(x,y) = x2 +2y2; x0 = 2;y0 = 1.

Проверим достаточные условия существования минимума:

Проделаем одну итерацию согласно алгоритму.

Q(x0,y0) = 6.

При х = x0и y = y0 ,

Шаг k = 0 = 0,5

Таким образом,4 < 8, следовательно, условие сходимости не выполняется итребуется, уменьшив шаг (= /2), повторять п.п.3-4 до выполнения условия сходимости. То есть, полученный шаг используется для нахождения следующей точки траектории спуска.

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

Суть метода состоит в следующем. Из выбранной точки (x0,y0) спуск осуществляют в направлении антиградиента до тех пор, пока не будет достигнуто минимальное значение целевой функции Q(x, y) вдоль луча (рис.1.8.4-1). В найденной точке луч касается линии уровня. Затем из этой точки спуск проводится в направлении антиградиента (перпендикулярном линии уровня) до тех пор, пока соответствующий луч не коснется в новой точке проходящей через нее линии уровня, и т.д.

Рис. 1.8.4-1

Выразим целевую функцию Q(x, y) через шаг . При этом представим целевую функцию на определенном шаге как функцию одной переменной, т.е. величины шага

Величина шага на каждой итерации определяется из условия минимума функции :

= min(()) k = *(xk, yk), >0.

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

аналитический метод (НСА);

численный метод (НСЧ).

В методе НСА значение шага получают из условия , а в методе НСЧ величину k находят на отрезке [0;1]c заданной точностью, используя один из методов одномерной оптимизации.

Алгоритм выбора шага в методе наискорейшего спуска с использованием метода золотого сечения приведен на рис. 1.8.4-2.

Рис. 1.8.4-2. Алгоритм выбора шага в численном методе наискорейшего спуска НСЧ

с использованием метода золотого сечения

Пример 1.8.4-1. Найти минимум функции Q(x,y)=x2 + 2y2с точностью =0.1, при начальных условиях: x0=2; y0=1.

Проделаем одну итерацию методом НСА.

Выразим целевую функцию через величину :

=(x-2x)2+2(y-4y) 2 = x2-4x2+42x2+2y2-16y2+322y2.

Из условия ()=0 найдем значение *:

Полученная функция =(x,y) позволяет найти значение . При x=2 и y=1 имеем =0.3333.

Вычислим значения координат следующей точки:

Проверим выполнение критерия окончания итераций при k=1:

Поскольку |2*0.6666|>0.1 и |-0.3333*4|>0.1 , то условия окончания процесса итераций не выполнены, т.е. минимум не найден. Поэтому следует вычислить новое значение при x=x1 и y=y1 и получить координаты следующей точки спуска. Вычисления продолжаются до тех пор, пока не выполнятся условия окончания спуска.

Отличие численного метода НС от аналитического состоит в том, что поиск значения на каждой итерации происходит одним из численных методов одномерной оптимизации (например, методом дихотомии или методом золотого сечения). При этом в качестве интервала неопределенности служит диапазон допустимых значений — [0;1].

1.8.5. Проблема оврагов. Метод покоординатного спуска

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

Градиентный метод сходится достаточно быстро, если для минимизируемой функции поверхности уровня близки к сферам (при m=2 линии уровня близки к окружностям).

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

В двумерном случае рельеф соответствует поверхности U=Q(x1,x2) и напоминает рельеф местности с оврагом. Поэтому такие функции называют «овражными» (рис.1.8.5-1).

Рис. 1.8.5-1

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

Если начальная точка Х0 попадает на «склон оврага» , то направление градиентного спуска оказывается почти перпендикулярным «дну оврага» и очередное приближение Х1 попадает на противоположный «склон оврага».

Следующий шаг в направлении ко «дну оврага» возвращает приближение Х2 напротивоположный «склон оврага» и т.д.

В результате вместо того, чтобы двигаться вдоль оврага (в направлении точки минимума), траектория спуска совершает зигзагообразные скачки поперек «оврага».

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

Проблему «оврагов» позволяют решать специально разработанные «овражные» и другие методы спуска, например, метод покоординатного спуска.

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

Рассмотрим очередной n+1 цикл одного из вариантов этого метода, считая, что приближение к минимуму функции Q(X)=Q(x1, … xm) уже найдено Хn.

1-й шаг. На первом шаге проводят спуск по координате x1. Значения остальных координат x2 = x2(n) , x3 = x3(n) , … , xm= xm(n) фиксируют, а x1(n) выбирают из условия:

Q(x1(n+1) , x2(n) … xm(n) ) = min Q(x1, x2(n) … xm(n) )

x1

Фактически решается задача минимизации функции одной переменной.

Q(x1) = min Q(x1, x2(n) … xm(n) ).

2-шаг. На втором шаге производится спуск по координате x2. Значения остальных координат x1 = x1(n) , x3 = x3(n) , … , xm= xm(n) фиксируют, а x2(n+1) выбирают как решение задачи одномерной оптимизации

Q(x1(n+1) , x2(n+1) , x3(n) … xm(n+1) ) = min Q(x1(n+1), x2, x3(n) … xm(n) ).

x2

Аналогично осуществляют следующие шаги.

m-й шаг. На последнем шаге координату xm(n+1) определяют из условия

Q(x1(n+1) , x2(n+1) , … xm-1(n+1),xm(n+1) ) = minQ(x1(n+1), … xm-1(n+1),xm).

x2

В результате получается очередное приближение x(n+1) к точке минимума.

Далее цикл метода снова повторяется. Каждый цикл метода состоит из m шагов (т.е. по количеству переменных). Т.к. на k-том шаге очередного цикла значение координаты xk(n+1) определяют из условия минимизации функции f по направлению xk, то необходимо, чтобы в точке (x1(n+1) , x2(n+1) , … xk-1(n+1), xk, xk+1(n+1) , …xm(n+1)) производная обращалась в ноль.

На рисунке изображена графическая иллюстрация циклического покординатного спуска для случая m=2.

Рис. 1.8.5-2

Рис.1.8.5-3. Схема алгоритма метода наискорейшего спуска

1.8.6. Тестовые задания по теме «Многомерная оптимизация»

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

одномерные и многомерные

одномерные и дискретные

дискретные и непрерывные

никак не делятся

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

целевой

оптимальной

векторной

дискретной

Если на значения параметров оптимизации существуют ограничения, то задача оптимизации называется

условной

ограниченной

сложной

векторной

Градиент это

вектор, состоящий из вторых частных производных целевой функции

вектор, позволяющий определить направление убывания функции

вектор, состоящий из первых частных производных целевой функции

в списке нет правильного ответа

Антиградиент направлен

в сторону наискорейшего возрастания целевой функции

в сторону наискорейшего изменения целевой функции

в сторону наискорейшего убывания целевой функции

в списке нет правильного ответа

Достаточным условием существования минимума функции нескольких переменных является

равенство нулю матрицы вторых производных

равенство нулю градиента функции

отличие от нуля градиента функции

матрица вторых производных должна быть положительно определена

отличие от нуля матрицы вторых производных

Точкой стационарности называется точка , в которой

матрица вторых производных равна нулю

градиент функции равен нулю

градиент функции отрицателен

матрица вторых производных отрицательно определена

Модуль градиента показывает

направление возрастания функции

скорость возрастания функции



Страницы: 1 | 2 | Весь текст




map