Dear all;
Following parts of the post is organized as :
0 - problem definition
1 - solution using constrained method
2 - solution using log barrier method
3 - attempt to solve using inverse barrier method
4 - things that I have tried
5 - things that I have deduced
6 - my ultimate question
7 - appendix
0 - Problem definition
I have an optimization problem that I can solve using constrained method and log barrier method. However I need to solve it using the inverse barrier method. To be more specific,
I am trying to optimize :
f = x1 - 2*x2
with following constraints:
x2**2 - x1 - 1 <= 0
-x2 <= 0
1 - Using constrained method I can solve it:
x1 = cp.Variable(1)
x2 = cp.Variable(1)
g1 = (x2**2 - x1 - 1)
g2 = (-x2)
f = x1 - 2*x2
obj = cp.Minimize(f)
constraints = [g1 <= 0] +
[g2 <= 0]
problem = cp.Problem(obj, constraints)
print(problem.solve())
print("x1 value : ", x1.value)
print("x2 value : ", x2.value)
result is
-1.9999999998524243
x1 value : [2.35228084e-05]
x2 value : [1.00001176]
2 - Using log barrier method I can solve it:
x1 = cp.Variable(1)
x2 = cp.Variable(1)
g1 = (x2**2 - x1 - 1)
g2 = (-x2)
f = x1 - 2*x2
obj = cp.Minimize(f)
mu = 0.000001
#obj = cp.Minimize(x1 - 2x2 - mucp.log(-1*(x2**2 - x1 - 1)) - mucp.log(-1(-x2)) )
obj = cp.Minimize(f - mucp.log(-g1) - mucp.log(-g2) )
problem = cp.Problem(obj)
print(problem.solve())
print("x1 value : ", x1.value)
print("x2 value : ", x2.value)
result is
-1.9999851857553026
x1 value : [1.81318945e-06]
x2 value : [1.00000041]
3 - Inverse barrier method I get the DCP ERROR:
x1 = cp.Variable(1)
x2 = cp.Variable(1)
g1 = (x2**2 - x1 - 1)
g2 = (-x2)
f = x1 - 2*x2
obj = cp.Minimize(f)
mu = 0.000001
obj = cp.Minimize(f - mu/g1 - mu/g2)
problem = cp.Problem(obj)
print(problem.solve())
However, when I ran the code above, it gives me the following error:
DCPError: Problem does not follow DCP rules. Specifically:
The objective is not DCP. Its following subexpressions are not:
1e-06 / (power(var82, 2.0) + -var81 + -1.0)
1e-06 / -var82
4 - things that I have tried
I know that
- (f).curvature is ‘AFFINE’
- (mu/g1).curvature is ‘QUASICONCAVE’
- (mu/g2).curvature is ‘QUASILINEAR’
- (f - mu/g1 - mu/g2).curvature is ‘UNKNOWN’
so I tried to solve using obj = cp.Minimize(f - mucp.inv_pos(g1) - mucp.inv_pos(g2))
but since
- (mu*cp.inv_pos(g2)).curvature is ‘CONVEX’
- (mu*cp.inv_pos(g1)).curvature is ‘QUASICONCAVE’
I get the same error
I have also tried using problem.solve(qcp=True)
but I get the following error DQCPError: The problem is not DQCP.
I have already seen The DCP ruleset — CVX Users’ Guide (cvxr.com) which basically states that implementing the same expression using different functions may change the DCP status. but no matter what, I cannot end up with DCP problem.
I have already seen python - Constraints do not follow DCP rules in CVXPY - Stack Overflow but it did not help since the problem given in the post can be solved by rewritng the utility function.
I have already seen DCPError(“Problem does not follow DCP rules. Specifically:\n” + append) raised when using SCS solver · Issue #863 · cvxgrp/cvxpy · GitHub but since I have no problem about log functions, this post is irrelevant.
I have already seen mathematical optimization - Problem does not follow DCP rules in CVXPY - Stack Overflow. This post states that multiplying two convex expressions is not possible. But this is not what I am trying to do. So this post is also irrelevant.
I have already seen python 3.x - Why is this CVXPY expression not DCP? - Stack Overflow . This post states that the problem should be reformulated. But since I am trying to solve the problem using the inverse barrier method, I cannot reformulate it.
I have already seen cvxpy - Convex optimization problem does not follow DCP rules - Stack Overflow which is about constraints. Since there is no constraints in inverse barrier method, this post is irrelevant too.
5 - things that I have deduced.
Both inverse barrier and logarithmic barrier methods, establish a rapidly increasing cost around the boundaries. (Constraints are implied using a high cost) So since the problem can be solved using log barrier method (refer to section 2 for a better understanding) , it should be solvable by using the inverse barrier method. Both methods work in a similar way.
Since expressing some functions in a different way (i.e. the following code is sqrt( x^2 + 1 ) interpreted as not DCP while the norm( [ x 1 ] ) is interpreted as DCP, The DCP ruleset — CVX Users’ Guide (cvxr.com)) changes the DCP status, rewriting the objective function may solve the problem.
6 - my ultimate question
(please see the code at the appendix)
- How can this problem be solved using the inverse barrier method?
- Should I rewrite the objective function so that it can be solved? If yes How can I rewrite the objective function?
- Should I apply the barrier method in a different way?
7 - appendix
code:
import cvxpy as cp
import numpy as np
import matplotlib.pyplot as plt
import math
#%% With constraints
x1 = cp.Variable(1)
x2 = cp.Variable(1)
g1 = (x2 ** 2 - x1 - 1)
g2 = (-x2)
f = x1 - 2x2
obj = cp.Minimize(f)
constraints = [g1 <= 0] +
[g2 <= 0]
problem = cp.Problem(obj, constraints)
print(problem.solve())
print("x1 value : ", x1.value)
print("x2 value : ", x2.value)
#%% with log barrier
x1 = cp.Variable(1)
x2 = cp.Variable(1)
g1 = (x2 ** 2 - x1 - 1)
g2 = (-x2)
f = x1 - 2x2
obj = cp.Minimize(f)
mu = 0.000001
#obj = cp.Minimize(x1 - 2x2 - mucp.log(-1*(x2 ** 2 - x1 - 1)) - mucp.log(-1(-x2)) )
obj = cp.Minimize(f - mucp.log(-g1) - mucp.log(-g2) )
problem = cp.Problem(obj)
print(problem.solve())
print("x1 value : ", x1.value)
print("x2 value : ", x2.value)
#%% inverse barrier
x1 = cp.Variable(1)
x2 = cp.Variable(1)
g1 = (x2 ** 2 - x1 - 1)
g2 = (-x2)
f = x1 - 2*x2
obj = cp.Minimize(f)
mu = 0.000001
obj = cp.Minimize(f - mucp.inv_pos(g1) - mucp.inv_pos(g2))
problem = cp.Problem(obj)
print(problem.solve(qcp=True))
w.value
Inverse barrier method :
5.7interiorpenalty.pdf (stanford.edu)
log barrier method :
15-barr-method-scribed.pdf (cmu.edu)