The confusion about the result of minimizing a l2-norm function minus an affine function

1

Hi, all

Specifically, I’m trying to solve a problem with the objective function of a l2-norm minus an affine function as follow,
f=||w||_2^2-(a*(y-x))
where w and y are optimization variables, a and x are kown parameters.

My confusion is that the final result is different from the iterative information. As you can see in the following, the iterative information shows that the result would be -2.67. However, the CVX demonstrates that the optimal value is -1.88. So could you please help me to explain this phenomenon? And which is the real optimal value?

I appreciate your kind help!

The following is the iterative information.

Calling SDPT3 4.0: 1097 variables, 513 equality constraints

num. of constraints = 513
dim. of socp var = 1097, num. of socp blk = 43

SDPT3: Infeasible path-following algorithms

version predcorr gam expon scale_data
NT 1 0.000 1 0
it pstep dstep pinfeas dinfeas gap prim-obj dual-obj cputime

0|0.000|0.000|4.2e+00|7.1e+03|5.4e+05| 5.742654e-01 0.000000e+00| 0:0:00| spchol 1 1
1|0.865|0.768|5.7e-01|1.6e+03|1.2e+05| 8.931482e-01 -2.780834e+04| 0:0:00| spchol 1 1
2|1.000|0.832|3.6e-05|2.7e+02|2.1e+04| 1.507160e+00 -1.020520e+04| 0:0:01| spchol 1 1
3|1.000|0.986|6.6e-05|3.8e+00|2.8e+02| 1.501680e+00 -1.399625e+02| 0:0:01| spchol 1 1
4|1.000|0.897|8.6e-07|3.9e-01|3.0e+01| 1.164379e+00 -1.442595e+01| 0:0:01| spchol 1 1
5|0.698|0.768|7.3e-07|9.0e-02|7.6e+00|-1.577403e-02 -4.422429e+00| 0:0:01| spchol 1 1
6|0.574|0.601|6.1e-07|3.6e-02|3.2e+00|-1.024427e+00 -2.957142e+00| 0:0:01| spchol 1 1
7|0.598|0.583|3.5e-07|1.5e-02|1.3e+00|-1.579591e+00 -2.386611e+00| 0:0:01| spchol 1 1
8|0.360|0.417|2.5e-07|8.8e-03|8.1e-01|-1.799819e+00 -2.245807e+00| 0:0:01| spchol 1 1
9|0.420|0.427|1.6e-07|5.0e-03|4.6e-01|-1.969387e+00 -2.173095e+00| 0:0:01| spchol 1 1
10|0.654|0.498|5.6e-08|2.5e-03|2.3e-01|-2.086029e+00 -2.161848e+00| 0:0:01| spchol 1 1
11|0.490|0.509|2.8e-08|1.2e-03|1.2e-01|-2.141224e+00 -2.166201e+00| 0:0:01| spchol 1 1
12|0.271|0.334|2.1e-08|8.3e-04|8.7e-02|-2.170143e+00 -2.175627e+00| 0:0:01| spchol 1 1
13|0.025|0.024|2.0e-08|8.1e-04|8.7e-02|-2.216368e+00 -2.176581e+00| 0:0:01| spchol 1 1
14|0.020|0.081|2.0e-08|7.4e-04|9.4e-02|-2.278096e+00 -2.193888e+00| 0:0:01| spchol 1 1
15|0.122|0.094|1.7e-08|6.7e-04|1.0e-01|-2.352233e+00 -2.213373e+00| 0:0:01| spchol 1 1
16|0.056|0.124|1.6e-08|5.9e-04|1.1e-01|-2.371701e+00 -2.246003e+00| 0:0:01| spchol 1 1
17|0.205|0.108|1.3e-08|5.2e-04|1.2e-01|-2.436082e+00 -2.271779e+00| 0:0:01| spchol 1 1
18|0.190|0.194|1.1e-08|4.2e-04|1.3e-01|-2.494459e+00 -2.330681e+00| 0:0:01| spchol 1 1
19|0.222|0.236|8.2e-09|3.2e-04|1.3e-01|-2.540943e+00 -2.395769e+00| 0:0:01| spchol 1 1
20|0.167|0.209|6.9e-09|2.6e-04|1.2e-01|-2.572555e+00 -2.446362e+00| 0:0:01| spchol 1 1
21|0.254|0.403|5.1e-09|1.5e-04|9.7e-02|-2.605267e+00 -2.529890e+00| 0:0:01| spchol 1 1
22|0.462|0.422|2.8e-09|8.8e-05|6.4e-02|-2.639981e+00 -2.586446e+00| 0:0:01| spchol 1 1
23|0.699|0.592|8.3e-10|3.6e-05|2.8e-02|-2.661479e+00 -2.636792e+00| 0:0:01| spchol 1 1
24|0.790|0.561|1.7e-10|1.6e-05|1.1e-02|-2.670405e+00 -2.657154e+00| 0:0:01| spchol 1 1
25|0.834|0.828|2.9e-11|2.7e-06|2.1e-03|-2.672510e+00 -2.670298e+00| 0:0:01| spchol 1 1
26|0.923|0.796|7.0e-12|5.6e-07|3.7e-04|-2.673037e+00 -2.672527e+00| 0:0:01| spchol 1 1
27|0.853|0.766|4.8e-12|1.3e-07|8.2e-05|-2.673101e+00 -2.672978e+00| 0:0:01| spchol 1 1
28|0.784|0.804|2.2e-11|2.6e-08|1.8e-05|-2.673114e+00 -2.673092e+00| 0:0:01| spchol 1 1
29|0.792|0.563|3.4e-11|1.1e-08|6.7e-06|-2.673119e+00 -2.673108e+00| 0:0:01| spchol 1 1
30|0.784|0.643|9.1e-11|4.0e-09|2.3e-06|-2.673120e+00 -2.673116e+00| 0:0:01| spchol 1 1
31|0.853|0.652|2.1e-09|1.4e-09|7.5e-07|-2.673120e+00 -2.673119e+00| 0:0:01| spchol 1 1
32|0.980|0.484|6.9e-09|7.2e-10|3.6e-07|-2.673120e+00 -2.673119e+00| 0:0:01| spchol 1 1
33|1.000|0.483|3.2e-09|3.8e-10|2.0e-07|-2.673120e+00 -2.673120e+00| 0:0:01| spchol 1 1
34|1.000|0.484|7.4e-10|2.0e-10|1.1e-07|-2.673120e+00 -2.673120e+00| 0:0:01| spchol 1 1
35|1.000|0.485|9.5e-10|1.1e-10|6.4e-08|-2.673120e+00 -2.673120e+00| 0:0:01|
stop: max(relative gap, infeasibilities) < 1.49e-08

