Планирование

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

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

Названием “методы нелинейного  программирования” объединяется большая  группа численных методов, многие из которых приспособлены для решения  оптимальных задач соответствующего класса. Выбор того или иного метода обусловлен сложностью вычисления критерия оптимальности и сложностью ограничивающих условий, необходимой точностью  решения, мощностью имеющейся вычислительной машины и т.д. Ряд методов нелинейного  программирования практически постоянно  используется в сочетании с другими  методами оптимизации, как, например, метод сканирования в динамическом программировании. Кроме того, эти методы служат основой построения систем автоматической оптимизации - оптимизаторов, непосредственно применяющихся для управления производственными процессами.

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

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

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

 

 

1.1 Минимизация  функций многих переменных. Основные  положения

Градиентом дифференцируемой функции f(x) в точке х[0] называется n-мерный вектор f(x[0]), компоненты которого являются частными производными функции f(х), вычисленными в точке х[0], т. е.

f'(x[0]) = (дf(х[0])/дх₁, …, дf(х[0])/дх_n)^T.

Этот вектор перпендикулярен  к плоскости, проведенной через  точку х[0] , и касательной к поверхности уровня функции f(x),проходящей через точку х[0] .В каждой точке такой поверхности функция f(x) принимает одинаковое значение. Приравнивая функцию различным постоянным величинам С₀, С₁, ... , получим серию поверхностей, характеризующих ее топологию (Рис. 1.1).

Рис. 1.1. Градиент

Вектор-градиент направлен  в сторону наискорейшего возрастания  функции в данной точке. Вектор, противоположный  градиенту (-f’(х[0])), называется антиградиентом и направлен в сторону наискорейшего убывания функции. В точке минимума градиент функции равен нулю. На свойствах градиента основаны методы первого порядка, называемые также градиентным и методами минимизации. Использование этих методов в общем случае позволяет определить точку локального минимума функции.

Очевидно, что если нет  дополнительной информации, то из начальной  точки х[0] разумно перейти в точку х [1], лежащую в направлении антиградиента - наискорейшего убывания функции. Выбирая в качестве направления спуска р[k] антиградиент -f’(х[k]) в точке х[k], получаем итерационный процесс вида

х[k+1] = x[k]-a_kf'(x[k]), а_k > 0; k=0, 1, 2, ...

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

x_i[k+1]=х_i[k] - a_k f(x[k])/ x_i

i = 1, ..., n; k= 0, 1, 2,...

В качестве критерия останова итерационного процесса используют либо выполнение условия малости  приращения аргумента || x[k+l] - x[k] || <= e, либо выполнение условия малости градиента

|| f’(x[k+l]) || <= g,

Здесь e и g - заданные малые величины.

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

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

f(х[k+1]) = f(x[k] – a_kf’(x[k])) < f(x[k]).

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

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

 

1.2 Метод наискорейшего спуска

 

