Почему решатель CVXPY нарушает это простое ограничение

Question

import cvxpy as cp
import numpy as np
x_1 = cp.Variable()
x_2 = cp.Variable()

objective = cp.Minimize(x_1)
constraints = [2*x_1 + x_2 >= 1, x_1+3*x_2>=1, x_1>=0, x_2>=0]
prob = cp.Problem(objective, constraints)

# The optimal objective value is returned by `prob.solve()`.
result = prob.solve()
# The optimal value for x is stored in `x.value`.
print(result)
print("x_1", x_1.value)
print("x_2", x_2.value)

Я указываю, что x_1 >= 0, однако решатель дал мне такой результат:

-9.944117370034156e-05
x_1 -9.944117370034156e-05
x_2 3.4085428032616

Где результат x_1 ниже 0

Answer 1

Большинство оптимизаторов допускают нарушение ваших ограничений вплоть до некоторого допуска. Это на самом деле сводится к тому, сколько нарушений ограничения вы готовы принять. В вашем случае это звучит так, как будто вы хотели бы, чтобы уровень нарушения был очень низким. Таким образом, вы можете изменить

result = prob.solve()

, что дает

-2.2491441767693296e-10
('x_1', array(-2.24914418e-10))
('x_2', array(1.5537159)

до

result = prob.solve(feastol=1e-24)

, что дает

1.139898310650857e-14
('x_1', array(1.13989831e-14))
('x_2', array(1.5537766))

По сравнению с результатом со значением по умолчанию feastol=1e-7, более низкое значение feastol вызывает удовлетворительные нарушения ограничений.