Closest Toeplitz SDP search.
P = [ 4, 1+2*j, 3-j ; ...
1-2*j, 3.5, 0.8+2.3*j ; ...
3+j, 0.8-2.3*j, 4 ];
n = size( P, 1 );
cvx_begin sdp
variable Z(n,n) hermitian toeplitz
dual variable Q
minimize( norm( Z - P, 'fro' ) )
Z >= 0 : Q;
cvx_end
disp( 'The original matrix, P: ' );
disp( P )
disp( 'The optimal point, Z:' );
disp( Z )
disp( 'The optimal dual variable, Q:' );
disp( Q )
disp( 'min( eig( Z ) ), min( eig( Q ) ) (both should be nonnegative, or close):' );
disp( sprintf( ' %g %g\n', min( eig( Z ) ), min( eig( Q ) ) ) );
disp( 'The optimal value, || Z - P ||_F:' );
disp( norm( Z - P, 'fro' ) );
disp( 'Complementary slackness: Z * Q, should be near zero:' );
disp( Z * Q )
Calling SDPT3: 20 variables, 6 equality constraints
For improved efficiency, SDPT3 is solving the dual problem.
------------------------------------------------------------
num. of constraints = 6
dim. of sdp var = 6, num. of sdp blk = 1
dim. of socp var = 11, 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 mean(obj) cputime
-------------------------------------------------------------------
0|0.000|0.000|1.8e+01|1.5e+00|2.1e+02| 0.000000e+00| 0:0:00| chol 1 1
1|0.942|1.000|1.0e+00|2.6e-02|1.6e+01|-6.371585e+00| 0:0:00| chol 1 1
2|0.949|0.763|5.3e-02|8.1e-03|2.4e+00|-2.301429e+00| 0:0:00| chol 1 1
3|0.873|0.976|6.7e-03|1.5e-03|1.3e-01|-1.474634e+00| 0:0:00| chol 1 1
4|1.000|0.976|5.8e-08|1.5e-04|1.1e-02|-1.450032e+00| 0:0:00| chol 1 1
5|0.987|0.987|1.0e-09|4.4e-06|1.4e-04|-1.450780e+00| 0:0:00| chol 1 1
6|0.981|0.986|7.6e-10|6.3e-08|2.3e-06|-1.450803e+00| 0:0:00| chol 1 1
7|0.993|1.000|7.2e-11|1.5e-10|6.7e-08|-1.450804e+00| 0:0:00| chol 1 1
8|1.000|1.000|1.1e-11|1.4e-11|3.5e-09|-1.450804e+00| 0:0:00|
stop: max(relative gap, infeasibilities) < 1.49e-08
-------------------------------------------------------------------
number of iterations = 8
primal objective value = -1.45080351e+00
dual objective value = -1.45080352e+00
gap := trace(XZ) = 3.52e-09
relative gap = 9.02e-10
actual relative gap = 8.50e-10
rel. primal infeas = 1.06e-11
rel. dual infeas = 1.45e-11
norm(X), norm(y), norm(Z) = 1.9e+00, 5.6e+00, 6.8e+00
norm(A), norm(b), norm(C) = 5.8e+00, 2.0e+00, 1.0e+01
Total CPU time (secs) = 0.2
CPU time per iteration = 0.0
termination code = 0
DIMACS: 1.1e-11 0.0e+00 2.2e-11 0.0e+00 8.5e-10 9.0e-10
-------------------------------------------------------------------
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +1.4508
The original matrix, P:
4.0000 1.0000 + 2.0000i 3.0000 - 1.0000i
1.0000 - 2.0000i 3.5000 0.8000 + 2.3000i
3.0000 + 1.0000i 0.8000 - 2.3000i 4.0000
The optimal point, Z:
4.2827 0.8079 + 1.7342i 2.5574 - 0.7938i
0.8079 - 1.7342i 4.2827 0.8079 + 1.7342i
2.5574 + 0.7938i 0.8079 - 1.7342i 4.2827
The optimal dual variable, Q:
0.3366 -0.0635 - 0.2866i -0.3051 + 0.1422i
-0.0635 + 0.2866i 0.2561 -0.0635 - 0.2866i
-0.3051 - 0.1422i -0.0635 + 0.2866i 0.3366
min( eig( Z ) ), min( eig( Q ) ) (both should be nonnegative, or close):
1.09801e-09 1.16792e-10
The optimal value, || Z - P ||_F:
1.4508
Complementary slackness: Z * Q, should be near zero:
1.0e-04 *
0.0711 - 0.0025i -0.0156 - 0.0601i -0.0634 + 0.0323i
0.0353 - 0.1591i -0.1421 + 0.0000i 0.0353 + 0.1591i
-0.0634 - 0.0323i -0.0156 + 0.0601i 0.0711 + 0.0025i