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 - 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**

(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 - 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)
#%% with log 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(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)

#%% 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 - mu*cp.inv_pos(g1) - mu*cp.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)