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

Для проверки унимодальности функции F(X) на практике обычно используют следующие критерии:

1)	если функция F(X) дифферен-
	цируема на отрезке [a;b] и
	производная F(X) не убывает
	на этом отрезке, то F(X)) уни-
	модальна;
2)	если функция F(X) дважды
	дифференцируема на отрезке
Рис. 34	[a;b] и F(X))≥0 при xЕ [a;b], то
	F(X)) также унимодальна.

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

Метод перебора (пассивный поиск) является простейшим из прямых методов минимизации. Пусть F(X) унимодальна, и требуется найти какую-либо из точек минимума x* функции F(X) на отрезке [a;b] с абсолютной погрешностью ε>0. Разобьем [a;b] на n равных частей точками деления Xi=a+i(b- a)/n, i=0, 1, 2, …, n, где n≥(b-a)/ε. Вычислив значения F(X) в этих точках, путем сравнения найдем точку xm, для которой

Отформ

Отступ: Выступ: нумеров 1 + Стил

3, … + Н

Выравни

Выровня

Табуляц + Отступ Поз.табу Выровня табуляц пт

Отформ

ширине, строка: нумерац

F(Xm)=min F(Xi).	(6.1)
0≤i≤n

Далее полагаем x*=xm, F*=F(Xm). При этом максимальная погрешность εn определения точки X* равна εn=(b--a)/n.

Метод деления отрезка пополам (метод дихотомии) является простейшим последовательным методом минимизации. Он позволяет для любой унимодальной функции F(X) построить последовательность вложенных отрезков [a;b] [a1;b1] … [an-1;bn-1] [an;bn], каждый из которых содержит хотя бы одну из точек минимума X* функции F(X).

Пусть ε>0 – требуемая точность определения точки X*. Выбрав δ=2ε, построим последовательности {an}, {bn}, {X1(n)}, { X2(n)}, n=0, 1, … , используя

рекуррентные формулы a0=a, b0=b;
x1(n-1)=(an-1+ bn-1- δ)/2, x2(n-1)=(an-1+ bn-1+ δ)/2;		( 6.2)
an =an-1, bn = x2(n-1),	если f(x1(n-1))≤ f(x2(n-1)),
an = x1(n-1), bn = bn-1,	если f(x1(n-1))> f(x2(n-1)).
98

а) б)

Рис. 35

Переход от отрезка [an-1; bn-1] к отрезку [an; bn] методом деления отрезка

пополам иллюстрируется на рис. 35а, если F(X1(n-1))< F(X2(n-1)),и на рис. 35б,

если F(X1(n-1))>F(X2(n-1)).

Полагая x* = (an+ bn)/2, находим X* с абсолютной погрешностью, не превосходящей величины

εn =(bn- an)/2=(b-a-δ)/2n+1+δ/2.

Кроме этих методов известны и другие, более эффективные методы, та-

кие как: метод Фибоначчи, метод золотого сечения, метод поиска по дискретным точкам [12, 25].

6.3. Градиентные методы многомерной оптимизации

Если ограничения в задаче НЛП отсутствуют, то применяют все методы оптимизации нелинейных функций. Причём, если в задаче с ограничениями решение гарантированно находится внутри области, то его можно найти этими методами, так как эти ограничения не являются активными и их можно отбросить. Рассмотрим наиболее широко применяемые методы оптимизации нелинейных функций многих переменных – это так называемые поисковые методы. Здесь поиск оптимальной точки начинают из начальной точки (ее выбирают из некоторых знаний о примерном месте нахождения решения). Далее в соответствии с некоторым разумным правилом переходят в новую точку с лучшим значением ЦФ и т.д. до тех пор, пока не выполнится некоторое заранее заданное правило остановки, например выполнение условия по точности.

99

6.3.1.Классический градиентный метод

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

гов от начальной точки до оптимальной будет очень велико. Поиск начинается из начальной точки X0. Точка X(k+1) ищется по формуле

X(k+1)=X(k)±λ(k)g(X(k)) ,

(+) – если F(X) → max и (-) – если F(X) → min,
где g(X(k)) – градиент в точке Xk ,				λ(k )		- множитель, определяющий длину
шага. В координатах	(k+1)	(k)	(k)		∂F	. Величина	λ(k ) может в простей-
	Xj	=Xj	+λ	(	∂Xj	) k
						x

шем случае не изменяться по мере движения λ(k)=λ = const .

Теоретически окончание поиска определяется следующим услови-

ем: X (r ) - точка экстре-

мума, если g( X (r ) ) = 0. На рисунке показаны траектории движения для а) – классического градиентного метода; б) – покоординатного метода,

в) – метода наискорейшего спуска.

Рис. 36

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

max	(	∂F	) ( r −1)	≤ ε , где ε - заданная малая величина.
		∂X j
			x

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

100

6.3.2.Покоординатный метод

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

первой координаты x1. Знак направления совпадает с направлением проекции градиента на эту координату (для F(X) → max) или противоположен ему, ес-

