Time-consuming semidefinite sparse matrix constraint

#1

Hi,

I have a matrix as
A = \begin{bmatrix} D & v\\ v^H & \alpha \end{bmatrix} ,
where D is a block diagonal matrix, with some of its blocks being zero matrices. Also, v is a vector with almost the upper half part being zeros, and \alpha is a constant. The matrix A has to be a hermitian semidefinite matrix as a constraint of a convex optimization problem, so the eigenvalues should be evaluated. The problem with this constraint takes a lot of time to be solved with MATLAB CVX algorithms. As an example, the dimensions of A starts from 1500x1500. I want to know how I can deal with this sparse matrix in constraints and reduce the computation complexity.

This is the constraint:
A == hermitian_semidefinite(dim(1)+1)

I would greatly appreciate it if anyone can help me.

Thanks

#2

To achieve sparsity you have to introduce additional constraints of the for

X_ij = 0

I suppose. If you have lot of them, they will make it computational costly to solve the problem.
It might be possible to reformulate your problem to work around that issue.

Also I suggest

  • You try different optimizers such as Mosek, SeDuMi, and SDPT3.
  • Post the log output from the best one.
#3

Okay, let me clear it out more. I have built matrix D as a block diagonal matrix which consists of two variables. So, it is known to the solver that the zero elements are actually zero. right? Is it needed to have them defined again as zeros in the constraints? The zeros in the vector v are known as well. The corresponding elements are absolute zeros and do not contain any variable. Therefore, I think it is not necessary for them to be constrained.

I get much faster results with Mosek. A sample log is shown below.

Calling Mosek 9.1.9: 2253068 variables, 5 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

MOSEK warning 710: #2 (nearly) zero elements are specified in sparse col ‘’ (1) of matrix ‘A’.
MOSEK warning 710: #2 (nearly) zero elements are specified in sparse col ‘’ (2) of matrix ‘A’.
MOSEK warning 710: #1 (nearly) zero elements are specified in sparse col ‘’ (3) of matrix ‘A’.
MOSEK warning 710: #2 (nearly) zero elements are specified in sparse col ‘’ (4) of matrix ‘A’.
MOSEK warning 710: #1 (nearly) zero elements are specified in sparse col ‘’ (5) of matrix ‘A’.
MOSEK warning 710: #1 (nearly) zero elements are specified in sparse col ‘’ (6) of matrix ‘A’.
MOSEK warning 710: #1 (nearly) zero elements are specified in sparse col ‘’ (7) of matrix ‘A’.
MOSEK warning 710: #2 (nearly) zero elements are specified in sparse col ‘’ (8) of matrix ‘A’.
MOSEK warning 710: #1 (nearly) zero elements are specified in sparse col ‘’ (9) of matrix ‘A’.
MOSEK warning 710: #1 (nearly) zero elements are specified in sparse col ‘’ (10) of matrix ‘A’.
Warning number 710 is disabled.
Problem
Name :
Objective sense : min
Type : CONIC (conic optimization problem)
Constraints : 5
Cones : 1
Scalar variables : 58
Matrix variables : 2
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.05
Problem
Name :
Objective sense : min
Type : CONIC (conic optimization problem)
Constraints : 5
Cones : 1
Scalar variables : 58
Matrix variables : 2
Integer variables : 0

Optimizer - threads : 2
Optimizer - solved problem : the primal
Optimizer - Constraints : 5
Optimizer - Cones : 1
Optimizer - Scalar variables : 6 conic : 4
Optimizer - Semi-definite variables: 2 scalarized : 4507524
Factor - setup time : 0.17 dense det. time : 0.00
Factor - ML order time : 0.02 GP order time : 0.00
Factor - nonzeros before factor : 13 after factor : 13
Factor - dense dim. : 0 flops : 9.76e+08
ITE PFEAS DFEAS GFEAS PRSTATUS POBJ DOBJ MU TIME
0 3.0e+03 2.8e+04 4.1e+04 0.00e+00 4.085279960e+04 0.000000000e+00 1.0e+00 12.89
1 1.1e+02 9.8e+02 7.7e+03 -1.00e+00 4.061884336e+04 -1.904483166e+02 3.5e-02 54.45
2 1.0e+00 9.3e+00 7.3e+02 -9.99e-01 1.637792316e+04 -1.987440012e+04 3.4e-04 101.09
3 2.5e-01 2.3e+00 3.0e+02 -8.56e-01 -2.601252164e+04 -4.851715196e+04 8.4e-05 147.02
4 2.3e-02 2.2e-01 1.9e+01 -1.28e-01 -8.017638988e+03 -9.204795001e+03 7.8e-06 192.24
5 1.6e-04 1.5e-03 1.1e-02 8.76e-01 -2.426184544e+02 -2.518768460e+02 5.3e-08 232.72
6 1.5e-05 1.4e-04 3.5e-04 9.81e-01 -2.950384407e+01 -3.016949633e+01 5.1e-09 275.25
7 1.6e-06 1.4e-05 1.7e-05 7.42e-01 -3.447183105e+00 -3.262732936e+00 5.2e-10 316.41
8 3.1e-07 2.9e-06 1.9e-06 6.05e-01 -3.804605588e-01 -2.890084538e-01 1.0e-10 355.17
9 5.5e-08 5.1e-07 1.1e-07 9.69e-01 -8.636310405e-02 -8.240456439e-02 1.8e-11 400.39
10 4.5e-09 4.2e-08 2.4e-09 1.03e+00 -9.003037094e-03 -8.962446359e-03 1.5e-12 441.97
11 1.0e-09 9.3e-09 2.5e-10 1.01e+00 -1.353946126e-03 -1.350535831e-03 3.4e-13 479.45
12 1.0e-10 9.3e-10 7.7e-12 9.99e-01 -1.010703344e-04 -1.026027754e-04 3.4e-14 527.70
13 4.2e-12 3.9e-11 6.5e-14 1.00e+00 -2.738069435e-06 -2.804942637e-06 1.4e-15 573.38
14 7.6e-14 7.1e-13 1.6e-16 1.00e+00 -3.235964008e-08 -3.359637249e-08 2.5e-17 621.45
Optimizer terminated. Time: 621.86

