3.12. Градиентные методы

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

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

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

Поисковая траектория представляет собой ломаную . Таким образом, надо построить последовательностьтак, чтобы она сходилась к точке максимума. Для точек последовательности выполняются условия

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

Блок 4

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

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

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

Рассмотрим метод штрафных функций.

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

,

где Н – штрафная функция, удовлетворяющая следующим условиям: для всех точек области допустимых значений Н=0 и Н>0 для всех остальных точек. Штрафную функцию можно построить различными способами. Для выпуклого программирования наиболее часто она имеет вид:

,

где

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

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

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

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