Як розв'язувати прості задачі оптимізації на пітоні з допомогою 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

От і все. Можна дізнатися більше на сайті модуля.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.