Анализ методов определения минимального, максимального значения функции при наличии ограничений (стр. 4 из 7)

Описанные методы относятся к разряду двойственных методов, поскольку в итерационном процессе участвуют как прямые (x), так и двойственные (l) переменные.

Можно строить также прямые методы решения условных задач. Например, реализовать идею о том, что следующее приближение градиентного метода. Приближение xⁿ⁺¹ ищется как минимум функции x ® (f ¢₀(xⁿ),x  xⁿ) + a||x  xⁿ||² на касательной гиперплоскости W¢_xn. Здесь "штрафной член" ||x  xⁿ||² позволяет "минимизировать" линейную функцию x ® (f ¢₀(xⁿ),x  xⁿ). Таким образом, мы приходим к прямому методу

xⁿ⁺¹ = argmin[(f¢₀(xⁿ),x  xⁿ) + a||x  xⁿ||²], (3.4)

f_i(xⁿ) + (f ¢_i(xⁿ),x xⁿ) = 0, i = 1, ..., k. (3.5)

Ограничения (3.5) в этом методе — это, очевидно, линеаризации ограничений (3.2) в точке xⁿ: минимум ищется на касательной гиперплоскости W¢_xn.

Один из распространенных методов решения задач с ограничениями, с которым мы еще столкнемся — так называемый метод штрафов. Он позволяет сводить задачу с ограничениями к задаче без ограничений и суть его заключается в наказании за невыполнение ограничений. Именно, вместо минимизации функции f₀ с ограничениями (3.2) минимизируется функция f^s(x) = f₀(x) + s||f(x)||² без ограничений, в которой s — положительный параметр.

Теперь рассмотрим постановку задач с ограничениями типа неравенств g_j(x) £ 0, j = 1, ..., l (3.6).

Рис. 3.2.

Определяются допустимые точки, локальный и глобальный, строгий и нестрогий минимумы. Так же мы будем использовать обозначения f и g для функций из R^m в R^k и R^l, соответственно, определяемые координатами f_i и g_j. Поэтому задачу (3.1)- (3.3), (3.6) можно записывать в виде

f(x) = Q, g(x) £ Q.

(напомним, что неравенство g(x) £ Q означает покоординатные неравенства).

f₀(x) ® min, f(x) = Q, g(x) £ Q.

Через J(x) будет обозначаться множество индексов так называемых активных ограничений: J(x) = {j Î {1, ..., l}: g_j(x) = 0} — это номера ограничений, которые в данной точке существенны.

Теорема (обобщенное правило множителей Лагранжа)

Пусть f₀, f, g Î C¹, а x* — локальное решение задачи f₀(x) ® min, f(x) = Q, g(x) £Q. Тогда найдутся такиеl*₀Î R, l* Î R^k, m* Î R^l, не равные одновременно нулю, такие, что m*_j³ 0 при j Î J(x*) и

l*₀f¢₀(x*)+

l*_if¢_i(x*)+

m*_jg¢_j(x*) = Q. (3.7)

Регулярный случай

Так же, как и в случае ограничений-равенств, в случае общей задачи нелинейной оптимизации, необходимый признак, информативен только в случае, если l*₀¹ 0. В этой ситуации можно разделить (3.7) на l*₀ и, следовательно, считать его равным единице. Это позволяет ввести функцию Лагранжа L: R^m×R^k×R^k® R (в регулярном случае) равенством

(x, l, m) = f₀(x) + (l, f(x)) + (m, g(x)).

Условие регулярности в случае общей задачи выглядит сложнее. Именно, допустимая точка x называется регулярной, если векторы f ¢₁(x),..., f ¢_k(x) линейно независимы и для некоторого ненулевого вектора

hÎR^m (f¢_i(x),h) = 0 при i = 1, ..., kи (g¢_j(x),h) < 0 при jÎJ(x).

Геометрически, эти условия означают, что, во-первых, вектор h является касательным к многообразию, выделяемому ограничениями-равенствами (т. е. ортогонален всем градиентам f ¢_i(x)), и, во-вторых, он образует с градиентами g¢_j(x) активных ограничений (указывающими, очевидно, вовне множества W) тупой угол.

Рис. 3.3.

Методы возможных направлений

