Objective function affects feasibility

1

Dear experts,
I am new with CVX and cannot understand the point:

cvx_begin sdp 
variable alpha(20,1)
minimize sum(alpha)+sum_square(alpha)
diag(alpha) >= B
cvx_end

This simple SDP model (I enclose matrix B below) shows Infeasible status when solved by SeDuMi under low precision and by SDPT3 under low and high precision (Inaccurate/Solved for SeDuMi under high precision).

When the objective function is changed to “minimize sum(alpha)” or the feasibility problem is considered, the status is Solved in all cases. Why does the objective function affect feasibility?

B is

-80,4761485955042 -29,5748607748623 29,3372357331135 23,1204513942210 -87,3323282888696 -135,202388421630 -397,174052587854 -25,0118322817781 -68,9220732243511 -464,408261445729 354,436277014027 -32,6210091306378 737,772968912729 -40,7270370532508 -43,7270434537630 4,27294747612693 -36,7270631471949 -34,7270819309761 -28,2493957342700 -47,2493989794566
-29,5748607748623 -19,4612892475974 1210,13693658537 1316,95616088984 145,997218269826 4,44844994982859 -424,869196192798 146,663066146686 70,1893695905364 417,227306683108 54,3930231232374 1226,29621493700 44,2756880428884 206,275685109065 1219,27568196156 2151,77567750125 102,775672277136 1153,27566304005 149,264690029108 -23,2353115667414
29,3372357331135 1210,13693658537 -94,4049585776183 -84,8919616271516 375,458816712899 532,694409198063 -869,027416764657 719,222853978773 292,020436378185 225,249046624667 313,090918595099 319,761956170420 266,348961468383 1272,34895500670 142,348948074382 396,348938250654 693,848926744659 536,348906400168 693,324738583861 -51,1752649309627
23,1204513942210 1316,95616088984 -84,8919616271516 -76,3375701603701 392,055124234730 449,406143506336 -743,195235945942 757,893322978464 269,134039310842 337,923277544196 187,650409777138 317,296997753149 238,503348281279 1269,50334247073 206,503336236965 802,003327403153 506,003317056595 638,503298762177 638,981566287893 -46,0184368727489
-87,3323282888696 145,997218269826 375,458816712899 392,055124234730 -152,639076401054 -4,18885894175847 -835,315247888661 617,425105832689 314,307955443979 4422,71615234540 51,6602195330760 712,108618884869 220,458594503794 -33,5414137125955 -32,5414225274268 477,958564981153 232,458550350638 93,9585244814797 334,927793751752 -65,0722107175426
-135,202388421630 4,44844994982859 532,694409198063 449,406143506336 -4,18885894175847 -309,036202004281 -958,078724065159 780,979573823801 7,84300331362681 7070,19909629300 -61,8702234704563 636,731055964564 234,453130765985 -56,5468809250466 -62,5468934675959 427,953088758467 143,953067940830 1,45303113182250 239,409304634772 -92,5907017245495
-397,174052587854 -424,869196192798 -869,027416764657 -743,195235945942 -835,315247888661 -958,078724065159 -12355,9105214192 -1196,73493200854 -911,917618688801 -9045,98150781726 -548,996631399145 -741,232522450841 702,313322917668 -565,186751006344 -560,686830314621 -461,186942701689 -550,687074334490 -529,687307082946 14007,0362042176 -585,463835993231
-25,0118322817781 146,663066146686 719,222853978773 757,893322978464 617,425105832689 780,979573823801 -1196,73493200854 -154,516449356202 -31,8584266433906 770,126739966631 -1,54352369648362 276,986996571434 249,059830935245 42,5598226684816 45,5598137996073 423,559801231603 108,559786511389 93,5597604836297 828,028841346297 1555,02883684960
-68,9220732243511 70,1893695905364 292,020436378185 269,134039310842 314,307955443979 7,84300331362681 -911,917618688801 -31,8584266433906 -77,3980086116821 1499,66220700640 -73,8106741065346 458,800686602646 34,1849703833048 4,18496453253449 -13,8150417443774 185,184949360665 118,184938942491 120,184920521443 153,163037620134 -46,3369655623850
-464,408261445729 417,227306683108 225,249046624667 337,923277544196 4422,71615234540 7070,19909629300 -9045,98150781726 770,126739966631 1499,66220700640 -7567,92000066924 -425,995424326623 -440,931329272520 601,021258878684 461,521201024281 -205,978861043955 -94,4789490003119 36,0209479812381 52,5207658276643 6522,30438026823 -458,195651201595
354,436277014027 54,3930231232374 313,090918595099 187,650409777138 51,6602195330760 -61,8702234704563 -548,996631399145 -1,54352369648362 -73,8106741065346 -425,995424326623 -252,552035184705 -17,9198241941512 196,837181949189 35,8371713804397 -40,6628399580857 357,337143974189 -24,1628748450555 33,3370918794234 272,797562914294 -83,7024428345629
-32,6210091306378 1226,29621493700 319,761956170420 317,296997753149 712,108618884869 636,731055964564 -741,232522450841 276,986996571434 458,800686602646 -440,931329272520 -17,9198241941512 -67,3498058742369 104,795873714524 1391,79586825674 305,795862401438 50,7958541039400 614,795844385537 503,295827201800 641,775414138493 -43,2245888302618
737,772968912729 44,2756880428884 266,348961468383 238,503348281279 220,458594503794 234,453130765985 702,313322917668 249,059830935245 34,1849703833048 601,021258878684 196,837181949189 104,795873714524 -27,7149503827362 3,28504611615824 4,78504236004920 208,785037037300 44,7850308030558 21,2850197798864 526,771925034422 -27,7280768700001
-40,7270370532508 206,275685109065 1272,34895500670 1269,50334247073 -33,5414137125955 -56,5468809250466 -565,186751006344 42,5598226684816 4,18496453253449 461,521201024281 35,8371713804397 1391,79586825674 3,28504611615824 -27,7149573849478 1680,28503885894 2625,28503353619 193,285027301948 182,285016278777 31,7719215316582 -27,7280803727639
-43,7270434537630 1219,27568196156 142,348948074382 206,503336236965 -32,5414225274268 -62,5468934675959 -560,686830314621 45,5598137996073 -13,8150417443774 -205,978861043955 -40,6628399580857 305,795862401438 4,78504236004920 1680,28503885894 -27,7149648971673 472,785029780082 580,285023545836 6012,28501252266 23,2719177737704 -27,7280841306519
4,27294747612693 2151,77567750125 396,348938250654 802,003327403153 477,958564981153 427,953088758467 -461,186942701689 423,559801231603 185,184949360665 -94,4789490003119 357,337143974189 50,7958541039400 208,785037037300 2625,28503353619 472,785029780082 -27,7149755426699 966,785018223083 1562,28500719991 436,271912448500 -27,7280894559223
-36,7270631471949 102,775672277136 693,848926744659 506,003317056595 232,458550350638 143,953067940830 -550,687074334490 108,559786511389 118,184938942491 36,0209479812381 -24,1628748450555 614,795844385537 44,7850308030558 193,285027301948 580,285023545836 966,785018223083 -27,7149880111650 424,285000965658 201,771906211304 -27,7280956931190
-34,7270819309761 1153,27566304005 536,348906400168 638,503298762177 93,9585244814797 1,45303113182250 -529,687307082946 93,5597604836297 120,184920521443 52,5207658276643 33,3370918794234 503,295827201800 21,2850197798864 182,285016278777 6012,28501252266 1562,28500719991 424,285000965658 -27,7150100575232 52,2718951829146 -27,7281067215093
-28,2493957342700 149,264690029108 693,324738583861 638,981566287893 334,927793751752 239,409304634772 14007,0362042176 828,028841346297 153,163037620134 6522,30438026823 272,797562914294 641,775414138493 526,771925034422 31,7719215316582 23,2719177737704 436,271912448500 201,771906211304 52,2718951829146 -27,7412057636462 -27,7412076689699
-47,2493989794566 -23,2353115667414 -51,1752649309627 -46,0184368727489 -65,0722107175426 -92,5907017245495 -585,463835993231 1555,02883684960 -46,3369655623850 -458,195651201595 -83,7024428345629 -43,2245888302618 -27,7280768700001 -27,7280803727639 -27,7280841306519 -27,7280894559223 -27,7280956931190 -27,7281067215093 -27,7412076689699 -27,7412095742936
3