ли F(X) → min. Конец шага определяется точкой, где ∂F =0. Затем движе-

∂X1

ние производится по второй координате X2, затем по X3 и т.д., и, наконец, по Xn. Затем повторяют движение опять по X1, X2 и т.д. Можно использовать

следующее правило остановки: max (∂∂XFj ) x( r −1) ≤ ε .

6.3.3.Метод наискорейшего спуска и его модификации

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

ит. д. Отличие здесь в том, что длина шага из точки Xk определяется из ус-

ловия, чтобы обеспечить:

min F[X k ± λg(X k )].

λ>0

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

Наискорейший и покоординатный методы называют методами с длинным шагом. Кроме этого существуют методы, использующие вторую производную для определения длины шага, например, метод Ньютона:

X k +1 = X k + [F ′′(X k )]−1 g(X k ),

где [F”(Xk)] -1 - обратная матрица вторых производных в точке Xk.

6.4. Метод деформируемого многогранника Нелдера-Мида

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

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

101

Отформа

русский (Р

1)отражение - поворот симплекса через одну из сторон;

2)растяжение - если идём в правильном направлении;

3)редукция - возврат назад, если перескочили оптимум;

4)сжатие - уменьшение сторон, чтобы движение было с более мелким шагом.

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

	дера-Мида заключается в сле-
Рис. 37	дующем:

1. Выбирается начальный симплекс (если в задаче 2 переменные n=2, то

симплекс–правильный треугольник). Его вершины Xi(0),i =											. Обозна-
										1, n +1
чим	X h(k )	- самая худшая точка, т.е. для F (X ) → min ,							F (X n(k ) )= max F(Xik );
Xl(k )	- лучшая точка,					т.е. F (Xl(k ) )= min F(Xik ); . X0(k )			- центр тяжести всех
вершин, исключая X hk , его координаты
	(k )		1	n+1	(k )	(k )
	X0	=		∑Xij		− Xnj ; j =1, n .
			n i=1
2. Осуществляют отражение (проектирование) X h(k )									через центр тяжести,
новая точка получается так:

Xα(k ) = X 0(k ) +α (X 0(k ) − X n(k ) )

где α - коэффициент отражения. Обычно α=1.

•Если F (Xα(k ) )≤ F (Xl(k ) ), то вектор Xα(k ) − X0(k ) растягивается в γ раз и по-

лучаем Xb(k ) = X0(k ) +γ (X à(k ) − X0(k ) );

102

Отформ

русский

•	Если для полученной точки F (Xb(k ) )< F (Xl(k ) ), то Xh(k ) заменяется на
	Xb(k ) , и переходим к пункту 2. В противном случае заменяем X h(k ) на X a(k )
	и переходим к пункту 2.
•	Если F (Xα(k ) )> F (Xh(k ) ), для всех i≠h то вектор X h(k ) − X0(k ) сжимается,
	получаем точку Xñ(k ) = X 0k + β (X 0(k ) − X h(k ) ) 0 < β <1.
	Точка X h(k ) заменяется на Xñ(k ) , и переходим к выполнению пункта 2.

•Если F (Xα(k ) )> F (X h(k ) ), то все векторы Xi(k ) − Xl(k ) уменьшаются в λ раз

	(обычно λ=2) - редукция	Xi(k ) = Xlk +	1	(Xi(k ) − Xl(k ) );	i =
						1, n +1 .
			λ

Возвращаемся к пункту 2. Правила остановки могут быть различными, например,

		1	n+1				2	1
				r		r		2
			∑ F(Xi		) − F(X	0 )			≤ δ
		+ n
1			=
			i 1

для простоты можно использовать правило:

i =1, n +1

max Xir, j − X pr , j ≤ ε j =1, n
j,i, p	p =1, n +1

решением будет точка X0(r) . Например:

F(X ) = −6X1 +2X12 −2X1 X2 +2X 2 → min

выберем параметры:

α =1, β = 12 ,γ = 2, λ = 2,ε = 0,1

решение видно из рисунка 38. Подробнее смотри в [16].

Рис. 38

6.5.Задача НЛП с ограничениями-равенствами

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

103

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

m
Ô (X ,λ)= F (X )+ ∑λi (ϕi (X )−bi ),	(6.3)

i=1

где F(X) - целевая функция, λi – множители Лагранжа, имеющие смысл коэффициентов чувствительности ограничений.

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

∂Ô

∂F

m

∂ϕi

=

+

∑i=1

λ

= 0,

j =1, n;

∂X

∂X

j

j

i ∂X

(6.4)

j

∂Ô

=ϕi (X )−bi

= 0,

i =1, m.

∂λ

i

После выполнения операций дифференцирования получаем систему в общем случае нелинейных уравнений относительно неизвестных Xi и λi - множителей Лагранжа.

Решение системы (6.4) дает точки подозрительные на экстремум, и их ещё надо проверить с помощью достаточных признаков экстремума. Рассмотрим некоторые из этих признаков.

