АЛГОРИТМЫ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

разделе представлен градиентный метод решения задач нелинейного программирования без ограничений

на переменные. В этом реализуется для нахождения экстремальной точки используется градиент целевой функции.
Градиентный метод
В этом разделе рассматривается метод решения задач нелинейного программирования с дважды непрерывно дифференцируемыми функциями. Основная идея метода заключается в построении последовательности точек, с учетом направления градиента исследуемой функции.
Одним из градиентных методов является изложенный ранее метод Ньютона – Рафсона, который ориентирован на решение систем уравнений. Здесь рассматривается еще один метод, который называется методом наискорейшего подъема. В русской математической литературе описываемый метод называется методом наискорейшего спуска и ориентирован на решение задач безусловной минимизации.
Согласно градиентному методу, вычисления завершаются при нахождении точки, в которой градиент функции равен нулю. Но это лишь необходимое условие для того, чтобы в данной точке находился оптимум. Чтобы удостовериться, что найдена именно точка оптимума, обычно привлекаются свойства вогнутости или выпуклости функции f(x).
Рассмотрим задачу максимизации функции f(x). Пусть X0 — начальная точка, с которой начинается реализация метода, ∇f(Xk) — градиент функции f в k-й точке Xk. Идея метода сводится к определению в данной точке направления p, вдоль которого производная по направлению df/dp достигает своего максимума. Это достигается в том случае, когда последовательные точки Xk и Xk+1 связаны соотношением
Xk+1 = Xk + rk∇f(Xk),
где rk — параметр, называемый длиной шага.

условия, чтобы в точке Xk+1 наблюдалось максимальное увеличение значения целевой

функции f. Другими словами, если функция h(r) определяется соотношением
h(r) = f(Xk + rk∇f(Xk)),
то rk равен значению r, на котором функция h(r) достигает максимума. Поскольку h(r) является функцией одной переменной, для нахождения ее максимума можно применить метод прямого поиска экстремума, если, конечно, функция h(r) строго одновершинная.
Описанная процедура заканчивается, когда две последовательные точки Xk и Xk+1 близки. Это эквивалентно тому, что rk∇f(Xk) ≈ 0. Поскольку rk ≠ 0, последнее соотношение означает, что в точке Xk выполняется необходимое условие экстремума ∇f(Xk) = 0.
Пример 9.1
Рассмотрим задачу максимизации функции
f(x1, x2) = 4x1 + 6x2 – 2x12 – 2x1x2 – 2x22.
Функция f(x1, x2) является квадратичной и нам известно, что ее абсолютный максимум достигается в точке (x1*, x2*) = (1/3; 4/3). Решим эту задачу методом наискорейшего подъема. На рис. 9.1 изображена последовательность получаемых точек. Градиенты в двух последовательных итерационных точках с необходимостью являются ортогональными (перпендикулярными) друг к другу. Для данной функции градиент вычисляется по формуле
 
∇f(X) = (4 - 4x1 - 2x2, 6 - 2x1 - 4x2).
 
Пусть начальной точкой является X0 = (1, 1).
Первая итерация
∇f(X0) = (-2, 0).
Следующая точка X1 находится на основании формулы
X = (1, 1) + r(-2, 0) = (1 – 2r, 1).
Отсюда получаем выражение для функции h(r):
h(r) = f(1 – 2r, 1) = - 2(1 – 2r)2 + 2(1 – 2r) + 4.

h(r) достигает максимума, равна 1/4. Таким образом, мы нашли, что

X1 = (1/2, 1).













Рис. 9.2.
Вторая итерация
∇f(X1) = (0, 1).
Теперь следующая точка X2 определяется выражением


Следовательно,
h(r) = -2(1 + r)2 + 5(1 + r) + 3/2
Отсюда получаем r = 1/4 и X2 = (1/2, 5/4).
Третья итерация
∇f(X2) = (-1/2, 0).

= (1/2, 5/4).
Третья итерация
∇f(X2) = (-1/2, 0).

Точка X3 определяется выражением



Отсюда получаем r = 1/4 и X3 = (3/8, 5/4).
Четвертая итерация
∇f(X3) = (0, ¼).
Точка X4 определяется выражением




Отсюда имеем r = 1/4 и X4 = (3/8, 21/16).
Пятая итерация
Точка X5 определяется выражением




