CVXPY finds no solution (unbounded) to a problem that definitely has a solution - how to debug

141 Views Asked by At

I encountered the following special case where CVXPY was returning a None solution, with status unbounded, for a problem that definitely has a solution.

It doesn't seem like I can enter LaTeX, so @ signifies matrix multiplication, .T means transpose, small letters are column vectors and caps letters are matrices. I'm looking to solve a minimization (or also argmin) problem of the form:

min_w ( w.T @ A @ w + 2 w.T @ b )

If A is symmetric positive definite, this should have a solution. If A symmetric we can complete the square and reformulate this as

min_w ( (U.T @ w + c).T @ (U.T @ w + c) - c.T @ c )

with c = U^(-1) @ b, and A = U @ U.T, where U is the eigenvector matrix multiplied by the diagonal matrix containing the square roots of the eigenvalues. We can calculate c and U if A is symmetric PD.

However, in the following example, I have a symmetric positive definite A, and yet CVXPY fails to find a solution

import numpy as np
import cvxpy as cp

A = np.array([
    [4.06361264e-05, 4.78152602e-05, 3.58988931e-05, 3.45978540e-05, 4.56347190e-05, 3.30402841e-05],
    [4.78152602e-05, 6.20243040e-05, 4.44641914e-05, 4.39168274e-05, 5.87695986e-05, 4.13444571e-05],
    [3.58988931e-05, 4.44641914e-05, 5.11820897e-05, 3.16788337e-05, 4.22214735e-05, 3.07681460e-05],
    [3.45978540e-05, 4.39168274e-05, 3.16788337e-05, 3.43880152e-05, 4.18058439e-05, 3.05503889e-05],
    [4.56347190e-05, 5.87695986e-05, 4.22214735e-05, 4.18058439e-05, 5.68791131e-05, 3.93696860e-05],
    [3.30402841e-05, 4.13444571e-05, 3.07681460e-05, 3.05503889e-05, 3.93696860e-05, 3.06327553e-05]
])

K = np.array([
    [4.37566619e-05, 2.69688463e-05, 4.38180809e-05],
    [5.45281929e-05, 3.46869714e-05, 5.63081373e-05],
    [4.43561108e-05, 2.42773248e-05, 4.05177865e-05],
    [3.92084931e-05, 2.55688144e-05, 3.98470925e-05],
    [5.20176190e-05, 3.29607102e-05, 5.30698420e-05],
    [3.72710707e-05, 2.41940081e-05, 3.80516226e-05]
])
h = np.array([ 5151.2868695 ,  1970.57848573, 10322.36834168])
b = K @ h

w = cp.Variable(len(A))
objective_1 = cp.Minimize(w @ A @ w + 2 * w @ b)
constraints = [True]
prob = cp.Problem(objective_1, constraints)
prob.solve()
solution = w.value

print(f"Solution: {solution}, status: {prob.status}")
Solution: None, status: unbounded

The condition number of A isn't particularly bad,

My questions:

  • What could be the cause of issues like this? Some sort of floating point arithmetic problem?
  • I'm not very experienced with CVXPY and quadratic programming, but how would you go about debugging a case where a solver can't find a solution when it should have one?
  • Last alternative: was I maybe wrong and am I missing a reason why this optimization problem really doesn't have a solution?

Also, I'm not looking for the solution, it can be calculated analytically. But I'm just trying to under see what aspect of cvxpy and optimization I'm misunderstanding here.

This is not a duplicate - other questions are also asking why they get an unbounded solution but not with this optimization problem.

0

There are 0 best solutions below