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

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

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

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

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

1) задачи безусловной оптимизации, в которых на управляемые переменные (х₁, х₂,..., х_n), которым соответствует минимальное значение целевой функции F (х₁, х₂,..., х_n), не накладывается никаких ограничений;

2) задачи условной оптимизации, в которых на управляемые переменные (х₁, х₂,..., х_n), которым соответствует минимальное значение целевой функции F (х₁, х₂,..., х_n), накладываются ограничения, задаваемые в виде равенств и неравенств.

Считается, что большинство задач проектирования безусловной оптимизации проще, чем задачи условной оптимизации. Поэтому, одним из способов решения задачи условной оптимизации является ее преобразование к задаче безусловной оптимизации.

Методы решения задач безусловной оптимизации можно разделить на две группы:

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

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

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

 

Метод прямого поиска

 

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

Возможен другой вариант метода поиска, когда аргументы по очереди изменяются на какую-то величину ±Δх и определяется новое улучшенное значение целевой функции. Процесс повторяется до тех пор, пока всякое изменение переменных не приводит к ухудшению значения целевой функции.

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

 

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

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

Градиентные методы минимизации целевой функции заключается в движении от точки х_k к точке х_k+1 в направлении антиградиента. Градиент функции определяется как вектор – столбец из частных производных

∂F(x_k)

∂ x₁

F(xk) =

∂F(x_k)

∂ x_{2 (162)}

………

∂F(x_k)

∂ x_n

Движение из точки х_k в направлении антиградиента в следующую точку х_k+1 осуществляется по следующей схеме

х_k+1 = х_k – λ * F(x_k) (163)

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

 

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

 

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

Пусть требуется минимизировать функцию F(x) при ограничениях f_i(x) ≤0, i = 1,2,…,m.

По методу штрафных функций задача сводится к минимизации другой функции

S(x,ℓ) = F(x) + F_ℓ [ℓ, f₁(x), f₂(x),…, f_m(x)], (164)

где F_ℓ - штраф, являющийся функцией ℓ и функций, задающих

ограничения f₁(x), f₂(x),…, f_m(x);

ℓ – набор штрафных параметров

Штрафная функция подбирается таким образом, чтобы она могла бы препятствовать выходу за пределы области допустимых решений и, с другой стороны, чтобы не имела существенного влияния на результат решения. То есть в конечном итоге экстремумы функции F(x) и S(x,ℓ) должны совпадать.

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

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

Рассмотрим некоторые типы штрафов.

Квадратичный штраф используется для учета ограничений - равенств и определяется выражением:

F_ℓ = ℓ { f_i (x)}². (165)

При минимизации этот штраф препятствует отклонению величины f_i (x) от нуля (как в сторону положительных, так и в сторону отрицательных значений).

Л огарифмический штраф. Другим широко используемым типом штрафа является логарифмический штраф, который определяется выражением:

F_ℓ = - ℓ ln { f_i (x)}. (166)

Этот штраф положителен при всех x, таких, что 0 < f_i (x) < 1, и отрицателен при f_i (x) > 1. В данном случае вводится искусственная дискриминация точек допустимой области: внутренним точкам отдается предпочтение перед граничными.

Итерацию начинают из допустимой начальной точки при положительном начальном значении ℓ (например, ℓ =10 или ℓ =100). После решения каждой подзадачи безусловной минимизации параметр ℓ уменьшается и в пределе стремится к нулю. Не следует для более быстрого решения задачи брать штрафной параметр близким к нулю, например ℓ =0,1, так как существует предел штрафного параметра для каждой штрафной функции, при котором его уменьшение не улучшает решение и процесс вычислений останавливается.

Пример. Найти минимум функции F(x) = (x₁-6)² + (x₂-8)² (167)

при ограничении f(x) = 5 - x₁ – x₂ ≥ 0. (168)

Используя метод штрафных функций, определим аналитическим путем точку минимума.

Штрафная функция имеет вид (164)

S(x,ℓ)= F(x) + F_ℓ [ℓ, f(x)] = (x₁-6)² + (x₂-8)² + ℓ ln(5 - x₁ – x₂), (169)

где F_ℓ = ℓ ln(5 - x₁ – x₂) – логарифмический штраф (166)

Условия стационарности принимают вид

∂ S(x,ℓ)/ ∂ x₁ = 2(x₁ – 6) + ℓ /(5 - x₁ – x₂) = 0 (170)

∂ S(x,ℓ)/ ∂ x₂ = 2(x₂ – 8) + ℓ /(5 - x₁ – x₂) = 0 (171)

Откуда следует, что x₁ = x₂ – 2. (172)

Тогда получим 2(x₂ – 8) + ℓ /(7 - 2x₂ ) = 0 (173)

и приходим к уравнению 2x₂² – 23x₂ + 56 – (ℓ /2) = 0, (174)

в котором один из корней дает координату стационарной точки

 

х₁ = (23/4) – (1/4)√(81+4 ℓ) (175)

Второй корень соответствует недопустимой точке и должен быть отброшен.

В пределе ℓ = 0, отсюда получаем Lim x₂(ℓ) = 3,5 (176)

^ℓ→0

Учитывая (172), определяем первое неизвестное

x₁ = x₂ – 2 = 3,5 -2 = 1,5 (177)

Подставим значения неизвестных x₁, x₂ в выражение исходной функции (167) и определим ее минимум

F(x)_min = (x₁-6)² + (x₂-8)² = (1,5 – 4)²+(3,5 – 4)² = 92,5 (178)

Получено точное решение. Однако, получить точное решение удается не всегда и требуется численное решение с использованием алгоритма метода штрафных функций [1].