Численные методы оптимизации

Занятие 15 декабрь 2011

кафедра систем телекоммуникаций Ловецкий К.П.

7/1/19

1

Стандартная постановка задачи конечномерной оптимизации (P)

Основная задача: Минимизировать целевую функцию F(x) : Rn R на допустимом множестве C Rn .

(P)	F(x)на	x( ,x...,		)x X Rn
	ci (x) 0,		1	n
			i 1,...,m
Введем обозначения:		gi (x)		F(x) ,	i 1,2,..., n
				xi
		a (x) ci (x) ,			i, k 1,2,..., n
		ik		xk

7/1/19	2	2
7/1/19

Условия первого порядка

•Теорема 11.1. Пусть точка x - решение задачи условной минимизации функции F (x) . Тогда не существует вектора p , для которого выполняется неравенство

g(x)T p 0
и при любых значениях из отрезка	0		,	0 , гарантирована
допустимость точек вида x p .
• Лемма Фаркаша. Пусть заданы векторы a		(i 1,...,t) и вектор g(x) .
Неравенства	i
g(x)T p 0
и
a T p 0, i 1,...,t,
i
несовместны тогда и только тогда, когда g(x)		принадлежит выпуклому

конусу, натянутому на векторы ai (i 1,...,t) .

3

Условия первого порядка

• Теорема 11.2.		Пусть	x - точка, доставляющая минимум функции
	F (x)			a T x b , i 1,...,m,
				i	i	g(x )
	при линейных ограниченияхx					причем первые
	из них обращаются в		в равенства. Тогда градиент
	представим в виде		t
		g(x ) iai ,		i 0.
			i 1
•	Теорема 11.3.		x
		Пусть	- точка, доставляющая минимум функции
	F (x)		x		ci (x) 0,	i 1,...,m
	t				g(x )	ai (x ),(i 1,...,t)
	при нелинейных ограничениях					причем первые
	из них обращаются в				в равенства и градиенты
			t			представим в виде
	линейно независимы. Тогда градиент
		g(x )	iai (x ),		i 0.

i 1

4

Функции Лагранжа

• Итак, как показано ранее, в точке минимума функции F (x) при
ограничениях	ci (x) 0,	i 1,...,m , обычно выполняется соотношение
		t
	g(x ) iai (x ),		i 0.
где g(x) и ai (x)		i 1		F (x) и ci (x)	. В предположении
	- градиенты функций
линейной независимости векторов			a	(x ),(i 1,...,t)		это разложение
			i
существует, причем множители i			определяются однозначно. Поэтому
решение исходной задачи при соответствующем выборе вектора
будет стационарной по		x точкой функции
			t
	L(x, ) F(x) ici (x).
			i 1
Она называется функцией Лагранжа, а параметры						i	- множителями

Лагранжа.

5

Точная штрафная функция Флетчера

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

связи с этим возникает желание построить точную
	(x)
штрафную функцию	сxлокальным

безусловным минимумом в точке , что позволит
решать задачу минимизации лишь один раз. При
x	2 (x )

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

6

Точная штрафная функция Флетчера

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

стационарной точкой соответствующей функции

, т.е.

x F

x

x

T

c x

, достаточно, чтобы

при

. Другими словами, если

x

g

x

x

x

A

x

x

c

то

7

Точная штрафная функция Флетчера

x

F

x

x T c

x

x

g

x

A

x

x

x

c

x

гдеA(x) - матрица, столбцами которой являются

x)

ограничений

производные от вектор-cфункцииi (

x ) 0

x x

и, следовательно,(

равенство

g, A, , c

,c

0

получается при

в силу gнепрерывности

x)

x x

. В качестве

и равенств(

1

T

T

функции

при

, можно

(x) A g

,

A

A A

A

взять

x

(x)

где

то есть

вычисляется как вектор,

A g

минимизирующий сумму квадратов невязок уравнений переопределенной системы8

Точная штрафная функция Флетчера

x

F

x

c

x

T A (x)g

x

Тогда

доставлять локальный

Посмотрим, будет ли

x

минимум этой функции. Матрица ее вторых

производных в

точке

x

ˆ

выглядит так

2

* ˆ

*

P,

гдеP A A

x

PW P PW

- матрица

P I P

,

ˆ

проектирования,

W

2

2

Fс i

i

i

и

По поводу положительной определенности? PW *P, матрицы вторых производных сказать ничего нельзя

поэтому модифицируем исходную функцию:

x F x c x T A (x)g x qc x T A (x)A T (x)c x

2	ˆ * ˆ	*	)P,	q 1/ 2		W	*
x	PW P P(2qI W						9

Fkизм

Пример.

,

• Аппроксимация кривой гауссианами.

				изм	xi	2		2
				xk
N		n		bi
x	a0	ai e						Fkизм
k 1		i 1

где N – количество измеренных точек спектра, n - количество функций

Гаусса,	ai	и bi	- параметры, задающие амплитуду и ширину гауссианов,
ai 0, bi	0 ,	xi	- координата середины гауссиана на оси абсцисс,

- значение спектра в измеренной точке xkизм

10