Геометрическая интерпретация метода множителей Лагранжа.

Относительный экстремум. 28

Метод множителей Лагранжа.

Безусловный экстремум ищется решением уравнения

Пусть теперь имеется m ограничений типа равенства

(*)

Условия (*) называют также уравнением связи

Точку x, удовлетворяющую условиям (*), будем называть допустимой.

Допустимая точка доставляет относительный локальный минимум функции f(x), если можно указать такое число , что для всех x, удовлетворяющих уравнениям связи (*) и условию имеет место неравенство

Пусть уравнения связи (*) можно разделить относительно части переменных, функций имеют в окрестности точки непрерывные частные производные по всем аргументам до второго порядка включительно. Кроме того, ранг матрицы Якоби для функций в точке равен m, т.е.:

Тогда система (*) может быть представлена в виде:

(**)

где – непрерывно дифференцируемые функции

Переменные , …, называются независимыми

, …, – зависимыми

Подставляя (**) в функцию , получим задачу отыскания безусловного определения функции n-m переменных

Однако, исключение части компонент выбор зачастую трудно или далее невозможно

Метод множителей Лагранжа.

В т. , доставляющей безусловный экстремум функции , ее полный дифференциал равен нулю

С учетом выше изложенного, имеем

(*)

"зависимые" переменные "независимые" переменные

Найдем теперь полный дифференциал уравнений связи

,

(**)

Т.е. расписываем дифференциал на 2 суммы и

Первая сумма – дифференциалы «зависимых переменных»;

Вторая – «независимых»

Исключим теперь дифференциалы «зависимых» переменных из уравнений (*) и (**):

Умножим каждое из уравнений (**) (всего m уравнений) на произвольные множители и результат сложим с уравнением (*).

Получим равенство:

(***)

Т.к. выбирались произвольно, то их можно выбрать так, чтобы коэффициенты при дифференциалах «зависимых» переменных обратились в нуль.

(****) 29

Т.е. =0

Это можно сделать, т.к. уравнения (****) линейны относительно , а ее определитель ≠ 0

Тогда в уравнении (***) останутся только числа, содержащие дифференциалы «независимых» переменных.

Поэтому коэффициенты при этих дифференциалах должны быть

нулевыми, т.е.

(*****)

Т.о. мы получим систему n+m уравнений относительно n+m неизвестных

Это и есть метод множителей Лагранжа.

Основные этапы метода:

1. Составляется функция n+m переменных – функция Лагранжа

(1)

2. Вычисляются и приравниваются к нулю ее частные производные по и :

(2)

3. Решается система m+n уравнений относительно n+m неизвестных

Решение – называются условно-стационарными точками

Характер экстремума определяется с помощью производных более высокого порядка функции и

Требования неравенства нулю становится весьма существенно, т.к. система уравнений (2) разрешима только в этом случае

(3)

Геометрическая интерпретация метода множителей Лагранжа.

Линия уровня функции 2х переменных:

– ограничение

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

В точке , т.е.

А это и есть необходимое условие экстремума (2).

Достигаемость условия экстремума (относительного экстремума).

Характер стационарной точки можно выяснить с помощью разложения функции , в ряд Тейлора

Пусть пара – решение уравнений (2) и Якоби (3) не равен 0

Рассмотрим приращение функции Лагранжа

Т.к. точка – стационарная, 1ый член в правой части равен 0, т.о.

Т.о. характер экстремума в задаче на относительный экстремум определен знаком квадратичной формы

При этом выполняется условие

Пример 1: 30

Пусть

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

Находим :

Выясняем характер экстремума:

На прямой:

Действительно:

В точке – минимум!

Условия связи, которые не должны нарушаться при переходе из точки

В нашем случае k=1 (только одно ограничение)

И так имеем:

Пример 2:

Пусть

В точке – минимум (проверять не будем)

I. Элементы выпуклого анализа.

1. Непустое множество и называется выпуклым, если отрезок прямой, соединяющий 2 любые точки множества , также принадлежит этому множеству.

Т.е. если , то для всех

Точка вида называют выпуклой комбинацией точек

выпуклое мн-во невыпуклое мно-во

Пример выпуклых множеств:

1) – плоскость в

В общем случае , где , – скаляр

называется гиперплоскостью в , ненулевой вектор – нормаль к гиперплоскости

2) – полупространство

В общем случае

3)

Пересечение двух полупространств

В общем случае , – матрица

–мерный вектор

– многогранное множество

4) – выпуклый конус

5) – круг

И т.д.

2. Выпуклые оболочки

Пусть – произвольное множество из

Выпуклой оболочкой множества называется совокупность всех выпуклых комбинаций точек из

Т.е. точка принадлежит тогда и только тогда, когда она может быть представлена в виде

а

Примеры выпуклых оболочек:

Выпуклая оболочка конечного числа точек называется многогранником

Если векторы – линейно-независимы, то выпуклая оболочка называется симплексом с вершинами

многогранник симплекс

II Условия оптимальности.

1. Конусы возможных направлений

Определение: Конусом возможных направлений в точке называется множество при всех для некоторого

Любой вектор из называется возможным направлением.

При целых любое перемещение вдоль вектора из т. приведет в точку

конус убывания функции, т.е. 50

- конус возможных направлений в т.

Теорема: Пусть дифференцируема в некоторой точке . Если – точка локального минимума, то

