Some concept need to check by using pow_pos function

FredericHong · January 7, 2019, 4:20pm

Hello,
I am a newbie to use CVX tool. The following example is my main question:

\min (x_1+x_2+x_3)^8+x_1^2+x_2^2+3x_3^2+2x_1x_2+2x_2x_3+2x_1x_3
subject to :
(|x_1-2x_2|+1)^4+ {1}/{x_3} \le 10,
2x_1+2x_2+x_3 \le 1,
0 \le x_3 \le 1.

====================== Matlab_Code ======================

clear all;
clc;

A=[1 1 1;1 1 1;1 1 1];

cvx_begin
variables x(3)

minimize (pow_pos((x(1)+x(2)+x(3))^2,4) + x'*A*x)

subject to 

 pow_abs(x(1)-2*x(2),4) + 4*pow_abs(x(1)-2*x(2),3) + 6*pow_abs(x(1)-2*x(2),2) + 4*abs(x(1)-2*x(2)) + 1 + quad_over_lin(1,x(3)) <= 10
 2*x(1)+2*x(2)+x(3) <= 1
 x(3) >= 0
 x(3) <= 1

====================== Matlab_Code End ======================

====================== Result ======================
Status: Solved
Optimal value (cvx_optval): +0.0246914

x =
-0.074074107262916
-0.037037053631458
0.111111158690451
====================== Result End ======================

But, if I changing the objective function by the following:
====================== Matlab_Code ======================
minimize (pow_pos(x(1)+x(2)+x(3),8) + x'*A*x)
====================== Matlab_Code End ======================

the result is
====================== Result ======================
Status: Solved
Optimal value (cvx_optval): +0.0493827

x =
1.0e+03 *
-8.182107365944137
-4.091053682972069
0.000111111115061
====================== Result End ======================
Why both way result is different ?
And I feel the second way is very strange. Is it true?

I will be very thankful if anyone can help me =)

Mark_L_Stone · January 7, 2019, 9:55pm

The exact optimal objective value is the same for both formulations.

However, apparently CVX provides a mathematically equivalent but different formulation for the two formulations to the solver. Given solver tolerance, the solutions produced by the solver and reported by CVX may not be identical.

I believe the exact optimal objective value is 0, so the reported cvx_optval is just noise around 0 due to solver tolerance. Here are the results for both formulations using both sdpt3 and sedumi.

cvx_begin
variables x(3)
minimize (pow_pos((x(1)+x(2)+x(3))^2,4) + x'*A*x)
subject to
pow_abs(x(1)-2*x(2),4) + 4*pow_abs(x(1)-2*x(2),3) + 6*pow_abs(x(1)-2*x(2),2) + 4*abs(x(1)-2*x(2)) + 1 + quad_over_lin(1,x(3)) <= 10
0 <= x(3) <= 1
cvx_solver sdpt3;cvx_end
 
Calling SDPT3 4.0: 40 variables, 18 equality constraints
   For improved efficiency, SDPT3 is solving the dual problem.
------------------------------------------------------------

 num. of constraints = 18
 dim. of sdp    var  = 20,   num. of sdp  blk  = 10
 dim. of socp   var  =  4,   num. of socp blk  =  2
 dim. of linear var  =  6
*******************************************************************
   SDPT3: Infeasible path-following algorithms
*******************************************************************
 version  predcorr  gam  expon  scale_data
   HKM      1      0.000   1        0    
it pstep dstep pinfeas dinfeas  gap      prim-obj      dual-obj    cputime
-------------------------------------------------------------------
 0|0.000|0.000|1.8e+01|4.6e+00|2.6e+03| 1.800000e+02  0.000000e+00| 0:0:00| chol  1  1 
 1|0.941|0.764|1.1e+00|1.1e+00|6.8e+02| 1.231055e+02 -2.221377e+01| 0:0:00| chol  1  1 
 2|1.000|1.000|4.0e-06|5.0e-03|7.6e+01| 7.020942e+01 -4.274184e+00| 0:0:00| chol  1  1 
 3|1.000|1.000|2.0e-07|5.0e-04|1.4e+01| 1.202207e+01 -1.523202e+00| 0:0:00| chol  1  1 
 4|0.933|0.962|3.7e-08|6.7e-05|2.2e+00| 1.958539e+00 -2.352798e-01| 0:0:00| chol  1  1 
 5|1.000|1.000|3.2e-10|5.0e-06|1.0e+00| 8.830278e-01 -1.160784e-01| 0:0:00| chol  1  1 
 6|0.911|0.911|7.9e-11|9.0e-07|1.2e-01| 1.029515e-01 -1.367775e-02| 0:0:00| chol  1  1 
 7|1.000|1.000|2.7e-10|5.0e-08|5.0e-02| 4.460070e-02 -5.740855e-03| 0:0:00| chol  1  1 
 8|0.911|0.911|7.0e-11|9.0e-09|6.1e-03| 5.343286e-03 -7.115789e-04| 0:0:00| chol  1  1 
 9|1.000|1.000|3.2e-10|5.1e-10|2.7e-03| 2.367900e-03 -3.036007e-04| 0:0:00| chol  1  1 
10|0.911|0.911|2.8e-11|1.1e-10|3.2e-04| 2.823195e-04 -3.772537e-05| 0:0:00| chol  1  1 
11|1.000|1.000|6.6e-16|1.1e-11|1.4e-04| 1.255930e-04 -1.606305e-05| 0:0:00| chol  1  1 
12|0.911|0.911|1.5e-12|2.4e-12|1.7e-05| 1.498007e-05 -2.003094e-06| 0:0:00| chol  1  1 
13|1.000|1.000|7.0e-13|1.0e-12|7.5e-06| 6.677755e-06 -8.534170e-07| 0:0:00| chol  1  1 
14|1.000|1.000|1.5e-13|1.0e-12|1.3e-06| 1.163687e-06 -1.561892e-07| 0:0:00| chol  1  1 
15|1.000|1.000|5.3e-14|1.0e-12|3.2e-07| 2.844630e-07 -3.701085e-08| 0:0:00| chol  1  1 
16|1.000|1.000|1.5e-14|1.0e-12|7.4e-08| 6.538100e-08 -8.625944e-09| 0:0:00| chol  1  1 
17|0.848|1.000|9.8e-15|1.0e-12|3.8e-08| 3.452677e-08 -3.795969e-09| 0:0:00| chol  1  1 
18|0.843|1.000|1.0e-14|1.0e-12|2.0e-08| 1.821048e-08 -2.016882e-09| 0:0:00| chol  1  1 
19|0.839|1.000|7.0e-15|1.0e-12|1.1e-08| 9.616040e-09 -1.055251e-09| 0:0:00|
  stop: max(relative gap, infeasibilities) < 1.49e-08
-------------------------------------------------------------------
 number of iterations   = 19
 primal objective value =  9.61603978e-09
 dual   objective value = -1.05525073e-09
 gap := trace(XZ)       = 1.07e-08
 relative gap           = 1.07e-08
 actual relative gap    = 1.07e-08
 rel. primal infeas (scaled problem)   = 7.00e-15
 rel. dual     "        "       "      = 1.00e-12
 rel. primal infeas (unscaled problem) = 0.00e+00
 rel. dual     "        "       "      = 0.00e+00
 norm(X), norm(y), norm(Z) = 3.2e+00, 2.9e+00, 4.8e+00
 norm(A), norm(b), norm(C) = 1.3e+01, 4.2e+00, 1.1e+01
 Total CPU time (secs)  = 0.31  
 CPU time per iteration = 0.02  
 termination code       =  0
 DIMACS: 7.3e-15  0.0e+00  1.1e-12  0.0e+00  1.1e-08  1.1e-08
-------------------------------------------------------------------
 
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +1.05525e-09
 
>> disp(x)
   -0.5141
   -0.2571
    0.7712

>> cvx_begin
variables x(3)
minimize (pow_pos(x(1)+x(2)+x(3),8) + x'*A*x)
subject to
pow_abs(x(1)-2*x(2),4) + 4*pow_abs(x(1)-2*x(2),3) + 6*pow_abs(x(1)-2*x(2),2) + 4*abs(x(1)-2*x(2)) + 1 + quad_over_lin(1,x(3)) <= 10
0 <= x(3) <= 1
cvx_solver sdpt3;cvx_end
 
Calling SDPT3 4.0: 39 variables, 17 equality constraints
   For improved efficiency, SDPT3 is solving the dual problem.
------------------------------------------------------------

 num. of constraints = 17
 dim. of sdp    var  = 20,   num. of sdp  blk  = 10
 dim. of socp   var  =  4,   num. of socp blk  =  2
 dim. of linear var  =  5
*******************************************************************
   SDPT3: Infeasible path-following algorithms
*******************************************************************
 version  predcorr  gam  expon  scale_data
   HKM      1      0.000   1        0    
it pstep dstep pinfeas dinfeas  gap      prim-obj      dual-obj    cputime
-------------------------------------------------------------------
 0|0.000|0.000|1.8e+01|4.5e+00|2.5e+03| 1.800000e+02  0.000000e+00| 0:0:00| chol  1  1 
 1|0.954|0.767|8.2e-01|1.1e+00|6.3e+02| 1.218531e+02 -2.398625e+01| 0:0:00| chol  1  1 
 2|1.000|0.990|7.2e-06|1.5e-02|7.6e+01| 6.823552e+01 -3.197148e+00| 0:0:00| chol  1  1 
 3|0.992|1.000|2.7e-07|4.9e-04|1.2e+01| 1.005093e+01 -1.853689e+00| 0:0:00| chol  1  1 
 4|1.000|1.000|8.1e-08|4.9e-05|2.8e+00| 2.597410e+00 -2.388827e-01| 0:0:00| chol  1  1 
 5|0.911|0.911|7.3e-09|8.9e-06|3.5e-01| 3.206875e-01 -3.168935e-02| 0:0:00| chol  1  1 
 6|1.000|1.000|5.8e-10|4.9e-07|1.5e-01| 1.362841e-01 -1.634642e-02| 0:0:00| chol  1  1 
 7|0.912|0.912|8.0e-11|8.8e-08|1.6e-02| 1.465085e-02 -1.748001e-03| 0:0:00| chol  1  1 
 8|1.000|1.000|4.5e-10|4.9e-09|6.8e-03| 6.102176e-03 -7.215241e-04| 0:0:00| chol  1  1 
 9|0.912|0.912|9.7e-11|9.1e-10|7.5e-04| 6.682484e-04 -7.939759e-05| 0:0:00| chol  1  1 
10|1.000|1.000|3.4e-16|6.9e-11|3.1e-04| 2.801955e-04 -3.301021e-05| 0:0:00| chol  1  1 
11|0.912|0.912|3.2e-16|1.2e-11|3.4e-05| 3.065495e-05 -3.642963e-06| 0:0:00| chol  1  1 
12|1.000|1.000|1.9e-12|1.0e-12|1.4e-05| 1.287644e-05 -1.514981e-06| 0:0:00| chol  1  1 
13|1.000|1.000|4.5e-13|1.0e-12|2.3e-06| 2.024106e-06 -2.423025e-07| 0:0:00| chol  1  1 
14|1.000|1.000|1.6e-13|1.0e-12|5.1e-07| 4.578596e-07 -5.417719e-08| 0:0:00| chol  1  1 
15|1.000|1.000|5.3e-14|1.0e-12|1.1e-07| 9.447667e-08 -1.123315e-08| 0:0:00| chol  1  1 
16|0.847|1.000|3.7e-14|1.0e-12|5.5e-08| 4.985952e-08 -4.970261e-09| 0:0:00| chol  1  1 
17|0.842|1.000|4.5e-14|1.0e-12|2.9e-08| 2.630475e-08 -2.633161e-09| 0:0:00| chol  1  1 
18|0.839|1.000|7.5e-15|1.0e-12|1.5e-08| 1.389042e-08 -1.378837e-09| 0:0:00| chol  1  1 
19|0.839|1.000|1.2e-15|1.0e-12|8.1e-09| 7.335048e-09 -7.274390e-10| 0:0:00|
  stop: max(relative gap, infeasibilities) < 1.49e-08
-------------------------------------------------------------------
 number of iterations   = 19
 primal objective value =  7.33504825e-09
 dual   objective value = -7.27439031e-10
 gap := trace(XZ)       = 8.07e-09
 relative gap           = 8.07e-09
 actual relative gap    = 8.06e-09
 rel. primal infeas (scaled problem)   = 1.20e-15
 rel. dual     "        "       "      = 1.00e-12
 rel. primal infeas (unscaled problem) = 0.00e+00
 rel. dual     "        "       "      = 0.00e+00
 norm(X), norm(y), norm(Z) = 3.2e+00, 2.9e+00, 4.8e+00
 norm(A), norm(b), norm(C) = 1.3e+01, 4.2e+00, 1.1e+01
 Total CPU time (secs)  = 0.30  
 CPU time per iteration = 0.02  
 termination code       =  0
 DIMACS: 1.3e-15  0.0e+00  1.1e-12  0.0e+00  8.1e-09  8.1e-09
-------------------------------------------------------------------
 
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +7.27439e-10
 
>> disp(x)
   -0.5141
   -0.2571
    0.7712

>> cvx_begin
variables x(3)
minimize (pow_pos((x(1)+x(2)+x(3))^2,4) + x'*A*x)
subject to
pow_abs(x(1)-2*x(2),4) + 4*pow_abs(x(1)-2*x(2),3) + 6*pow_abs(x(1)-2*x(2),2) + 4*abs(x(1)-2*x(2)) + 1 + quad_over_lin(1,x(3)) <= 10
0 <= x(3) <= 1
cvx_solver sedumi;cvx_end
 
 
Calling SeDuMi 1.34: 40 variables, 18 equality constraints
   For improved efficiency, SeDuMi is solving the dual problem.
------------------------------------------------------------
SeDuMi 1.34 (beta) by AdvOL, 2005-2008 and Jos F. Sturm, 1998-2003.
Alg = 2: xz-corrector, Adaptive Step-Differentiation, theta = 0.250, beta = 0.500
eqs m = 18, order n = 31, dim = 41, blocks = 11
nnz(A) = 71 + 0, nnz(ADA) = 118, nnz(L) = 72
 it :     b*y       gap    delta  rate   t/tP*  t/tD*   feas cg cg  prec
  0 :            1.90E+01 0.000
  1 :   3.59E+00 9.46E+00 0.000 0.4967 0.9000 0.9000   3.21  1  1  4.0E+00
  2 :   6.82E-01 3.26E+00 0.000 0.3448 0.9000 0.9000   3.02  1  1  7.6E-01
  3 :   1.04E-01 7.50E-01 0.000 0.2302 0.9000 0.9000   1.76  1  1  2.2E-01
  4 :   2.39E-02 2.02E-01 0.000 0.2689 0.9000 0.9000   1.27  1  1  1.3E-01
  5 :   6.54E-03 5.68E-02 0.000 0.2812 0.9000 0.9000   1.09  1  1  1.1E-01
  6 :   1.64E-03 1.56E-02 0.000 0.2741 0.9000 0.9000   1.03  1  1  1.1E-01
  7 :   5.15E-04 2.42E-03 0.000 0.1557 0.9135 0.9000   1.01  1  1  9.7E-02
  8 :   1.81E-04 5.75E-04 0.000 0.2373 0.9083 0.9000   1.01  1  1  6.0E-02
  9 :   5.71E-05 1.57E-04 0.000 0.2726 0.9021 0.9000   1.00  1  1  1.7E-02
 10 :   5.71E-05 1.87E-05 0.000 0.1193 0.9000 0.0000   1.00  1  1  5.3E-04
 11 :   2.87E-05 5.79E-07 0.000 0.0310 0.9303 0.9000   1.00  1  1  3.7E-06
 12 :   5.76E-06 8.14E-08 0.000 0.1406 0.9000 0.8513   1.00  1  1  7.5E-07
 13 :   1.35E-06 1.95E-08 0.000 0.2395 0.9000 0.8506   1.00  3  3  1.8E-07
 14 :   3.42E-07 4.77E-09 0.000 0.2444 0.9000 0.9000   1.00  3  3  4.4E-08
 15 :   9.60E-08 1.28E-09 0.000 0.2686 0.9000 0.9000   1.00  3  3  1.2E-08

iter seconds digits       c*x               b*y
 15      0.2   Inf  8.1299323795e-08  9.6003654706e-08
|Ax-b| =   5.3e-09, [Ay-c]_+ =   3.6E-08, |x|=  2.2e+00, |y|=  2.6e+00

Detailed timing (sec)
   Pre          IPM          Post
2.300E-02    1.030E-01    4.999E-03    
Max-norms: ||b||=3, ||c|| = 1.000000e+01,
Cholesky |add|=1, |skip| = 0, ||L.L|| = 3.27051.
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): -9.60037e-08
 
>> disp(x)
   -0.5059
   -0.2530
    0.7589

>>  cvx_begin
variables x(3)
minimize (pow_pos(x(1)+x(2)+x(3),8) + x'*A*x)
subject to
pow_abs(x(1)-2*x(2),4) + 4*pow_abs(x(1)-2*x(2),3) + 6*pow_abs(x(1)-2*x(2),2) + 4*abs(x(1)-2*x(2)) + 1 + quad_over_lin(1,x(3)) <= 10
0 <= x(3) <= 1
cvx_solver sedumi;cvx_end
 
Calling SeDuMi 1.34: 39 variables, 17 equality constraints
   For improved efficiency, SeDuMi is solving the dual problem.
------------------------------------------------------------
SeDuMi 1.34 (beta) by AdvOL, 2005-2008 and Jos F. Sturm, 1998-2003.
Alg = 2: xz-corrector, Adaptive Step-Differentiation, theta = 0.250, beta = 0.500
eqs m = 17, order n = 30, dim = 40, blocks = 11
nnz(A) = 67 + 0, nnz(ADA) = 107, nnz(L) = 66
 it :     b*y       gap    delta  rate   t/tP*  t/tD*   feas cg cg  prec
  0 :            1.97E+01 0.000
  1 :   3.27E+00 9.41E+00 0.000 0.4784 0.9000 0.9000   3.21  1  1  3.8E+00
  2 :   6.04E-01 3.20E+00 0.000 0.3399 0.9000 0.9000   3.06  1  1  7.1E-01
  3 :   9.86E-02 6.88E-01 0.000 0.2150 0.9000 0.9000   1.70  1  1  2.1E-01
  4 :   2.15E-02 1.67E-01 0.000 0.2427 0.9000 0.9000   1.22  1  1  1.3E-01
  5 :   5.29E-03 4.26E-02 0.000 0.2554 0.9000 0.9000   1.06  1  1  1.1E-01
  6 :   1.24E-03 1.07E-02 0.000 0.2502 0.9000 0.9000   1.02  1  1  1.1E-01
  7 :   3.40E-04 1.93E-03 0.000 0.1808 0.9084 0.9000   1.01  1  1  1.0E-01
  8 :   1.01E-04 4.12E-04 0.000 0.2136 0.9066 0.9000   1.00  1  1  4.3E-02
  9 :   2.79E-05 1.01E-04 0.000 0.2445 0.9021 0.9000   1.00  1  1  1.1E-02
 10 :   2.79E-05 1.21E-05 0.000 0.1200 0.9000 0.0000   1.00  1  1  5.4E-04
 11 :   1.35E-05 2.00E-07 0.000 0.0166 0.9322 0.9000   1.00  1  1  1.7E-06
 12 :   1.21E-06 1.57E-08 0.000 0.0784 0.9900 0.9734   1.00  1  1  1.5E-07
 13 :   4.66E-07 5.72E-09 0.000 0.3649 0.9000 0.9000   1.00  1  1  5.6E-08
 14 :   1.48E-07 1.82E-09 0.000 0.3172 0.9000 0.9000   1.00  1  1  1.8E-08
 15 :   5.06E-08 5.94E-10 0.000 0.3274 0.9000 0.9000   1.00  1  1  5.8E-09

iter seconds digits       c*x               b*y
 15      0.2   Inf  4.4300009488e-08  5.0615610148e-08
|Ax-b| =   1.9e-09, [Ay-c]_+ =   1.9E-08, |x|=  2.2e+00, |y|=  2.6e+00

Detailed timing (sec)
   Pre          IPM          Post
2.300E-02    8.200E-02    6.005E-03    
Max-norms: ||b||=3, ||c|| = 1.000000e+01,
Cholesky |add|=0, |skip| = 0, ||L.L|| = 3.19665.
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): -5.06156e-08
 
>> disp(x)
   -0.5080
   -0.2540
    0.7620

FredericHong · January 9, 2019, 3:46pm

Hi Mark,
Thank you very much for your reply.

Regarding your experiment, I’m very surprised the sdpt3 and sedumi can output the similar result in this problem.

By the way, sdpt3 is covert the prime problem to the dual problem, right? Anything I’m loss?!

If sdpt3 is doing what I think. Why the output result is very different in my experiment without using sdpt3?
Could it be different a lot?

Mark_L_Stone · January 9, 2019, 4:24pm

As I wrote, the differences between the various solutions are just due to solver tolerance.

FredericHong · January 9, 2019, 4:47pm

Hi Mark,
Oh~
Thank for your friendly reminder and reply.
Now It’s clear for me.

Best regards,
Frederic.