ТЕМА
Классические методы безусловной оптимизации
Введение
Как известно,классическая задача безусловной оптимизации имеет вид:
/> (1)
/> (2)
Существуют аналитическиеи численные методы решения этих задач.
Прежде всего вспомниманалитические методы решения задачи безусловной оптимизации.
Методы безусловнойоптимизации занимают значительное место в курсе МО. Это обусловленонепосредственным применением их при решении ряда оптимизационных задач, а такжепри реализации методов решения значительной части задач условной оптимизации(задач МП).
1. Необходимые условиядля точки локального минимума (максимума)
Пусть т. /> доставляет минимальные значения функции />. Известно, что в этой точкеприращение функции неотрицательно, т.е.
/>. (1)
Найдем />, используя разложения функции /> в окрестности т. /> в ряд Тейлора.
/>, (2)
где />, />, /> -сумма членов ряда порядок которых относительно приращений /> (двум) и выше.
Из (2) имеем:
/> (3)
Далее предположим, чтоизменяется только одна переменная из множества переменных />. Например, />, тогда (3) преобразуется к виду:
/> (4)
Из (4) с очевидностьюследует, что
/> (5)
Предположим, что />, тогда
/> (6)
С учетом (6) имеем: />. (7)
Предположим, что /> положительно, т.е. />. Выберем при этом />, тогда произведение />, что противоречит (1).
Поэтому, действительно, /> очевиден.
Рассуждая аналогично относительнодругих переменных /> получаемнеобходимое условие для точек локального минимума функции многих переменных
/>
/> (8)
Легко доказать, что дляточки локального максимума необходимые условия будут точно такими же, как и дляточки локального минимуму, т.е. условиями (8).
Понятно, что итогомдоказательства будет неравенство вида: /> - условие неположительного приращения функции вокрестности локального максимума.
Полученные необходимые условияне дают ответ на вопрос: является ли стационарная точка /> точкой минимума или точкой максимума.
Ответ на этот вопросможно получить, изучив достаточные условия. Эти условия предполагаютисследование матрицы вторых производных целевой функции />.
2. Достаточные условиядля точки локального минимума (максимума)
Представим разложениефункции /> в окрестности точки/> в ряд Тейлора с точностьюдо квадратичных по /> слагаемых.
/> (1)
Разложение (1) можно представитьболее кратко, используя понятие: «скалярное произведение векторов» и«векторно-матричное произведение».
/> (1')
/>
/>
/>
/> - матрица двух производных от целевой функции посоответствующим переменным.
/>, />
Приращение функции /> на основании (1') можнозаписать в виде:
/> (3)
Учитывая необходимыеусловия:
/>, /> (4)
Подставим (3) в виде:
/> (4')
/> (5)
Квадратичная форма /> называется дифференциальнойквадратичной формой (ДКФ).
Если ДКФ положительноопределена, то /> и стационарнаяточка /> является точкойлокального минимума.
Если же ДКФ и матрица />, ее представляющая, отрицательноопределены, то /> истационарная точка /> являетсяточкой локального максимума.
Итак, необходимое идостаточное условие для точки локального минимума имеют вид
/>
/> (эти же необходимые условия можно записать так:
/>, />,/>)
/> - достаточное условие.
Соответственно,необходимое и достаточное условие локального максимума имеет вид:
/>, /> (/>), />.
Вспомним критерий,позволяющий определить: является ли квадратичная форма и матрица, еепредставляющая, положительно определенной, или отрицательно определенной.
3. Критерий Сильвестра
Позволяет ответить навопрос: является ли квадратичная форма и матрица, ее представляющая,положительно определенной, или отрицательно определенной.
Далее изложение будетотносительно ДКФ и матрицы /> ееопределяющей, т.е. ДКФ вида
/>.
/>, /> -называется матрицей Гессе.
/>
Главный определитель матрицыГессе />
/>
/>
/>
/>
/> и ДКФ, которую оно представляет, будут положительноопределенными, если все главные определители матрицы Гессе (/>) положительны (т.е. имеет место следующаясхема знаков:
/>)
Если же имеет местодругая схема знаков для главных определителей матрицы Гессе />, например, />, то матрица /> и ДКФ отрицательно определены.
4. Метод Эйлера –классический метод решения задач безусловной оптимизации
Этот метод основан нанеобходимых и достаточных условиях, изученных в 1.1 – 1.3; применим нахождениюлокальных экстремумов только непрерывных дифференцируемых функций.
Алгоритм этого методадостаточно прост:
1) используянеобходимые условия формируем систему /> в общем случае нелинейных уравнений. Отметим, чторешить аналитически эту систему в общем случае невозможно; следует применитьчисленные методы решения систем нелинейных уравнений (НУ) (см. «ЧМ»).По этой причине метод Эйлера будет аналитически-численным методом. Решая указаннуюсистему уравнений находим координаты стационарной точки />.;
2) исследуем ДКФ иматрицу Гессе />, которая еепредставляет. С помощью критерия Сильвестра определяем, является листационарная точка /> точкойминимума или точкой максимума;
3) вычисляемзначение целевой функции /> вэкстремальной точке
/>
Методом Эйлера решитьследующую задачу безусловной оптимизации: найти 4 стационарные точки функциивида:
/>
Выяснить характер этихточек, являются ли они точками минимума, или Седловыми (см. [3]). Построитьграфическое отображение этой функции в пространстве и на плоскости (с помощьюлиний уровня).
Далее эту функцию будемименовать типовой функцией, исследуя ее экстремальные свойства всеми изученнымиметодами.
5. Классическая задачаусловной оптимизации и методы ее решения: Метод исключения и Метод множителей Лагранжа(ММЛ)
Как известно,классическая задача условной оптимизации имеет вид:
/> (1)
/> (2)
График, поясняющийпостановку задачи (1), (2) в пространстве />.
/> (1')
/> (2')
/>, />
/>
/> - уравнения линий уровня
Итак, ОДР /> в рассматриваемой задаче представляет собойнекоторую кривую, представленную уравнением (2').
Как видно из рисунка,точка /> является точкойбезусловного глобального максимума; точка /> - точкой условного (относительного) локальногоминимума; точка /> - точкаусловного (относительного) локального максимума.
Задачу (1'), (2') можнорешить методом исключения (подстановки), решив уравнение (2') относительнопеременной />, и подставляянайденное решение (1').
/>
Исходная задача (1'),(2') таким образом преобразована в задачу безусловной оптимизации функции />, которую легко решить методомЭйлера.
Метод исключения(подстановки).
Пусть целевая функциязависит от /> переменных:
/>
/>
называются зависимымипеременными (или переменными состояния); соответственно можно ввести вектор
/>
Оставшиеся /> переменных /> называются независимыми переменными решения.
Соответственно можно говоритьо вектор-столбце:
/> и вектора />.
В классической задачеусловной оптимизации:
/> (1)
/> (2)
Система (2) всоответствии с методом исключения (подстановки) должна быть разрешенаотносительно зависимых переменных (переменных состояния), т.е. должны бытьполучены следующие выражения для зависимых переменных:
/> (3)
Всегда ли системауравнений (2) разрешима относительно зависимых переменных /> - не всегда, это возможно лишь в случае,когда определитель />,называемый якобианом, элементы которого имеют вид:
/>, />
не равен нулю (см. соответствующуютеорему в курсе МА)
/>
Как видно, функции />, /> должны быть непрерывными дифференцируемымифункциями, во-вторых, элементы определителя /> должны быть вычислены в стационарной точке целевойфункции.
Подставляем /> из (3) в целевую функцию (1), имеем:
/>
/> (5)
Исследуемая функция /> на экстремум можно произвестиметодом Эйлера – методом безусловной оптимизации непрерывно дифференцируемойфункции.
Итак, метод исключения(подстановки) позволяет использовать задачу классической условной оптимизациипреобразовать в задачу безусловной оптимизации функции /> - функции /> переменных приусловии (4), позволяющим получить систему выражений (3).
Недостаток методаисключения: трудности, а иногда и невозможность получения системы выражений(3). Свободный от этого недостатка, но требующий выполнения условия (4) /> является ММЛ.
5.2. Метод множителейЛагранжа. Необходимые условия в классической задаче условной оптимизации.Функция Лагранжа />
ММЛ позволяет исходнуюзадачу классической условной оптимизации:
/> (1)
/> (2)
Преобразовать в задачубезусловной оптимизации специально сконструированной функции – функцииЛагранжа:
/>, (3)
где />, /> - множители Лагранжа;
/>.
Как видно, /> представляет собой сумму, состоящую изисходной целевой функции /> и«взвешенной» суммы функций />, /> -функции, представляющие их ограничения (2) исходной задачи.
Пусть точка /> - точка безусловного экстремумафункции />, тогда, какизвестно, />, />, или /> (полный дифференциал функции /> в точке />).
Используя концепциязависимых и независимых переменных /> - зависимые переменные; /> - независимые переменные, тогда представим (5) вразвернутом виде:
/> (5')
Из (2) с очевидностьюследует система уравнений вида:
/>, /> (6)
Результат вычисленияполного дифференциала для каждой из функций
/>
Представим (6) в«развернутом» виде, используя концепцию зависимых и независимыхпеременных:
/>, /> (6')
Заметим, что (6') вотличии от (5') представляет собой систему, состоящую из /> уравнений.
Умножим каждое />-ое уравнение системы (6') насоответствующий />-ый множительЛагранжа. Сложим их между собой и с уравнением (5') и получим выражение:
/>
/> (7)
Распорядимся множителямиЛагранжа /> таким образом,чтобы выражение в квадратных скобках под знаком первой суммы (иными словами,коэффициенты при дифференциалах независимых переменных />, />)равнялось нулю.
Термин«распорядимся» множителями Лагранжа вышеуказанным образом означает,что необходимо решить некоторую систему из /> уравнений относительно />.
Структуру такой системыуравнений легко получить приравняв выражение в квадратной скобке под знакомпервой суммы нулю:
/>, /> (8)
Перепишем (8) в виде
/>, /> (8')
Система (8') представляетсобой систему из /> линейныхуравнений относительно /> известных:/>. Система разрешима, если /> (вот почему, как и в методеисключения в рассматриваемом случае должно выполняться условие />). (9)
Поскольку в ключевомвыражении (7) первая сумма равна нулю, то легко понять, что и вторая суммабудет равняться нулю, т.е. имеет место следующая система уравнений:
/> (10)
Система уравнений (8)состоит из /> уравнений, асистема уравнений (10) состоит из /> уравнений; всего /> уравнений в двух системах, а неизвестных
/>: />,/>
Недостающие /> уравнений дает система уравненийограничений (2):
/>, />
Итак, имеется система из /> уравнений для нахождения /> неизвестных:
/> (11)
Полученный результат – системауравнений (11) составляет основное содержание ММЛ.
Легко понять, что системууравнений (11) можно получить очень просто, вводя в рассмотрение специальносконструированную функцию Лагранжа (3).
Действительно
/>, /> (12)
/>, /> (13)
Итак, система уравнений(11) представима в виде (используя (12), (13)):
/> (14)
Система уравнений (14)представляет необходимое условие в классической задаче условной оптимизации.
Найденное в результатерешение этой системы значение вектора /> называется условно-стационарной точкой.
Для того, чтобы выяснитьхарактер условно-стационарной точки /> необходимо воспользоваться достаточными условиями.
5.3 Достаточные условия вклассической задаче условной оптимизации. Алгоритм ММЛ
Эти условия позволяют выяснить,является ли условно-стационарная точка /> точкой локального условного минимума, или точкойлокального условного максимума.
Относительно просто,подобно тому, как были получены достаточные условия в задаче на безусловныйэкстремум. Можно получить достаточные условия и в задаче классической условнойоптимизации.
Результат этогоисследования:
/>
где /> - точка локального условного минимума.
/>
где /> - точка локального условного максимума, /> - матрица Гессе с элементами
/>, />
Матрица Гессе /> имеет размерность />.
Размерность матрицы Гессе/> можно уменьшить, используяусловие неравенства нулю якобиана: />. При этом условии можно зависимые переменные /> выразить через независимыепеременные />, тогда матрицаГессе будет иметь размерность />, т.е. необходимо говорить о матрице />с элементами
/>, />
тогда достаточные условиябудут иметь вид:
/>, /> -точка локального условного минимума.
/>, /> -точка локального условного максимума.
Доказательство: АлгоритмММЛ:
1) составляем функциюЛагранжа: />;
2) используянеобходимые условия, формируем систему уравнений:
/>
3) из решения этойсистемы находим точку />;
4) используядостаточные условия, определяем, является ли точка /> точкой локального условного минимума или максимума,затем находим
/>
1.5.4.Графо-аналитический метод решения классической задачи условной оптимизации впространстве /> и егомодификации при решении простейших задач ИП и АП
Этот метод используетгеометрическую интерпретацию классической задачи условной оптимизации и основанна ряде важных фактов, присущих этой задаче.
/>
/>; />;/>;
/>
/>
В /> - общая касательная для функции /> и функции />, представляющей ОДР />.
Как видно из рисункаточка /> - точка безусловногоминимума, точка /> точкаусловного локального минимума, точка /> - точка условного локального максимума.
Докажем, что в точкахусловных локальных экстремумов кривая /> и соответствующие линии уровня
/>; />.
Из курса МА известно, чтов точке касания выполняется условие
/>
где /> - угловой коэффициент касательной, проведеннойсоответствующей линией уровня; /> - угловой коэффициент касательной, проведенной кфункции
/>
Известно выражение (МА)для этих коэффициентов:
/>; />
Докажем, что эти коэффициентыравны.
/>
/>; />
потому что об этом«говорят» необходимые условия
/>
/>.
Вышесказанное позволяетсформулировать алгоритм ГФА метода решения классической задачи условной оптимизации:
1) строим семейство линий уровня целевойфункции:
/>; />;
2) строим ОДР, используя уравнениеограничения
/>
3) с целью внесения исправлениявозрастания функции />,находим /> и выясняем характерэкстремальных точек;
4) исследуем взаимодействие линий уровняи функции />, находя при этомиз системы уравнений /> координатыусловно стационарных точек – локальных условных минимумов и локальных условныхмаксимумов.
5) вычисляем
/>
Следует особо отметить,что основные этапы ГФА метода решения классической задачи условной оптимизациисовпадают с основными этапами ГФА метода решения задач НП и ЛП, отличие лишь вОДР />, а также в нахожденииместоположения экстремальных точек в ОДР (например, в задачах ЛП эти точкиобязательно находятся в вершинах выпуклого многоугольника, представляющего ОДР />).
5.5. О практическомсмысле ММЛ
Представим классическую задачуусловной оптимизации в виде:
/> (1)
/> (2)
где /> - переменные величины, представляющие вприкладных технических и экономических задачах переменные ресурсы.
В пространстве /> задача (1), (2) принимает вид:
/> (1')
/>
где /> - переменная величина. (2')
Пусть /> - точка условного экстремума:
/>
При изменении /> изменяется
/>, т.е. />
Соответственно изменитсяи значение целевой функции:
/>
Вычислим производную:
/>. (3)
/> (4)
/> (5)
Из (3), (4), (5)/>/>. (6)
Из (5)/>/>. (5')
Подставим (5') в (3) иполучаем:
/> (6')
Из (6)/>, что множитель Лагранжа /> характеризует «реакцию»значение />(ортогональназначению целевой функции) на изменения параметра />.
В общем случае (6) принимаетвид:
/>; /> (7)
Из (6), (7)/>, что множитель />, /> характеризуетизменение /> при изменениисоответствующего />-тогоресурса на 1.
Если /> - максимальная прибыль или минимальнаястоимость, то />, /> характеризует изменения этойвеличины при изменении />, /> на 1.
5.6. Классическая задачаусловной оптимизации, как задача о нахождении седловой точки функции Лагранжа: />
Пара /> называется седловой точкой, если выполняетсянеравенство.
/> (1)
Очевидно, что из (1)/>/>. (2)
Из (2)/>, что />. (3)
Как видно система (3)содержит /> уравнений, подобныхтем /> уравнениям, которыепредставляют необходимое условие в классической задаче условной оптимизации:
/> (4)
где /> - функция Лагранжа.
В связи с аналогиейсистем уравнений (3) и (4), классическую задачу условной оптимизации можнорассматривать как задачу о нахождении седловой точки функции Лагранжа.