Второй метод

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

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

Графически это выглядит так:

Ясно, что экстремальной точкой будет такая, в которой проекция градиента на L будет равна 0.

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

Величина веса l на k-ом шаге определяется из условия ортогональности нормали и проекции градиента:

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

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

Пример: Пусть дана функция . Матрице Гессе имеет вид: . Ограничение: , N=(1, 1).

Начальная точка .

Градиент функции в точке х^к:

Первая итерация:

,

1)

2)

3)

4)

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

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

Фундаментальной теоремой для решения неклассической задачи является теорема Вейерштрасса, которая в случае функции одной переменной говорит о том, что непрерывная функция, определенная на отрезке [a, b], достигает минимума или максимума, по крайней мере, в одной точке этого отрезка. По этой теореме монотонная функция и ее частный случай – линейная функция достигает минимума или максимума на концах отрезка. Если задана функция многих переменных на замкнутом множестве М, то теорема Вейерштрасса гарантирует существование решения задачи на условный экстремум.

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

Если дано линейное уравнение

,

то оно определяет в пространстве некоторую гиперплоскость. Если взять строгое неравенство

,

то данное неравенство определяет открытое полупространство (множество). Открытое потому, что границы не входят во множество.

Если рассматривать нестрогое неравенство

,

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

Аналогичные понятия можно дать и для уравнения произвольного вида. Примеры открытых и замкнутых полупространств (для двумерного случая) даны на рисунке.

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

а) Если – выпуклая функция, заданная при , то множество точек – выпукло и замкнуто.

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

в) Пересечение выпуклых множеств также является выпуклым множеством.

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

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