Рис. 6.20. Метод отсечений

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

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

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

1.Метод отсечений предусматривает исследование по­

верхности отклика в одной из точек х1 изучаемой области Ха и исключение из дальнейшего рассмотрения части этой области, признанной бесперспективной с точки зрения поиска экстрему­ ма. Принципиальная схема простейшего из методов отсечений представлена на рис. 6.20. Метод предусматривает:

1) численное определе­ ние направления градиента (и антиградиента) в некоторой (начальной) точке факторного пространства х1е Х0";

2) построение прямой (гиперплоскости), ортогональ­ ной направлению градиента. В исследованной точке эта прямая (плоскость) касатель-

на к линии (поверхности) уровня; 3) исключение из дальнейшего рассмотрения области, где

функция качества возрастает (в случае минимизации), как бес­ перспективной с точки зрения поиска экстремума.

Для выделенной после отсечения перспективной области все вычисления повторяются. После ряда отсечений остается достаточно малая область (интервал неопределенности) Х„, со­ держащая экстремум.

W(x). Тогда улучшению ее на шаге (к + 1) поиска будет соответ- ствовать условие

ЩХк+1) < ЩХк).	(6.97)
Из выбранной начальной точки	поиска * 0 выполняется

пробный шаг И0 в положительном направлении одной из коор­ динатных осей (обычно вдоль оси первого управляемого пара­

метра х\). В	новой точке Х\ с координатами Х {= (*,, =
•^2.1 *Х2,о, ■■*’	^п,о) вычисляется значение целевой функции

Щ-Х) ^ сравнивается с ее значением в начальной точке W(Xо). Если W(Xi) < W(Xо), это направление принимается для осущест­ вления дальнейшего пошагового движения к экстремуму в соот­

ветствии с выражением
* I,*+I = Хц + Л0.	(6.98)

В противном случае производится возврат в исходную точку Хо и движение осуществляется в отрицательном направ­

лении оси х 1:
XiM\ = x\,k-ho.	(6.99)

Движение в выбранном направлении оси х\ выполняется до тех пор, пока целевая функция улучшается, т.е. выполняется условие (6.97). При его нарушении на шаге (к + 1) производится возврат в точку определяется направление движения вдоль следующей координатной оси х2, и совершаются спуски в на­ правлении, обеспечивающем улучшение целевой функции.

Х2М1 =x2jc±h.

(6.100)

После осуществления спусков вдоль всей п осей первый цикл спусков N= 1 завершается и начинается новый цикл N = 2. Если на очередном цикле движение оказалось невозможным ни

по одной из осей, тогда уменьшается шаг поиска:
hN = hN-{у,	(6.101)
где у - коэффициент уменьшения шага: 0 < у < 1.

3. Метод градиента

рад IT векторная величина, компонентами которой

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

	gmdW(X) =	'dw dw	dW V
		^ Эх, 5дх2 9	*дх.	(6.103)
				/

Градиент всегда сориентирован в направлении наиболее быстрого изменения функции. Градиентное направление являет­ ся локально наилучшим направлением поиска при максимиза­ ции целевой функции, а антиградиентное - при ее минимиза­ ции. Это свойство вектора grad W{X) и используется в методе градиента, определяя вид траектории поиска.

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

Движение в пространстве управляемых параметров осу­

ществляется в соответствии с выражением
X M = Xk +htSk,	(6.104)

где hk - шаг поиска; Sk - единичный вектор направления поиска

на шаге {к+ 1), характеризующий направление градиента в точкеА*. При минимизации целевой функции вектор 5* должен иметь направление, противоположное направлению вектора гра­

диента, поэтому для его определения используется выражение

- gradW(Xk)_ (6.105)

*|grad^(X*)| ’

где IgradH^JQI - модуль вектора градиента, вычисленный для

точки Хк.

Дадим краткое изложение алгоритма поиска минимума целевой функции W(X). В каждой точке траектории поиска Хк, в том числе в исходной точке Х0, определяется градиент целевой

функции для			“ °Й
ныл уровней	целевой	функции обозначен я, ' я Г
s & v	* а ~	—	~

Рис. 6.23. Схема методов:

а —градиента; б —наискорейшего спуска

Движение в градиентном направлении по определению должно приводить к улучшению функции качества. Если это не так и Щ Х>+1) < ЩХ„), можно предположить, что поиск просто «проскочил» оптимальную точку. В этом случае следует уменьшить величину шага и повторить вычисления.

4. Метод наискорейшего спуска, предложенный Л.В. Кан­ торовичем, является наиболее популярной модификацией мето­ да градиентного поиска.

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

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

координатами факторного пространства, что сообщает поиску большую гибкость.

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

Поиск экстремума целевой функции „ри „сполиованш

этих методов осуществляется перебором совокупностей случай-

