Prescribing tolerance for positivedefiniteness


(Lucas) #1

I have specified a problem whose objetive function comprises a norm error cost function to be minimized subject to LMI constraints.

minimize norm (error)
subject to LMI ==semidefinite

CVX does solve the problem with an excelent fit to the data but there seems to be some very small negative (something of the magnitude -1e^-7) eigenvalues which violate the constraints.

Is there a way to require cvx not to allow for negative eigenvalues? So to speak could I raise the tolerance to some small but positive eigenvalue, say +1e^-7?


Handling a strict positive semidefinite constraint in CVX
(Mark L. Stone) #2

If X is an n by n matrix to be constrained:
lambda_min(X) >= 1e-7
or
X - 1e-7*eye(n) == semidefinite(n)


(Erling D.Andersen) #3

You can also perturb the optimal X so it becomes postive semidefinite i.e. a small multiple of the indemnity to it.


(Henry Wolkowicz) #4

did you use cvx_precision best that would be the first thing to try. Also showing us the LMI might help. If it is badly conditioned in the sense of not have any strictly feasible points then you will have difficulty finding a good solution with guaranteed nonnegativity.


(Henry Wolkowicz) #5

Also you can try sdpt3 rather than sedumi. sedumi is the default I think for cvx? But sedumi allows for small negative eigenvalues for the dual slacks in the primal-dual embedding.


(Lucas) #6

Hello everyone!

I’m puzzled by solutions I’m getting with Mosek. @Erling.

Given a state-space realization (A,B,Co,Do) (problem data) which is controllable but does not satisfy the Kalman-Yakubovich-Popov Lemma (Positive-Real Lemma), my problem consists of computing perturbations to the elements of matrices (C,D) so that the KYP is satisfied while minimizing the perturbation size. That is to say I want the nearest model that satisfies the KYP LMI constraints.
I measure proximity by norm which and the constraints are the KYP constraints explicitly written:

`
minimize norm(Hx)

subject to [-A'*P-P*A, -P*B+Co+\deltaC(x); -B'*P+(Co+\deltaC(x) )', (D+\deltaD)+(D+\deltaD)'] == 
semidefinite
P == semidefinite

`
I perturb only parameter matrices Co and Do while keeping A and B fixed, A is obviously stable.
Mosek does find a solution which satisfies the Lyapunov inequality with a positive definite auxiliar Lyapunov variable but the LMI constraint is violated.
Mosek signals the problem as unbounded (perhaps because the unfeasible start) and the solver stalls with both primal and dual almost identical in value.
I had initially thought relaxing the semidefinite constraints but violations are large in mgnitude, ie the KYP LMI is indefinite and I cannot force it to be definite by computiong perturbations to it.

Any help is greatly appreciated.


(Lucas) #7

By the way, I pinned @Erling because when I switch from Mosek to SDPt3 The solver presents a solution even though the duality gap is not zero as well. I tend to believe Mosek to be the best. There is something fishy in my problem.


(Erling D.Andersen) #8

Fixed an important typo 2019-03-28.

If I should say something meaningful about a concrete problem then showing the complete log is always a good idea.

Based on the information you provide your problem is illposed though. An arbitrary example of an illposed problem you obtain by minimize 1/x st. x>=0. The optimal value is 0 but is never attained.

However, when I had a course on convex optimization by Ken Kortanek he would show there was a tons of ways for a problem to be illposed.


(Lucas) #9

Sorry about not disclosing the log, here it goes…

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

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

MOSEK warning 710: #1 (nearly) zero elements are specified in sparse col '' (3) of matrix 'A'.
MOSEK warning 710: #1 (nearly) zero elements are specified in sparse col '' (5) of matrix 'A'.
MOSEK warning 710: #3 (nearly) zero elements are specified in sparse col '' (19) of matrix 'A'.
MOSEK warning 710: #3 (nearly) zero elements are specified in sparse col '' (20) of matrix 'A'.
MOSEK warning 710: #1 (nearly) zero elements are specified in sparse col '' (22) of matrix 'A'.
MOSEK warning 710: #3 (nearly) zero elements are specified in sparse col '' (26) of matrix 'A'.
MOSEK warning 710: #1 (nearly) zero elements are specified in sparse col '' (28) of matrix 'A'.
Problem
Name                   :                 
Objective sense        : min             
Type                   : CONIC (conic optimization problem)
Constraints            : 160             
Cones                  : 0               
Scalar variables       : 34              
Matrix variables       : 3               
Integer variables      : 0               