Отсюда получаем r = 1/4 и X5 = (11/32, 21/16).
Шестая итерация
Так как ∇f(X5) ≈ 0, вычисления можно закончить. Получена приближенная точка максимума X5 = (0.3437, 1.3125). Точный максимум достигается в точке X* = (0.3333, 1.3333).

нелинейного программирования с ограничениями записывается в виде:
максимизировать

(или минимизировать) z = f(X)
при ограничениях
g(X) ≤ 0.
Условия неотрицательности переменных X ≥ 0 составляют часть заданных ограничений общего вида. Предполагается также, что, по крайней мере, одна из функций f(x) или g(X) является нелинейной и все функции непрерывно дифференцируемы.
Универсальных алгоритмов решения задач нелинейного программирования не существует, и связано это, главным образом, с разнообразием нелинейных функций. Возможно, наиболее общим результатом, имеющим отношение к рассматриваемым задачам, являются условия Куна – Таккера. Как показано в ранее, эти условия являются лишь необходимыми для существования экстремума, за исключением, когда функции f(x) и g(X) являются выпуклыми или вогнутыми.
Существует ряд алгоритмов решения задач нелинейного программирования, которые условно можно разделить на непрямые и прямые. В непрямых методах решение задачи нелинейного программирования сводится к решению одной или нескольких линейных задач, порожденных исходной. Прямые методы непосредственно имеют дело с исходной нелинейной задачей и позволяют построить последовательность точек, сходящуюся к точке экстремума.
Непрямые методы представлены алгоритмами сепарабельного, квадратичного, геометрического и стохастического программирования. К числу прямых методов относится метод линейных комбинаций и метод последовательной безусловной максимизации, изложенный далее вкратце.

xn) называется сепарабельной (разделимой), если она представляется в виде суммы

и функций одной переменной f1(x1), f2(x2), …, fn(xn), т.е.
f(x1, x2, …, xn) = f(x1) + f(x2) + … + f(xn).
К примеру, линейная функция
h(x1, x2, …, xn) = a1x1 + a2x2 + … + anxn
(здесь ai, i = 1, 2, …, n – константы) является сепарабельной. Функция же
h(x1, x2, x3) = + x1sin(x2 + x3) + x2
таковой не является.
Некоторые нелинейные функции сепарабельными непосредственно не являются, однако могут быть приведены к такому виду путем соответствующих подстановок. Рассмотрим, к примеру, задачу максимизации функции z = x1x2. Если ввести обозначение y = x1x2, то ln y = ln x1 + ln x2 и задача принимает следующий вид.
Максимизировать z = y
при ограничении
ln y = ln x1 + ln x2
т.е. она является сепарабельной. При такой замене предполагается, что переменные x1 и x2 принимают положительные значения, иначе логарифмическая функция не определена.
В случае, когда переменные x1 и x2 принимают и нулевые значения (т.е. x1, x2 ≥ 0), можно поступить следующим образом. Пусть δ1 и δ2 – положительные константы, введем новые переменные w1 = x1 + δ1 и w2 = x2 + δ2.
Эти переменные принимают только положительные значения. Теперь имеем
x1x2 = w1w2 – δ2w1 – δ1w2 + δ1δ2.
Пусть y = w1w2, тогда исходная задача эквивалентна следующей.
Максимизировать z = y – δ2w1 – δ1w2 + δ1δ2
при ограничениях
ln y = ln w1 + ln w2, w1 ≥ δ1, w2 ≥ δ2.

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

к сепарабельным, могут служить и . В этих случаях для реализации свойства сепарабельности следует применить соответствующий вариант описанной выше процедуры.
В сепарабельном программировании рассматриваются задачи нелинейного программирования, в которых как целевая функция, так и функции ограничений являются сепарабельными. В этом разделе рассматриваются методы приближенного решения задачи сепарабельного программирования, основанные на линейной аппроксимации функций и на симплекс-методе линейного программирования.
Функцию одной переменной f(x) можно аппроксимировать кусочно-линейной функцией с помощью методов частично-целочисленного программирования. Пусть требуется аппроксимировать функцию f(x) на интервале [a, b]. Обозначим через ak, k = 1, 2, …, K, k-ю точку разбиения интервала [а, b], причем a = a1 < a2 < … < ak = b. Тогда функция f(x) аппроксимируется следующей кусочно-линейной функцией:

