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

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

f₀(X) →min (2.2)

при условиях

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

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

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

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

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

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

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

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

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

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

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

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

Рассмотрим вначале метод покоординатного спуска Гаусса-Зейделя на примере функции двух переменных, линии равного уровня которой изображены на рис.2.6. Из некоторой начальной точки x⁰=(x₁⁰, x₂⁰) производится поиск минимума вдоль направления оси х₁ с получением точки X⁰. В этой точке касательная к линии равного уровня параллельна оси х₁. Затем из точки X⁰ производится поиск минимума вдоль направления оси х₂ с получением точки x¹. Следующие итерации выполняются аналогично. Для минимизации функции f₀(x) вдоль осевых направлений может быть использован любой из методов одномерной минимизации. Для локализации отрезка, содержащего точку минимума в осевом направлении, может быть использована, например, следующая процедура. Обозначим через у₁ значение х₁⁰, а через y₂ - значение x₁⁰+, где>0. Вычислим значения f₀(у_1,х₂⁰), f₀(у₂,х₂⁰).

Пусть, например, f₀(y₁, x₂⁰) >f₀(y₂, x₂⁰). Тогда следует вычислять значения f₀(y_i,х₂⁰), y_i=y_i-1 + , i= 3, 4,… до тех пор, пока не будет найдена такая точка у_i, что f₀(y_i,x₂⁰) f₀(y_i-1,x₂⁰). В этом случае отрезком локализации минимума функции f₀ вдоль направления оси х₁, проходящего через точку Х⁰, будет являться отрезок [y_i-2,y_i]. При этом можно выбирать =const или ,i>0. В том случае, если f₀(y₁, x₀²) f₀(y₂,x₀²), то y₁=y₂, и процедура локализации отрезка выполняется подобно описанной выше. В этом случае отрезком локализации будет являться отрезок [y_i , y_i-2].

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

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

Для минимизации функций многих переменных М.Пауэлл предложил использовать следующую модификацию метода Гаусса-Зейделя. После получения точки локальным поиском вдоль координатных осей выполняется поиск вдоль направления, соединяющего точки Х⁰ и (рис. 2.7) с получением точкиX¹, т.е. Х¹=X⁰+h₀(), где h₀ вычисляется из условия того, что точка Х¹ является точкой минимума функции f₀ вдоль направления

S⁰=,т.е. h₀ =argmin(f₀(X°+hS°)

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

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

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

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

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

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

2. Вычисляются величины f₁ =f₀(X¹), …, f_n+1 =f₀(Xⁿ⁺¹).

3. Определяются вершины h, g, l, для которых f_h - наибольшее значение среди всех f_i, i=l,… , n+l; f_g - следующее за наибольшим; f_l - наименьшее значение.

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

и вычисляется значение целевой функции f₀ в точке Х^C – f_C.

5. Выполняется операция отражения точки Х^h относительно точки X^C с коэффициентом отражения и получением точкиX⁰ (рис. 2.8). При этом X⁰-X^C=(X^C-X^h), откуда X⁰=(1+)X^C-X^h. Вычисляется значение целевой функции f₀, в точке Х⁰ – f₀.

6. Значение f₀ сравнивается со значениями f₁ и f_g. Возможны три случая:

6.1. Если f₀ < f₁, то направление из точки X^C в точку Х⁰ является наиболее предпочтительным для перемещения. В этом случае выполняется операция растяжения симплекса с коэффициентом растяжения и получением точки X^r. При этом X^r-X^C=(X⁰-X^C),

откуда X^r=(1-)X^C-X⁰.

Далее вычисляется значение целевой функции f₀ в точке Х^r-f_r и осуществляется его сравнение со значением f₁. Возможны два случая:

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

6.1.2. Если f_r f₁, то точка X^r отбрасывается, т.к. перемещение было выполнено слишком далеко. В этом случае точка Х^h перемещается в точку Х⁰, образуя новый симплекс, текущая итерация заканчивается и выполняется переход к шагу 10 для проверки критерия останова.

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

6.2. Если f₁< f₀ f_g_, то Х⁰ является не самой плохой точкой. В этом случае точка Х^h перемещается в точку Х⁰ и выполняется переход к шагу 10.

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

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

7.1. Если f₀ < f_h, то результатом операции сжатия является точка X^S, определяемая из условия

X^S-X^C=(X⁰-X^C) или X^S=X⁰+(1-)X^C

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

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

X^S –X^C = (X^h-X^C) или X^S = X^h + ( 1-)X^C.

В этом случае точка X^S будет лежать между X^h и X^C (рис.2.9б). Далее вычисляется значение целевой функции в точке X^S – f_S.

8. Сравниваются значения f_h и f_S.

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

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

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

Xⁱ=Xⁱ + (Xⁱ-X¹),

i ≠ 1.

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

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

, где/(n+1) и

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

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

X²= X¹+kE¹, X³= X²+kE²,..., Xⁿ⁺¹ =Xⁿ+ kEⁿ, где

E^j=(e₁,e₂, …, e_j, …, e_n) – вектор, у которого e_j=1, а остальные элементы равны 0, j=1,…, n, k - произвольная длина шага.

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

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

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

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

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

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

Рассмотрим использование метода наискорейшего спуска для минимизации функции двух переменных f₀(х₁, x₂). Пусть в качестве начального приближения выбрана некоторая точка Х⁰= (). Каждая итерация при поиске минимума методом наискорейшего спуска состоит из двух этапов. На первом этапе в точке Х⁰ вычисляются значения частных производных по переменным х₁, x₂, которые определяют направление градиента функции f₀(X) в этой точке. На втором этапе определяется следующая точка Х¹ как X¹=X⁰+h₀S⁰, где S⁰ = - антиградиент функции f₀ в точке X⁰, h₀ - неизвестное значение коэффициента h.

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

h₀ =argmin f₀(X⁰ +hS⁰).

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

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

.

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

(2.3)

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

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

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

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

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

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

, (2.4)

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

f₀ (X)=

где Х=(х₁, x₂ , . . . , х_n ) - вектор-строка; - вектор-столбец; T- символ транспонирования; A=(a_ij ), i, j=l,..., n – симметричная матрица размера nn ; B=(b_i), i=1,…, n - постоянный вектор размера n, с - константа.

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

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

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

(S^k)A(S^k+1)^T=0.

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

(Sⁱ)A(S^j)^T=0 .

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

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

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

(S^k-1)A(S^k)^T=0

(S^k-1)A(.

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

(2.6)

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

X^k+1=X^k +h_kS^k, .

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

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

(2.7)

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

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