Interior-point solution summary
Problem status : PRIMAL_AND_DUAL_FEASIBLE
Solution status : OPTIMAL
Primal. obj: -3.2359640084e-08 nrm: 6e+00 Viol. con: 2e-07 var: 7e-15 barvar: 0e+00 cones: 0e+00
Dual. obj: -3.3596372486e-08 nrm: 3e+04 Viol. con: 0e+00 var: 8e-12 barvar: 2e-08 cones: 0e+00
Optimizer summary
Optimizer - time: 621.86
Interior-point - iterations : 14 time: 621.84
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: Solved
Optimal value (cvx_optval): +3.35964e-08

#4

“it is known to the solver that the zero elements are actually zero” because CVX passes this information to the solver in the form of the constraints X_{ij}=0 as written by Erling. Otherwise how would the solver know? Without any information the solver would consider these elements to be unrestricted - no bounds.

However in this case this is probably not relevant, because as you can see from the log CVX dualized the problem before calling MOSEK so everything the solver sees is dual of what you might think, and in particular it may happen that the number of constraints is significantly reduced. This maybe saves the day. See Example 8.7 in https://docs.mosek.com/modeling-cookbook/duality.html#semidefinite-duality-and-lmis for this type of trick and why it might be relevant. You can also dualize your model yourself and input that to see how it performs directly.

You are welcome to either dump the problem to a task file (https://docs.mosek.com/latest/faq/faq.html#how-do-i-dump-the-problem-to-a-file-to-attach-with-my-support-question) or prepare a reproducible cvx example and send it to MOSEK support. We like large SDPs and dualizing them so maybe we can be able to give better suggestions when we have the specific data.

You can also install Mosek 10. Maybe it will be a bit faster.

#5

Thank you for your comprehensive response. Sure, I will do your suggestions.

Btw, isn’t there a way to mathematically reduce dimensions of such sparse matrices, without losing a considerable amount of information (In this case, the sign of eigenvalues as the constraint is tackling semidefiniteness)?

#6

There are two matrix variables in the problem Mosek sees.

You have to reformulate the problem so the size of those variables gets smaller without introducing too many constraints. That may or may not be possible.

Using Mosek v10 and a faster computer is likely the best way to speed up the solution process.

#7

If you want a better assessment of what CVX does or does not provide to the solver, you should show us your CVX code, preferably reproducible, with input data if possible. As @Michal_Adamaszek points out, CVX provided the dual to the solver, as shown at the beginning of the output, so that complicates things. Also, you should pay attention to Mosek’s warnings about near-zero elements.

When formulating your problem, you can use concatenation, which often works well for many types of structured sparsity. Individual (matrix) variables can be declared with any combination of
keywords:

banded(lb,ub) diagonal hankel hermitian
skew_symmetric symmetric toeplitz tridiagonal
lower_bidiagonal lower_hessenberg lower_triangular
upper_bidiagonal upper_hankel upper_hessenberg upper_triangular

as discussed in http://cvxr.com/cvx/doc/basics.html#variables . CVX does not support blkvar, but YALMIP does, so you might be better of using YALMIP, although I think you can “manually” achieve the effect of what blkvar does by concatenating the constituent diagonal matrices and zeros matrices of appropriate dimensions. I don’t know what CVX is doing behind the scenes in all cases when these keywords are used. But if they are applicable, you should probably use them, in combination with building up the higher level matrices from these building blocks using concatenation.