How to minimize the largest singular value of the matrix

1

I have such an optimization problem to minimize the largest singular value of the matrix:
\min_{\left\{x_i\right\}}\sigma_{max}\left(\mathbf{H}\right) =\sigma_{max}\left(\sum_{i=1}^{L}x_i\mathbf{H}_i\right) \\ \text{s.t.} \sum_{i=1}^{L}x_i=1, x_i\geq0
where \mathbf{H}_i \in \mathbb{C}^{M \times N} and \sigma_{max}\left(\mathbf{X}\right) means the largest singular value of \mathbf{X}, respectively.
Introducing \mathbf{W}=\left[\mathbf{0},\mathbf{H};\mathbf{H}^{\mathrm{T}},\mathbf{0}\right] and \mathbf{W}_i=\left[\mathbf{0},\mathbf{H}_i;\mathbf{H}_i^{\mathrm{T}},\mathbf{0}\right], the optimization problem above can be transformed into:
\min_{\left\{x_i\right\}}\lambda_{max}\left(\mathbf{W}\right) =\lambda_{max}\left(\sum_{i=1}^{L}x_i\mathbf{W}_i\right) \\ \text{s.t.} \sum_{i=1}^{L}x_i=1, x_i\geq0
where \lambda_{max}\left(\mathbf{X}\right) denotes the largest eigenvalue of \mathbf{X}. This problem can be transformed as a SDP problem:
\min_{\boldsymbol{x},t}t \\ \text{s.t. }W(\boldsymbol{x})-t\mathbf{I}_{M+N} \preceq 0,\sum_{i=1}^{L}x_i=1, x_i\geq0
where W(\boldsymbol{x})=\sum_{i=1}^{L}x_i\mathbf{W}_i. The CVX code I used is shown as following:

W0=zeros(Nt+Nr);
cvx_begin sdp
    variable x(L);
    variable t;
    minimize t;
    subject to
        for i=1:L
            W0=W0+x(i)*W(:,:,i);
        end
        x'*ones(L,1)==1;
        x>=0;
        t*eye(Nt+Nr)-W0==semidefinite(Nt+Nr);
    cvx_end

However, the obtained optimal \boldsymbol{x} is NaN. The cvx_status is shown as following:

Calling Mosek 9.1.9: 1090 variables, 11 equality constraints
For improved efficiency, Mosek is solving the dual problem.

MOSEK Version 9.1.9 (Build date: 2019-11-21 11:34:40)
Copyright © MOSEK ApS, Denmark. WWW: mosek.com
Platform: Windows/64-X86

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

Optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator started.
Freed constraints in eliminator : 0
Eliminator terminated.
Eliminator started.
Freed constraints in eliminator : 0
Eliminator terminated.
Eliminator - tries : 2 time : 0.00
Lin. dep. - tries : 1 time : 0.00
Lin. dep. - number : 0
Presolve terminated. Time: 0.01
Problem
Name :
Objective sense : min
Type : CONIC (conic optimization problem)
Constraints : 11
Cones : 0
Scalar variables : 270
Matrix variables : 1
Integer variables : 0

Optimizer - threads : 8
Optimizer - solved problem : the primal
Optimizer - Constraints : 11
Optimizer - Cones : 1
Optimizer - Scalar variables : 267 conic : 257
Optimizer - Semi-definite variables: 1 scalarized : 820
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 : 66 after factor : 66
Factor - dense dim. : 0 flops : 3.57e+05
ITE PFEAS DFEAS GFEAS PRSTATUS POBJ DOBJ MU TIME
0 3.9e+01 1.0e+00 1.0e+00 0.00e+00 0.000000000e+00 0.000000000e+00 1.0e+00 0.03
1 2.1e+01 5.5e-01 1.7e-01 3.51e+00 -3.577315806e-02 -1.371427890e-01 5.5e-01 0.08
2 1.5e+01 3.9e-01 6.7e-01 5.53e-01 -4.330990656e+00 -4.108603708e+00 3.9e-01 0.08
3 6.3e+00 1.6e-01 3.2e-02 3.55e+00 -1.129435191e+00 -1.392990285e+00 1.6e-01 0.08
4 1.7e+00 4.3e-02 2.2e-02 -1.03e-01 -7.632153254e+00 -7.783272849e+00 4.3e-02 0.08
5 1.7e-02 4.4e-04 3.0e-03 -7.90e-01 -1.656095769e+03 -1.611546014e+03 4.4e-04 0.08
6 1.7e-08 4.4e-10 4.2e-06 -9.96e-01 -3.376083486e+09 -3.283855737e+09 4.4e-10 0.09
7 3.1e-15 1.0e-15 9.3e-13 -1.00e+00 -9.067269377e-01 -8.819569976e-01 1.9e-19 0.09
Optimizer terminated. Time: 0.13

Interior-point solution summary
Problem status : DUAL_INFEASIBLE
Solution status : DUAL_INFEASIBLE_CER
Primal. obj: -9.0672693765e-01 nrm: 1e+00 Viol. con: 3e-15 var: 0e+00 barvar: 0e+00
Optimizer summary
Optimizer - time: 0.13
Interior-point - iterations : 7 time: 0.09
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