При использовании метода наискорейшего спуска на каждой итерации величина шага а_k выбирается из условия минимума функции f(x) в направлении спуска, т. е.  
f(x[k] –a_kf’(x[k])) =  f(x[k] – af'(x[k])).

Это условие означает, что  движение вдоль антиградиента происходит до тех пор, пока значение функции f(x) убывает. С математической точки зрения на каждой итерации необходимо решать задачу одномерной минимизации по а функции  
j(a) = f(x[k] - af'(x[k])) .

Алгоритм метода наискорейшего  спуска состоит в следующем.

1. Задаются координаты  начальной точки х[0].

2. В точке х[k], k = 0, 1, 2, ... вычисляется значение градиента f’(x[k]).

3. Определяется величина  шага a_k, путем одномерной минимизации по а функции j(a) = f(x[k] - af'(x[k])).

4. Определяются координаты  точки х[k+1]:

х_i[k+1] = x_i[k] – а_kf’_i(х[k]), i = 1 ,..., п.

5. Проверяются условия  останова стерационного процесса. Если они выполняются, то вычисления  прекращаются. В противном случае  осуществляется переход к п. 1.

В рассматриваемом методе направление движения из точки х[k] касается линии уровня в точке x[k+1] (Рис. 1.2). Траектория спуска зигзагообразная, причем соседние звенья зигзага ортогональны друг другу. Действительно, шаг a_k выбирается путем минимизации по а функции ?(a) = f(x[k] - af'(x[k])). Необходимое условие минимума функции dj(a)/da = 0. Вычислив производную сложной функции, получим условие ортогональности векторов направлений спуска в соседних точках:

dj(a)/da = -f’(x[k+1]f’(x[k]) = 0.

Рис. 1.2. Геометрическая интерпретация метода наискорейшего спуска

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

мало отличаются друг от друга, т. е. матрица Н(х) хорошо обусловлена. Напомним, что собственными значениями l_i, i =1, …, n, матрицы являются корни характеристического уравнения

Однако на практике, как  правило, минимизируемые функции имеют  плохо обусловленные матрицы  вторых производных (т/М << 1). Значения таких функций вдоль некоторых направлений изменяются гораздо быстрее (иногда на несколько порядков), чем в других направлениях. Их поверхности уровня в простейшем случае сильно вытягиваются (Рис. 1.3), а в более сложных случаях изгибаются и представляют собой овраги. Функции, обладающие такими свойствами, называют овражными. Направление антиградиента этих функций (см. Рис. 1.3) существенно отклоняется от направления в точку минимума, что приводит к замедлению скорости сходимости.

Рис. 1.3. Овражная функция

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

 

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

 

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

f(x) = (х, Нх) + (b, х) + а

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

По определению, два n-мерных вектора х и у называют сопряженными по отношению к матрице H (или H-сопряженными), если скалярное произведение (x, Ну) = 0. Здесь Н - симметрическая положительно определенная матрица размером пхп.

Одной из наиболее существенных проблем в методах сопряженных  градиентов является проблема эффективного построения направлений. Метод Флетчера-Ривса  решает эту проблему путем преобразования на каждом шаге антиградиента -f(x[k]) в направление p[k], H-сопряженное с ранее найденными направлениями р[0], р[1], ..., р[k-1]. Рассмотрим сначала этот метод применительно к задаче минимизации квадратичной функции.

Направления р[k] вычисляют по формулам:

p[k] = -f’(x[k])+b_k-1p[k-l], k >= 1;

p[0] = -f’(x[0]).

Величины b_k-1 выбираются так, чтобы направления p[k], р[k-1] были H-сопряженными:

(p[k], Hp[k-1])= 0.

В результате для квадратичной функции

,

итерационный процесс  минимизации имеет вид

x[k+l] =x[k] +a_kp[k],

где р[k] - направление спуска на k-м шаге; а_k - величина шага. Последняя выбирается из условия минимума функции f(х) поа в направлении движения, т. е. в результате решения задачи одномерной минимизации:

f(х[k] + а_kр[k]) =   f(x[k] + ар [k]).

Для квадратичной функции

Алгоритм метода сопряженных  градиентов Флетчера-Ривса состоит  в следующем.

1. В точке х[0] вычисляется p[0] = -f’(x[0]).

2. На k-м шаге по приведенным выше формулам определяются шаг а_k. и точка х[k+1].

3. Вычисляются величины f(x[k+1]) и f’(x[k+1]).

4. Если f’(x[k+1]) = 0, то точка х[k+1] является точкой минимума функции f(х). В противном случае определяется новое направление p[k+l] из соотношения

и осуществляется переход  к следующей итерации. Эта процедура  найдет минимум квадратичной функции  не более чем за пшагов. При минимизации неквадратичных функций метод Флетчера-Ривса из конечного становится итеративным. В таком случае после (п+1)-й итерации процедуры 1-4 циклически повторяются с заменой х[0] на х[п+1] , а вычисления заканчиваются при  , где   - заданное число. При этом применяют следующую модификацию метода:

x[k+l] = x[k] +a_kp[k],

p[k] = -f’(x[k])+b_k-1p[k-l], k >= 1;

p[0] = -f’(x[0]);

f(х[k] + a_kp[k]) =   f(x[k] + ap[k];

.

Здесь I- множество индексов: I = {0, n, 2п, Зп, ...}, т. е. обновление метода происходит через каждые п шагов.