2. Методы оптимизации

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

Вначале рассмотрим методы поиска min f (x1,…,xn) при условиях (2.1).

Постановка задачи: Найти вектор, доставляющий минимум функции f (x1,x2,…,xn) при условиях, j=1,2,…,m. Другими словами, см. рисунок 2.20, требуется найти точку, в кото-рой функция f (x1,x2,…,xn) достигает минимума, но эта точка должна при-надлежать области D значений x1,x2,…,xn, в которой справедливы все ограничения (2.1). Число ограничений m может быть как больше, так и меньше числа переменных n (рисунок 2.2).

Рисунок 2.1 Иллюстрация к постановке задачи условной оптимизации

Рисунок 2.2 а) пять ограничений вида aix1+bix2+ci ? 0 б) одно ограничение вида

(x1-a) 2+ (x2-b) 2-r2 ? 0

Наиболее популярными методами поиска min f (x₁,x₂,…,x_n) при условиях (2.1) являются методы штрафных функций, прямого поиска с возвратом, возможных направлений, случайных направлений, сравнения значений функции на сетке значений аргументов.

Метод штрафных функций

Рисунок 2.3 Идея метода штрафных функций

Идея метода (рисунок 2.3):

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

Одним из методов безусловной оптимизации осуществляется поиск минимума функции

F (x₁,…,x_n) =f (x₁,…,x_n) + Ш (x₁,…,x_n), (2.2)

где - положительное число, выбираемое таким образом, чтобы всюду за пределами области D выполнялось неравенство

, j= 1,2,…,n.

Функцию штрафа обычно записывают в виде

Ш (x₁,x₂,…,x_n) = , (2.3), где

.

Если ограничение одно (m=1), то необходимо найти минимум функции

F (x₁,…,x_n) = f (x₁,…,x_n) + k [g (x₁,…,x_n)] ²,

где , >> 0.

В области D функция F (x₁,x₂,…,x_n) совпадает с функцией f (x₁,x₂,…,x_n) и процесс поиска ее минимума протекает так же, как и при отсутствии ограничений. В момент выхода за допустимую область функция Ш (x₁,x₂,…,x_n) изменяет направление градиента функции F (x₁,x₂,…,x_n) и осуществляется возврат в допустимую область (рисунок 2.4). Заметим, что возврат осуществляется не по нормали к линии ограничения, а под некоторым углом к ней в сторону уменьшения значений исходной целевой функции f (x₁,x₂,…,x_n).

Рисунок 2.4 Иллюстрация к алгоритму метода штрафных функций

При использовании метода штрафных функций очень важен правильный выбор значения . При слишком малом значении может быть найдена точка за пределами допустимой области, а при слишком большом - функция F (x₁,x₂,…,x_n) образует овраг вдоль поверхности g (x₁,x₂,…,x_n) =0. Метод не чувствителен к выбору начальной точки поиска: если она окажется за пределами допустимой области, то штраф будет включен сразу.

Наиболее популярный алгоритм метода штрафных функций предусматривает формирование функции Ш (x₁,x₂,…,x_n) в начальной точке и использование для поиска min F (x₁,x₂,…,x_n) метода градиента с постоянным шагом, где после каждого изменения значений x₁,x₂,…,x_n вновь формируется функция Ш (x₁,x₂,…,x_n).

Метод прямого поиска с возвратом

В области D допустимых значений аргументов поиск min f (x₁,x₂,…,x_n) осуществляется любым методом безусловной оптимизации (чаще всего используют метод градиента с постоянным шагом и наискорейшего спуска).

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

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

G (x₁,x₂,…,x_n) =, (2.4)

где , т.е. значения параметров задачи изменяются следующим образом:

. (2.5)

Рисунок 2.5 Иллюстрация к методу прямого поиска с возвратом

Здесь - точка, в которой нарушаются ограничения, h - текущее значение шага поиска в области D. Дробление шага производится, когда значение функции в допустимой области увеличивается. Признак окончания поиска - выполнение неравенства h < . Так же, как и метод штрафных функций, метод прямого поиска с возвратом не чувствителен к выбору начальной точки поиска: движение из точки на рисунке 2.5 начнется сразу с применения формулы (2.5).

Рисунок 2.6 Прямой поиск с возвратом при ограничении x₂ x₂^max

На практике ограничения часто задаются в виде: .

При нарушении некоторых из них для возврата в область D по нормали к линии ограничения нет необходимости использовать соотношение (2.5) - достаточно уменьшить или увеличить соответствующие параметры на величину шага поиска (рисунок 2.6).

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

Алгоритм метода прямого поиска с возвратом предусматривает проверку выполнения ограничений (2.1) в начальной точке и после каждого изменения значений x₁,x₂,…,x_n. В случае невыполнения некоторых из них согласно (2.4) формируется функция G (x₁,x₂,…,x_n) и значения x₁,x₂,…,x_n изменяются в соответствии с соотношением (2.5) до тех пор, пока не будет обеспечено выполнение всех ограничений (2.1).

Метод возможных направлений.

Определения: а) _{0 -} конус допустимых направлений поиска min f (x₁,x₂,…,x_n) при условиях , j=1,2,…,m - все направления в окрестности текущей точки, не приводящие к выходу за область D; б) ₁ - конус подходящих направлений - все направления, вдоль которых функция f (x₁,x₂,…,x_n) убывает в окрестности текущей точки; в) ₀₁ - конус возможных направлений - пересечение конусов допустимых и подходящих направлений (все направления, вдоль которых функция f (x₁,x₂,…,x_n) убывает при выполнении ограничений).