Note: I changed the commas to periods in the input for B. I used the version of B in your surviving, now edited, original post (there was another post which was held up for moderator review, but I am guessing you edited your original post, and that edited version superseded the other post, which I have deleted).

The problem as provided is poorly scaled numerically when the sum_sq term is included in the objective. Even though in exact arithmetic the objective function doesn’t affect feasibility, in practice, due to presolve or otherwise, solver feasibility determination can be affected by the objective function, especially on poorly scaled problems.

Given that I got feasible alpha with elements of the order of magnitude 1e4 for the feasibility problem, I solved the problem by rescaling alpha as 1e4*alphaa = alpha (CVX didn’t want me to use the variable name alpha, anyhow). This converts the objective function to 1e4*sum(alphaa)+1e8*sum_square(alphaa) . To further improve scaling, I divided the objective by 1e4, although this turned out to be unnecessary.

cvx_begin sdp 
variable alphaa(20,1)
minimize(sum(alphaa)+1e4*sum_square(alphaa))
diag(alphaa) >= B/1e4
cvx_end

Calling SDPT3 4.0: 232 variables, 21 equality constraints
   For improved efficiency, SDPT3 is solving the dual problem.
------------------------------------------------------------

 num. of constraints = 21
 dim. of sdp    var  = 20,   num. of sdp  blk  =  1
 dim. of socp   var  = 22,   num. of socp blk  =  1
