Hey friends,
I formulate one problem in two ways (they are mathematically equivalent) but get different optimal-value out of the optimization (convex), the difference is like 12.1053 and 11.9096. May I ask is this due to the precision of the optimization or it does not seem normal?
Besides, is there any way that I can obtain some numerical measure of how close my optimal result is from the actual optimal point?
Thanks a lot!
Can you show both programs, complete with all solver and CVX output? Preferably with all input data as well?
%%%%code%%%formulation 1 and 2 are both included
One = ones(NM2+2,1);
cvx_begin;
cvx_solver Gurobi;
variables t(NM2+2) v(NM2+2);
logfile = sprintf(’%s/gurobi.log’,foldername);
cvx_solver_settings(‘NumericFocus’,3, …
‘LogFile’,logfile, ‘ScaleFlag’, 2,‘NumericFocus’,3);
cvx_precision(‘best’);
flip1 = sparse(diag(ones(NM+1,1),NM+1));
flip2 = sparse(diag(ones(NM+1,1),-NM-1));
flip = sparse(flip1+flip2);
B = A.’*v; %%A is known matrix
%%%%%%%%%formula1%%%%%%%%%%%%%%%%
inv_eps_min = 1./sqrt(epsilon_min_op);%constant
inv_eps_max = 1./sqrt(epsilon_max_op);%constant
X_min = sparse(diag((inv_eps_min)))(B + epsilon_min_op.v);
X_max = sparse(diag((inv_eps_max)))(B + epsilon_max_op.v);
X_min2 = flipX_min;
X_max2 = flipX_max;
t >= weight_op.*((X_min.*X_min)+(X_min2.X_min2)); %weight_op is constant
t >= weight_op.((X_max.*X_max)+(X_max2.*X_max2));
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%formula2%%%%%%%%%%%%%%%%
X_min = (B + epsilon_min_op.v);
X_max = (B + epsilon_max_op.v);
X_min2 = flipX_min;
X_max2 = flipX_max;
inv_eps_min = 1./(epsilon_min_op);%constant
inv_eps_max = 1./(epsilon_max_op);%constant
factor_min = sparse(diag(weight_op.*inv_eps_min));%constant
factor_max = sparse(diag(weight_op.*inv_eps_max));%constant
t >= (factor_min)*((X_min.*X_min)+(X_min2.X_min2));
t >= (factor_max)((X_max.*X_max)+(X_max2.*X_max2));
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
maximize (-1/4*(One.’*t) - v.’*b);
cvx_end;
%%%%%%%55output from formalism 2%%%%%%%%%%%%
Gurobi optimizer, licensed to CVX for CVX
Academic license - for non-commercial use only
Warning for adding variables: zero or small (< 1e-13) coefficients, ignored
Optimize a model with 131222 rows, 209958 columns and 727360 nonzeros
Model has 52488 quadratic constraints
Coefficient statistics:
Matrix range [6e-03, 1e+06]
QMatrix range [1e+00, 1e+00]
Objective range [2e-01, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [1e+00, 1e+00]
Presolve removed 13124 rows and 26249 columns
Presolve time: 1.93s
Presolved: 118098 rows, 183709 columns, 687990 nonzeros
Presolved model has 52488 second-order cone constraints
Ordering time: 2.27s
Barrier statistics:
Free vars : 13123
AA’ NZ : 2.447e+06
Factor NZ : 2.487e+07 (roughly 300 MBytes of memory)
Factor Ops : 2.020e+10 (less than 1 second per iteration)
Threads : 4
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 5.31103232e+12 0.00000000e+00 1.00e+03 1.00e+03 2.92e+07 6s
1 2.94021421e+12 -6.28341116e+06 5.53e+02 5.98e+02 1.62e+07 7s
2 1.63593851e+12 -1.04045196e+07 3.07e+02 3.33e+02 8.98e+06 8s
3 9.17914136e+11 -1.27026751e+07 1.73e+02 1.84e+02 5.04e+06 9s
4 5.21393346e+11 -1.39332564e+07 9.80e+01 1.01e+02 2.86e+06 10s
5 3.01453928e+11 -1.46379752e+07 5.67e+01 5.58e+01 1.65e+06 11s
6 1.16105621e+11 -2.46667727e+07 2.18e+01 2.13e+01 6.37e+05 13s
7 6.41228230e+10 -2.38741888e+07 1.20e+01 1.17e+01 3.52e+05 14s
8 3.00202717e+10 -2.20877231e+07 5.63e+00 5.47e+00 1.65e+05 15s
9 1.47280765e+10 -1.80875453e+07 2.76e+00 2.68e+00 8.07e+04 17s
10 7.11104800e+09 -1.21923987e+07 1.33e+00 1.29e+00 3.89e+04 18s
11 3.49823039e+09 -8.01899284e+06 6.56e-01 6.35e-01 1.92e+04 19s
12 1.72669006e+09 -4.59147285e+06 3.24e-01 3.13e-01 9.45e+03 20s
13 8.52357323e+08 -2.40260413e+06 1.60e-01 1.54e-01 4.66e+03 21s
14 4.68891888e+08 -1.34426274e+06 8.79e-02 8.49e-02 2.56e+03 22s
15 2.57934752e+08 -7.49140709e+05 4.83e-02 4.71e-02 1.41e+03 24s
16 1.41882790e+08 -4.14589365e+05 2.66e-02 2.60e-02 7.75e+02 25s
17 7.88402683e+07 -2.28068307e+05 1.48e-02 1.43e-02 4.31e+02 26s
18 4.40658229e+07 -1.25446936e+05 8.26e-03 7.86e-03 2.41e+02 27s
19 2.47326240e+07 -6.90027918e+04 4.63e-03 4.32e-03 1.35e+02 28s
20 1.40796072e+07 -3.79614596e+04 2.64e-03 2.38e-03 7.69e+01 29s
21 8.00988743e+06 -2.10094495e+04 1.50e-03 1.31e-03 4.37e+01 31s
22 4.53369056e+06 -1.17471122e+04 8.49e-04 7.18e-04 2.47e+01 32s
23 2.58769063e+06 -6.63132293e+03 4.85e-04 3.95e-04 1.41e+01 33s
24 1.47079169e+06 -3.88174839e+03 2.75e-04 2.17e-04 8.03e+00 34s
25 8.30466156e+05 -2.48690039e+03 1.56e-04 1.19e-04 4.53e+00 36s
26 4.68216262e+05 -1.57471146e+03 8.77e-05 6.55e-05 2.56e+00 38s
27 2.64246961e+05 -9.82972233e+02 4.95e-05 3.60e-05 1.44e+00 39s
28 1.49498276e+05 -6.02999328e+02 2.80e-05 1.98e-05 8.17e-01 41s
29 8.46881053e+04 -3.66623604e+02 1.58e-05 1.09e-05 4.63e-01 42s
30 4.80125265e+04 -2.16561709e+02 8.98e-06 5.97e-06 2.63e-01 44s
31 2.73632512e+04 -1.33201870e+02 5.12e-06 3.45e-06 1.50e-01 45s
32 1.55958528e+04 -8.31709831e+01 2.92e-06 1.96e-06 8.54e-02 46s
33 8.88043456e+03 -5.40053330e+01 1.66e-06 1.11e-06 4.86e-02 47s
34 5.04602942e+03 -3.72030147e+01 9.45e-07 6.38e-07 2.77e-02 48s
35 2.88456615e+03 -2.73136625e+01 5.41e-07 3.71e-07 1.59e-02 49s
36 1.64271383e+03 -2.15402870e+01 3.09e-07 2.49e-07 9.06e-03 51s
37 9.33517206e+02 -1.77644547e+01 1.76e-07 3.02e-07 5.18e-03 52s
38 5.30229901e+02 -1.54622460e+01 1.01e-07 3.98e-07 2.97e-03 54s
39 2.99676840e+02 -1.41400727e+01 5.82e-08 5.42e-07 1.71e-03 55s
40 1.67483864e+02 -1.33193826e+01 3.35e-08 7.78e-07 9.84e-04 56s
41 9.00105652e+01 -1.28314226e+01 1.91e-08 9.64e-07 5.60e-04 58s
42 4.61754946e+01 -1.25261460e+01 1.09e-08 1.24e-06 3.20e-04 59s
43 2.16145275e+01 -1.23519813e+01 6.42e-09 1.80e-06 1.85e-04 61s
44 7.39854143e+00 -1.22531093e+01 3.81e-09 2.33e-06 1.07e-04 62s
45 -7.14882386e-01 -1.21886796e+01 2.37e-09 3.26e-06 6.25e-05 63s
46 -5.50172481e+00 -1.21518946e+01 1.56e-09 4.31e-06 3.62e-05 65s
47 -8.28516903e+00 -1.21300461e+01 1.10e-09 5.07e-06 2.09e-05 67s
48 -9.89394552e+00 -1.21177678e+01 9.89e-10 7.15e-06 1.21e-05 68s
49 -1.08212723e+01 -1.21101085e+01 1.01e-09 1.06e-05 7.02e-06 69s
50 -1.14730399e+01 -1.21046917e+01 1.11e-09 1.97e-05 3.44e-06 70s
51 -1.17872350e+01 -1.21020816e+01 1.83e-09 7.52e-05 1.71e-06 72s
52 -1.19359224e+01 -1.21008080e+01 2.72e-09 3.39e-04 8.98e-07 74s
53 -1.20052694e+01 -1.21002431e+01 4.03e-09 9.92e-04 5.17e-07 75s
54 -1.20456887e+01 -1.20998957e+01 4.57e-09 2.96e-03 2.95e-07 76s
55 -1.20682772e+01 -1.20997076e+01 6.15e-09 7.83e-03 1.71e-07 77s
56 -1.20875051e+01 -1.20996120e+01 9.09e-09 2.22e-02 6.59e-08 79s
57 -1.20958395e+01 -1.20995996e+01 1.70e-08 2.22e-02 2.05e-08 81s
58 -1.20985701e+01 -1.20995947e+01 1.69e-08 3.36e-02 5.58e-09 82s
59 -1.20991751e+01 -1.20995935e+01 2.58e-07 3.66e-02 2.28e-09 84s
60 -1.20992926e+01 -1.20995932e+01 2.04e-07 4.46e-02 1.64e-09 86s
61 -1.20993564e+01 -1.20995929e+01 1.14e-07 4.43e-02 1.29e-09 87s
62 -1.20993865e+01 -1.20995928e+01 7.83e-07 4.76e-02 1.13e-09 89s
63 -1.20993902e+01 -1.20995927e+01 6.39e-07 5.39e-02 1.11e-09 91s
64 -1.20993940e+01 -1.20995926e+01 1.27e-06 6.78e-02 1.08e-09 93s
65 -1.20994132e+01 -1.20995925e+01 1.29e-06 6.74e-02 9.79e-10 94s
66 -1.20994165e+01 -1.20995925e+01 1.60e-06 9.49e-02 9.60e-10 96s
67 -1.20994181e+01 -1.20995924e+01 1.61e-06 1.25e-01 9.51e-10 98s
68 -1.20994262e+01 -1.20995923e+01 1.50e-06 1.42e-01 9.07e-10 100s
69 -1.20994266e+01 -1.20995923e+01 1.62e-06 1.70e-01 9.06e-10 102s
70 -1.20994267e+01 -1.20995922e+01 1.63e-06 1.35e-01 9.05e-10 104s
71 -1.20994266e+01 -1.20995922e+01 1.53e-06 3.41e-01 9.05e-10 105s
72 -1.20994263e+01 -1.20995922e+01 1.55e-06 3.02e-01 9.05e-10 107s
73 -1.20994263e+01 -1.20995922e+01 1.58e-06 2.49e-01 9.05e-10 108s
74 -1.20994261e+01 -1.20995922e+01 1.53e-06 2.16e-01 9.05e-10 109s
75 -1.20994263e+01 -1.20995922e+01 1.76e-06 3.56e-01 9.05e-10 112s
Barrier performed 75 iterations in 111.58 seconds
Sub-optimal termination - objective -1.20456887e+01
Gurobi optimizer, licensed to CVX for CVX
Academic license - for non-commercial use only
Warning for adding variables: zero or small (< 1e-13) coefficients, ignored
Optimize a model with 131222 rows, 209958 columns and 727360 nonzeros
Model has 52488 quadratic constraints
Coefficient statistics:
Matrix range [6e-03, 1e+06]
QMatrix range [1e+00, 1e+00]
Objective range [2e-01, 1e+00]
Bounds range [0e+00, 0e+00]
RHS range [1e+00, 1e+00]
Presolve removed 13124 rows and 26249 columns
Presolve time: 1.86s
Presolved: 118098 rows, 183709 columns, 687990 nonzeros
Presolved model has 52488 second-order cone constraints
Ordering time: 2.31s
Barrier statistics:
Free vars : 13123
AA’ NZ : 2.447e+06
Factor NZ : 2.487e+07 (roughly 300 MBytes of memory)
Factor Ops : 2.020e+10 (less than 1 second per iteration)
Threads : 4
Objective Residual
Iter Primal Dual Primal Dual Compl Time
0 5.31103260e+12 0.00000000e+00 1.00e+03 1.00e+03 2.92e+07 6s
1 1.85577450e+12 -1.02767997e+07 3.49e+02 3.43e+02 1.02e+07 6s
2 7.52789913e+11 -1.34683082e+07 1.42e+02 1.34e+02 4.13e+06 7s
3 3.84286936e+11 -1.44944889e+07 7.22e+01 6.43e+01 2.11e+06 8s
4 2.23944140e+11 -1.52295781e+07 4.21e+01 3.53e+01 1.23e+06 9s
5 8.70358170e+10 -2.62529309e+07 1.63e+01 1.35e+01 4.77e+05 11s
6 3.08379115e+10 -2.27319234e+07 5.79e+00 4.77e+00 1.69e+05 12s
7 9.85144688e+09 -1.49278903e+07 1.85e+00 1.52e+00 5.40e+04 13s
8 5.41945813e+09 -8.50857094e+06 1.02e+00 8.35e-01 2.96e+04 14s
9 2.98131874e+09 -5.65094099e+06 5.59e-01 4.59e-01 1.63e+04 15s
10 1.64008137e+09 -3.43285157e+06 3.08e-01 2.52e-01 8.96e+03 16s
11 9.02167117e+08 -1.97186917e+06 1.69e-01 1.39e-01 4.93e+03 17s
12 4.96249492e+08 -1.10207235e+06 9.30e-02 7.61e-02 2.71e+03 18s
13 2.72957562e+08 -6.09143545e+05 5.12e-02 4.18e-02 1.49e+03 19s
14 1.50131803e+08 -3.35352878e+05 2.81e-02 2.30e-02 8.19e+02 20s
15 8.40541005e+07 -1.84426739e+05 1.58e-02 1.26e-02 4.59e+02 21s
16 4.78499263e+07 -1.01438249e+05 8.97e-03 6.94e-03 2.61e+02 22s
17 2.75539531e+07 -5.61241309e+04 5.17e-03 3.82e-03 1.50e+02 23s
18 1.57451467e+07 -3.28056429e+04 2.95e-03 2.10e-03 8.59e+01 24s
19 8.81144050e+06 -2.01311886e+04 1.65e-03 1.15e-03 4.81e+01 26s
20 4.86544535e+06 -1.23096395e+04 9.12e-04 6.33e-04 2.66e+01 27s
21 2.68179188e+06 -7.24892329e+03 5.02e-04 3.48e-04 1.46e+01 28s
22 1.50457379e+06 -4.23139151e+03 2.82e-04 1.99e-04 8.21e+00 29s
23 8.52453015e+05 -2.42114457e+03 1.60e-04 1.09e-04 4.65e+00 30s
24 4.81580289e+05 -1.39857272e+03 9.02e-05 6.00e-05 2.63e+00 32s
25 2.71477604e+05 -7.97120505e+02 5.08e-05 3.29e-05 1.48e+00 33s
26 1.53267323e+05 -4.57565427e+02 2.87e-05 1.81e-05 8.37e-01 34s
27 8.63978387e+04 -2.65760465e+02 1.62e-05 9.95e-06 4.72e-01 36s
28 4.90366917e+04 -1.56463426e+02 9.18e-06 5.47e-06 2.68e-01 37s
29 2.79044053e+04 -9.49753714e+01 5.23e-06 3.00e-06 1.52e-01 38s
30 1.58614725e+04 -5.93481405e+01 2.97e-06 1.65e-06 8.67e-02 40s
31 8.96596311e+03 -3.96068570e+01 1.68e-06 9.15e-07 4.90e-02 41s
32 5.05815632e+03 -2.81979824e+01 9.49e-07 5.22e-07 2.77e-02 43s
33 2.88109944e+03 -2.14520521e+01 5.41e-07 2.90e-07 1.58e-02 44s
34 1.63123094e+03 -1.74881931e+01 3.08e-07 3.45e-07 8.98e-03 46s
35 9.21369471e+02 -1.52866857e+01 1.75e-07 4.51e-07 5.10e-03 47s
36 5.19270734e+02 -1.39837898e+01 9.94e-08 6.11e-07 2.90e-03 48s
37 2.90238076e+02 -1.32184552e+01 5.66e-08 8.06e-07 1.65e-03 49s
38 1.60322060e+02 -1.27600722e+01 3.23e-08 1.02e-06 9.42e-04 51s
39 8.57818467e+01 -1.24995051e+01 1.84e-08 1.44e-06 5.35e-04 52s
40 4.34519887e+01 -1.23438061e+01 1.06e-08 1.77e-06 3.04e-04 53s
41 1.92966017e+01 -1.22475780e+01 6.09e-09 2.22e-06 1.72e-04 55s
42 5.66401577e+00 -1.21911047e+01 3.62e-09 3.08e-06 9.72e-05 56s
43 -2.04844977e+00 -1.21569146e+01 2.25e-09 4.04e-06 5.50e-05 58s
44 -6.39108721e+00 -1.21346963e+01 1.56e-09 5.58e-06 3.13e-05 59s
45 -8.86636398e+00 -1.21204645e+01 1.21e-09 7.03e-06 1.77e-05 61s
46 -1.02481223e+01 -1.21118219e+01 1.16e-09 1.07e-05 1.01e-05 62s
47 -1.10340569e+01 -1.21066910e+01 1.27e-09 1.49e-05 5.84e-06 64s
48 -1.14858088e+01 -1.21036709e+01 1.52e-09 3.76e-05 3.36e-06 65s
49 -1.17507788e+01 -1.21019743e+01 1.80e-09 8.97e-05 1.91e-06 66s
50 -1.19513662e+01 -1.21005647e+01 2.01e-09 2.71e-04 8.12e-07 68s
51 -1.20218600e+01 -1.21000293e+01 5.26e-09 1.45e-03 4.26e-07 69s
52 -1.20547953e+01 -1.20997855e+01 6.51e-09 7.84e-03 2.45e-07 71s
53 -1.20737182e+01 -1.20996401e+01 7.08e-09 1.53e-02 1.41e-07 72s
54 -1.20899016e+01 -1.20995867e+01 1.87e-08 1.98e-02 5.27e-08 73s
55 -1.20967458e+01 -1.20995784e+01 1.97e-07 3.08e-02 1.54e-08 75s
56 -1.20987603e+01 -1.20995765e+01 5.67e-08 3.08e-02 4.46e-09 76s
57 -1.20992175e+01 -1.20995758e+01 5.95e-07 3.52e-02 1.97e-09 78s
58 -1.20993143e+01 -1.20995757e+01 8.20e-07 3.55e-02 1.44e-09 79s
59 -1.20993484e+01 -1.20995755e+01 7.07e-07 5.29e-02 1.26e-09 81s
60 -1.20993874e+01 -1.20995753e+01 3.68e-07 5.25e-02 1.04e-09 84s
61 -1.20994000e+01 -1.20995752e+01 6.80e-07 5.55e-02 9.73e-10 86s
62 -1.20994025e+01 -1.20995752e+01 1.09e-06 5.46e-02 9.58e-10 88s
63 -1.20994084e+01 -1.20995751e+01 9.46e-07 6.70e-02 9.27e-10 89s
64 -1.20994107e+01 -1.20995751e+01 1.00e-06 9.22e-02 9.15e-10 91s
65 -1.20994173e+01 -1.20995750e+01 1.44e-06 8.15e-02 8.78e-10 93s
66 -1.20994178e+01 -1.20995749e+01 9.48e-07 2.11e-01 8.75e-10 95s
67 -1.20994184e+01 -1.20995749e+01 9.18e-07 1.72e-01 8.72e-10 97s
68 -1.20994196e+01 -1.20995748e+01 1.05e-06 2.84e-01 8.63e-10 99s
69 -1.20994224e+01 -1.20995747e+01 2.18e-06 3.13e-01 8.48e-10 101s
70 -1.20994237e+01 -1.20995746e+01 2.00e-06 2.59e-01 8.42e-10 103s
71 -1.20994245e+01 -1.20995745e+01 2.14e-06 3.80e-01 8.37e-10 106s
72 -1.20994247e+01 -1.20995744e+01 1.41e-06 8.86e-01 8.35e-10 109s
73 -1.20994248e+01 -1.20995744e+01 1.93e-06 8.93e-01 8.34e-10 110s
Barrier solved model in 73 iterations and 110.13 seconds
Optimal objective -1.20992175e+01
I have lower the size of the optimization problem. ideally, the size of the problem would be larger.
Thanks for your help!
Formulation 2 solver log says "Sub-optimal termination ",. So apparently the solver, Gurobi, encountered (numerical) difficulty. The coefficient range of 6e-03 to 1e±06 is rather wide in magnotude, and may be substantially contributing to numerical difficulty of the solver. Your calculations involving variants of things called epsilon appear rather suspicious, as likely contributors to this wide range of coefficient magnitudes.
I suggest you reexamine your model, and try to improve the scaling such that all input data to the model is either exactly zero or much closer to one in magnitude.
Formulation one has the same range of coefficient values as formulation 2, but perhaps the solver is able to report success by being lucky, maybe due to such a thing as the constraints or variables being in a different order, or as a result of any other differences in presentation by CVX to the solver of what are equivalent models in exact arithmetic.
If you have access to Mosek, it may be worth trying that as well. But you should try to improve scaling in any event.
Thanks! I will try the rescaling idea.
May I also ask is there any way I can obtain some numerical evaluation of my optimal value (like at least how far from the optimal)?
If you use Mosek, perhaps some of the Mosek guys who read this forum can offer some guidance.
Got it! Thanks Mark. I will update you how it goes.