Краткое введение в нелинейную оптимизацию с ограничениями и кусочно-линейными приближениями

Кусочно-линейные аппроксимации — это практичный способ обработки нелинейных моделей с ограничениями, использующих решатели LP/MIP, такие как Gurobi.

Делиться

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

Общая задача оптимизации с ограничениями состоит в выборе nn действительных переменных решения x0, x1, …, xn−1x_0, x_1,dots,x_{n-1} из заданной допустимой области таким образом, чтобы оптимизировать (минимизировать или максимизировать) заданную целевую функцию.

[f(x_0,x_1,dots,x_{n-1}).]

Обычно мы обозначаем xx вектором из nn действительных переменных решения x0, x1, …, xn−1.x_0, x_1, …, x_{n-1}. То есть, x=(x0, x1, …, xn−1)x=(x_0, x_1, …, x_{n-1}), и записываем общую нелинейную программу следующим образом:

[begin{aligned}text{ Максимизировать }&f(x)text{ При условии }&g_i(x)leq b_i&&qquad(i=0,1,dots,m-1)&xinmathbb{R}^nend{aligned}]

где каждая из функций ограничения g0g_0 до gm−1g_{m-1} задана, а каждый bib_i является константой (Брэдли и др., 1977).

Это лишь один из возможных способов сформулировать задачу. Минимизация f(x)f(x) эквивалентна максимизации −f(x)⋅-f(x). Аналогично, равенство h(x)=bh(x)=b можно выразить как пару неравенств h(x)≤bh(x)leq b и −h(x)≤−b⋅-h(x)leq-b. Более того, добавив дополнительную переменную, любое неравенство можно преобразовать в равенство (Bradley et al., 1977).

Подобные проблемы встречаются во многих областях применения, например, в бизнесе, где компания стремится максимизировать прибыль или минимизировать затраты, работая в условиях ограниченных ресурсов или финансирования (Черри, 2016).

Если f(x) — линейная функция, а ограничения — линейные, то задача называется задачей линейного программирования (ЛП) (Черри, 2016).

«Задача называется задачей нелинейного программирования (НЛП), если целевая функция нелинейна и/или допустимая область определяется нелинейными ограничениями» (Брэдли и др., 1977, с. 410).

Допущения и приближения, используемые в линейном программировании, иногда позволяют получить подходящую модель для интересующих диапазонов переменных решения. Однако в других случаях нелинейное поведение целевой функции и/или ограничений имеет важное значение для точной формулировки приложения в виде математической программы (Брэдли и др., 1977).

Нелинейное программирование относится к методам решения задач нелинейного программирования. Хотя существует множество зрелых программ для решения задач линейного программирования, задачи нелинейного программирования, особенно те, которые включают нелинейности более высокого порядка, как правило, сложнее решить (Cherry, 2016).

Сложные задачи нелинейного программирования возникают в таких областях, как проектирование электронных схем, оптимизация финансового портфеля, оптимизация газовых сетей и проектирование химических процессов (Черри, 2016).

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

Чтобы перейти от теории к работающей модели на Python, мы рассмотрим следующие разделы:

• Разделяемые функции
• Пример
• Комплекты типа 2, изготавливаемые по специальному заказу.
• О выпуклых и вогнутых функциях
• Реализация на Python
• Дополнительная литература
• Заключение
• Ссылки

Данный текст предполагает некоторое знакомство с математическим программированием. После определения разделяемых функций мы приводим пример разделяемой нелинейной максимизации и описываем подход, основанный на кусочно-линейных (PWL) аппроксимациях нелинейной целевой функции.

Далее мы определяем специальные упорядоченные множества типа 2 и объясняем, как они подтверждают численную формулировку.

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

В заключение мы представляем процедуру реализации на Python, которая использует аппроксимации нелинейной целевой функции с помощью Gurobipy и PWL, что позволяет решателям задач линейного программирования/целочисленного линейного программирования получать полезные аппроксимации для достаточно больших задач нелинейного программирования.

Источник: towardsdatascience.com