CVX Status:Infeasible. The solution result cannot satisfy the constraint

1

I would like to solve the following SDP problem：

function [rho,status] = closestDensityMatrix(rho0,observables,expectations,options,status)
dim = size(rho0,1);
cvx_begin sdp
variable rho(dim,dim) hermitian semidefinite
if options.initmethod == 1
minimize norm(rho0-rho)
elseif options.initmethod == 2
minimize -lambda_min(rho)
end
for i = 1:numel(observables)
abs(trace(observables{i}'*rho) - expectations(i)) <= options.linearconstrainttolerance
% linearconstrainttolerance = 1e-10
end
cvx_end

if options.verbose & (strcmp(cvx_status, 'Infeasible')) % | strcmp(cvx_status, 'Failed'))
    fprintf("**** Warning: step 1 solver exception, closestDensityMatrix status: %s ****\n",cvx_status);
end

status = [status, string(cvx_status)];

end

But under some parameters, CVX is not feasible.

MOSEK Version 9.1.9 (Build date: 2019-11-21 11:34:40)
Copyright (c) MOSEK ApS, Denmark. WWW: mosek.com
Platform: Windows/64-X86

Problem
Name :
Objective sense : min
Type : CONIC (conic optimization problem)
Constraints : 9919
Cones : 117
Scalar variables : 351
Matrix variables : 2
Integer variables : 0

Optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator started.
Freed constraints in eliminator : 0
Eliminator terminated.
Eliminator - tries : 1 time : 0.00
Lin. dep. - tries : 1 time : 0.01
Lin. dep. - number : 0
Presolve terminated. Time: 0.06
Problem
Name :
Objective sense : min
Type : CONIC (conic optimization problem)
Constraints : 9919
Cones : 117
Scalar variables : 351
Matrix variables : 2
Integer variables : 0

Optimizer - threads : 8
Optimizer - solved problem : the primal
Optimizer - Constraints : 9802
Optimizer - Cones : 117
Optimizer - Scalar variables : 234 conic : 234
Optimizer - Semi-definite variables: 2 scalarized : 39402
Factor - setup time : 3.27 dense det. time : 0.00
Factor - ML order time : 1.56 GP order time : 0.00
Factor - nonzeros before factor : 4.80e+07 after factor : 4.80e+07
Factor - dense dim. : 0 flops : 3.16e+11
ITE PFEAS DFEAS GFEAS PRSTATUS POBJ DOBJ MU TIME
0 2.0e+02 3.8e+00 1.0e+00 0.00e+00 1.170000000e-08 0.000000000e+00 1.0e+00 3.38
1 1.1e+02 2.0e+00 9.3e-02 4.84e+00 -8.230740271e-03 -3.492208504e-02 5.4e-01 8.02
2 3.8e+01 7.2e-01 1.4e-02 2.71e+00 -2.262145064e-02 -2.930680880e-02 1.9e-01 12.34
3 1.3e+01 2.5e-01 1.9e-03 1.71e+00 -8.421161043e-03 -1.058588838e-02 6.8e-02 16.73
4 4.2e+00 8.0e-02 2.6e-04 1.28e+00 -2.454062356e-03 -3.133128810e-03 2.1e-02 21.16
5 3.4e-01 6.6e-03 2.7e-06 1.04e+00 -2.316165693e-04 -2.952428154e-04 1.7e-03 25.42
6 2.8e-02 5.4e-04 6.2e-08 9.51e-01 -2.135148852e-05 -2.669453786e-05 1.4e-04 29.72
7 4.0e-03 7.6e-05 5.7e-09 6.76e-01 -1.227235844e-05 -1.332968593e-05 2.0e-05 34.28
8 5.7e-04 1.1e-05 4.3e-09 -7.52e-01 -4.007834455e-04 -4.032415263e-04 2.9e-06 38.39
9 7.2e-06 1.4e-07 2.3e-10 -7.76e-01 -7.895310877e-03 -7.857912502e-03 3.6e-08 43.23
10 9.5e-09 1.8e-10 9.2e-12 -9.99e-01 -7.510077020e+00 -7.473444310e+00 4.8e-11 47.66
11 3.5e-09 2.5e-16 7.1e-14 -1.00e+00 -1.152729383e+07 -1.147173104e+07 6.8e-17 52.16
12 1.8e-09 1.3e-16 6.4e-14 -1.00e+00 -2.305418156e+07 -2.294305795e+07 3.4e-17 57.09
13 9.1e-15 6.0e-19 1.8e-09 -1.00e+00 -2.777493560e+16 -2.764105746e+16 1.9e-26 61.83
14 2.8e-17 2.1e-18 2.6e-09 -1.00e+00 -2.522496690e-04 -2.510337994e-04 4.0e-33 66.22
Optimizer terminated. Time: 66.33

Interior-point solution summary
Problem status : DUAL_INFEASIBLE
Solution status : DUAL_INFEASIBLE_CER
Primal. obj: -2.5224966897e-04 nrm: 5e+00 Viol. con: 4e-15 var: 0e+00 barvar: 0e+00 cones: 0e+00
Optimizer summary
Optimizer - time: 66.33
Interior-point - iterations : 14 time: 66.22
Basis identification - time: 0.00
Primal - iterations : 0 time: 0.00
Dual - iterations : 0 time: 0.00
Clean primal - iterations : 0 time: 0.00
Clean dual - iterations : 0 time: 0.00
Simplex - time: 0.00
Primal simplex - iterations : 0 time: 0.00
Dual simplex - iterations : 0 time: 0.00
Mixed integer - relaxations: 0 time: 0.00

Status: Infeasible
Optimal value (cvx_optval): +Inf
If the answer is right, the Optimal value should be a very small negative number, for example -1.62167e-06. When I increase the linear constraint tolerance to 1e-3 or higher, CVX is feasible, but it does not meet the requirements at this time. I want to know how to make CVX feasible while ensuring constraint tolerance remains unchanged. Thank you very much！

2

You could make things clearer by stating which branch of objective function specification you are referring to (options.method value).

Aside from that, your problem is not reproducible, because the input data is not provided. Are you asking for something impossible, such as a constraint that a new car must be bought for less than $1e4, and the problem only becomes feasible when the $1e4 is increased to $2e4?

All but the first section of Debugging infeasible models - YALMIP also applies to CVX.

Also, you should also use the latest version of Mosek 10.x, rather than 9.1.9 which is bundled with CVX. In order to do so, follow the directions in

1 Like
3

Thank you for your answer. Below is the corresponding response：

  1. The objective function is “minimize -lambda_min(rho) ”
  2. I think it is feasible in principle.In principle, “trace(observables{i}'*rho)**=**expectations(i)” and the parameter “options.linearconstrainttolerance” is set considering computational accuracy. If “linearconstrainttolerance” is too big, it doesn’t meet the requirements of the equal sign anymore.
  3. Thank you for the reminder. I have replaced it with the latest version of Mosek. Unfortunately, the results are not improve。

I can be certain that this SDP is theoretically feasible. I think this is an accuracy issue with CVX, or is there any other parameter that can be optimized? What do you think may be the reason for this？I really don’t know how to correct it.

4

You haven’t provided a reproducible problem, so it is hard to give very specific advice.