Optimizer started.
Conic interior-point optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator started.
Freed constraints in eliminator : 0
Eliminator terminated.
Eliminator - tries                  : 1                 time                   : 0.00            
Lin. dep.  - tries                  : 1                 time                   : 0.00            
Lin. dep.  - number                 : 0               
Presolve terminated. Time: 0.02    
Optimizer  - threads                : 6               
Optimizer  - solved problem         : the primal      
Optimizer  - Constraints            : 160
Optimizer  - Cones                  : 1
Optimizer  - Scalar variables       : 19                conic                  : 18              
Optimizer  - Semi-definite variables: 3                 scalarized             : 4629            
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 : 1.28e+004         after factor           : 1.28e+004       
Factor     - dense dim.             : 0                 flops                  : 3.68e+006       
ITE PFEAS    DFEAS    GFEAS    PRSTATUS   POBJ              DOBJ              MU       TIME  
0   6.2e+001 5.4e+005 1.0e+000 0.00e+000  3.893061106e+002  0.000000000e+000  1.0e+000 
0.03  
1   3.0e-002 2.6e+002 1.1e-005 -1.00e+000 -3.451322450e+007 -2.675476956e+005 4.8e-004 
0.05  
2   1.3e-003 1.1e+001 5.8e-007 -2.70e-001 -2.320950377e+007 -5.484486713e+005 2.1e-005 
0.05  
3   2.4e-004 2.1e+000 2.1e-007 6.50e-001  -6.879467819e+006 -6.804411855e+005 3.9e-006 
0.06  
4   6.4e-005 5.6e-001 5.6e-008 2.32e-001  -7.226851909e+006 -1.309955747e+006 1.0e-006 
0.06  
5   2.1e-005 1.8e-001 3.4e-008 5.25e-001  -3.176872636e+006 -1.503392737e+006 3.3e-007 
0.06  
6   6.8e-006 5.9e-002 1.7e-008 6.24e-001  -2.662295274e+006 -1.914019934e+006 1.1e-007 
0.08  
7   1.9e-006 1.6e-002 9.9e-009 1.00e+000  -1.948695104e+006 -1.791893301e+006 3.0e-008 
0.08  
8   1.0e-006 8.8e-003 6.5e-009 1.07e+000  -1.617401580e+006 -1.510289596e+006 1.6e-008 
0.08  
9   4.0e-007 3.5e-003 4.1e-009 5.89e-001  -1.423827534e+006 -1.380599311e+006 6.5e-009 
0.08  
10  2.5e-007 2.2e-003 3.6e-009 9.77e-001  -8.006658281e+005 -7.797775449e+005 4.0e-009 
0.09  
11  1.1e-007 9.9e-004 1.9e-009 6.29e-001  -8.922393882e+005 -8.759484877e+005 1.8e-009 
0.09  
12  4.3e-008 3.8e-004 1.1e-009 7.55e-001  -2.766293706e+005 -2.696640933e+005 6.9e-010 
0.09  
13  1.9e-008 1.7e-004 6.9e-010 7.90e-001  -2.283021363e+005 -2.248585467e+005 3.1e-010 
0.09  
14  5.2e-009 4.4e-005 3.2e-010 7.68e-001  -1.858878655e+005 -1.847682387e+005 8.1e-011 
0.11  
15  3.3e-009 1.1e-005 1.6e-010 9.37e-001  -1.808577556e+005 -1.805752384e+005 2.1e-011 
0.11  
16  2.2e-009 7.4e-006 8.7e-011 4.95e-001  -1.715122376e+005 -1.710962017e+005 1.4e-011 
0.13  
17  1.5e-009 4.9e-006 6.7e-011 2.61e-001  -1.672952687e+005 -1.669817671e+005 9.0e-012 
0.13  
18  8.1e-010 2.7e-006 3.8e-011 2.38e-001  -1.603234657e+005 -1.600228753e+005 5.0e-012 
0.14  
19  4.1e-010 1.4e-006 2.8e-011 7.22e-001  -1.593255043e+005 -1.591883588e+005 2.5e-012 
 0.16  
20  1.6e-010 4.2e-007 1.3e-011 6.32e-001  -1.561115227e+005 -1.560474843e+005 7.8e-013 
0.16  
21  1.6e-010 4.2e-007 1.3e-011 1.04e-001  -1.561115227e+005 -1.560474843e+005 7.8e-013 
0.19  
Interior-point optimizer terminated. Time: 0.20. 

Optimizer terminated. Time: 0.23    

 Interior-point solution summary
 Problem status  : UNKNOWN
 Solution status : UNKNOWN
 Primal.  obj: -1.5611152271e+005  nrm: 9e+006   Viol.  con: 1e+002   var: 0e+000   barvar: 
 0e+000 
 Dual.    obj: -1.5604748434e+005  nrm: 2e+008   Viol.  con: 0e+000   var: 1e-004   barvar: 
 5e+000 
 Optimizer summary
 Optimizer                 -                        time: 0.23    
 Interior-point          - iterations : 22        time: 0.20    
  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: Inaccurate/Unbounded
 Optimal value (cvx_optval): -Inf


(Lucas) #10

Despite the difficult solution process, mosek has spitted out a numeric solution instead of Nans or Infs, the the solution violates the positivity constraints.

I sometimes run this same formulation but call SDPT3 instead, I get a worse approximation but constraints are not violated. I got me puzzled.


(Erling D.Andersen) #11

The numbers in the column

PRSTATUS

does not converge towards -1 or +1. That usually means your problem is illposed.

A newer version of MOSEK than you are using might be doing better. However, I suspect you will have to improve your model if you want to use the results you get.


(Lucas) #12

By newer version you mean the Beta 9.0.81?
Because the version I have is the one downloaded from link
8.1.0.80
, even though the log strangely refers to a much older 8.0.0.60) maybe there is something wrong with the link at Mosek websit. But I get version 8.0.0.60 even when I download 8.1.0.80.


(Mark L. Stone) #13

MOSEK 8.0.0.60 is provided in the CVX distribution, and is the version chosen for use by CVX if cvx_solver mosek is specified. You can either get rid of or rename the mosek directory under CVX so that CVX doesn’t find it. Or see what the version you want is called in the output of cvx_solver and specify that with cvx_solver.


(Lucas) #15

How do I specify the other/newer version to CVX ? Is there a way to set the path in CVX? I set the matlab path but it failed to find the solver.
Actually, the question is how to set the location for the solver when I want cvx to use other version than the one provided in the CVX distribution.


(Mark L. Stone) #16

If you give the command
cvx_solver
you should see a list of all the Mosek versions CVX has access to. For instance,if 8.1.0.80 is Mosek_2 . then give the command
cvx_solver Mosek_2

The same with multiple versions of other solvers.


Matlab OUT OF MEMORY error on optimization problem