Как решать простые задачи оптимизации на питоне с помощью cvxpy

Всем доброго времени суток! Простым поиском я не сумел обнаружить упоминание модуля cvxpy и потому решил написать обучающий материал по нему – просто примеры кода, по которым в дальнейшем новичку будет проще использовать этот модуль для своих задач. cvxpy предназначен для решения задач оптимизации – нахождения минимумов/максимумов функций при определённых ограничениях. Если вам интересна эта тема – прошу под кат.

Общая постановка задачи

Здесь x – независимая переменная (в общем случае вектор), f(x)
целевая функция, которую нужно оптимизировать. Ограничения на область определения f(x) могут быть заданы при помощи равенств и неравенств.

Пример задачи

Давайте рассмотрим следующую задачу линейного программирования ^[1]:

Если посмотреть на область, заданную неравенством с модулем, то можно увидеть что эта область легко может быть задана при помощи линейных неравенств:

В нашем случае ограничения будут следующими:

Решение задачи посредством cvxpy

О установке модуля подробно рассказано на сайте модуля ^[2]. Давайте напишем простой код, который позволит нам решить нашу тестовую задачу оптимизации:

import numpy as np
import cvxpy as cvx

# наши независимые переменные
x = cvx.Variable(2)

A = np.array([[1, 1], 
              [1, -1], 
              [-1, 1], 
              [-1, -1]])

b = np.array([8, 2, 12, 6])

c = np.array([7, -3])

# ограничения
constraints = [A * x <= b]

# целевая функция и что с ней делать
obj = cvx.Minimize(c * x)

# формулируем задачу и решаем
prob = cvx.Problem(obj, constraints)
prob.solve()

print(prob.status) # optimal
print(prob.value) # -71.999999805
print(x.value) # [[-8.99999997] [ 3.00000002]]

Наше текущее решение нецелое и выходит за ограничения, однако видно что оно лежит рядом с оптимальным решением (-9, 3). В cvxpy можно использовать разные решатели для решения задачи, подбирая лучший. Давайте попробуем GLPK:

prob.solve(solver = "GLPK")
print(prob.status) # optimal
print(prob.value) # -72.0
print(x.value) # [[-9.] [ 3.]]

Список доступных решателей возвращает функция installed_solvers().

Другие примеры

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

# ограничения
constraints = [cvx.abs(x[0] + 2) + cvx.abs(x[1] - 3) <= 7]

# целевая функция и что с ней делать
obj = cvx.Minimize(c * x)

# формулируем задачу и решаем
prob = cvx.Problem(obj, constraints)
prob.solve(solver = "GLPK")

print(prob.status) # optimal
print(prob.value) # -72.0
print(x.value) # [[-9.] [ 3.]]

Также можно искать решение для метода наименьших квадратов ^[3]:

# целевая функция и что с ней делать
obj = cvx.Minimize(cvx.norm(A * x - b)) # по умолчанию используется вторая норма

# формулируем задачу и решаем
prob = cvx.Problem(obj)
prob.solve()

print(prob.status) # optimal
print(prob.value) # 13.9999999869
print(x.value) # [[-2.] [ 3.]]

Конечно, некоторые задачи могут иметь тривиальное решение:

A = np.array([[1, 1], 
              [1, -1], 
              [-1, 1]])

b = np.array([8, 2, 12])

c = np.array([7, -3])

# ограничения
constraints = [A * x <= b]

# целевая функция и что с ней делать
obj = cvx.Minimize(c * x)

# формулируем задачу и решаем
prob = cvx.Problem(obj, constraints)
prob.solve()

print(prob.status) # unbounded
print(prob.value) # -inf
print(x.value) # None

А некоторые могут не иметь решения вовсе:

A = np.array([[1, 1], 
              [1, -1], 
              [-1, 1], 
              [-1, -1]])

b = np.array([-6, -12, -2, -8])

# ограничения
constraints = [A * x <= b]

# целевая функция и что с ней делать
obj = cvx.Minimize(c * x)

# формулируем задачу и решаем
prob = cvx.Problem(obj, constraints)
prob.solve()

print(prob.status) # infeasible
print(prob.value) # inf
print(x.value) # None

Вот и всё. Можно узнать больше на сайте модуля ^[4].

Автор: AC130

Источник ^[5]