Задачи оптимизации при ограничениях в виде неравенств

Рассмотрим задачу поиска минимума функции

min f(x)

при условии

g_i(x) £ 0, i = 1,2, …, k, x Î Rⁿ.

Обозначим через D – область возможных значений аргументов функций g_i(x). Если g_i(x) = 0, то ограничение называется активным (насыщенным). Если g_i(x) < 0, то ограничение называется неактивным (ненасыщенным)

Рис. 4.1.

На рис. 4.1. отмечена точка x¹, в которой оба ограничения являются активными. В точке x² оба ограничения неактивные.

Предполагается, что в области D функции f(x) и g_i(x) непрерывны и дифференцируемы по своим аргументам.

Предположим, что множество активных ограничений g_i(x) = 0 равно m.

Для решения задачи оптимизации при ограничениях в виде неравенств, вводится функция Лагранжа вида

(4.1)

Необходимое условие экстремума можно записать в виде

(4.2)

(4.3)

(4.4)

При решении этих уравнений надо придерживаться следующих правил. Из уравнения (4.3) следует, что возможны два варианта: 1) если m_i = 0, то y_i ¹ 0; 2) если y_i = 0, то m_i ¹ 0.

Если m_i = 0, то функция Лагранжа равна f(x), решаем систему уравнений ¶f(x)/¶x_j = 0, j = 1,2, …, n. Из полученных решений выделяем те, которые принадлежать области D. Вычисляем значения функции при этих решениях и запоминаем их. В этом случае мы находим стационарные точки соответствующие неактивным ограничениям. Вычисляем вторые частные производные, составляем матрицу Гесса и по критерию Сильвестра определяем точки локального минимума. Запоминаем эти точки и значения функций в этих точках.

Если m_i ¹ 0, то согласно уравнению (4.3) y_i = 0, и функция Лагранжа имеет такой же вид, как при решении задачи условного экстремума. Решая совместно уравнения (4.2) и (4.3) при y_i =0, определяем условно стационарные точки x^*. Вычисляем матрицу вторых производных от функции Лагранжа, и определяем ее положительную определенность в этих точках при выполнении условия При выполнении этих условий в точке x^* имеем локальный минимум. Запоминаем локальные минимумы при активных ограничениях, т.е. во внутренних точках области D.

Сравнивая локальные минимумы внутри области D и на ее границе, выбирая среди них наименьшее значение, определяем минимум функции f(x) в области D.

Множители m_I в выражении (4.1) называются множителями Куна-Такера. При y_i равном нулю эти множители совпадают с множителями Лагранжа.

Приведенный метод дает последовательный алгоритм поиска экстремума при ограничениях в виде равенств и неравенств. Рассмотрим пример.

Пример.Надо определить минимум функции

f(x₁, x₂) = 3x₁² + 2x₂² - 3x₁+1,

при условиях:

Границы областей ограничений представлены на рис. 4.2. Условие g₁(x₁, x₂) = 0 определяет окружность с радиусом равным двум. При условии, что g₂(x₁, x₂) = 0, имеем прямую, проходящую через точки A и B. Условие g₃(x₁, x₂) = 0 определяет прямую, проходящую через точки A и C. Область D допустимых значений аргумента, в которой надо определить минимум функции, находится внутри границы, обозначенной на рис.4.2 через ABECA.

Рис. 4.2.

Составляем функцию Лагранжа

Вычисляем производные по всем аргументам и приравняем их нулю:

(4.5)

В результате получили восемь нелинейных уравнений с восемью неизвестными.

а) Приравняем нулю все множители Куна-Такера: m₁ = 0, m₂ = 0, m₃ = 0. В этом случае найдем точку безусловного экстремума и определим принадлежность ее области D.

Определяем частные производные

Вычисляем стационарную точку x⁰ = (0.5 0)^T и значение функции в этой точке f(0.5, 0) = 0.25. Эта точка принадлежит области D.