(т.е. конус убывания функции не пересекается с конусом возможных направлений)

Теорема: Пусть задана задача Р:

Минимизировать и обозначена через

(т.е. – множество индексов , соответствующих активным ограничением)

Предположим, что функций и при дифференцируемы в точке , а функции при непрерывны в точке .

Если – точка локального минимума, то

Здесь , для всех (т.е. - конус убывания функции (полупространство, антиградиент функции)

- конус антиградиентов активных ограничений

Пример:

Минимизировать:

При условий:

В этом случае:

Рассмотрим точку

В этой точке активно одно ограничение

В т.

Для удобства перенесем начало координат в точку

Точка – не оптимальна

Рассмотрим теперь точку

Активны ограничения и

Градиенты равны:

Конусы и не пересекаются

Точка (2,1) – точка оптимума

2.Условия Кука-Токкера(для задач с ограничениями-неравенствами)

Рассмотрим задачу:

Минимизировать:

При условий:

– непустое открытое множество

Пусть – произвольная допустимая точка задачи 51

Предположим, что и для дифференцируемы в точке , а функции для непрерывны в этой точке.

Пусть также векторы при линейно независимы.

Если точка – точка локального оптимума, то существуют такие числа для , то:

Если, кроме того, функции для дифференцируемы в точке , то условие Кука-Таккера можно переписать в следующей форме:

=0

В векторной форме:

– матрица порядка n x m, у которой i-й столбец равен

– m-мерный вектор (вектор множителей Лагранжа)

(В рассмотренном примере в точке множители Лагранжа – условие оптимальности удовлетворяется).

I. Методы спуска

1. Процедуры линейной аппроксимации

Шаг 1.

1. Пусть

2. Линеаризуем задачу (а) в точке

Решением задачи является 54

Вектор допустим по отношению к задаче , но НЕ ДОПУСТИМ для исходной задачи (а)

Чтобы не допустить выход из допустимой области задачи (а), накладывается ограничение в виде (**)

(в)

Выбор

При этом заметим, что движение из в влечет увеличение и уменьшение , т.е.

Поэтому полагаем , т.е.

В результате получаем:

Шаг 2.

Уменьшаем . Пусть

Линеаризуем задачу в точке

Решение задачи (2)

Последовательно уменьшаем (например

Решение заканчивается, когда

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

Т.о. при линеаризации функции задается некоторая зона допускаемой погрешности

Трудности, возникающие при аппроксимации линейного программирования:

1. Оптимизация происходит поэтапно, если сделать векторы допустимыми, или очень близкими к допустимым

Т.о. необходимо делать слишком малые шаги при поиске оптимума, т.е. метод мелкошаговый

2. Трудно сравнивать два «соседних» вектора и из-за несовпадения подмножеств ограничений на каждом шаге (различные (или те же самые) ограничения нарушаются по разному разными векторами)

3. Если целевая функция сильно нелинейная, то направление поиска оптимума на основе линеаризации может быть выбрано слишком неточно.

2.2 Метод возможных направлений (метод Зойтендейка) 55

1. Случай линейных ограничений

Минимизировать – нелинейна!

При условиях – матрица x

– матрица x

– -мерный вектор

– -мерный вектор

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

;

– матрица активных ограничений

направлен в стороны убывания

– нормали к ограничениям

Т.о. вектор возможного направления спуска обеспечивает убывание функции и выполнение ограничения

4-4 пространство направлений спуска

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

Т.е. ,

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

А) 3 типа нормировки (отыскание вектора )

Задача :

при условиях ограничение на модуль

Задача :

при условиях ограничение на норму вектора

Задача :

при условиях

Задачи – задачи линейного программирования.

Задача содержит квадратичное ограничение

Точка – допустимая во всех 3х задачах. В этой точке , т.е. значение целевой функции равно 0.

Если в задачах (1-3) отрицательно, то можно найти допустимое направление спуска.

Если , то – точка Кука-Таккера, т.е. – решение задачи (1-3)

Б) Линейный поиск минимума в направлении

После определения вектора необходимо решить следующую задачу – определить шаг , обеспечивающий минимизацию

Минимизировать

при условиях

Пусть теперь , , так что

– активные ограничения

– ограничения, несущественные на данном шаге (заведомо вычисленные)

Тогда т.к. , то 56

Т.о. ограничение не зависит от и становится излишним

Т.к. и , то для всех

Т.о. задача сводится к задаче линейного поиска (поиск минимума в заданном направлении)

(*)

при условии , где

(**)

Условия (**) обеспечивают соблюдение ограничивающих условий: при движении в сторону

В) Алгоритм Зойтендейка (случай линейных ограничений)

Начальный этап.

Найти допустимую т. , для которой . Положить и перейти к основному этапу.

Основной этап.

Шаг 1. Пусть задан . Разбиваем матрицу :

и вектор , так что

(Т.е. определяем активные ограничения)

В качестве берется оптимальное решение одной из задач (Пусть )

при условиях

Если – остановиться: – решение, иначе перейти к шагу 2.

Шаг 2. Положить равным оптимальному решению следующей задачи линейного поиска:

при условии

Положить

Определить новое множество активных ограничений в и переопределить и . Заменить на и перейти к шагу 1.

Пример:

При (1)

(2)

(3)

(4)

Итерация 1.

Шаг 1. Поиск направления

В имеем

Активными в являются ограничения (3) и (4)

Задача поиска направления имеет вид: