Бронов С.А. Методы оптимизации в САПР
Подождите немного. Документ загружается.
61
0),(
2
xLd
для всех ненулевых
n
R
x
d
таких, что
0)(
xdq
j
,
m
j
,
,
1
,
a
Jj
при 0
j
для минимума ( 0
j
для максимума),
0)(
xdq
j
,
a
Jj
при 0
j
,
то точка
x
— локальный минимум (максимум).
Алгоритм решения задачи условной оптимизации при смешанных
ограничениях
Исходные данные: вектор искомых переменных
x
размерности
n
, целе-
вая функция
)
(
x
I
и функции-ограничения в форме равенств 0)(
xq
j
,
m
j
,
,
1
неравенств 0)(
xq
j
,
p
m
j
,
,
1
.
Шаг 1. Составляется обобщённая функция Лагранжа
p
j
jj
xqxIxL
1
00
)()(),,(
.
Шаг 2. Записываются необходимые условия экстремума первого поряд-
ка:
.,,1,0)(
;,,1(max),0(min),0
;,,1,0)(
;,,1,0)(
;,,1,0
),,(
0
pmjxq
pmj
pmjxq
mjxq
ni
x
xL
jj
jj
j
j
i
Шаг 3. Решается полученная система уравнений для двух случаев:
1) 0
0
;
2) 0
0
, для чего первое условие шага 2 делится на
0
и производится
замена переменных
0
j
на новые
j
.
В результате находятся значения
x
и
, соответствующие условно-
стационарным точкам
x
, которых в общем случае может быть несколько.
Из них выделяются те, что найдены при условии 0
0
— эти точки могут
62
быть регулярными точками экстремума. В каждом из двух случаев рассмат-
ривают
mp
2
вариантов удовлетворения последнему условию на шаге 2 (до-
полнительной нежёсткости). Наличие в полученных точках экстремумов
необходимо проверить с помощью достаточных условий.
Шаг 4. Для выделенных на шаге 3 точек проверяются достаточные
условия экстремума первого или второго порядка.
Проверка достаточных условий первого порядка:
а) определяют общее число
l
ограничений-равенств и активных в точке
x
ограничений-неравенств;
б) если
n
l
(т. е. число всех уравнений равно числу переменных
x
) и
для всех
a
Jj
(т. е. для всех активных ограничений) 0
j
, то в точке
x
— локальный минимум, а если 0
j
, то в точке
x
— локальный мак-
симум; если
n
l
или соответствующие множители Лагранжа не удовлетво-
ряют достаточным условиям первого порядка, следует проверить достаточ-
ные условия второго порядка.
Для проверки достаточных условий второго порядка выполняются сле-
дующие действия:
а) записывается выражение для второго дифференциала классической
функции Лагранжа в точке ),(
x :
ji
n
i
n
j
ji
dxdx
xx
xL
xLd
1 1
2
2
),(
),(
;
б) записывается общая система уравнений для первого дифференциала
функций ограничений-равенств:
0
)(
)(
1
i
n
i
i
j
j
dx
x
xq
xdq ,
m
j
,
,
1
,
и ограничений-неравенств
0
)(
)(
1
i
n
i
i
j
j
dx
x
xq
xdq ,
a
Jj
, 0
j
при 0
j
для минимума и 0
j
для максимума,
в) из условия б) определяются первые дифференциалы
i
dx и на этой ос-
нове осуществляется проверка знака второго дифференциала функции Ла-
гранжа: если 0),(
2
xLd при ненулевых
i
dx , то в точке
x
— условный
63
локальный минимум; если 0),(
2
xLd при ненулевых
i
dx , то в точке
x
— условный локальный максимум.
Если достаточные условия экстремума первого и второго порядков не
выполняются, то следует проверить выполнение необходимых условий вто-
рого порядка по аналогичной процедуре. Если они выполняются, то требу-
ются дополнительные исследования, если не выполняются — в точке
x
нет
условного экстремума.
Шаг 5. Если точки условного экстремума найдены, в них вычисляются
значения целевой функции.
Пример 5.8. Пусть задана целевая функция
2
2
2
1
)( xxxI на множестве
02
01
21
1
xx
x
xX , т. е. задано одно ограничение-равенство 01
1
x
02)(
211
xxxq одно ограничение-неравенство 02)(
212
xxxq ,
причём здесь
2
n
,
1
m
,
2
p
.
Решение.
1. Составляется обобщённая функция Лагранжа:
1
1
00
)()(),,(
j
jj
xqxIxL
)2()1()(
21211
2
2
2
10
xxxxx
.
2. Выписываются необходимые условия экстремума первого порядка:
2.1
;02
2)(
),,(
;02
21)(
),,(
220
211
2
2
2
10
22
0
2110
21211
2
2
2
10
11
0
x
xxxx
xx
xL
x
xxxxx
xx
xL
2.2
;02)(
;01)(
212
11
xxxq
xxq
2.3 0
2
(для минимумов), 0
2
(для максимумов);
2.4 0)2()(
21222
xxxq
.
Таким образом, получена система уравнений и неравенств:
64
,0)2(
(max);0
(min);0
;02
;01
;02
;02
212
2
2
21
1
220
2110
xx
xx
x
x
x
для которой ищется решение.
3. Решение системы может быть получено для двух случаев: для 0
0
и 0
0
.
В первом случае принимается 0
0
. Тогда из второго уравнения си-
стемы следует, что:
0022
22220
xx , 0
2
;
из первого уравнения системы:
00022
112110
xx , 0
1
,
что противоречит необходимому условию условного экстремума первого по-
рядка о существовании ненулевого вектора, состоящего совместно из
0
и
,
поэтому допущение о 0
0
неверное.
Во втором случае 0
0
. Тогда можно перейти от обобщённой к клас-
сической функции Лагранжа, поделив её на
0
и заменив
0
j
на новые
j
:
.022)(
),(
;0221)(
),(
22211
2
2
2
1
22
21121211
2
2
2
1
11
xxxxx
xx
xL
xxxxxx
xx
xL
Тогда новая система уравнений и неравенств будет иметь вид:
65
,0)2(
(max);0
(min);0
;02
;01
;02
;02
212
2
2
21
1
22
211
xx
xx
x
x
x
где изменились только первые два уравнения, в которые входила
0
.
В результате из уравнений исчезла одна переменная —
0
.
Далее необходимо рассмотреть все возможные варианты решений, кото-
рых имеется
2
2
2
2
112
mp
.
Вариант 3.1. Принимается 0
2
. Тогда из второго уравнения системы
0022
222
xx
, 0
2
x . Из третьего уравнения ( 01
1
x ) следует
1
1
x , а из первого уравнения 00122
1211
x следует 2
1
.
Таким образом, получена условно-стационарная точка, которую обозначим
A
: 1
1
x , 0
2
x , 2
1
, 0
2
.
Вариант 3.2. Принимается 0
2
. Тогда решается система уравнений:
,0)2(
;01
;02
;02
212
1
22
211
xx
x
x
x
из которой получается вторая условно-стационарная точка, которую обозна-
чим
B
: 1
1
x , 1
2
x , 0
1
, 02
2
. С учётом того, что 0
2
, эта точ-
ка отвечает необходимым условиям максимума (поэтому на минимум её про-
верять не нужно).
Точки
A
и
B
называются стационарными потому, что в них градиент
(первые производные по
x
) функции Лагранжа равен нулю, а условно-
стационарными, так как выполняется условная оптимизация.
Выполнение необходимых условий означает, что найденные точки могут
быть искомыми точками экстремума, но не обязательно. Следует проверить
это с помощью достаточных условий. Т. е. необходимые условия использу-
ются для нахождения точек возможного экстремума, а достаточные — для
доказательства, что они действительно таковыми являются и для определе-
ния вида экстремума — максимум это или минимум.
66
4. Проверяются достаточные условия экстремума для обеих наёденных
точек.
Исследуется точка
A
. В ней ограничение-неравенство не является ак-
тивным, поэтому суммарное число ограничений равенств и активных огра-
ничений-неравенств
1
l
, что меньше числа переменных
x
2
n
. Это озна-
чает, что достаточные условия первого порядка в точке
A
не выполняются.
Следует проверить достаточные условия второго порядка, для чего рассмат-
ривается второй дифференциал функции Лагранжа в данной точке:
n
i
n
j
ji
ji
dxdx
xx
xL
ALd
1 1
2
2
),(
)(
2
1
2
1
21211
2
2
2
1
2
21)(
i j
ji
ji
dxdx
xx
xxxxx
2
121211
2
2
2
1
2
1
2
21)( dxxxxxx
x
2121211
2
2
2
1
21
2
21)( dxdxxxxxx
xx
1221211
2
2
2
1
12
2
21)( dxdxxxxxx
xx
2
221211
2
2
2
1
2
2
2
21)( dxxxxxx
x
2
121211
2
2
2
1
11
21)( dxxxxxx
xx
2121211
2
2
2
1
21
21)( dxdxxxxxx
xx
1221211
2
2
2
1
12
21)( dxdxxxxxx
xx
2
221211
2
2
2
1
22
21)( dxxxxxx
xx
2
121
1
1
00101)02( dxx
x
2121
2
1
01000)20( dxdxx
x
67
1221
1
2
00101)02( dxdxx
x
2
221
2
2
01000)20( dxx
x
2
2
2
1
2
21221
2
1
222002 dxdxdxdxdxdxdxdx
.
Единственное ограничение-неравенство в рассматриваемой точке
A
не
активно (не превращается в равенство): 012012)(
212
xxxq ,
поэтому рассматривается первый дифференциал ограничения-равенства:
2
2
1
1
1
1
1
11
)()(
)()(
)( dx
x
xq
dx
x
xq
dx
x
xq
dx
x
xq
xdq
i
i
i
j
n
i
i
i
j
j
001
)1()1(
1212
2
1
1
1
1
22
11
22
11
22
11
22
11
dxdxdxdx
x
x
dx
x
x
xx
xx
xx
xx
xx
xx
xx
xx
,
тогда второй дифференциал функции Лагранжа
022)0(222)(
2
2
2
2
22
2
2
1
2
dxdxdxdxALd ,
т. е. всегда положительный, если 0
2
dx .
Следовательно, в точке
A
— условный локальный минимум (условный
и локальный, так как найден при заданных условиях-ограничениях, когда ко-
эффициенты Лагранжа 0
1
и 2
2
не равны оба нулю, в противном
случае это был бы глобальный минимум).
С другой стороны, целевая функция
2
2
2
1
)( xxxI — выпуклая, ограни-
чение-равенство — линейное, ограничение-неравенство — выпуклое. Поэто-
му в действительности в точке
A
достигается всё же глобальный минимум, а
не только условный локальный.
Исследуется точка
B
. В ней ограничение-неравенство является актив-
ным (т. е. превращается в равенство: 02112
21
xx ), поэтому сум-
марное число ограничений равенств и активных ограничений-неравенств
2
l
равно числу переменных
x
2
n
. Это означает, что достаточные усло-
вия первого порядка в точке
B
выполняются. Поскольку 0
2
, то точка
B
является точкой локального максимума.
Таким образом, с помощью достаточных условий было определено, что
в точке
A
минимум, а в точке
B
— максимум. Соответствующие значения
целевой функции:
1
)
(
A
I
,
2
)
(
B
I
.
68
3 Численная оптимизация
3.1 Общие принципы численной оптимизации
Рассмотренные выше методы позволяют однозначно определять точки
экстремума, но при некоторых специальных условиях для целевой функции,
а именно: она должна быть дважды непрерывно дифференцируема. Не все
целевые функции обладают таким качеством. Кроме того, в реальных задачах
осуществляется оптимизация по многим переменным со многими ограниче-
ниями (часто смешанного типа), в результате получается сложная система
уравнений и неравенств, которую приходится решать с помощью ЭВМ. Та-
ким образом, с одной стороны, некоторые задачи невозможно решить анали-
тически, а с другой стороны, даже те, которые можно решить аналитически, в
конечном счёте, решаются численно на ЭВМ, хотя и формулируются на ос-
нове рассмотренных выше аналитических методов, связанных с использова-
нием необходимых и достаточных условий существования экстремума. В
связи с этим возникает общая идея перейти к численным методам решения
оптимизационных задач.
Самым естественным численным способом определения экстремумов
целевой функции является её табулирование (расчёт) с последующим анали-
зом полученных результатов и определением максимумов или минимумов.
При этом можно просто последовательно перебирать рассчитанные значения
целевой функции, сравнивать их между собой и таким образом определить
наибольшее или наименьшее значение. Но при этом возникает несколько
проблем, которые можно рассмотреть на примере целевой функции одной
переменной.
Во-первых, необходимо знать границы интервала изменения
x
, так как в
общем случае границы изменения каждого
x
могут быть от –∞ до +∞, что
делает расчёты невозможными, поэтому необходимо определиться с крайней
левой границей
min
x и крайней правой границей
max
x .
Во-вторых, расчёты необходимо выполнять с некоторым шагом по каж-
дому
x
: чем крупнее шаг, тем больше вероятность "проскочить" экстремум,
что плохо; чем меньше шаг, тем больше будет расчётов, что тоже плохо.
Такой расчёт всех значений целевой функции может занять много вре-
мени, особенно при большом числе
x
, поэтому стремятся уменьшить число
вычислений, действуя по следующему обобщённому алгоритму. Выбирают
случайную точку
1
x
и вычисляют значение целевой функции )(
1
xI . Выбира-
ют вторую точку
2
x
и вычисляют новое значение целевой функции )(
2
xI .
69
Сравнивают )(
1
xI и )(
2
xI , а затем выбирают направление дальнейшего изме-
нения каждого
x
(увеличение или уменьшение) и новое значение
3
x
. Вычис-
ляют )(
3
xI , сравнивают с ранее рассчитанным )(
2
xI , на основе этого сравне-
ния выбирают следующее значение
4
x
. Таким образом, выполняются после-
довательные вычисления целевой функции, но не везде, а только в специаль-
но выбранных точках.
В целом при численной оптимизации всегда стремятся уменьшить число
вычислений, и первой основной задачей является выбор последовательности
точек
x
, приводящей наиболее быстрым образом к точке экстремума. Вторая
основная задача заключается в попадании в точку экстремума, так как, вооб-
ще говоря, изменение
x
является дискретным и можно "проскочить" точку
экстремума. Поэтому необходимо вблизи точки экстремума
x
уменьшать
шаг с целью попасть в точку
x
точно или с заданной погрешностью.
Численная оптимизация может быть безусловной (при отсутствии каких-
либо ограничений) или условной (если какие-то ограничения имеются).
Ограничения могут быть разными, что приводит к различным постановкам
задачи оптимизации и, соответственно, разным методам её решения. Можно
выделить следующие характерные виды ограничений.
Ограничения, связанные с характером получаемых значений для
x
,
например: вещественные, неотрицательные, положительные, целые и др.
Ограничения могут быть связаны с тем, является ли целевая функция
унимодальной, т. е. имеющей один экстремум, или неунимодальной, т. е.
имеющей несколько экстремумов в области изменения
x
. В первом случае
ищется глобальный экстремум, а во втором — локальный. Понятно, что ло-
кальных экстремумов может быть несколько. Под поиском экстремума по-
нимают определение значения
x
независимой переменной
x
, при котором
имеется экстремум, а также значения целевой функции в этой точке )(
xI .
Может оказаться, что в различных точках
x
будет одно и то же значение
)(xI , например, в случае синусоидальной функции. Тогда имеет место случай
множественного локального экстремума и необходимо выбрать, какой имен-
но нужно считать решением задачи оптимизации.
Ограничения могут быть связаны с областью допустимых значений це-
левой функции с ограничениями типа "больше", "больше или равно", "мень-
ше", "меньше или равно".
Все рассмотренные ограничения имеют существенное значение, но в
теории оптимизации под ограничениями понимают специальные функции,
70
содержащие комбинации переменных
x
. Эти функции записываются как ра-
венства или как неравенства (строгие или нестрогие) и их необходимо учи-
тывать при определении точек экстремума.
При поиске экстремума чрезвычайно полезной является информация о
типе предполагаемого экстремума — максимуме или минимуме. Тогда про-
ще организовать выбор направления движения. Например, в случае поиска
максимума следует двигаться в сторону увеличения целевой функции, а в
случае поиска минимума — в сторону уменьшения. Если же тип экстремума
неизвестен, то движение должно осуществляться в обе стороны, что может
существенно затруднить расчёты. В реальных задачах оптимизации тип экс-
тремума обычно известен, так как все задачи можно свести к одному из двух
случаев: минимум затрат или максимум эффекта, соответственно этому фор-
мируется и целевая функция.
Таким образом, процесс численной оптимизации протекает следующим
образом:
1 устанавливаются границы интервала (левая
min
x и правая
max
x ) выбо-
ром минимальных и максимальных значений для каждой переменной вектора
x
;
2 выбирается первая пробная точка
1
x
(значение каждой из переменной
вектора
x
);
3 вычисляется значение целевой функции в выбранной точке )(
1
xI ;
4 выбирается по каждой переменной приращение x
1
Δ
;
5 определяется новое значение в сторону увеличения xxx
1
12
Δ ;
6 определяется новое значение в сторону уменьшения xxx
1
13
Δ ;
7 вычисляется значение целевой функции во второй точке )(
2
xI ;
8 вычисляется значение целевой функции в третьей точке )(
3
xI ;
9 сравниваются три точки: )(
1
xI , )(
2
xI , )(
3
xI ;
10 определяют направление движения пробной точки (в сторону увели-
чения или в сторону уменьшения);
11 определяется новое значение
4
x
с соответствующим приращением
относительно предыдущего значения;
12 вычисляется значение целевой функции в новой точке )(
4
xI ;
13 сравниваются три точки: )(
1
xI , )(
3
xI , )(
4
xI или )(
1
xI , )(
2
xI ,
)(
4
xI — в зависимости от выбранного направления движения;