Необходимые и достаточные условия экстремума.
Классические методы безусловной оптимизации применяют в тех случаях, когда известен вид целевой функции F(X), т. е. дано ее аналитическое выражение, и предполагается, что F(X) не менее чем дважды дифференцируема по управляемым параметрам. Тогда для определения экстремума используют необходимые и достаточные условия безусловного экстремума. Эти условия легко получить с помощью разложения F(X) в окрестностях экстремальной точки в ряд Тейлора для функции yj{X).
Имеем
(7)
где
градиент целевой функции; ΔХ = X — X*; Ю — матрица Гессе (ее элементы — вторые производные целевой функции по управляемым параметрам).
Очевидно, что условие (2) может выполняться, только если линейный член<grad F(X), ΔХ > равен нулю. Следовательно, необходимым условием экстремума является условие
grad F (X) = 0.
Все точки, в которых выполняется это условие, называют стационарными. Но неравенство (2) не обязательно выполняется в стационарной точке. Для его выполнения нужно, чтобы квадратичный член в (7) при любых ΔХ оставался отрицательным, т. е.
(ΔХ)tЮ(ΔХ)<0. (8)
Условие (8) есть достаточное условие максимума. Матрицу Ю, удовлетворяющую условию (8) при любых ΔХ, называют отрицательно - определенной матрицей, а в случае (АХ)'Ю(АХ)> 0 для любых ΔХ — положительно - определенной матрицей. Поэтому достаточные условия экстремума можно представить как требование отрицательной определенности матрицы Гессе для максимума или положительной определенности для минимума в экстремальной точке.
Итак, если известно выражение F(X), то достаточно продифференцировать целевую функцию по управляемым параметрам и приравнять производные нулю. Решение полученной таким образом системы уравнений даст стационарную точку. Далее нужно убедиться в том, что это действительно экстремальная точка, с помощью проверки выполнения достаточных условий. Если достаточные условия не выполняются, то имеем не экстремальную, а седловую точку.
К сожалению, отсутствуют легко проверяемые признаки многоэкстремальных ситуаций. Зная координаты какой-либо экстремальной точки, нельзя сделать никаких заключений о локальном или глобальном характере этого экстремума, не исследуя F(X) во всей области определения. Исключением являются задачи, где целевая функция — выпуклая при минимизации или вогнутая при максимизации. Выпуклость (или вогнутость) есть достаточный признак одноэкстремальности. Но в задачах проектирования при отсутствии аналитического задания целевых функций проверка F(X) на выпуклость или вогнутость, как правило, невозможна.
При известных аналитических выражениях целевой функции и ограничений условная оптимизация осуществляется с помощью метода неопределенных множителей Лагранжа, который непосредственно применим к задачам с ограничениями типа равенств (5). В соответствии с этим методом задача условной максимизации F(X) заменяется задачей безусловной максимизации функции Лагранжа
где Λ = (λ1, λ2, ..., λp) — вектор неопределенных множителей Лагранжа;
ψ k(X) — k-е ограничение из группы ограничений-равенств; р — количество ограничений.
Значения функций Ф(Х, Λ) и F(X) при XХР совпадают, так как в области работоспособности ψ k(X) = 0. Тогда, если найдем mах Ф(Х, Λ) при XХР, то он будет одновременно , и условным максимумом функции F(X). Поэтому находим максимум Ф(Х, Λ), используя необходимые условия экстремума
(9)
(10)
и решая полученные уравнения (9) и (10). Из (10) видно, что стационарная точка функции Ф(Х, Λ) будет принадлежать области ХР, а следовательно, она дает решение и исходной задачи условное! максимизации функции F(X).
Поисковая оптимизация. Область математики, исследующая вопросы теории и методы решения задач условной оптимизации, получила название математического программирования. Известны такие разделы математического программирования, как линейное, выпуклое, геометрическое и др., занимающиеся исследованием частных случаев задач математического программирования. В процессе проектирования технических объектов наиболее часто встречаются задачи математического программирования со следующей формулировкой: найти максимум (или минимум) целевой функции F(X) в области ХР, определяемой (6), где целевая функция и функции-ограничения являются нелинейными функциями управляемых параметров. Такую задачу обычно записывают в виде
(11)
Рисунок. Линии равного уровня функции с двумя максимумами.
Задача (11) есть задача нелинейного программирования. В отдельных случаях при проектировании удается задачу поставить так, что F(X) и ограничения будут линейными функциями своих аргументов. Тогда имеет место задача линейного программирования.
Классические методы нахождения экстремумов целевых функций непосредственно в САПР практически не применяются, так как случаи аналитического задания функций в задаче (11) крайне редки. Характерной ситуацией является наличие алгоритмических математических моделей. В связи с этим определение значений целевых функций, функций-ограничений и их градиентов возможно только через численное решение систем уравнений, подсчет функционалов и выполнение других необходимых алгоритмов. В такой ситуации используют поисковую оптимизацию, при которой поиск цели — экстремальной точки в пространств управляемых параметров— осуществляется последовательными шагами, ведущими от исходной точки Х0 через некоторые промежуточные отображающие точки Хк в заданную ε-окрестность точки экстремума X*.
При рассмотрении методов поисковой оптимизации полезны некоторые геометрические представления. Будем называть последовательность отображающих точек Xk, соединенных отрезками прямых, траекторией поиска. Геометрическое представление функций дается в виде поверхностей отклика (при размерности пространства более двух имеем гиперповерхности отклика). В свою очередь, поверхности отклика на рисунках представляются в виде совокупности линий равного уровня. Линия равного уровня (при п> 2 — поверхность или гиперповерхность равного уровня) имеет уравнение F(X) = а и является геометрическим место точек в пространстве управляемых параметров, в которых значения целевой функции равны a.
Рис. 6.3. Линии равного уровня функции с седловой точкой
Воспользуемся геометрическими представлениями для графической иллюстрации некоторых из введенных здесь понятий. Во всех случаях будем использовать двумерное пространство управляемы; параметров X = (x1, х2). На рис. 1 показаны линии равного уровня некоторой функции F(X) с двумя максимумами в точках А и Б (значения функции указаны на рисунке рядом с линиями равного уровня). Здесь точка А — точка глобального максимума, так как F(A) превышает значение F (Б).
На рис. 2 приведен пример одноэкстремальной функции
F(X) = — 1,1*x12— 1,5x22+2x1*x2 + x1+5, (12)
ее линии равного уровня на рисунке сплошные, точка Э — точка безусловного экстремума, Э = (1,15, 0,77).
Пусть имеется ограничение x1 + 1,5 x2 — 1 = 0, соответствующая ему линия показана на рис. 2 пунктиром. Очевидно, что точка условного экстремума Y здесь не совпадает с точкой безусловного экстремума Э.
На рис. 3 показаны линии равного уровня функции
F (X) = — 0,5*x12— 0,25x22 - x1*x2 - 3x1
Для этой функции в стационарной точке С = (1,— 2) выполняются необходимые, но не выполняются достаточные условия экстремума. Следовательно, С — седловая точка.
На рис..1 седловой точкой будет тонка В.
'Этапы вычислительного процесса при оптимизации. Перед началом поиска, выбирается некоторая исходная точка Х0 в пределах допустимой области ХД. Далее вычислительный процесс состоит из последовательности шагов. На каждом шаге сначала выбирается направление движения. Затем производится сам шаг в пространстве управляемых параметров, в результате из предыдущей точки Хk осуществляется переход в новую точку Хk+1. В этой точке вычисляется значение целевой функции F(Xk+1), благодаря чему можно судить о достигнутом успехе. Шаг заканчивается проверкой условий прекращения поиска: если условия выполнены, то поиск заканчивается, иначе делается переход к новому шагу. Изложенная схема вычислений иллюстрируется рис. 4.
Рис. 4. Схема вычислений при поисковой оптимизации.
Выше неоднократно отмечалось, что при алгоритмических математических моделях цена каждого варианта анализа достаточно высока. В процессе же оптимизации приходится выполнять анализ многократно.
Обозначим через п1 и п2 количества вариантов анализа работы объекта на этапе вычисления целевой функции и на этапе определения направления поиска соответственно, а через n3 — количество шагов 'поиска. Пусть Тм1 — затраты машинного времени на один вариант анализа работы объекта. Тогда общее время решения задачи оптимизации на ЭВМ
TK = TM1(n1 + n2)n3. (13)
Значения n1, п2 и п3 характеризуют эффективность принятой стратегии поиска с позиций затрат машинного времени, эти параметры обычно называют потерями на поиск и относят к основным критериям эффективности алгоритмов. Кроме потерь на поиск к показателям эффективности относят точность определения экстремальной точки, надежность поиска, понимаемую как вероятность получения -решения задачи с заданной точностью. F