Hello everyone,
When solving a problem with CVX, regardless of the chosen solver, I am getting the cvx_optval different from the value obtained with the evaluation of the objective function using the value assigned to the optimization variable.
For example, when maximizing F(x), the solver returns cvx_optval = 48.7069, but F(x) = 48.7090. Is it expected behaviour?
Thanks
Show us the complete reprodudible problem, with all solver and CVX output, and your calculation of optimal objective value.
Dear Mark,
It follows a small reproducible example:
F = @(q)sum(500*q - 30*log(2^q(1) + 2^q(2) + 2^q(3) + 1000)./log(2));
cvx_begin
cvx_solver sedumi
variable q(5);
maximize( F(q) );
subject to
2^q(1) + 2^q(2) + 2^q(3) <= 20;
2^q(4) + 2^q(5) <= 20;
-(q(1) - log(2^q(4) + 2^q(5))./log(2)) <= 0;
cvx_end
optval_gap = F(q) - cvx_optval
Status: Solved
Optimal value (cvx_optval): +4878.29
optval_gap =
1.1015e-04
In this example the gap is small, but for some instances of my original problem, it can be more than 5% difference.
The gap in this example is an order of magnitude smaller when using Mosek rather than Successive Approximation method.
Anyhow, the optimal objective value is 5e3, so the gap is fairly small on a percentage basis.
If you have an example with a much larger percent difference, please show it.
This is an output example:
MOSEK Version 9.1.9 (Build date: 2019-11-21 11:34:40)
Copyright © MOSEK ApS, Denmark. WWW: mosek.com
Platform: Windows/64-X86
Problem
Name :
Objective sense : min
Type : CONIC (conic optimization problem)
Constraints : 73
Cones : 69
Scalar variables : 212
Matrix variables : 0
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 started.
Freed constraints in eliminator : 0
Eliminator terminated.
Eliminator - tries : 2 time : 0.00
Lin. dep. - tries : 1 time : 0.00
Lin. dep. - number : 0
Presolve terminated. Time: 0.08
Problem
Name :
Objective sense : min
Type : CONIC (conic optimization problem)
Constraints : 73
Cones : 69
Scalar variables : 212
Matrix variables : 0
Integer variables : 0
Optimizer - threads : 6
Optimizer - solved problem : the primal
Optimizer - Constraints : 67
Optimizer - Cones : 69
Optimizer - Scalar variables : 212 conic : 207
Optimizer - Semi-definite variables: 0 scalarized : 0
Factor - setup time : 0.00 dense det. time : 0.00
Factor - ML order time : 0.00 GP order time : 0.00
Factor - nonzeros before factor : 273 after factor : 333
Factor - dense dim. : 0 flops : 4.84e+03
ITE PFEAS DFEAS GFEAS PRSTATUS POBJ DOBJ MU TIME
0 2.5e+07 1.9e+01 2.0e+08 0.00e+00 1.823558167e+02 -1.950038234e+08 1.0e+00 0.11
1 6.2e+06 4.6e+00 9.7e+07 -1.00e+00 8.060333180e+02 -1.950031699e+08 2.5e-01 0.27
2 7.2e+05 5.3e-01 3.3e+07 -1.00e+00 7.683943462e+03 -1.949959599e+08 2.9e-02 0.27
3 1.5e+05 1.1e-01 1.5e+07 -1.00e+00 3.820109973e+04 -1.949623903e+08 5.8e-03 0.28
4 9.4e+03 6.9e-03 3.8e+06 -1.00e+00 5.964454163e+05 -1.943402379e+08 3.7e-04 0.28
5 2.6e+02 1.9e-04 6.2e+05 -9.99e-01 2.118721697e+07 -1.713744583e+08 1.0e-05 0.28
6 3.9e+01 2.9e-05 2.3e+05 -9.73e-01 1.175325358e+08 -5.941616080e+07 1.6e-06 0.30
7 2.0e+01 1.5e-05 1.3e+05 -6.21e-01 7.533158561e+07 -5.999357126e+07 8.1e-07 0.30
8 6.6e+00 4.9e-06 3.2e+04 -8.69e-02 2.472410378e+07 -3.823611032e+07 2.6e-07 0.31
9 1.7e+00 1.3e-06 4.4e+03 6.08e-01 -9.480139674e+06 -2.805155947e+07 6.9e-08 0.31
10 6.9e-01 5.1e-07 1.2e+03 8.67e-01 -1.968700498e+07 -2.756937920e+07 2.7e-08 0.33
11 3.8e-01 2.8e-07 5.3e+02 8.85e-01 -2.332395488e+07 -2.796847238e+07 1.5e-08 0.33
12 2.6e-01 1.9e-07 3.1e+02 9.03e-01 -2.498303018e+07 -2.824587452e+07 1.0e-08 0.33
13 8.0e-02 5.9e-08 5.6e+01 9.39e-01 -2.765460794e+07 -2.869191536e+07 3.2e-09 0.34
14 3.9e-02 2.9e-08 2.0e+01 9.05e-01 -2.832570177e+07 -2.885953072e+07 1.6e-09 0.34
15 4.3e-03 3.1e-09 7.3e-01 9.88e-01 -2.894419453e+07 -2.900228345e+07 1.7e-10 0.36
16 4.8e-04 3.5e-10 2.7e-02 9.96e-01 -2.901123086e+07 -2.901774405e+07 1.9e-11 0.36
17 4.8e-05 3.5e-11 8.5e-04 1.01e+00 -2.901922710e+07 -2.901987535e+07 1.9e-12 0.38
18 5.7e-06 4.2e-12 3.4e-05 1.02e+00 -2.901998250e+07 -2.902005928e+07 2.3e-13 0.38
19 8.4e-07 6.2e-13 1.9e-06 1.02e+00 -2.902006554e+07 -2.902007666e+07 3.3e-14 0.39
20 2.4e-07 1.7e-13 2.9e-07 1.00e+00 -2.902007539e+07 -2.902007852e+07 9.5e-15 0.39
21 2.2e-08 1.6e-14 7.8e-09 1.00e+00 -2.902007885e+07 -2.902007913e+07 8.6e-16 0.41
Optimizer terminated. Time: 0.48
Interior-point solution summary
Problem status : PRIMAL_AND_DUAL_FEASIBLE
Solution status : OPTIMAL
Primal. obj: -2.9020078846e+07 nrm: 3e+07 Viol. con: 2e-03 var: 0e+00 cones: 0e+00
Dual. obj: -2.9020079129e+07 nrm: 2e+06 Viol. con: 0e+00 var: 3e-08 cones: 0e+00
Optimizer summary
Optimizer - time: 0.48
Interior-point - iterations : 21 time: 0.41
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: Solved
Optimal value (cvx_optval): +0.916948
cvx_optval =
0.9169
cvx_optval_gap =
-0.0304
Here, as you can see, the gap is significant. But my point is: as the solver updates the variable and evaluates the objective function on each iteration (I suppose), why do we have such a gap? The solver was not supposed to return the variable for which the last objective function evaluation was done?
We don’t know how you computed cvx_optval . Need to see the program, not just a general description.
In particular, after CVX completes, expressions and expression holders do not necessarily have their “optimal” (final) values. if you want to know the optimal (values) of expressions, you need to compute them starting from CVX variables, which will be at their optimal values. So if your calculation of the objective value involves CVX expressions, and not just CvX variables, you have to calculate everything starting from the optimal CVX variable values.
I don’t know how CVX computes and transforms these things, but generally I would imagine the following. You want to solve a problem
minimize F(q)
Then CVX sends it to the solver in the form
minimize t
subject to t>=F(q)
(Actually the conic representation of t\geq F(q) can potentially be very complicated, but let’s leave it like that).
When you solved the problem, you compute F(q). But the optimal value reported by the solver is of course the value of t. They are equal in the perfect mathematical world, but they will hardly ever be exactly equal in practice, and the more numerically challenging the problem the more they can diverge in the end. (Even worse: I don’t think CVX always returns t but rather some transformation of it as optval). For example your Mosek solution
Primal. obj: -2.9020078846e+07 nrm: 3e+07 Viol. con: 2e-03 var: 0e+00 cones: 0e+00
Dual. obj: -2.9020079129e+07 nrm: 2e+06 Viol. con: 0e+00 var: 3e-08 cones: 0e+00
has rather large-ish norm and a constraint violation, which can lead to many errors accumulating in all the computations or even in just recomputing F(q). That’s just a guess though, based on my understanding how things might work.