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

Г.И.Шкатова, Методы оптимизации

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

 

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

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

 

Особенности поиска экстремума функции многих переменных

 

Задачи отыскания экстремумов  в многомерном случае существенно  осложняются. Возникают следующие  качественно новые стороны рассматриваемой задачи:

1. Функция F(X) может иметь сложную форму. Для графической интерпретации поверхности принято изображать ее с помощью линий уровня. Линия уровня – это кривая в 2-х мерном сечении пространства параметров, значение функции, на которой константа. Поверхность, соответствующая зависимости F(X) может иметь: «овраги» или «гребни» (поверхности уровня имеют структуру, сильно отличающуюся от сферической); «плато» (плоские горизонтальные участки); особые точки типа «седло». Это не имеет себе аналогий в классе одномерных функций. («Седло» – точка гладкой поверхности, вблизи которой поверхность лежит по разные стороны от своей касательной плоскости. В окрестности седла имеются 4 интегральные кривые, которые входят в особую точку. Между ними располагаются интегральные кривые типа гипербол).
2. Если в одномерном случае имеется только два возможных направления поиска, то в многомерном – таких направлений ¥. В связи с этим центральной проблемой поиска экстремума многомерной функции является проблема выбора направления поиска.
3. Переменные х₁, х₂, . . . , х_n могут быть взаимосвязаны.
4. В многомерном случае область допустимых значений имеет бесчисленное множество форм.

 

Стратегия методов безусловной оптимизации 

 

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

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

Большинство применяемых на практике прямых методов решения задач  математического программирования являются итеративными.

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

 

Общее правило построения последовательности численными методами безусловной оптимизации записывается в виде:

 

 

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

 

Стратегия предполагает на очередной итерации следующие шаги:

1. Задание начальной точки поиска, из которой производится спуск к минимуму.
2. Выбор направления поиска очередной точки (на основании исследования локальных свойств целевой ф-ии).
3. Выбор величины шага до новой точки вдоль выбранного направления.
4. Переход в очередную точку итерационного процесса.
5. Проверка критерия окончания итерационного процесса.

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

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

 

Критерии  для завершения поиска

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

1.    (норма разности 2 последовательных итераций)
2.   (норма разности 2 последовательных значений критериев оптимальности)
3.    (модуль градиента этого критерия)

(1) – недостаточна, т.к.  функция может иметь поведение  типа скачка (резкое изменение  критерия оптимальности).

(2) – основана на  предположении монотонного убывания величины в зависимости от числа итераций . При пологом характере F(X) вблизи оптимума, разность может мало меняться даже при большом шаге, поэтому (1)+(2).

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

 

Оценка  эффективности методов оптимизации

 

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

1. Точность поиска – значение окрестности локального оптимума, в которую приводит алгоритм после выполнения заданного числа итераций.
2. Скорость сходимости – число итераций, необходимое для достижения заданной точности.
3. Время счета – время поиска на ЭВМ локального оптимума с заданной точностью, отнесенное к коэффициенту сложности задачи (или к быстродействию ЭВМ).
4. Стабильность – свойство алгоритма незначительно увеличивать число итераций при малых возмущениях выбора начальных точек, а также вследствие погрешности вычислений.
5. Надежность - свойство алгоритма приводить к оптимуму при многократном повторении поиска из разных начальных точек.

 

 

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

 

Классификация методов на основании порядка  производных при выборе направления

1. методы нулевого порядка – используют лишь значения функции;
2. методы первого порядка – используют значения функции и векторы первых производных;
3. методы второго порядка, в которых определяются матрицы вторых производных;
4. методы более высоких порядков обычно не применяются.

 

Классификация методов на основании выбора метода аппроксимации целевой функции

1. линейные методы, в которых используется локальная аппроксимация функции в окрестности точки линейным полиномом с помощью вектора – градиента F^/(X);
2. квадратичные методы, в которых принята локальная квадратичная аппроксимация с помощью F^/(X) и матрицы вторых производных F^//(X);

 

 

Методы  нулевого порядка

 

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

 

1. Метод  покоординатного спуска (Гаусса-Зейделя).

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

 

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

   

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

 

 

 

Рис.1

 

 

 

 

 

 

 

 

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

 

2. Метод Розенброка

Метод Розенброка направлен  на ликвидацию одного из недостатков метода покоординатного спуска — высокую чувствительность к выбору системы координат. Метод сводится по сути к отысканию «удачной» системы координат путем поворота исходных осей координат. После чего осуществляется поиск поочередно по всем переменным последовательно. Первый цикл поиска совпадает с Г.-З. А далее поворот в зависимости от вектора смещения точки поиска.

 

Рис.2

 

3. Симплексный метод (метод деформируемого многогранника)

 

Симплексом в n- мерном пространстве называют фигуру, содержащую n+1 вершину. На плоскости – треугольник,  в трехмерном пространстве – тетраэдр и т.д. Если все вершины симплекса равно удалены друг от друга, то такой симплекс называется регулярным.

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

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

Рис.3

 

4. Метод параллельных касательных

Из двух произвольных точек, не лежащих на одной прямой заданного направления, проводят два спуска по направлению и находят две точки оптимума (х11,х21). Далее оптимум (х31) ищут на прямой линии, соединяющей эти точки. Во всех поисках по направлению могут применяться любые одномерные методы поиска. Затем — в направлении  прямой (х11,х31) ,…. Возникновение названия связано с тем, что метод использует свойство семейства концентрических эллипсов, которыми обычно являются линии уровня. Минимум лежит на общем центре линии, соединяющей точки касания.

 

 

Рис.4

 

 

 

Градиентная оптимизация

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

 

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

 

 

Рис.5

 

 

 

 

 

 

 

 

 

 

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

 

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

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

Однако, значения R и M обычно заранее неизвестны.

Разработаны различные  методы, относящиеся к группе градиентного спуска. Среди них: с постоянным шагом, с дробным шагом и наискорейшего спуска.

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

 

 

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