Лекция: Методы безусловной оптимизации нелинейного программирования

Математическая постановка задачи оптимизации Математическая постановка задачи оптимизации включает в себя целевую функцию f0(X), Х=(х1, х2, ...., хn), представляющую собой количественную оценку качества решения, и допустимое множество Xd, представляющее собой множество допустимых вариантов решения. Решением задачи оптимизации является такой вектор Х* Хd, который минимизирует или максимизирует целевую функцию f0(X). Очевидно, что всякую задачу максимизации f0(X) можно заменить задачей минимизации функции –f0(Х), поэтому в дальнейшем будем рассматривать оптимизационные задачи вида

f0(Х)→min (2.1)

при X Xd.

Если допустимое множество Хd лежит в евклидовом пространстве Rn, то задачи вида (2.1) называют конечномерными оптимизационными задачами, а теорию и методы решения конечномерных задач — математическим программированием.

Классификацию задач оптимизации можно проводить по нескольким признакам в зависимости от вида функции f0(X) и допустимого множества Xd.

2. Задачи безусловной и условной оптимизации

Если множество Хd совпадает с Rn, то имеет место задача безусловной оптимизации. В задачах условной оптимизации множество Хd определяется, как правило, системой линейных и нелинейных ограничений (равенств и неравенств). В этом случае имеет место наиболее общий случай конечномерной оптимизационной задачи, называемой общей задачей математического программирования:

f0(X) →min (2.2)

при условиях

fi(X)≥0, i=1, …, p,

fi(X)=0, i=p+1, …, m.

В частных случаях задача (2.2) может не содержать ограничений-равенств или ограничений-неравенств.

Геометрическую интерпретацию задач оптимизации и методов нахождения их решений удобно проводить на примере двумерных задач с отображением целевой функции в виде линий равного уровня (равных значений), а множества Хd — в виде соответствующей области на координатной плоскости (рис.2.1). Пересечение частей плоскости, определяемых неравенствами fi(X)≥0 (заштрихованные части) определяет допустимое множество Хd. Векторы f0(Х) и — f0(Х) — соответственно градиент и антиградиент функции f0(X) в некоторой точке X, показывающие направления наискорейшего возрастания и убывания функции в этой точке.

В зависимости от вида функций f0(Х) и fi(X) выделяют частные случаи задачи (2.2). Если f0(X) и fi(X) — линейные функции, то имеет место задача линейного программирования. Если хотя бы одна из функций f0(X) или fi(X) нелинейна, то задача (2.2) есть задача нелинейного программирования. В том случае, если допустимое множество Хd конечно или счетно и не имеет предельных точек, то имеет место задача дискретного программирования. Частным случаем последней является задача целочисленного программирования, когда все допустимые точки имеют целочисленные координаты.

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

Для каждого типа конечномерных оптимизационных задач существуют свои численные методы их решения. Разработанный комплекс лабораторных работ в рамках учебной дисциплины «Оптимизация» предназначен для практического изучения наиболее распространенных методов решения одномерных и многомерных задач безусловной и условной оптимизации.

РЕШЕНИЕ ЗАДАЧИ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ

МЕТОДАМИ ПОКООРДИНАТНОГО СПУСКА И СИМПЛЕКСНЫМ

Методика решения

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

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

Рассмотрим вначале метод покоординатного спуска Гаусса-Зейделя на примере функции двух переменных, линии равного уровня которой изображены на рис.2.6. Из некоторой начальной точки x0=(x10, x20) производитсяпоиск минимума вдоль направления оси х1 с получением точки X0. В этой точке касательная к линии равного уровня параллельна оси х1. Затем из точки X0производится поиск минимума вдоль направления оси х2 с получением точки x1. Следующие итерации выполняются аналогично. Для минимизации функции f0(x) вдоль осевых направлений может быть использован любой из методов одномерной минимизации. Для локализации отрезка, содержащего точку минимума в осевом направлении, может быть использована, например, следующая процедура. Обозначим через у1 значение х10, а через y2 — значение x10+, где >0. Вычислим значения f0(у1,х20), f0(у2, х20).

Пусть, например, f0(y1, x20) >f0(y2, x20). Тогда следует вычислять значения f0(yi, х20), yi=yi-1 +, i= 3, 4,… до тех пор, пока не будет найдена такая точка уi, что f0(yi,x20) f0(yi-1,x20). В этом случае отрезком локализации минимума функции f0вдоль направления оси х1, проходящего через точку Х0, будет являться отрезок [yi-2,yi]. При этом можно выбирать =const или, i>0. В том случае, если f0(y1, x02) f0(y2,x02), то y1=y2, и процедура локализации отрезка выполняется подобно описанной выше. В этом случае отрезком локализации будет являться отрезок [yi, yi-2].