T J L T Y О и О Т Т Р и Г Л у Г \ / П П О г > т т Л » „ ________	J
ных значении управляемых параметров.

Наиболее эффективны методы случайного поиска яв­

ляющиеся статистическими аналогами детерминированных ме­ тодов спуска, рассмотренных выше.

Существует много разновидностей случайного поиска, о простейшем из них выбирается случайное направление движе­ ния в пространстве управляемых параметров, проверяется его перспективность и при благоприятном результате проверки осу­ ществляется движение в этом направлении. При отрицательном результате выбирается новое случайное направление, и процесс повторяется. Проверка перспективности направления основана на вычислениях целевой функции W(XM ) в новой (£+ 1)-й точке и сравнении ее значения со значением в предыдущей k-ti точке.

Координаты (к + 1)-й точки определяются выражением

~ Х к + hak ,

(6.109)

где h - шаг поиска; а к - случайный вектор, определяющий на­

правление поиска.

Размерность вектора д.к равна размерности п вектора X.

Для получения вектора а к может использоваться п значений равномерно распределенной в интервале [-1; 1] случайной ве­ личины а = (а ь а 2, ..., а„). Алгоритмы получения псевдослучай­ ных величин с различными распределениями описаны в [4,20].

Рассмотрим кратко работу алгоритму случайного поиска при минимизации целевой функции. После определения вектора

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

Выберем три точки в пространстве управляемых парамет­ ров, расположенные на направлении вектора Sk на расстояниях h\, h2 и Аз от точки Хк, и вычислим значения целевой функции

в этих точках:
Wl =W{Xk +hlSk), W2 =W(Xk+h2Sk) W3=W(Xk + h3Sk).	(6.112)
Интерполяционный полином представляет собой квадра­
тичную функцию:
F{h) = a0+ai(h - h\) + a2(h - Л,) (h - h2).	(6.113)

Значения функции W(h) в точках с координатами h\, h2, h2

на оси S k, определяющей направление поиска, равны соответ­

ственно W\, W2, W3. Используя эти данные, можно найти значе­ ния коэффициентов а\, а2, аъ интерполяционного полинома

