Hello,

I’m trying to solve an optimization problem, but sometimes (it depends on the setup), even if the problem is ‘Solved’, the constraints are violated (of a non-negligible value for my purpose).

The constraint is not ignored: The results give very small number for the variable with constraint == 0.

Do you know what can be the possible reason for it?

The problem I am trying to solve is where \mathcal{E} is the set where a matrix A has zero entries.

A = np.array([[1,1,0,1,1],[1,1,1,0,1],[0,1,1,1,1],[1,0,1,1,1],[1,1,1,1,1]])

L = np.array([4,5,7,6,11])

n = A.shape[0]

P = np.zeros((n,n))

sumL = (A - np.identity(n)).dot(L)

pi = L/np.sum(L)

pi_sqrt = np.sqrt(pi)

Q = np.outer(pi_sqrt, pi_sqrt.T)

PI_sqrt = np.diag(pi_sqrt)

PI_sqrt_inv = np.diag(1/pi_sqrt)

X = cp.Variable((n,n), symmetric=False)

s = cp.Variable()

one = np.ones(n)

iden = np.identity(n)

zero_index = []

for i in range(n):

for j in range(n):

if A[i,j] == 0:

zero_index.append([i,j])

zero_indeces = tuple(zip(*zero_index))
zero_values = np.zeros(len(zero_index))
constraints = [cp.vec(X) >= 0]
constraints += [PI_sqrt@X@PI_sqrt_inv - Q + s*iden >> 0]

constraints += [0 >> PI_sqrt@X@PI_sqrt_inv - Q - s*iden]

constraints += [X@one == one]

constraints += [PI_sqrt@X == X.T@PI_sqrt]

constraints += [X[zero_indeces] == 0]

prob = cp.Problem(cp.Minimize(s), constraints)

prob.solve(solver = cp.SCS)

P = X.value

And the outcome gives:

optimal

0.23075128629982344

[[ 2.00945263e-01 2.24474692e-01 -1.60803788e-11 2.43695617e-01

3.30884428e-01]

[ 2.00776268e-01 2.22688940e-01 2.59026263e-01 -1.86612685e-11

3.17508528e-01]

[-1.73584394e-11 2.18917148e-01 2.50375526e-01 2.35000873e-01

2.95706452e-01]

[ 1.98976638e-01 -1.72719877e-11 2.53829954e-01 2.37736614e-01

3.09456795e-01]

[ 1.99530818e-01 2.14064206e-01 2.35892144e-01 2.28548990e-01

1.21963842e-01]]