Если приравнять одновременно нулю y₁ = y₂ = y₃, и решать систему уравнений, то получим множество решений относительно переменных x₁, x₂, m₁, m₂, m₃ . Эти решения лежат на окружности или принадлежат отрезкам AB, AC Аналитически решить эту систему, применяя методы компьютерной алгебры [Mathcad MATLAB], не удается. Поэтому поступим следующим образом.

б) Положим m1 ¹0, m2 = m3 =0. Это означает, что ограничение g₁(x₁, x₂) является активным, а остальные два ограничения g₂(x₁, x₂), g₃(x₁, x₂) выполняются. В этом случае отыскиваем минимум на дуге BEC. Имеем

Решая эту систему из трех уравнений, получаем два решения: 1) x₁⁽¹⁾ = 1.5, x₂⁽¹⁾ = 1.323, m₁⁽¹⁾ = -2; 2) x₁⁽²⁾ = 1.5, x₂⁽²⁾ = -1.323, m₁⁽²⁾ = -2. Эти точки x⁽¹⁾ и x⁽²⁾ лежат на дуге BEC. Значение функции в этих точках f(1.5,1.323) = f(1.5, -1.323) = 6.75. Квадратичная форма от матрицы вторых производных и положительно определена. Значит в точках x⁽¹⁾ и x⁽²⁾ имеем относительный минимум. С другой стороны, функция f(x₁,x₂) является выпуклой в выпуклой области D, поэтому условия равенства нулю частных производных первого порядка являются достаточными для существования относительного минимума.

в) Ищем минимум функции на отрезке AB, где выполнено условие g₂(x₁, x₂) = 0. Для этого случая положим m2 ¹ 0, m1 = m3 =0. Записываем функцию Лагранжа и ее частные производные приравняем нулю:

Решая эту систему уравнений, найдем x₁⁽³⁾ = -0.1, x₂⁽³⁾ = 0.9, m₂ = -3.6. Точка x⁽³⁾ = (-1, 0.9) принадлежит отрезку AB. Из уравнения связи имеем, что x₁ = x₂. Квадратичная форма от матрицы вторых производных положительна. В точке x⁽³⁾ = (-0.1, 0.9) имеем локальный минимум искомой функции равный f(-0.1, 0.9) = 2.95.

г) Определим минимум функции на отрезке AC, где g₃(x₁, x₂) = 0. Для этого случая положим m3 ¹ 0, m1 = m2 =0. Записываем функцию Лагранжа, и ее частные производные приравняем нулю:

Решая эту систему уравнений, найдем x₁ = -0.1, x₂ = -0.9, m₂ = -3.6. Точка с координатами (-1, -0.9) принадлежит отрезку AС. Из уравнения связи имеем, что x₁ = -x₂. Квадратичная форма от матрицы вторых производных положительна, и в точке с координатами x⁽⁴⁾ = (-0.1, -0.9) имеем локальный минимум искомой функции на отрезке AC равный f(-0.1, -0.9) = 2.95.

В результате нашли четыре точки локального экстремума, принадлежащих области D. Среди них в точке x⁽⁰⁾ = (0.5, 0) исследуемая функция имеет наименьшее значение f(0.5, 0) = 0.25.

На данном примере рассмотрели процедуру решения задачи оптимизации при ограничениях в виде неравенств. Эта задача сложнее, чем задача поиска безусловного и условного экстремумов.

В заключении отметим, что задача поиска экстремума сводится к решению нелинейных систем уравнений. Найти аналитическое решение систем уравнений возможно только в некоторых частных случаях. Разработаны различные способы приближенного решения таких уравнений. Применение этих способов сводится к тому, что задаются точка начального приближения x^* = (x₁^*,x₂^*, …, x_n^*). Далее строится некоторая последовательность точек {x^k}. При условии, что эта последовательность сходится к решению систем уравнений, можно найти искомое решение. Условие сходимости зависит от используемого способа численного решения, от свойств целевой функции и от начального приближения, которое задается лицом, решающим систему уравнений. Универсальной методики задания начального приближения, обеспечивающего сходимость решения, не существует. В каждом случае надо использовать различные способы анализа: свойства выпуклости целевой функции, пределы изменения ее частных производных, линейность некоторых уравнений системы и т.д.