(6.113). При h = h\	получаем		a0= Wl, при h = h2:
W2 = W\+ a\(h - ЛО, отсюда
	_W2	-W ,j		(6.114)
Для определения коэффициента а2 подставим в выраже­
ние (6.124) h - h 2. Выполнив преобразования, получим
1	W3	-W,	w 2 - w x	(6.115)
	К	К	- \

Вычислив производную функции W(h) по переменной И и приравнивая ее к нулю, найдем значение А*о, т.е. величину оп­ тимального шага в направлении Sk:

Ко ~~

(6.116)

2 J

Рис. 6.24. Сходимость метода	Рис. 6.25. Прекращение поиска
покоординатного спуска	в малой окрестности дна
в овражной ситуации	узкого извилистого оврага

Градиентный поиск в этом случае также невозможен из-за малой ширины оврага. Например, из точки В на рис. 6.25 нельзя осуществить шаг величиной h> hm\n. Вероятность нахождения удачного направления методом случайного поиска в условиях узкого оврага также весьма невелика.

Единственная				благо­
приятная		ситуация, при ко­
торой	направление			поиска
совпадает		с осью		оврага,
возможна		только	в	случае
прямолинейного оврага (ось
оврага	параллельной			одной
из координатных				осей)
(рис. 6.26), но и в этом слу­
чае поиск экстремума возмо­					Рис. 6.26. Поиск экстремума
жен только методом покоор­
динатного		спуска	(сплошная		при параллельности оси
линия	на	рис. 6.26),		поиск	оврага одной
же градиентным			методом		из координатных осей
не дает результата (штрихо­
вая линия на рис. 6.26).

Число же обусловленности р есть отношение наибольше­ го и наименьшего по модулю корней уравнения (6.119). Число р характеризует форму поверхности отклика и возможности оп­ тимизации. Чем ближе р к единице, тем лучше сходимость по­

	исковых методов и наоборот.
		Для поиска оптимума в условиях сложного рельефа по­
	верхности отклика разработаны следующие методы.
		1. Метод вращающихся координат
		При анализе эффективности			х .		. .
	методов поиска в овражной си-					. .И
	туации в предыдущем параграфе				2	1	1
	бьшо отмечено, что если ось овра­
	га параллельна какой-либо коор­
	динатной оси (рис. 6.27), то нали­
	чие оврага не приводит к сниже­
	нию	эффективности метода по­				х ,
	координатного спуска. Это свой­						Ч
	ство	метода	покоординатного
					Рис. 6.27. Схема метода
	спуска используется			в методе
					вращающихся координат
	Розенброка, который			также но­
	сит	название	метод	вращаю­

щихся координат. Метод основан на повороте координатных осей после каждого цикла спусков для создания удобного вза­ имного расположения оси оврага и осей системы координат. Рассмотрим реализацию идеи метода на примере двумерной за­ дачи (см. рис. 6.27).

Из начальной точки поиска Х0 выполняется первый цикл спусков вдоль координатных осей х\ и х2 так же, как и в методе Гаусса-Зейделя. Будем предполагать, что спуски совершаются с оптимальными шагами, определяемыми одномерной миними­ зацией целевой функции в направлении спуска. Тогда спуски вдоль каждой из осей будут выполняться за один шаг. Спуск из начальной точки Х0 вдоль оси *i приводит в точку Х и а вдоль

ОСИ Х2 —в точку Х2.

Примем направление вектора (Х2- XQ) за новое направле­ ние первой координатной оси х \, а направление второй оси х2

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

Поиск завершается, если значения оптимальных шагов А*о вдоль всех и координатных осей в N-м цикле не превышают за­

данное значение минимального шага Amj„.
В окрестности оптимальной точки	поиск начинает со­

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

2. Метод симплекса

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

Симплексом в «-мерном пространстве называют фигуру, содержащую п + 1 вершину. Регулярный симплекс в «-мерном пространстве управляемых параметров представляет собой мно­ гогранник, образованный « + 1 равноотстоящими друг от друга вершинами. В случае двумерного пространства Х= (ху, хт) сим­ плексом является равносторонний треугольник. В трехмерном пространстве симплекс представляет собой тетраэдр.

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

Валгоритме поиска используется также второе важное

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

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

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

Рис. 6.28. Построение симплекса для двумерной задачи

Алгоритм поиска экстремума целевой функции с исполь­ зованием симплекса содержит следующие процедуры. Вначале необходимо построить начальный симплекс, определив коорди­ наты Х\ всех его вершин Х\,Хг, ..., Хп+\. В двумерной задаче оп­ ределяют координаты X], Xj, Х3 трех вершин равностороннего треугольника (рис. 6.28, а). Затем вычисляют значения целевой функции для всех вершин и выбирают вершину с наибольшим (наихудшим) значением целевой функции. Эту вершину про­ ецируют через центр тяжести остальных вершин симплекса в новую точку, которая используется в качестве вершины ново­ го симплекса. Предположим, что наибольшее значение целевой функции соответствует точке Х3. Тогда через эту точку и центр тяжести вершин с координатами Х\ и Х3 (точка X ) проводят прямую, на которой находят новую точку Х4(рис. 6.28, б). Точку Х3 исключают, а точки Х\, Хг и Х4 образуют новый симплекс (рис. 6.28, в). Т.е. точка, соответствующая худшему значению функции качества, отбрасывается и заменяется отраженной через противоположную грань точкой.

Новая точка Х4 называется «дополнением» наихудшей точ­ ки. Если в только что полученной вершине нового симплекса значение целевой функции оказывается худшим, то алгоритм ■предусматривает возврат в исходную точку - вершину прежнего симплекса. Затем осуществляется переход к той вершине прежне­ го симплекса, в которой целевая функция имеет следующее по величине значение, и отыскивается точка, являющаяся ее допол­ нением. Такой алгоритм обеспечивает систематическое смещение центра симплекса в направлении экстремума целевой функции.

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

Операцию определения координат новой вершины сим­ плекса называют отражением относительно центра тяжести.

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

(6.123)

Координаты точек, расположенных на прямой, проходя­ щей через точки X/ и X , можно найти из выражения

X = X J + U X e - X J).

(6.124)

При X = 0 получаем точку Х„ которая подлежит отраже­ нию, а X = 1 соответствует центру тяжести X Для того чтобы вновь построенный симплекс оказался регулярным, отражение

должно быть симметричным, а это возможно, если	принять
X = 2. Тогда искомые координаты новой вершины Х„+2
Хп+2~ 2ХС- X j.	(6.125)

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

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

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

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

Разложим целевую функцию ЩХ) в окрестности точки Хк в ряд Тейлора, ограничиваясь членами разложения второго порядка:

д Щ Х к)	пТ	(6.126)
W(X) = W(Xk) +	2!
дХ		а г

Перепишем эту формулу, используя выражения для опреде­ ления градиента целевой функции (6.103) и матрицы Гессе (6.117):

fV(X) = W(Xk) +[grad W( Xk) f AX + - AX rH{ Xk)AX. (6.127)

Выражение представляет собой квадратичную аппрокси­ мацию целевой функции W(X), построенную в точке Хк. На ос­ нове этой аппроксимации построим последовательность итера­ ций таким образом, чтобы во вновь получаемой точке Хк~\ гра­ диент аппроксимирующей функции обращался в нуль:

grad W(XM ) = gradW(Xk) + H ( X k )AX = 0. (6.128)