Градиентный метод с постоянным m

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

Например, для функции при с проекциями градиентов методом наискорейшего спуска определен . Примем параметр постоянным на всех итерациях.

Вычисляем координаты х⁽¹⁾:

Для вычисления координат точки х⁽²⁾ находим проекции градиента в точке х⁽¹⁾: , тогда

и т.д.

Данная последовательность также сходится.

Шаговый градиентный метод

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

Пусть дана сепарабельная функция и начальная точка . Зададимся постоянным шагом по координате х₁, пусть Dх₁=0,2. Шаг по координате х₂ находим из соотношения градиентов и шагов:

, тогда

Координаты точки х⁽¹⁾:

Теперь определяется Dх₂ для второй итерации:

Координаты х⁽²⁾:

Продолжая вычисления, получим:

Итерация
х₁		0,2	0,4	0,6	0,8
х₂	2,044	2,008

На девятой итерации получили х⁽⁸⁾=(1,2). При попытке вычислить Dх₂ получим:

– неопределенность, т.к. проекции градиентов равны 0, т.е. мы попали в экстремальную точку – итерации можно завершить.

Шаговый градиентный метод не обладает свойством сходимости, но весьма эффективен.

Метод сопряженных направлений

В заключение изучения приближенных методов поиска экстремума ФМП без ограничений рассмотрим метод сопряженных направлений, который завоевывает на практике все большую популярность.

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

, (7)

Сопряженность связана с ортогональностью. Если Н – единичная матрица, то при имеем два взаимно перпендикулярных вектора. Соотношение (7) можно трактовать таким образом: матрица Н, примененная к вектору , изменяет его длину и поворачивает на некоторый угол так, что новый вектор должен быть ортогонален вектору .

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

1) Производится выбор и в этом направлении отыскивается экстремум.

Возьмем вектор с направлениями и . Вектор можно выбирать произвольно, поэтому возьмем = =1. Вектор дает направление L₁.

Проведем через L₁ плоскость перпендикулярную плоскости {x₁, x₂}. Плоскость пересечет экстремальную поверхность у(х₁, х₂) и выделит на ней экстремальную линию. Определим координаты минимума на этой линии (параболе), для чего вычислим проекции градиента в точке х⁰:

и по формуле (6) найдем m:

Тогда:

Естественно, линия L₁ касается в точке х⁽¹⁾ линии равного уровня функции у.

2) Отыскивается из условия сопряженности .

Получим сопряженный вектор с проекциями и , воспользовавшись формулой (7):

Получили одно уравнение с двумя неизвестными. Т.к. нам требуется только направление вектора , а не его длина, то одним из неизвестных можно задаться произвольно. Пусть =1, тогда = –4.

3) Из точки х⁽¹⁾ в направлении ищется экстремум.

Сопряженный вектор должен проходить через х⁽¹⁾. Сделаем шаг в сопряженном направлении:

Величина шага m⁽¹⁾ в х⁽¹⁾:

тогда

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

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

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

Классическая задача Лагранжа на условный экстремум (ограничения-равенства).

Пусть задана целевая функция и ограничение-равенство (уравнение связи) . Требуется найти минимум на множестве . Считаем, что функции и имеют непрерывные первые производные и являются выпуклыми или вогнутыми.

Рассмотрим геометрическую интерпретацию классической задачи. На плоскости {x₁, x₂} построим функцию , а также линии равного уровня функции со значениями N₁<N₂<…N_n. Линия N₁ не имеет общих точек с , линия N₃ имеет 2 общих точки с и они не могут быть решением задачи, т.к. N₃> N₂. Остается линия уровня N₂, которая имеет единственную точку касания с . Абсолютный минимум N₀ может не принадлежать ограничению и поэтому не может быть решением задачи. Отсюда ясно и название «условный экстремум», т.е. такой экстремум, который достигается только на заданных ограничениях.

В точке касания с функцией проведем касательную линию L. Поострим градиенты функций и в точке касания, они будут лежать на одной линии, т.к. оба перпендикулярны L и направлены в разные стороны. Определим проекции градиентов на оси х₁ и х₂ в точке касания:

Из подобия треугольников можно записать:

– множитель Лагранжа.

или

Составим теперь функцию следующим образом:

– функция Лагранжа.

Запишем соотношения для нахождения экстремума функции F.

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

В общем случае, число переменных примем за n, а число ограничений за m. Тогда функция Лагранжа запишется в виде:

или в векторной форме

Для решения задачи записывается система уравнений:

, (8)

т.е. для n+m переменных будем иметь n+m уравнений. Если система совместна, то задача Лагранжа имеет единственное решение.

Т.к. для определения экстремума использовались только первые производные, то полученные условия будут являться только необходимыми. Если функции и выпуклые или вогнутые, то условный экстремум единственный. Если одна из функций невыпуклая, то экстремум может быть и не единственным. Кроме того, открыт вопрос о том, что найдено – минимум или максимум, хотя в инженерной практике обычно из физических соображений это бывает ясно.

Пример: Покажем технику решения задачи методом Лагранжа.

Для рассмотренного выше примера с двумя насосами, задан объем перекачиваемой жидкости:

При этом ограничении требуется найти потребляемую мощность насосов . Пусть коэффициенты равны a₁=a₂=1, К₁=1, К₂=1,5. Тогда целевая функция , найти минимум при ограничении: .

Процедура решения:

1. Составляем функцию Лагранжа

2. Составляется система уравнений (8):

3. Записываются Q_i через l и подставляются в третье выражение:

, , ,

Тогда координаты экстремума:

Пример 2:

Пусть дано последовательное соединение компрессоров. Задана требуемая степень сжатия: , которую требуется обеспечить при минимуме расхода мощности:

Решение:

3. , , подставляем в выражение для :

, , . Из физических соображений положительный корень отбрасываем, поэтому l= –0,98.

Тогда координаты экстремума:

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

Приближенные методы решения классической задачи Лагранжа на условный экстремум

Первый метод численного решения задачи Лагранжа основан на соотношении Лагранжа:

т.е. только в экстремальной точке все соотношения градиентов функций равны. Это соотношение и используется при поиске экстремума.

Пример:

По первому методу решим задачу поиска экстремума функции при ограничении .

Отношение проекций градиентов функции равно , следовательно, отношение проекций градиентов функции в экстремальной точке х^* должно быть равно

Проекции градиентов функции в произвольной точке равны: , . В качестве начальной точки примем х⁰=(0,2; 0,8), в которой . Возьмем шаг по координате х₁ Dх₁=0,2.

Если в качестве первого приближения взять точку (0, 1), то в ней соотношение , т.е. шаг был сделан не в ту сторону (т.к. требуется двигаться в сторону равенства ). Следовательно нужно идти в сторону увеличения х₁.