*******************************************************************
   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|8.9e+01|9.8e+00|8.0e+07| 0.000000e+00  0.000000e+00| 0:0:00| chol  1  1 
 1|0.400|0.447|5.4e+01|5.7e+00|5.7e+07| 5.335143e+05 -1.353711e+06| 0:0:00| chol  1  1 
 2|0.417|0.520|3.1e+01|2.8e+00|3.8e+07| 1.754183e+06 -3.530081e+06| 0:0:00| chol  1  1 
 3|0.591|0.745|1.3e+01|8.2e-01|1.8e+07| 3.171271e+06 -4.461389e+06| 0:0:00| chol  1  1 
 4|1.000|1.000|5.7e-08|6.3e-02|4.7e+06| 2.499103e+06 -1.968006e+06| 0:0:00| chol  1  1 
 5|0.457|1.000|3.1e-08|3.1e-02|3.6e+06| 7.795588e+05 -2.819519e+06| 0:0:00| chol  1  1 
 6|1.000|0.844|1.6e-08|1.8e-02|1.1e+06| 5.434330e+05 -5.056854e+05| 0:0:00| chol  1  1 
 7|0.839|0.858|3.1e-09|9.3e-03|2.4e+05| 1.859508e+04 -2.163551e+05| 0:0:00| chol  1  1 
 8|0.626|0.880|1.2e-09|4.6e-03|1.1e+05|-7.703322e+04 -1.891507e+05| 0:0:00| chol  1  1 
 9|1.000|0.828|4.2e-11|2.4e-03|3.1e+04|-1.252073e+05 -1.551975e+05| 0:0:00| chol  1  1 
10|0.931|0.905|2.9e-12|1.1e-03|3.0e+03|-1.454865e+05 -1.479455e+05| 0:0:00| chol  1  1 
11|0.955|0.963|1.3e-13|5.1e-04|2.9e+02|-1.474173e+05 -1.474728e+05| 0:0:00| chol  1  1 
12|0.941|0.954|1.2e-14|2.6e-04|1.9e+01|-1.476450e+05 -1.475481e+05| 0:0:00| chol  1  1 
13|0.897|0.927|1.1e-12|1.9e-05|2.5e+00|-1.476594e+05 -1.476535e+05| 0:0:00| chol  1  1 
14|0.804|1.000|1.9e-12|1.0e-12|5.4e-01|-1.476610e+05 -1.476615e+05| 0:0:00| chol  1  1 
15|0.969|1.000|2.3e-12|1.0e-12|2.4e-02|-1.476615e+05 -1.476615e+05| 0:0:00| chol  1  1 
16|0.939|0.995|1.2e-12|1.0e-12|1.4e-03|-1.476615e+05 -1.476615e+05| 0:0:00|
  stop: max(relative gap, infeasibilities) < 1.49e-08
-------------------------------------------------------------------
 number of iterations   = 16
 primal objective value = -1.47661493e+05
 dual   objective value = -1.47661494e+05
 gap := trace(XZ)       = 1.43e-03
 relative gap           = 4.84e-09
 actual relative gap    = 4.84e-09
 rel. primal infeas (scaled problem)   = 1.23e-12
 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.5e+05, 8.7e+00, 1.2e+01
 norm(A), norm(b), norm(C) = 7.5e+00, 2.0e+04, 4.6e+00
 Total CPU time (secs)  = 0.18  
 CPU time per iteration = 0.01  
 termination code       =  0
 DIMACS: 1.2e-12  0.0e+00  1.9e-12  0.0e+00  4.8e-09  4.8e-09
-------------------------------------------------------------------
 
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +137659
 
>> disp(alphaa)
   0.061181480851997
   0.961348201553588
   0.797729794606017
   0.831649649483347
   0.891014474456778
   1.054390475703228
   1.016859738289154
   0.728243941432959
   0.540044715792631
   1.201587458773255
   0.163939441351838
   0.751633596342568
   0.314819667500721
   0.956411061490104
   1.054443111047675
   1.037126175754440
   0.626187215339680
   1.107425971658949
   0.923023822905204
   0.198485997299390

Undoing the scaling, the optimal objective value = 1.37659e+09, which i is huge. And that is the cvx_optval for this version

cvx_begin sdp 
variable alphaa(20,1)
minimize(1e4*sum(alphaa)+1e8*sum_square(alphaa))
diag(alphaa) >= B/1e4
cvx_end

Either version with either solver, produces the same solution, within tolerance.

Multiply the optimal alphaa by 1e4 to recover the optimal alpha.

4

Mark, thank you for the comprehensive answer. I could not even imagine that modern solvers were such sensitive to scaling.