inverse barrier method - DCPError: Problem does not follow DCP rules.

[burak akdemir]

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

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 - 2*x2 - mu*cp.log(-1*(x2**2 - x1 - 1)) - mu*cp.log(-1*(-x2)) )

obj = cp.Minimize(f - mu*cp.log(-g1) - mu*cp.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 - mu*cp.inv_pos(g1) - mu*cp.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

- How can this problem be solved using the inverse barrier method?

7 - appendix

Inverse barrier method : 

5.7interiorpenalty.pdf (stanford.edu) 

log barrier method : 

15-barr-method-scribed.pdf (cmu.edu)