I wonder whether such a optimization problem can not obtain a non-trivial solution or not? If the answer is yes, how can I get it through CVX? Thank you for your attention.

1 Like
2

You haven’t provided a reproducible problem, with input data.

I made up a 3 by 3 (Nt + Nr = 3) problem having (W(:,:,i) = eye(3) for i=1:3. The problem was solved to optimality using your program. Also using the simpler (in CVX) approach of using norm(W0) as the objective function, because that is the spectral norm of W0 i.e., the maximum singular value of W0.

W0=zeros(Nt+Nr);
cvx_begin
variable x(L);
variable t;
for i=1:L
  W0=W0+x(i)*W(:,:,i);
end
minimize norm(W0);
x'*ones(L,1)==1;
x>=0;
cvx_end

BTW, specifying sdp mode is redundant when you use ... == semdefinite(...). But it does no harm. In sdp mode you can directly input W0 - t*eye(Nt+Nr) <= 0 to specify the SDP constraint. CVX will even let you input double sided SDP constraints when in SDP mode

1 Like
3

Thank you for your advice, Mark. I should give more detailed description. The structure of \mathbf{W}_i=\left[\mathbf{0},\mathbf{H}_i;\mathbf{H}_i^{\mathrm{T}},\mathbf{0}\right] determines that W(:,:,i) cannot be eye(3). What’s more, \mathbf{H}_i=\boldsymbol{v}_i\boldsymbol{u}_i^{\mathrm{H}} so that \operatorname{rank}\left(\mathbf{H}_i\right)=1 and the norm is limited by \left\|\mathbf{H}_i\right\|_{\mathrm{F}}^{2}=1. Maybe the structure of the problem determines that it cannot be solved as SDP?

1 Like
4

I made up this data.

Nt=2;Nr=2;L=3;
K(:,:,1)=[1 2;3 4];K(:,:,2)=[-3 4;0 1];K(:,:,3)=[4 1;-3 2];
for i=1:3,W(:,:,i)=i*[zeros(2) K(:,:,i);K(:,:,i)' zeros(2)];end

I then ran your program and mine. They both produced the same optimal result, within solver tolerance.

Status: Solved
Optimal value (cvx_optval): +5.08094
 
>> x
x =
   0.770069411513271
   0.229930556548411
   0.000000023246215

Can you provide a minimum reproducible program, complete with input data, which results in infeasible?

I’m confused by the Mosek and CVX output. CVX reports that Mosek is solving the dual, and Mosek declares dual infeasible. So I believe that should correspond to primal unbounded. But CVX reports the problem as infeasible.

1 Like
5

Dear Mark, I have summarized my code:

Nt=32;
Nr=8;
L=10;
AoA=unifrnd(-pi/2,pi/2,[L,1]);
AoD=unifrnd(-pi/2,pi/2,[L,1]);
AT=zeros(Nt,L);  AR=zeros(Nr,L);
for i_cl=1:L
    for i=1:Nt
        AT(i,i_cl)=1/sqrt(Nt)*exp(-1i*2*pi*0.5*sin(AoD(i_cl))*(i-1));
    end
for i=1:Nr
    AR(i,i_cl)=1/sqrt(Nr)*exp(-1i*2*pi*0.5*sin(AoA(i_cl))*(i-1));
end
end
sub_H_M=zeros(Nr,Nt,L); 
for l=1:L
    sub_H_M(:,:,l)=AR(:,l)*AT(:,l)';
end
for i=1:L
    W(:,:,i)=[zeros(Nr),sub_H_M(:,:,i);sub_H_M(:,:,i)',zeros(Nt)];
end
W0=zeros(Nt+Nr);
cvx_begin sdp
   variable x(L);
   variable t;
   minimize t;
subject to
    for i=1:L
        W0=W0+x(i)*W(:,:,i);
    end
    x'*ones(L,1)==1;
    x>=0;
    t*eye(Nt+Nr)-W0==semidefinite(Nt+Nr);
cvx_end

You can have a try. Thanks a lot.

1 Like
6

This appears to be a bug in CVX.

On a common random instantiation (input data) I ran, my version of the CVX problem solved to the same optimal solution, using all of Mosek, SeDuMi, and SDPT3. For your version, for all of these solvers, CVX reported the solver was provided the dual problem, the solver reported dual infeasibility, and CVX reported infeasibility, which as I wrote in an earlier post, seems inconsistent.

I also ran “your version”, in YALMIP. It solved correctly.

 x=sdpvar(L,1);
 t=sdpvar;
 for i=1:L
     W0=W0+x(i)*W(:,:,i);
 end
 optimize([sum(x)==1 x>=0,t*eye(Nt+Nr)-W0>=0],t)

Your W(:,:,i) are all symmetric, so your formulation should have a feasible solution for large enough t. In this case, I don’t think the choke is due to numerical issues, such as the required t being too large; I think it is just a flub by CVX in the problem formulation.

1 Like