QP problem infeasible

Mingxi_Liu · February 27, 2019, 11:35pm

I was trying to solve a very simple QP problem, however encountered infeasible issues. Below I attached the code.

The interesting thing is if I change the objective function from minimize (x’Hx+p*x) to minimize (norm(x)), the problem can be solved. Any idea of this?

clear all
close all
clc

H=[2.27348224441650,-0.00117286389833350,-0.00109341693417775,0.000525651695935969,-0.00291951592982850,-0.00802439502739480,-0.0114214153882029,-0.0114620136996767,-0.00845190795382778;...
    -0.00117286389833388,3.56239456159405,0.0398547487807126,0.0328171924298543,0.0299758081507038,0.0123217494092350,-0.00901074350081043,-0.0237237606826626,-0.0270802505403330;...
    -0.00109341693417792,0.0398547487807124,7.42913142321275,0.162937514595914,0.134548945141430,0.118326196608746,0.0580454993729156,-0.0119697594207837,-0.0606306755382558;...
    0.000525651695935912,0.0328171924298543,0.162937514595915,19.0293416281818,0.532185506903310,0.439743884792902,0.383377020153317,0.195216554687546,-0.0208466825418427;...
    -0.00291951592982837,0.0299758081507038,0.134548945141430,0.532185506903311,53.8299706380636,1.63992819461429,1.35532735815322,1.17852804655466,0.606728898544638;...
    -0.00802439502739478,0.0123217494092349,0.118326196608746,0.439743884792902,1.63992819461430,158.231850886465,4.96315081082055,4.10207209308923,3.56397502386629;...
    -0.0114214153882030,-0.00901074350081046,0.0580454993729158,0.383377020153317,1.35532735815321,4.96315081082053,471.437462980860,14.9327956461337,12.3422822781181;...
    -0.0114620136996768,-0.0237237606826627,-0.0119697594207840,0.195216554687545,1.17852804655466,4.10207209308921,14.9327956461338,1411.05417821418,44.8416329206889;...
    -0.00845190795382779,-0.0270802505403330,-0.0606306755382552,-0.0208466825418400,0.606728898544646,3.56397502386630,12.3422822781181,44.8416329206888,4229.90381247754];

p=[-0.305793573917451,1.91905584131655,3.19068549918678,4.37515748927000,4.70401769642371,3.96622856939228,2.49644394347549,0.890028616139999,-0.315944243461946];

A=[0.435600000000000,0,0,0,0,0,0,0,0;...
    -0.259036070725624,0.435600000000000,0,0,0,0,0,0,0;...
    -0.305463292084454,-0.259036070725624,0.435600000000000,0,0,0,0,0,0;...
    -0.217756731595858,-0.305463292084454,-0.259036070725624,0.435600000000000,0,0,0,0,0;...
    -0.137485208103031,-0.217756731595858,-0.305463292084454,-0.259036070725624,0.435600000000000,0,0,0,0;...
    -0.0854903739189647,-0.137485208103031,-0.217756731595858,-0.305463292084454,-0.259036070725624,0.435600000000000,0,0,0;...
    -0.0545735124757641,-0.0854903739189647,-0.137485208103031,-0.217756731595858,-0.305463292084454,-0.259036070725624,0.435600000000000,0,0;...
    -0.0360507198086653,-0.0545735124757641,-0.0854903739189647,-0.137485208103031,-0.217756731595858,-0.305463292084454,-0.259036070725624,0.435600000000000,0;...
    -0.0244407393687872,-0.0360507198086653,-0.0545735124757641,-0.0854903739189646,-0.137485208103031,-0.217756731595858,-0.305463292084454,-0.259036070725624,0.435600000000000];

b=[-44.4556031581127;-38.4931452767985;-25.0186511927410;-14.5856920501390;-7.92139179179135;-3.83162376690024;-1.27144478051163;0.392968382581787;1.51075798786650];

