В задаче условной оптимизации целью является найти наилучшее (максимальное или минимальное) значение целевой функции путём выбора действительных переменных, которые удовлетворяют набору ограничений равенства и неравенства.
Общая задача условной оптимизации состоит в выборе n действительных переменных решения x₀, x₁, …, xₙ₋₁ из заданной допустимой области таким образом, чтобы оптимизировать (минимизировать или максимизировать) заданную целевую функцию f(x₀, x₁, …, xₙ₋₁).
Обычно мы обозначаем через x вектор n действительных переменных решения x₀, x₁, …, xₙ₋₁. То есть x = (x₀, x₁, …, xₙ₋₁) и записываем общую нелинейную программу как:
Максимизировать f(x)
При условии gᵢ(x) ≤ bᵢ, x ∈ ℝⁿ (i = 0, 1, …, m-1)
где каждая из функций ограничения g₀ через gₘ₋₁ задана, и каждое bᵢ — константа (Bradley et al., 1977).
Это только один из возможных способов записи задачи. Минимизация f(x) эквивалентна максимизации −f(x). Аналогично, ограничение равенства h(x) = b можно выразить как пару неравенств h(x) ≤ b и −h(x) ≤ −b. Кроме того, добавляя дополнительную переменную, любое неравенство можно преобразовать в ограничение равенства (Bradley et al., 1977).
Такие типы задач появляются в разных областях применения, например, в бизнесе, где компания стремится максимизировать прибыль или минимизировать затраты при работе с ограничениями по ресурсам или финансированию (Cherry, 2016).
Если f(x) является линейной функцией и ограничения линейны, то задача называется задачей линейного программирования (LP) (Cherry, 2016).
«Задача называется задачей нелинейного программирования (NLP), если целевая функция нелинейна и/или допустимая область определена нелинейными ограничениями». (Bradley et al., 1977, p. 410)
Предположения и аппроксимации, используемые в линейном программировании, иногда могут дать подходящую модель для интересующего диапазона переменных решения. Однако в других случаях нелинейное поведение целевой функции и/или ограничений необходимо для точного формулирования приложения как математической программы (Bradley et al., 1977).
Нелинейное программирование относится к методам решения NLP. Хотя существует много зрелых решателей для LP, NLP, особенно те, которые включают нелинейности высшего порядка, обычно сложнее решать (Cherry, 2016).
Сложные задачи нелинейного программирования возникают в таких областях, как проектирование электронных схем, оптимизация финансовых портфелей, оптимизация газовых сетей и проектирование химических процессов (Cherry, 2016).
Один из способов решения задач нелинейного программирования — это их линеаризация и использование решателя LP для получения хорошей аппроксимации. Это желательно по нескольким причинам. Например, линейные модели обычно решаются быстрее и могут быть более численно устойчивы.
Чтобы перейти от теории к работающей модели на Python, мы рассмотрим следующие разделы:
- Отделяемые функции
- Пример
- Специальные упорядоченные наборы типа 2
- О выпуклых и вогнутых функциях
- Реализация на Python
- Дополнительное чтение
- Заключение
- Ссылки
Этот текст предполагает некоторое знакомство с математическим программированием. После определения отделяемых функций мы представляем пример задачи отделяемого нелинейного максимизирования и описываем подход, основанный на кусочно-линейных (PWL) аппроксимациях нелинейной целевой функции.
Далее мы определяем специальные упорядоченные наборы типа 2 и объясняем, как они поддерживают числовую формулировку.
Затем мы вводим теоретическую базу, предоставляя инструменты, используемые на протяжении этой работы по нелинейному программированию (NLP).
Наконец, мы представляем процедуру реализации на Python, которая использует Gurobipy и PWL аппроксимации нелинейной целевой функции, позволяя решателям LP/MIP получать полезные аппроксимации для довольно больших NLP.
Отделяемые функции
Процедура решения в этой статье предназначена для отделяемых программ. Отделяемые программы — это задачи оптимизации вида:
Максимизировать ∑ⱼ₌₀ⁿ⁻¹ fⱼ(xⱼ)
При условии ∑ⱼ₌₀ⁿ⁻¹ gᵢⱼ(xⱼ) ≤ 0 (i = 0, 1, …, m-1)
x ∈ ℝⁿ
где каждая из функций fⱼ и gᵢⱼ известна. Эти задачи называются отделяемыми, потому что переменные решения отделены: по одной в каждой функции ограничения gᵢⱼ и по одной в каждой целевой функции fⱼ (Bradley et al., 1977).
Пример
Рассмотрим следующую задачу из Bradley et al. (1977), которая возникает при выборе портфеля:
Максимизировать f(x) = 20x₀ + 16x₁ − 2x₀² − x₁² − (x₀ + x₁)²
При условии x₀ + x₁ ≤ 5
x₀ ≥ 0, x₁ ≥ 0
В таком виде задача не является отделяемой из-за члена (x₀ + x₁)² в целевой функции. Однако неотделяемые задачи часто можно привести к отделяемому виду, используя различные формулировочные приёмы. В частности, обозначив x₂ = x₀ + x₁, мы можем переформулировать задачу выше в отделяемый вид:
Максимизировать f(x) = 20x₀ + 16x₁ − 2x₀² − x₁² − x₂²
При условии x₀ + x₁ ≤ 5
x₀ + x₁ − x₂ = 0
x₀ ≥ 0, x₁ ≥ 0, x₂ ≥ 0
Ясно, что линейные ограничения отделяемы, и целевую функцию теперь можно записать как f(x) = f₀(x₀) + f₁(x₁) + f₂(x₂), где
f₀(x₀) = 20x₀ − 2x₀²
f₁(x₁) = 16x₁ − x₁²
и
f₂(x₂) = −x₂²
Для формирования аппроксимационной задачи, мы аппроксимируем каждый нелинейный член fⱼ(xⱼ) кусочно-линейной функцией f̂ⱼ(xⱼ), используя указанное количество точек разрыва.
Каждая PWL функция f̂ⱼ(xⱼ) определена на интервале [l, u] и состоит из отрезков прямых, конечные точки которых лежат на нелинейной функции fⱼ(xⱼ), начиная с (l, fⱼ(l)) и заканчивая (u, fⱼ(u)). Мы представляем PWL функции, используя следующую параметризацию. Любое l ≤ xⱼ ≤ u можно записать как:
xⱼ = ∑ᵢ₌₀ʳ⁻¹ θᵢⱼ aᵢ
f̂ⱼ(xⱼ) = ∑ᵢ₌₀ʳ⁻¹ θᵢⱼ fⱼ(aᵢ)
∑ᵢ₌₀ʳ⁻¹ θᵢⱼ = 1
θⱼ = (θ₀ⱼ, θ₁ⱼ, …θᵣ₋₁ⱼ) ∈ ℝʳ₊ ≥ 0
для каждого j = 0, 1, 2, где PWL функции задаются точками {(aᵢ, fⱼ(aᵢ))} для i = 0, 1, …, r-1 (Cherry, 2016).