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

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

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



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

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


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



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


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


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


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

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.]]

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

# целевая функция и что с ней делать
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

Вот и всё. Можно узнать больше на сайте модуля.
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 5

    0
    Еще можно добавить, что cvxpy предназначен для решения именно задач выпуклой оптимизации, т.е. функции должны иметь вид
    image
    Примеры таких функций: экспонента, квадратичная. Представить задачу в выпуклой форме — та еще проблема.
      0

      Ничего представлять не надо — функция (и ограничения) либо выпукла (если выполняется неравенство), либо нет. И всё таки выпуклое программирование, если уж на то пошло.

        +1
        Вы не совсем правы. Зачастую функция бывает выпукла лишь в какой то области (как sin(x) например), и задавая ограничения минимизируемую функцию делают выпуклой на пространстве искомых значений.
          0
          Задача геометрического программирования в общем виде невыпукла. Но с помощью замены переменных и трансформации функций ее вполне можно превратить в выпуклую.
          И если уж на то пошло, то термины оптимизация и программирование в данном контексте вполне себе синонимы.
        0
        Кстати, по выпуклой оптимизации есть отличный курс от Стэнфорда и учебник по этой же теме.

        Only users with full accounts can post comments. Log in, please.