number of iterations = 35
primal objective value = -2.67312018e+00
dual objective value = -2.67312007e+00
gap := trace(XZ) = 6.42e-08
relative gap = 1.01e-08
actual relative gap = -1.70e-08
rel. primal infeas (scaled problem) = 9.51e-10
rel. dual " " " = 1.09e-10
rel. primal infeas (unscaled problem) = 0.00e+00
rel. dual " " " = 0.00e+00
norm(X), norm(y), norm(Z) = 3.4e+03, 4.0e-01, 5.9e-01
norm(A), norm(b), norm© = 1.1e+04, 1.1e+01, 1.5e+00
Total CPU time (secs) = 1.09
CPU time per iteration = 0.03
termination code = 0
DIMACS: 3.3e-09 0.0e+00 1.5e-10 0.0e+00 -1.7e-08 1.0e-08

Status: Solved
Optimal value (cvx_optval): -1.88714

3

What happens if you evaluate your objective function at the solution?

CVX performs a variety of transformations on your model before solve it. It’s possible there is some sort of transformation that is modifying the objective function. I would trust CVX’s output over the solvers because of that.

Still, verify as well…

4

mcg can come along and hopefully expand on/confirm the following.

cvx_optval should be the optimal value of the objective of your problem as entered in CVX. You are seeing the output from the SDPT3 solver solving the problem which CVX provided it. But CVX may have transformed the problem from what you entered, resulting in a different objective function. After solution by the solver, CVX untransforms back to the problem you entered, and cvx_optval is the resulting optimal objective value after this untransformation has been performed by CVX.

6

Thank you very much for your kind help. What do you mean by “evaluate your objective function at the solution”? To calculate the objective function through the given solutions? If so, that would equal to the value of the cvx_optval.

7

Yes, take the numeric values of w and y and compute the numeric value of the objective function. We would expect them to match the value of cvx_optval.

8

Thank you very much for your kind help

9

@mcg @Mark_L_Stone. Thank you very much for your kind help. I have another problem when solving the same problem. Given some specifical parameters, it will result in the ‘Failed’ status. I tried to change the precision using cvx_precision([1.49e-08,1.49e-08,1.0e-02]). Then it can be solved. However, the precision is too much lower for me. So could you explain for me how this ‘Failed’ happens, and is there any solution to solve this without changing the precision?

Calling SDPT3 4.0: 1102 variables, 460 equality constraints

num. of constraints = 460
dim. of socp var = 1098, num. of socp blk = 38
dim. of linear var = 4

SDPT3: Infeasible path-following algorithms

version predcorr gam expon scale_data
NT 1 0.000 1 0
it pstep dstep pinfeas dinfeas gap prim-obj dual-obj cputime