где tk — неотрицательный весовой коэффициент, связанный с k-й точкой разбиения интервала. Весовые коэффициенты удовлетворяют условию

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

программирования следующим образом. Обозначим через Ki число точек разбиения для

i-й переменной xi, а через aik – k-ю точку разбиения. Пусть tik – весовой коэффициент, ассоциируемый с k-й точкой разбиения для i-й переменной. Тогда эквивалентная задача частично-целочисленного программирования имеет вид




0 ≤ ti1 ≤ yi1, 0 ≤ tik ≤ yik-1, k = 2, 3, …, Ki – 1,
0 ≤ tiKi ≤ yiKi - 1,



yik = 0 или 1, k = 1, 2, …, Ki, i = 1, 2, …, n.
В аппроксимирующей задаче переменными являются tik и yik.
Данное представление свидетельствует о том, что в принципе любая задача сепарабельного программирования может быть решена методами частично-целочисленного программирования. Трудность такого подхода к решению задачи связана с быстрым ростом числа ограничений при увеличении количества точек разбиения. В частности, проблематичной является вычислительная реализация процедуры, поскольку нет эффективных компьютерных программ для решения задач частично-целочисленного программирования большой размерности.
Для решения аппроксимирую шей задачи можно использовать также обычный симплекс-метод, дополненный правилом ограниченного ввода в базис. В этом случае игнорируются вспомогательные ограничения, содержащие yik. Согласно данному правилу, в базисе может находиться не более двух положительных весовых коэффициентов tik. Более того, два коэффициента tik могут быть положительными лишь тогда, когда они являются смежными. Таким образом, строгое условие оптимальности симплекс-метода только тогда используется для выбора переменной tik подлежащей введению в число базисных, когда она удовлетворяет указанным выше требованиям

аппроксимирующей задачи, тогда как симплекс-метод с учетом правила ограниченного ввода

в базис может гарантировать нахождение лишь локального оптимума. Кроме того, приближенное решение, полученное любым из двух упомянутых методов, может быть недопустимым для исходной задачи, поскольку при решении аппроксимирующей задачи могут быть обнаружены дополнительные экстремальные точки, которые для исходной задачи экстремальными не являются. Это зависит от точности линейной аппроксимации исходной задачи.
Сепарабельное выпуклое программирование. Задача выпуклого сепарабельного программирования имеет места в том случае, когда функции gi j(xi) являются выпуклыми, обеспечивая, таким образом, выпуклость области допустимых решений. Кроме того, считаем, что функции fi(xi) являются выпуклыми в задаче минимизации и вогнутыми в задаче максимизации. При этих условиях можно использовать следующий упрощенный метод аппроксимации.
Рассмотрим задачу минимизации. Пусть функция fi(xi) имеет такой вид, как показано на рис. 9.3. Обозначим точки разбиения для функции fi(xi) через xi = aki, k = 0, 1, …, Ki.
Пусть xki - величина изменения переменной xi на интервале (ak-1, aki), k = 1, 2, …, Ki, а ρki – тангенс угла наклона линейного сегмента на том же интервале.

aki - ak-1, k = 1, 2, …, Ki.

Так как функция fi(xi) выпуклая, то ρ1i < ρ2i < ρk,i. Это означает, что в задаче минимизации при p < q большее влияние на значение целевой функции оказывает переменная xpi чем xqi. Следовательно, переменная xpi всегда будет входить в решение до того, как в него войдет xqi. При этом значения каждой переменной xki должны быть ограничены сверху величиной (aki – ak-1, i).
Выпуклые функции ограничений gi j(xi) аппроксимируются аналогичным образом.
Пусть — тангенс угла наклона k-го линейного сегмента, соответствующего функции gi j(xi). Тогда функция gi j(xi) аппроксимируется формулой


Следовательно, рассматриваемая задача принимает вид










Задача максимизации преобразуется аналогично. В этом случае, ρ1i > ρ2i > ρk,i откуда следует, что при p < q переменная всегда xpi будет входить в решение раньше xqi.
Полученную задачу можно решить симплекс-методом, предназначенным для решения задач с ограниченными сверху переменными. При этом исчезает необходимость в соблюдении правила ограниченного ввода в базис, поскольку выпуклость (вогнутость) функций гарантирует надлежащий выбор переменных.