Аналогичным образом определяется отрезок локализации функции f0вдоль направления оси х2.

Критерием окончания поиска является выполнение условия:

Для минимизации функций многих переменных М.Пауэлл предложил использовать следующую модификацию метода Гаусса-Зейделя. После получения точки локальным поиском вдоль координатных осей выполняется поиск вдоль направления, соединяющего точки Х0и (рис. 2.7) с получением точки X1, т.е. Х1=X0+h0( ), где h0вычисляется из условия того, что точка Х1 является точкой минимума функции f0вдоль направления

S0=, т.е. h0 =argmin(f0(X°+hS°)

Значение h0отыскивается любым из методов одномерной минимизации. Для локализации отрезка [h’ ,h” ], содержащего минимум по h, необходимо использование процедуры локализации, описанной выше. При этом очевидно, что в точке Х0h0=0, в точке h0=1.

Следующие итерации выполняются аналогично.

Симплексный метод

Множество (n+1)-й равноудаленной точки в n-мерном пространстве называется правильным симплексом. В случае n=2 правильным симплексом является равносторонний треугольник. Идея симплексного метода состоит в сравнении значений функции в (n+1) вершинах симплекса и перемещении его в направлении наилучшей точки. Симплексный метод, допускающий как правильные, так и неправильные симплексы, является одним из самых эффективных методов нулевого порядка при n 6.

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

1. Задаются n+1 точка Х1, Х2 ,...,Xn+1, являющиеся вершинами начального симплекса.

2. Вычисляются величины f1 =f0(X1), …, fn+1 =f0(Xn+1).

3. Определяются вершины h, g, l, для которых fh — наибольшее значение среди всех fi, i=l,…, n+l; fg — следующее за наибольшим; fl — наименьшее значение.

4. Определяется центр тяжести ХC всех точек, кроме Хh

и вычисляется значение целевой функции f0в точке ХC – fC.

5. Выполняется операция отражения точки Хh относительно точки XC с коэффициентом отражения и получением точки X0(рис. 2.8). При этом X0-XC= (XC-Xh), откуда X0=(1+ )XC — Xh. Вычисляется значение целевой функции f0, в точке Х0– f0.

6. Значение f0сравнивается со значениями f1 и fg. Возможны три случая:

6.1. Если f0< f1, то направление из точки XC в точку Х0является наиболее предпочтительным для перемещения. В этом случае выполняется операция растяжения симплекса с коэффициентом растяжения и получением точки Xr. При этом Xr-XC= (X0-XC),

откуда Xr=(1- )XC — X0.

Далее вычисляется значение целевой функции f0в точке Хr-fr и осуществляется его сравнение со значением f1. Возможны два случая:

6.1.1. Если fr < f1, то точка Хh перемещается в точку Хr, образуя новый симплекс, текущая итерация заканчивается и выполняется переход к шагу 10 для проверки критерия останова.

6.1.2. Если fr f1, то точка Xr отбрасывается, т.к. перемещение было выполнено слишком далеко. В этом случае точка Хh перемещается в точку Х0, образуя новый симплекс, текущая итерация заканчивается и выполняется переход к шагу 10 для проверки критерия останова.

Рис.2.8. Операция отражения и растяжения симплекса

6.2. Если f1< f0fg_, то Х0является не самой плохой точкой. В этом случае точка Хh перемещается в точку Х0и выполняется переход к шагу 10.

6.3. Если f0> fg, то выполняется переход к шагу 7.

7. Выполнение операции сжатия симплекса. Возможны два варианта сжатия в зависимости от значений f0и fh.

7.1. Если f0< fh, то результатом операции сжатия является точка XS, определяемая из условия

XS-XC= (X0-XC) или XS= X0+(1- )XC

В этом случае точка ХS будет лежать между XC и Х0(рис.2.9а).

7.2. Если f0 fh, то результатом операции сжатия является точка ХS, определяемая из условия

XS –XC = (Xh-XC) или XS = Xh + ( 1- )XC.

В этом случае точка XS будет лежать между Xh и XC (рис.2.9б). Далее вычисляется значение целевой функции в точке XS – fS.

8. Сравниваются значения fh и fS.

8.1. Если fS< fh, то точка Хh перемещается в точку XS, образуя новый симплекс, текущая итерация заканчивается и выполняется переход к шагу 10.

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

9. Выполнение операции уменьшения размеров симплекса. Размерность симплекса уменьшается относительно точки Xl путем уменьшения в 2 раза расстояний от точки Xl до всех остальных вершин симплекса (рис.2.10). При этом

Xi=Xi + (Xi-X1),

i ≠ 1.

Затем вычисляются значения fi=f0(Хi), i=l,..., n+l, и выполняется переход к шагу 10.

10. Проверка критерия останова. Процесс поиска прекращается, если по завершении очередной k-й итерации выполняется условие

, где /(n+1) и

Если условие не выполняется, то осуществляется переход к шагу 3.

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

X2= X1+kE1, X3= X2+kE2,..., Xn+1 =Xn+ kEn, где

Ej=(e1,e2, …, ej, …, en) – вектор, у которого ej=1, а остальные элементы равны 0, j=1,…, n, k — произвольная длина шага.

РЕШЕНИЕ ЗАДАЧИ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ МЕТОДАМИ

НАИСКОРЕЙШЕГО СПУСКА И СОПРЯЖЕННЫХ ГРАДИЕНТОВ

Методика решения

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

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

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

Рассмотрим использование метода наискорейшего спуска для минимизации функции двух переменных f0(х1, x2). Пусть в качестве начального приближения выбрана некоторая точка Х0= ( ). Каждая итерация при поиске минимума методом наискорейшего спуска состоит из двух этапов. На первом этапе в точке Х0вычисляются значения частных производных по переменным х1, x2, которые определяют направление градиента функции f0(X) в этой точке. На втором этапе определяется следующая точка Х1 как X1=X0+h0S0, где S0= — антиградиент функции f0в точке X0, h0 — неизвестное значение коэффициента h.

Значение h0вычисляется из условия того, что точка Х1 является точкой минимума функции f0(X) вдоль направления антиградиента, т.е.

h0=argmin f0(X0+hS0).

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

Для произвольных k-й итерации и функции n переменных следующее приближение Хk+1 к точке минимума Х вычисляется как

.

Поиск заканчивается при выполнении следующего условия:

(2.3)

где — заранее заданное положительное число.

Для приближенного вычисления частных производных целевой функции f0(Х) по переменным хi, i=l, ..., n, в точке Хk используется разностная схема:

где — малое приращение по переменным хi, i=1,..., n.

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

Метод сопряженных градиентов

Функция n переменных, приводимая к виду

, (2.4)

называется квадратичной функцией. В векторной форме записи функцию f0( X) можно представить в виде

f0(X)=

где Х=(х1, x2,..., хn ) — вектор-строка; — вектор-столбец; T- символ транспонирования; A=(aij ), i, j=l,..., n – симметричная матрица размера n n; B=(bi), i=1,…, n — постоянный вектор размера n, с — константа.

Для квадратичных функций

Идея метода сопряженных градиентов основана на стремлении минимизировать квадратичную функцию за конечное число шагов. Для этого требуется найти направления S0, S1,..., Sn-1 такие, что последовательность n одномерных минимизаций вдоль этих направлений приводит к отысканию минимума функции (2.5) при любом начальном приближении X0.

Указанным свойством обладает система взаимно сопряженных относительно матрицы вторых производных А векторов. Два вектора Sk и Sk+1 называются сопряженными (относительно матрицы A), eсли они отличны от нуля и для них выполняется условие

(Sk)A(Sk+1)T=0.

Векторы S0,S1,…, Sk называются взаимно сопряженными, если все они отличны от нуля и для любых i, j=0,..., k и i≠j выполняется условие

(Si)A(Sj)T=0 .

Частным случаем сопряженности векторов Sk и Sk+1 является случай их ортогональности (перпендикулярности), когда матрица А представляет собой единичную матрицу.

В методе сопряженных градиентов система взаимно сопряженных направлений строится по правилу

где коэффициент определяется из условия сопряженности векторов Sk и Sk-1, т.е.

(Sk-1)A(Sk)T=0

(Sk-1)A( .

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

(2.6)

Для произвольной k-й итерации следующее приближение Хk+1 к точке минимума Х* определяется из условия того, что точка Хk+1 является точкой минимума функции f0(X) вдоль направления, определяемого вектором Sk, т.е.

Xk+1=Xk +hkSk, .

Локализация отрезка (h’, h”) содержащего значение hk, и поиск значения hk выполняются с использованием тех же процедур, что и в методе наискорейшего спуска.

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

(2.7)

В таком виде оно может быть использовано как для минимизации квадратичных, так и неквадратичных функций, у которых значения вторых производных в точках Хk, k=0,1,…, не являются неизменными.

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