0|0.000|0.000|4.1e+00|5.2e+04|6.9e+06| 2.000000e+01 0.000000e+00| 0:0:00| chol 2 2
1|1.000|0.880|1.2e-01|6.3e+03|8.1e+05| 3.153658e+01 -4.146420e+05| 0:0:00| chol 2 2
2|1.000|0.944|3.9e-05|3.5e+02|4.8e+04| 1.354632e+02 -2.564158e+04| 0:0:00| chol 2 2
3|1.000|0.988|3.8e-06|4.0e+00|5.5e+02| 1.965285e+00 -2.958332e+02| 0:0:00| chol 2 2
4|0.988|0.973|6.9e-07|1.1e-01|1.5e+01|-5.747411e-03 -8.045498e+00| 0:0:00| chol 2 2
5|1.000|0.720|1.8e-07|3.1e-02|3.9e+00|-1.281748e+00 -3.200966e+00| 0:0:00| chol 2 2
6|0.810|0.621|6.5e-07|1.2e-02|1.3e+00|-2.308180e+00 -2.674880e+00| 0:0:00| chol 2 2
7|0.139|0.279|6.1e-07|8.3e-03|9.9e-01|-2.502991e+00 -2.718701e+00| 0:0:00| chol 2 2
8|0.647|0.532|3.5e-07|3.9e-03|4.3e-01|-2.813198e+00 -2.786135e+00| 0:0:00| chol 1 1
9|0.620|0.617|1.8e-07|1.5e-03|1.7e-01|-2.921117e+00 -2.888160e+00| 0:0:00| chol 1 1
10|0.496|0.190|1.0e-07|1.2e-03|1.3e-01|-2.999048e+00 -2.904340e+00| 0:0:00| chol 1 1
11|0.401|0.138|6.7e-08|1.0e-03|1.7e-01|-2.986207e+00 -2.937897e+00| 0:0:00| chol 1 1
12|0.072|0.113|6.2e-08|9.3e-04|1.7e-01|-3.082335e+00 -2.971940e+00| 0:0:00| chol 1 1
13|0.310|0.215|4.5e-08|7.3e-04|1.6e-01|-3.146915e+00 -3.035652e+00| 0:0:00| chol 1 1
14|0.215|0.200|3.7e-08|5.8e-04|1.4e-01|-3.186594e+00 -3.071303e+00| 0:0:00| chol 1 1
15|0.247|0.240|2.9e-08|4.4e-04|1.2e-01|-3.234057e+00 -3.114995e+00| 0:0:00| chol 1 1
16|0.169|0.191|2.4e-08|3.6e-04|1.1e-01|-3.266053e+00 -3.150357e+00| 0:0:00| chol 1 1
17|0.230|0.266|1.9e-08|2.6e-04|9.7e-02|-3.297261e+00 -3.198379e+00| 0:0:00| chol 1 1
18|0.168|0.386|1.6e-08|1.6e-04|7.5e-02|-3.313740e+00 -3.256640e+00| 0:0:00| chol 1 1
19|0.231|0.325|1.2e-08|1.1e-04|6.0e-02|-3.330386e+00 -3.289904e+00| 0:0:00| chol 1 1
20|0.205|0.553|9.9e-09|4.9e-05|4.0e-02|-3.338271e+00 -3.330426e+00| 0:0:00| chol 1 1
21|0.770|0.588|2.3e-09|2.0e-05|1.4e-02|-3.358509e+00 -3.350074e+00| 0:0:00| chol 1 1
22|0.766|0.785|5.4e-10|4.3e-06|3.3e-03|-3.362633e+00 -3.361096e+00| 0:0:00| chol 1 1
23|0.830|0.218|9.1e-11|3.4e-06|1.8e-03|-3.364013e+00 -3.361752e+00| 0:0:00| chol 1 1
24|0.076|0.015|1.7e-10|3.3e-06|1.8e-03|-3.364682e+00 -3.361807e+00| 0:0:00| chol 1 1
25|0.014|0.043|1.7e-10|3.2e-06|1.9e-03|-3.365472e+00 -3.362016e+00| 0:0:00|
stop: steps too short consecutively

number of iterations = 25
primal objective value = -3.36401349e+00
dual objective value = -3.36175194e+00
gap := trace(XZ) = 1.76e-03
relative gap = 2.27e-04
actual relative gap = -2.93e-04
rel. primal infeas (scaled problem) = 9.07e-11
rel. dual " " " = 3.37e-06
rel. primal infeas (unscaled problem) = 0.00e+00
rel. dual " " " = 0.00e+00
norm(X), norm(y), norm(Z) = 1.9e+03, 8.1e-01, 1.1e+00
norm(A), norm(b), norm© = 1.0e+05, 1.1e+01, 2.5e+00
Total CPU time (secs) = 0.44
CPU time per iteration = 0.02
termination code = -5
DIMACS: 3.2e-10 0.0e+00 4.2e-06 0.0e+00 -2.9e-04 2.3e-04

Status: Failed
Optimal value (cvx_optval): NaN

10

Try the other solvers in CVX and see if they do a better job. See the documentation—we talk about just these kinds of issues.

12

Thank you very much!
I have tried the sedumi and scs, but sometimes they also result in ‘Failed’.
Also I have scanned the document, the explanation of the ‘Failed’ status is all about the precision. Is changing the precision the only way to solve this problem?