cvx_begin
variable x(9)
minimize (x'*H*x+p*x)
%minimize (norm(x))
subject to
A*x<=b
cvx_end

Mark_L_Stone · February 28, 2019, 12:18am

I’d say that SDPT3 is not very robust. SeDuMi handled this o.k.

The following was found to be feasible with SDPT3: There is indeed a solution slack = zeros(9,1) and x = A\b, as there must be because A is non-singular.

cvx_begin
variable x(9) 
variable slack(9) nonnegative
minimize (norm(slack))
subject to
A*x + slack == b
cvx_end

Mingxi_Liu · February 28, 2019, 2:00am

Thanks Mark!

Does this necessarily mean the unique solution to the original problem x’Hx+px is A\b?

I’m recursively solving such problems for stochastic MPC. Using SeDuMi can bypass some problems (e.g., the one I posted) but sill failed in some.

Mark_L_Stone · February 28, 2019, 2:46am

X = A\b is feasible if the only constraint is A*x <= b for this particular value of A. But it is not the unique feasible solution. In fact, the feasible space is unbounded for this A and b.

This may not apply for other A and b.

You can perhaps improve the numerics for the solver by reformulating the quadratic using norm via rotated lorentz, as described in section 3,.2.3 Convex quadratic sets of the MOSEK Modeling Cookbook 3.1 https://docs.mosek.com/modeling-cookbook/cqo.html … Also see http://cvxr.com/cvx/doc/advanced.html#eliminating-quadratic-forms .Condition number of chol(H) is the square root of the condition number of H, which I think is the main reason it could help.

Adapted to your problem and using CVX’s rotated_lotentz,this would be

cvx_begin
variables x(9) t
minimize (t + p*x)
subject to
{chol(H)*x,t,1} == rotated_lorentz(9)
A*x<=b
cvx_end

Unfortunately, this is reported infeasible for both SDPT3 and SeDuMi. But in reality, x = A\b with t any value >= x' * H * x is feasible, among infinitely many other solutions.

Erling · February 28, 2019, 5:32am

How do you get H? Is the original objective something like

||Fx+f||

so

H=F^TF.

Mingxi_Liu · February 28, 2019, 6:06am

I tried the rotated_lotentz by setting Gurobi as the solver. It simply gave me A\b as the solution. This solution is basically not optimal for my application use. Like you said, it would be easy to have t>=x'*H*x, leading to infinite number of solutions. The solver might have a hard time searching for that and returns with either infeasible primal or dual problem.

In general I think “unbounded” would be the problem. I will try to refine my problem formulation to make the constraint bounded and then see if the problem still exists.

Thank you Mark!

Mingxi_Liu · February 28, 2019, 6:07am

Nope, it’s not from the 2-norm form. Actually, H was obtained by recursively calculating H-K'*H*K=L until it converged, where L is positive definite. In addition, the vector p is not related to H.

Erling · February 28, 2019, 6:52am

Ok. You can also try out Mosek. It is more stable than SeDuMi in most cases. If not I would like to know.

You say minimize the norm of x is easy but not with quadratic objective. Why should not that be the case I wonder. For instance minimizing

10^{-12} x^2 + x

leads to a very large solution. Hence my small QP is illposed. Whereas the problem of minimizing the norm of x is a very nice problem.

Mingxi_Liu · February 28, 2019, 3:37pm

Thanks Erling!

I tried by setting Mosek as the solver. It still reports Infeasible. Below is the log.

I don’t think my original problem is small, but probably ill posted. BTW, what is your definition of “ill posted” in this context. I checked the eigenvalues of H, they range from 7.4 to 4231. Do you think that would be an issue?

Calling Mosek 8.0.0.60: 20 variables, 10 equality constraints
   For improved efficiency, Mosek is solving the dual problem.
------------------------------------------------------------

MOSEK Version 8.0.0.60 (Build date: 2017-3-1 13:08:15)
Copyright (c) MOSEK ApS, Denmark. WWW: mosek.com
Platform: MACOSX/64-X86

Problem
  Name                   :                 
  Objective sense        : min             
  Type                   : CONIC (conic optimization problem)
  Constraints            : 10              
  Cones                  : 1               
  Scalar variables       : 20              
  Matrix variables       : 0               
  Integer variables      : 0               

Optimizer started.
Conic interior-point optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator - tries                  : 0                 time                   : 0.00            
Lin. dep.  - tries                  : 1                 time                   : 0.00            
Lin. dep.  - number                 : 0               
Presolve terminated. Time: 0.03    
Optimizer  - threads                : 8               
Optimizer  - solved problem         : the primal      
Optimizer  - Constraints            : 10
Optimizer  - Cones                  : 1
Optimizer  - Scalar variables       : 20                conic                  : 11              
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 : 55                after factor           : 55              
Factor     - dense dim.             : 0                 flops                  : 1.16e+03        
ITE PFEAS    DFEAS    GFEAS    PRSTATUS   POBJ              DOBJ              MU       TIME  
0   4.3e+01  2.0e+00  1.0e+00  0.00e+00   0.000000000e+00   0.000000000e+00   1.0e+00  0.07  
1   1.2e+01  5.8e-01  1.6e-01  -9.61e-01  -1.477103024e+04  -1.239807234e+04  2.8e-01  0.18  
2   1.9e+00  9.0e-02  1.0e-02  -9.17e-01  -1.521790624e+05  -1.337839949e+05  4.5e-02  0.19  
3   4.3e-01  2.0e-02  1.0e-03  -1.02e+00  -8.203214330e+05  -7.270882589e+05  9.9e-03  0.19  
4   7.7e-02  3.6e-03  8.0e-05  -1.03e+00  -4.602185412e+06  -4.092154367e+06  1.8e-03  0.20  
5   2.3e-02  1.1e-03  1.3e-05  -1.01e+00  -1.534627786e+07  -1.355901597e+07  5.3e-04  0.21  
6   5.1e-03  2.4e-04  1.5e-06  -9.15e-01  -5.938465367e+07  -5.280980264e+07  1.2e-04  0.21  
7   2.1e-03  9.8e-05  4.1e-07  -8.05e-01  -1.317777723e+08  -1.175475667e+08  4.8e-05  0.22  
8   8.6e-04  4.0e-05  1.3e-07  -6.90e-01  -2.606955321e+08  -2.362378814e+08  2.0e-05  0.23  
9   6.2e-04  2.9e-05  7.3e-08  -8.49e-01  -3.475929339e+08  -3.073592514e+08  1.4e-05  0.24  
10  1.7e-04  7.9e-06  1.5e-08  -6.14e-01  -7.952656486e+08  -7.279292878e+08  3.9e-06  0.25  
11  8.3e-05  3.9e-06  5.1e-09  -6.11e-01  -1.372043837e+09  -1.226971478e+09  1.9e-06  0.25  
12  2.5e-05  1.2e-06  1.4e-09  -3.07e-01  -2.419664943e+09  -2.252133524e+09  5.7e-07  0.26  
13  1.2e-05  5.4e-07  4.7e-10  -3.64e-01  -3.934811142e+09  -3.595866314e+09  2.7e-07  0.26  
14  3.8e-06  1.8e-07  1.7e-10  4.44e-03   -5.517624836e+09  -5.238242709e+09  8.9e-08  0.27  
15  1.9e-06  8.9e-08  5.5e-11  -3.25e-01  -8.518372321e+09  -7.882735003e+09  4.4e-08  0.28  
16  5.3e-07  2.5e-08  2.0e-11  1.97e-01   -1.082937275e+10  -1.043513068e+10  1.2e-08  0.29  
17  2.1e-07  1.0e-08  5.6e-12  -1.34e-01  -1.570796250e+10  -1.491996978e+10  4.9e-09  0.30  
18  6.2e-08  2.9e-09  2.2e-12  3.91e-01   -1.798930307e+10  -1.755207597e+10  1.4e-09  0.30  
19  2.6e-08  1.2e-09  7.3e-13  5.73e-02   -2.201673410e+10  -2.133380455e+10  6.0e-10  0.31  
20  5.8e-09  2.7e-10  2.8e-13  6.47e-01   -2.313278214e+10  -2.289666973e+10  1.4e-10  0.32  
21  1.7e-09  8.2e-11  1.0e-13  5.44e-01   -2.410348688e+10  -2.395063203e+10  4.0e-11  0.32  
22  2.1e-10  9.8e-12  1.3e-14  9.05e-01   -2.423102718e+10  -2.421003436e+10  4.8e-12  0.33  
23  1.6e-10  1.1e-12  1.7e-14  9.60e-01   -2.425153769e+10  -2.424900041e+10  5.4e-13  0.34  
24  1.6e-10  1.1e-12  1.7e-14  9.90e-01   -2.425153769e+10  -2.424900041e+10  5.4e-13  0.34  
Interior-point optimizer terminated. Time: 0.35. 


MOSEK DUAL INFEASIBILITY REPORT.

Problem status: The problem is dual infeasible
Optimizer terminated. Time: 0.46    

Interior-point solution summary
  Problem status  : DUAL_INFEASIBLE
  Solution status : NEAR_DUAL_INFEASIBLE_CER
  Primal.  obj: -3.3135681203e+02   nrm: 3e+02    Viol.  con: 2e-05    var: 0e+00    cones: 0e+00  
Optimizer summary
  Optimizer                 -                        time: 0.46    
    Interior-point          - iterations : 25        time: 0.35    
      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    

Mosek error: MSK_RES_TRM_STALL ()
------------------------------------------------------------
Status: Inaccurate/Infeasible
Optimal value (cvx_optval): +Inf

Erling · February 28, 2019, 4:28pm

Now you should be careful. Mosek says your problem is dual infeasible.
The word dual is important. That means if your problem is feasible then it is unbounded.

Now if you look at the output you can see the objective value goes to minus infinity. So it seems that although the conclusion Mosek reach is strictly speaking wrong then happens for reason.

In other words you have a bad problem which behaves like the small problem I showed.

You could multiple of the identity to H to regularize the problem but since H is will conditioned according to information it has to be large I think.

Mark_L_Stone · February 28, 2019, 4:45pm

Which problem does the Mosek output correspond to? Please show us the CXV code which produced that.

Your original problem (as shown in your first post) has a positive definite objective function (H has eigenvalues ranging from 7.4268 to 4.2307e+03), so it has a unique optimal solution. That QP is not actually unbounded even though the set of feasible solutions ,A*x <= b, is unbounded.

Mingxi_Liu · February 28, 2019, 5:00pm

Hi Mark, it was generated from the following code (only the solver was changed from my original post)

clear all

close all

clc

 

H=[2.27348224441650,-0.00117286389833350,-0.00109341693417775,0.000525651695935969,-0.00291951592982850,-0.00802439502739480,-0.0114214153882029,-0.0114620136996767,-0.00845190795382778;...

-0.00117286389833388,3.56239456159405,0.0398547487807126,0.0328171924298543,0.0299758081507038,0.0123217494092350,-0.00901074350081043,-0.0237237606826626,-0.0270802505403330;...

-0.00109341693417792,0.0398547487807124,7.42913142321275,0.162937514595914,0.134548945141430,0.118326196608746,0.0580454993729156,-0.0119697594207837,-0.0606306755382558;...

0.000525651695935912,0.0328171924298543,0.162937514595915,19.0293416281818,0.532185506903310,0.439743884792902,0.383377020153317,0.195216554687546,-0.0208466825418427;...

-0.00291951592982837,0.0299758081507038,0.134548945141430,0.532185506903311,53.8299706380636,1.63992819461429,1.35532735815322,1.17852804655466,0.606728898544638;...

-0.00802439502739478,0.0123217494092349,0.118326196608746,0.439743884792902,1.63992819461430,158.231850886465,4.96315081082055,4.10207209308923,3.56397502386629;...

-0.0114214153882030,-0.00901074350081046,0.0580454993729158,0.383377020153317,1.35532735815321,4.96315081082053,471.437462980860,14.9327956461337,12.3422822781181;...

-0.0114620136996768,-0.0237237606826627,-0.0119697594207840,0.195216554687545,1.17852804655466,4.10207209308921,14.9327956461338,1411.05417821418,44.8416329206889;...

-0.00845190795382779,-0.0270802505403330,-0.0606306755382552,-0.0208466825418400,0.606728898544646,3.56397502386630,12.3422822781181,44.8416329206888,4229.90381247754];

 

p=[-0.305793573917451,1.91905584131655,3.19068549918678,4.37515748927000,4.70401769642371,3.96622856939228,2.49644394347549,0.890028616139999,-0.315944243461946];

 

A=[0.435600000000000,0,0,0,0,0,0,0,0;...

-0.259036070725624,0.435600000000000,0,0,0,0,0,0,0;...

-0.305463292084454,-0.259036070725624,0.435600000000000,0,0,0,0,0,0;...

-0.217756731595858,-0.305463292084454,-0.259036070725624,0.435600000000000,0,0,0,0,0;...

-0.137485208103031,-0.217756731595858,-0.305463292084454,-0.259036070725624,0.435600000000000,0,0,0,0;...

-0.0854903739189647,-0.137485208103031,-0.217756731595858,-0.305463292084454,-0.259036070725624,0.435600000000000,0,0,0;...

-0.0545735124757641,-0.0854903739189647,-0.137485208103031,-0.217756731595858,-0.305463292084454,-0.259036070725624,0.435600000000000,0,0;...

-0.0360507198086653,-0.0545735124757641,-0.0854903739189647,-0.137485208103031,-0.217756731595858,-0.305463292084454,-0.259036070725624,0.435600000000000,0;...

-0.0244407393687872,-0.0360507198086653,-0.0545735124757641,-0.0854903739189646,-0.137485208103031,-0.217756731595858,-0.305463292084454,-0.259036070725624,0.435600000000000];

 

b=[-44.4556031581127;-38.4931452767985;-25.0186511927410;-14.5856920501390;-7.92139179179135;-3.83162376690024;-1.27144478051163;0.392968382581787;1.51075798786650];

cvx_begin

cvx_solver mosek

variable x(9)

minimize (x'*H*x+p*x)

subject to

A*x<=b

cvx_end

Mark_L_Stone · February 28, 2019, 5:12pm

Can you show us the Mosek output and results from running my SOCP formulation (same as my previous post, except adding cvx_solver mosek).

cvx_begin
variables x(9) t
minimize (t + p*x)
subject to
{chol(H)*x,t,1} == rotated_lorentz(9)
A*x<=b
cvx_solver mosek
cvx_end

Mingxi_Liu · February 28, 2019, 5:26pm

Sure, it generates the following.

cvx_begin
cvx_solver mosek
variables x(9) t
minimize (t + p*x)
subject to
{chol(H)*x,t,1} == rotated_lorentz(9)
A*x<=b
cvx_end



Calling Mosek 8.0.0.60: 20 variables, 10 equality constraints
   For improved efficiency, Mosek is solving the dual problem.
------------------------------------------------------------

MOSEK Version 8.0.0.60 (Build date: 2017-3-1 13:08:15)
Copyright (c) MOSEK ApS, Denmark. WWW: mosek.com
Platform: MACOSX/64-X86

Problem
  Name                   :                 
  Objective sense        : min             
  Type                   : CONIC (conic optimization problem)
  Constraints            : 10              
  Cones                  : 1               
  Scalar variables       : 20              
  Matrix variables       : 0               
  Integer variables      : 0               

Optimizer started.
Conic interior-point optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator - tries                  : 0                 time                   : 0.00            
Lin. dep.  - tries                  : 1                 time                   : 0.00            
Lin. dep.  - number                 : 0               
Presolve terminated. Time: 0.03    
Optimizer  - threads                : 8               
Optimizer  - solved problem         : the primal      
Optimizer  - Constraints            : 10
Optimizer  - Cones                  : 1
Optimizer  - Scalar variables       : 20                conic                  : 11              
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 : 55                after factor           : 55              
Factor     - dense dim.             : 0                 flops                  : 1.16e+03        
ITE PFEAS    DFEAS    GFEAS    PRSTATUS   POBJ              DOBJ              MU       TIME  
0   1.0e+00  3.2e+01  1.0e+00  0.00e+00   0.000000000e+00   0.000000000e+00   1.0e+00  0.05  
1   2.1e-01  7.0e+00  8.5e-02  -1.11e+00  -4.182108180e+02  -9.197996123e+01  2.1e-01  0.15  
2   6.8e-02  2.2e+00  9.3e-03  -1.55e+00  -4.262939775e+03  -9.668915828e+02  6.8e-02  0.16  
3   2.4e-02  7.8e-01  1.4e-03  -2.44e+00  -2.193828518e+04  -3.259981443e+03  2.4e-02  0.16  
4   7.3e-03  2.4e-01  1.8e-04  -1.56e+00  -1.315025849e+05  -2.288820555e+04  7.3e-03  0.17  
5   1.5e-03  4.8e-02  1.5e-05  -1.52e+00  -6.309681366e+05  -4.388530648e+04  1.5e-03  0.17  
6   1.8e-04  5.8e-03  3.4e-07  -1.07e+00  -2.041663483e+07  -2.905714045e+06  1.8e-04  0.18  
7   2.2e-05  7.2e-04  1.5e-08  -1.21e+00  -1.612712372e+08  -1.840325037e+07  2.2e-05  0.18  
8   2.5e-06  8.2e-05  5.9e-10  -1.07e+00  -1.319928559e+09  -1.402632671e+08  2.5e-06  0.18  
9   1.9e-07  6.2e-06  1.5e-11  -9.72e-01  -1.242804076e+10  -1.448570914e+09  1.9e-07  0.19  
10  4.1e-08  1.3e-06  2.0e-12  -6.41e-01  -3.346181039e+10  -5.467563042e+09  4.1e-08  0.20  
Interior-point optimizer terminated. Time: 0.21. 


MOSEK DUAL INFEASIBILITY REPORT.

Problem status: The problem is dual infeasible
Optimizer terminated. Time: 0.33    

Interior-point solution summary
  Problem status  : DUAL_INFEASIBLE
  Solution status : DUAL_INFEASIBLE_CER
  Primal.  obj: -3.5587195229e+02   nrm: 2e+01    Viol.  con: 3e-07    var: 0e+00    cones: 0e+00  
Optimizer summary
  Optimizer                 -                        time: 0.33    
    Interior-point          - iterations : 10        time: 0.21    
      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: Infeasible
Optimal value (cvx_optval): +Inf

Mark_L_Stone · February 28, 2019, 5:37pm

@Erling Can you comment on the immediately preceding post? I

As I wrote in a previous post,
In reality, x = A\b with t any value >= x' * H * x is feasible, among infinitely many other solutions.

disp(A\b)
1.0e+03 *

To be feasible for this x, requires t >= x’ * H * x = 2.4254e+10, which is quite large. Maybe that is the difficulty.

Erling · February 28, 2019, 6:29pm

That is very likely the case. Note also Mosek provides a decent certificate of dual infeasibility.

So if you can rewrite the objective to

||F x + f||

then the optimal objective value will be much smaller. In other words do not convert a least squares objectives to a quadratic function.

I love taking square root of positive numbers because it make numbers close to 1 and 1 is such a nice number.

Mingxi_Liu · February 28, 2019, 6:42pm

That actually solved the problem and avoided the Infeasible issue. I changed the objective to

minimize (norm(chol(H)*x+0.5*(p*inv(chol(H)))'))

which uses chol(H) for F and 0.5*(p*inv(chol(H)))' for f. All of Mosek, Sedumi, Gurobi, and SDPT3 can solve the problem with A\b.

Mark_L_Stone · February 28, 2019, 7:24pm

I’m still trying to understand why that norm in the objective function works out so much better than the SOCP epigraph formulation with the rotated cone constraint in the formulation I posted.

I believe that
{chol(H)*x,t,1} == rotated_lorentz(9)
is equivalent to
norm(chol(H)*x) <= sqrt(t), t >= 0

When evaluated at x = A\b,
norm(chol(H)*x+0.5*(p*inv(chol(H)))') = 1.557375279953413e+05
and
norm(chol(H)*x) = 1.557375613970817e+05

However, the optimal objective of my SOCP epigraph formulation is 2.4254e+10, because the RHS of the rotated cone constraint is sqrt(t), which is getting squared to become t in the objective function.

Erling · March 1, 2019, 6:01am

The trick Ming uses does not always work. For instance if H is very ill-conditioned it may not help.
But given H is very well conditioned in this case that is not an issue.

The norm is a homogeneous function of degree one just like linear functions so it is nice. In addition the primal and dual solution change a lot. In particular the norm of the primal solution to the underlying conic problem gets much smaller.

Btw it is reformulation trick we use often.

Mark_L_Stone · March 1, 2019, 2:30pm

@Erling I am still trying to understand at a deeper level why your formulation is better than my SOCP eipgraph formulation.

Both of these formulation use norm, not norm squared. Is it because my formulation has disparate magnitude terms in the objective function In my formulation, at the optimum, the objective function has additive terms,

t =  2.4254e+10
p*x = -1.0405e+04

However, your formulation has a single term consisting of a norm. And disparate magnitudes inside the norm are not causing difficulty? I believe that CVX will transform your formulation into an SOCP epigraph formulation. But unlike what happens with my formulation, yours will be a pure epigraph formulation having a single term “t” in the objective function