Эти методы основываются на следующем простом понятии. Вектор (направление) z в допустимой точке x назовем возможным для задачи (3.1), (3.3), если малое перемещение в этом направлении уменьшает значение функции f₀ и не выводит из множества допустимых точек, т. е. если при достаточно малых s точка x^s = x + sz допустима и f(x^s) < f(x). Если теперь на каждом шаге сдвигаться в возможном направлении на достаточно малое расстояние, то мы очевидно получим релаксационную последовательность, которая во многих случаях будет сходиться к решению задачи. Методы этого типа называются методами возможных направлений.

Методы проекции градиента

Проекцией P_Wx точки x Î R^m на множествоW Ì R^m называется любая ближайшая к x точка множества W:

||x  P_Wx|| £ ||x  y|| при всех y Î W.

В тех случаях, когда проекцию точки на множество допустимых точек задачи (3.1), (3.3) найти достаточно легко (например, когда  — линейное подпространство, полупространство, шар, R^m и т. д.) используют метод проекции градиента:

xⁿ⁺¹ = P_W(xⁿ  aⁿf¢₀(xⁿ))

(см. рис. 3.4), являющийся прямым обобщением градиентного метода.

Рис. 3.4.

Можно доказать, например, что если функция f₀Î C¹ сильно выпукла и f ¢ удовлетворяет условию Липшица, а множество W замкнуто и ограничено, то метод проекции градиента сходится со скоростью геометрической прогрессии.

Методы линеаризации

Суть этих методов, как следует из названия, состоит в линеаризации минимизируемой функции и ограничений в очередной точке xⁿ строящейся релаксационной последовательности и объявлении следующим значением xⁿ⁺¹ решения получающейся линейной задачи, т. е. задачи

(f ¢₀(xⁿ),x  xⁿ) ® min, (3.8)

g_i(xⁿ) + (g¢_i(xⁿ),x  xⁿ) £ 0, i = 1, ..., l. (3.9)

Чтобы эта (линейная) задача была разрешима либо добавляют штраф в минимизируемую функцию, заменяя (3.8), например, задачей

(f¢₀(xⁿ), x xⁿ) + d||x  xⁿ||²®min,

либо добавляя к (3.9) простые ограничения, которые делают множество допустимых точек этой задачи ограниченным, например, (линейные) ограничения

x_i  xⁿ_i aⁿ£ 0, x_i + xⁿ_i aⁿ£ 0 (i = 1, ..., m).

Методы штрафов

Основная идея здесь заключается в переходе от задачи (3.1), (3.3) к задаче безусловной оптимизации, в которой "наказывается" либо удаление от множества W допустимых точек (внешний штраф), либо приближение изнутри множества W к его границе (внутренний штраф). Различают методы внешних штрафов и внутренних штрафов. При методе внешних штрафов задачу решают тем или иным методом решения безусловных задач, увеличивая на каждом шаге штраф s. Как и в случае задач с ограничениями-равенствами, основным недостатком метода штрафов является рост числа обусловленности s. На несколько другой идее основываются так называемые методы внутренних штрафов или барьеров. Образно его можно описать так: у границы множества W возводятся барьеры, не позволяющие приближаться к его границе.

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

Симплекс - метод

Симплекс-метод – один из наиболее эффективных методов численного решения задач ЛП. Суть понятия "симплекс" заключается в следующем. Для тела в k-мерном пространстве симплексом называется множество, состоящее из k+1 вершин этого тела. Так, при k = 2, т.е. на плоскости, симплексом будут вершины треугольника; при k = 3 симплексом являются вершины четырехгранника, например тетраэдра, и т.д. Такое название методу дано по той причине, что в его основе лежит последовательный перебор вершин ОДЗП с целью определения координат той вершины, в которой функция цели имеет экстремальное значение.

Решение задачи с помощью симплекс-метода разбивается на два основных этапа. На первом этапе находят одно из решений, удовлетворяющее системе ограничений. Системы, в которых переменных больше, чем ограничений N > m, называются неопределенными. Они приводятся к определенным системам (N = m) путем приравнивания к нулю N-m каких-либо переменных.

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

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

В системе из m уравнений с N неизвестными общее число базисных решений при N > m определяется числом сочетаний

Базисное решение, в котором все xi ≥ 0, i = [1,m], называется допустимым базисным решением. Таким образом, первый этап завершается нахождением допустимого базисного решения, хотя бы и неудачного.

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