Mixed-integer optimization is not DCP

MIDCP
1

Hi everyone. I am trying to solve a financial mixed-integer programming optimization problem using the ‘SCIP’ solver.

The problem I am trying to solve is set in the following manner:
w = cp.Variable(5) # asset weights of the portfolio (5 assets in this example). This is the solution of our optimization.
k = cp.Variable() # Relaxation variable (not sure yet why cvx problem is infeasable with this variable, but it works when we use it)

mu is an the expected_return vector

sigma is the covariance matrix

objective = cp.Minimize(cp.quad_form(w, sigma))

constraints = [
(mu - 0.02).T @ w == 1,
cp.sum(w) == k,
k >= 0,
]

cp.Problem(objective, constraints).solve()

The problem shown above works. but when we do this:

v = cp.Variable(5, boolean=True) # Binary variable vector indicating if we are going to invest or not in the asset

For each asset “i” we add the contraints:

w[i] >= 0.3 * v[i], # Vector switching variables
w[i] <= v[i]

Then cvx says the it can’t solve because the problem does not follow DCP rules…

I agree that it’s not convex, but how can I rearrange the constraints and/or objective so that I have the same problem in a DCP format?

2

This forum addresses CVX. Your question pertains to CVXPY, which is a different tool. Please seek help in a CVXPY venue.

3

Hi Mark. Actually I was trying to understand how I can turn these non-convex constraints into a convex one. I know I’m using CVXPY, but CVX has the same problem of not accepting non-DCP constraints even in mixed-integer programming

4

if you want help on this forum, then I suggest you show MATLAB/CVX code, or at least a clear mathematical statement of your problem, not Python/CVXPY code which not all forum readers may understand.

5

On the face of it there is nothing here that could make the problem non-dcp after you added these new constraints - it looks like a mixed-integer DCP. So there is probably something else you are doing or not showing us. Or your sigma is not always PSD. Only reproducible code could help.