Для любой точки (x₁,x₂,…,x_n), лежащей на поверхности ограничений, в центре конуса ₁ находится вектор [ - grad f (x₁,x₂,…,x_n)], в центре конуса ₀ - вектор gradG (x₁,x₂,…,x_n) (функция G (x₁,x₂,…,x_n) формируется согласно (2.4)). Центру конуса возможных направлений будет соответствовать векторная сумма [-grad f (x₁,x₂,…,x_n)] и gradG (x₁,x₂,…,x_n), т.е. направление

, i= 1,…,n (2.6)

В точке условного минимума функции , см. рисунок 2.26, конусы допустимых и подходящих направлений не пересекаются, т.е. ₀₁ = Ш: векторы [-grad f (x₁,x,…,x_n)] и gradG (x₁,x₂,…,x_n) лежат на одной прямой и направлены в противоположные стороны.

Алгоритм поиска условного минимума функции f (x₁,x₂,…,x_n) методом возможных направлений сводится к следующему: из начальной точки внутри области D осуществляется поиск min f (x₁,x₂,…,x_n) любым методом безусловной оптимизации (более предпочтителен метод градиента с постоянным шагом); при выходе за пределы области D поиск с предыдущей точки ведется в направлении, определяемом формулой (2.6); дробление шага поиска осуществляется, когда движение в центре конуса возможных направлений приводит к возрастанию целевой функции, либо когда первый же шаг в этом направлении приводит к нарушению ограничений; окончания поиска - при выполнении неравенства h <.

Рисунок 2.7 Иллюстрация к методу возможных направлений

Замечания:

1. Величина шага поиска в направлении, определяемом (2.6), должна быть постоянной (равной h), т.е. значения переменных x₁,x₂,…,x_n следует изменять в соответствии с выражением

, i=1,…,n; k=0,1,…, (2.7)

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

2. Метод возможных направлений чувствителен к выбору начальной точки поиска за - пределами области допустимых значений параметров x₁,x₂,…,x_n возможные направления отсутствуют и алгоритм метода неработоспособен.

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

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

Постановка задачи: Найти вектор X^* = (x₁^*,x₂^*,…,x_n^*), доставляющий минимум функции f (x₁,x₂,…,x_n) при условиях (2.2), т.е. , k = 1,2,…,p.

Рисунок 2.8 Поиск min f (x₁,x₂) при условии h (x₁,x₂) =0

При решении подобных задач связи , k=1,…,p заменяются ограничениями

,k=1,…, р, (2.8)

см. рисунок 2.8, и задача решается методом штрафных функций, прямого поиска с возвратом или возможных направлений. Чем меньше значения _k, тем ближе решение новой задачи к исходной, но сложнее поиск. Обычно задают начальные значения _k, k=1,2,…, р (не слишком маленькие), находят решение новой задачи, а затем постепенно уменьшают _k, пока они не станут меньше заданной точности. Так же поступают со связями в случае решения задачи условной оптимизации при наличии и ограничений и связей.

Для нахождения начальной точки поиска, удовлетворяющей неравенствам (2.8), рекомендуется найти значения x₁,x₂,…,x_n, доставляющие минимум функции

.

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

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

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

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

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

1. Функция F (X) может иметь сложную форму. Для графической интерпретации поверхности принято изображать ее с помощью линий уровня. Линия уровня - это кривая в 2-х мерном сечении пространства параметров, значение функции, на которой константа.

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

Это не имеет себе аналогий в классе одномерных функций. ("Седло" - точка гладкой поверхности, вблизи которой поверхность лежит по разные стороны от своей касательной плоскости.

В окрестности седла имеются 4 интегральные кривые, которые входят в особую точку. Между ними располагаются интегральные кривые типа гипербол).

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

3. Переменные х₁, х₂,., х_n могут быть взаимосвязаны.

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

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

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

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

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

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

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

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

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

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

2. Выбор направления поиска очередной точки (на основании исследования локальных свойств целевой ф-ии).

3. Выбор величины шага до новой точки вдоль выбранного направления.

4. Переход в очередную точку итерационного процесса.

5. Проверка критерия окончания итерационного процесса.

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

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

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

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

(норма разности 2 последовательных итераций)

(норма разности 2 последовательных значений критериев оптимальности)

(модуль градиента этого критерия)

(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. Метод покоординатного спуска (Гаусса-Зейделя).

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

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

Направления, конечно, фиксированы.

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

.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В этом методе направление из касается линии в

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

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

Условия окончания итерационного поиска в градиентных методах связывают обычно с величиной градиента (критерий с номером 3).

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

Метод сопряженных градиентов является попыткой объединить достоинства методов первого и второго порядков с исключением их недостатков.

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

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

Для квадратичной функции (очень эффективен) значение оптимума этим методом можно получить за n шагов, где n - размерность задачи.

Метод тяжелого шарика

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

Скорость шарика при движении вниз будет возрастать, и он будет стремиться занять нижнее положение, т.е. точку минимума.

X_i+1 = X_i - (X_i - X_i-1) - h gradF (X_i)

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

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

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

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

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

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

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

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

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

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

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

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

- относительное время.