1) Пусть X * - точка подозрительная на экстремум, полученная с помощью выражений (6.4). Рассмотрим матрицу Гессе – матрицу H вторых производных в точке X*:

	H =	∂2Ô		.	(6.5)
		∂Xi	∂X j

Если эта матрица определена положительно, то точка X* -минимум, а если определена отрицательно, то максимум. Если же матрица Гессе знаконеопределена, то в этой точке экстремума нет, а если полуопределена, то этот признак не даёт ответа на вопрос.

2) Пусть Dk - главный определитель матрицы Гессе k-го порядка.

а) если D1 > 0, D2 > 0, D3 > 0,K - это достаточный признак минимума;

б) если D1 < 0, D2 > 0, D3 < 0,K - достаточный признак максимума (знаки

строгих неравенств чередуются); в) если же в определителях знаки ≥ и ≤, то это необходимый, а не дос-

таточный признак и вопрос об экстремуме не решается.

104

3) Наиболее «сильным» достаточным признаком является следующий. Составим расширенную матрицу Гессе HB, для чего используем матрицу производных от функций ограничений:

∂ϕ1

∂ϕ1

L

∂ϕ1

∂X1

∂X2

∂Xn

∂ϕ

2

∂ϕ

2

∂ϕ

2

0

Q

L

∂X1

∂X2

,

Q =

∂Xn

, H β =

L L L L

Q′

H

∂ϕn

∂ϕn

L

∂ϕn

∂X1

∂X2

∂Xn

Q′ - транспонированная матрица.

Матрица HB имеет размерность (m+n)×(m+n).

Признак: точка X* соответствует максимуму, если начиная с главного определителя порядка m+1, последние n-m определителей матрицы HB образуют знакопеременный ряд, а

знак определителя	стоящего	на
(n-m)-м месте от конца совпадает с
знаком: если (-1)m+1,	то max;	если
(-1)m, то min.		Рис. 39

Например: n=3, m=2, n-m=1, проверяем D5; n=7, m=4, n-m=3, проверяем D9.

Пример:

F = X1 X 2→ max , X1 + X 2 =1

Запишем функцию Лагранжа

Φ(X1 , X 2 , λ) = X1 X 2 + λ(X1 + X 2 −1) → max .

Найдем решение, используя необходимые условия

105

	∂Φ	= X2		+λ			= 0
	∂X1
	∂Φ	= X1		+λ			= 0
								.
	∂X2
	∂Φ
		=	X1 + X2 −1 = 0
	∂λ
Получаем решение системы:
	X1 = X2 ;
	X1 = X2 =				1	;	λ = −		1	.
				2				2
Запишем матрицу H B :
	H B = 0 Q						; H= 0 1				;
		Q′			H			1 0
		0		1			1
	H B =		1	0			1 ; n=2; m=1; m+1=2; n-m=1.
			1	1
							0

Начиная со второго определителя (m+1=2) знаки чередуются:

D1 = 0 , D2 < 0 , D3 = 2 > 0 , причем (−1)m+1 = (−1)1+1 > 0 .

Проверяем: D3 >0, значит в точке X1=X2=1/2 находится максимум.

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

6.6. Выпуклое НЛП

Теория нелинейного программирования разработана только для одного частного случая выпуклых целевых функций F(X) и ограничений ψi(X) и этот раздел соответственно называется выпуклым программированием.

106

Выпуклое множество обладает

тем свойством, что отрезок, соеди-
няющий любые две точки множества,
также принадлежит этому множеству.
Таким образом, С En выпукло, если
из (X1, X2) С следует, что λ=θX1+(1-
θ)X2 С для любого 0≤θ≤1.	Рис. 40

Важно: если Сi - выпуклое множество, то С=∩ Сi также выпукло.

Т.е. если каждое ограничение в задаче НЛП образует выпуклое множество, то и все ограничения дают выпуклое множество.

Дважды дифференцируемая функция F(x) является выпуклой в том и только в том случае, когда

n h	∂2 F(X )	Xi	X j ≥ 0 .
∑ ∑	∂Xi ∂X j
i=1 i=1

Для любых x M, M - выпуклое множество и хi и хj не обращается в нуль одновременно. Для проверки выпуклости F(X) используется критерий Сильвестра:

Функция F(X)- выпукла, если неотрицательны (для строго выпуклой положительна) все главные миноры матрицы Гессе:

	=		a11	...		a1k	;
k				...
			ak1	...		akk
a	=		∂2 F		;
		∂Xi		∂X j
ij
k=1, 2, … n.
Если все k>0, то F(X) - строго выпукла.
Функция F(X)						n переменных ||X1, X21,…, Xn|| = X G называется выпук-
лой функцией в выпуклой области G, если для любых двух точек выполняет-
ся соотношение
F{λX (1)				+(1−λ)X (2)} ≤ λF(X (1) ) +(1−λ)F(X (2) ) , где 0<γ<1.

Когда λ – переменная, то промежуточная точка пробегает значения от

X(1) до X(2)

Функция строго выпукла, если знак ≤ можно заменить на <.

107