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

Градиентный метод

Рассмотрим задачу максимизации функции  без ограничений, т.е. случай, когда . Градиент функции   будем для краткости обозначать . Условие оптимальности в таком случае имеет вид:

,                  (3.22)

однако непосредственное решений системы (3.22) может оказаться слишком сложным, поэтому не практике поступают следующим образом. Выбирая произвольную начальную точку , строят итеративный процесс:

               (3.23)

Число  называют длиной шага или просто шагом. Если все  равны между собой, то имеем процесс с постоянным шагом.

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

.              (3.24)

Градиентный метод поиска экстремума (3.23) с выбором шага по способу (3.24) называется методом скорейшего подъема (или спуска для задачи на минимум).

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

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

Пример

Определить максимум функции , начав процесс с точки .

Решение

Градиент целевой функции есть

,

а в точке  он будет:

.

Осуществим движение из точки  вдоль градиента в новую точку :

.

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

.

Чтобы найти  используем условие (3.24):

.

Необходимое условие экстремума дает уравнение:

,

откуда .

Так как , то найденное значение  является точкой максимума функции . Тогда

и

.

Следовательно,  является точкой, в которой целевая функция достигает максимального значения:

.

Пример 2

Найти .

Решение

Возьмем начальную точку . Градиент целевой функции есть

,

а в точке  он равен (0; 3).

Так как в задаче минимизации надо двигаться в направлении, обратном направлению градиента, то следующее приближение определяется по формуле (3.23) в виде:

.

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

.

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

 

и т.д. Значения целевой функции при этом . Получающийся процесс бесконечный, но сходящийся к точке (0; 0), которая является решением задачи. Минимальное значение целевой функции равно 0.

Метод Ньютона

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

на множестве X. Пусть , тогда следующее приближение строят по формуле:

.

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

.

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

.                       (3.25)

Значит, для нахождения  надо решить систему линейных уравнений (3.25). Если матрица  не вырождена, то имеем (при ):

.

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

Метод штрафных функций

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

Рассмотрим общую задачу математического программирования, в которой необходимо найти:

,                  (3.26)

где

.

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

В качестве такой функции можно взять, например, квадратичную функцию штрафа

,

которая является дифференцируемой, если дифференцируемы функции ограничений .

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

.                       (3.27)

При этом, если  реализует максимум в правой части (3.27), то любая предельная точка последовательности  есть решение задачи (3.26).

Недостатком метода штрафных функций является ухудшение свойств вспомогательных задач (в правой части выражения (3.27)) при больших значениях k, в частности, чувствительность к ошибкам вычислений. Эти недостатки преодолены в некоторых вариантах метода, когда можно ограничиться конечными значениями штрафных констант k.

Пример 3

Найти  при ограничении .

Здесь функция Лагранжа , как было показано в примере (см. подраздел 3.3), не имеет седловой точки, поэтому метод множителей Лагранжа неприменим. Возьмем в качестве функции штрафа саму функцию ограничения, т.е.

,

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