I have an SDP that has a lot of matrix inequalities with other scalar variables. I want to use sedumi to solve the problem. Knowing that CVX essentially parses the data from the high-level SDP description (i.e., the mathematical one) to the language that sedumi understands by formulating the SDP problem in this standard form
min trace(C’ * X)
s.t. trace(A_k’ * X) = b_k , \forall k=1,…,m
X >=0
Is it possible to actually obtain these matrices (C,A_k,b_k) from CVX? Or CVX code does not allow that? In many linear matrix inequalities, it is very hard to get to that form.
Please read these threads and see if that helps you do what you want, or close enough to what you want.
Per help cvx_solver_settings
cvx_solver_settings( 'dumpfile', <filename> ) is a setting supported by
all solvers. If set, it will save a .MAT file containing the exact
input arguments delivered to the solver. This file will be created
immediately before the solver is called, so you will be able to examine
their contents even if the solver fails with an error. This feature is
to be used primarily by solver developers.
What I am trying to do is to include pre-processing block right before the solver is called. That reduces the dimension of the SDP; see https://arxiv.org/pdf/1608.02300.pdf.
What you are asking goes beyond my ability to answer. In general, pre-processing could be done by any combination of the modeling tool, in this case CVX, and the solver.
To get some insight as to how CVX input is transformed into input to the solver, read mcg’s thesis “Disciplined Convex Programming” https://stanford.edu/~boyd/papers/pdf/mcg_thesis.pdf3 . If you have any questions on his thesis, or want to find out about subsequent developments in CVX’s under the hood processing, he’s the right one to answer.
The solver itself may carry out various pre-processing steps, known as pre-solve, which, among other things, tries to reduce problem size, eliminate redundancies, etc, Various solvers called by CVX, especially (?) commercial solvers, have pre-solves, but I don’t know specifically with regard to SeDuMi. For instance, see http://docs.mosek.com/8.0/toolbox/presolver.html regarding MOSEK’s pre-solve. MOSEK can be called to solve SDPs from CVX Professional.
You are of course free to apply any preprocessing steps you want prior to submitting your model to CVX, so long as you follow CVX’s rukes.
CVX actually performs very similar preprocessing, though not on individual semidefinite constraints. I think you’ll find that in practice this kind of reduction stage is going to offer no benefit to most models.
I don’t blame academics for not knowing CVX does this, given that I never discussed that work in papers.
Thanks Michael.
I’ll try recent preprocessing algorithms on large SDPs and let you and @Mark_L_Stone know about it.
The authors in https://arxiv.org/pdf/1408.4685.pdf claim that it might be very advantageous. We’ll see how it works.
Again many thanks for the quick response. You guys are awesome!
Just so that I am clear, I do anticipate that this kind of preprocessing can come in handy for problems that are expressed wit, say, one giant semidefinite constraint, or for problems where there is good reason to believe that there is unexploited structure in the semidefinite constraints.
But if you’re using CVX to build your models using combinations of linear equations and inequalities and DCP compliant nonlinearities, you’re not going to be generating these kinds of models in the first place. You’re communicating a lot of structure by expressing your model in this way, and CVX is taking advantage of that. It never builds a single, large monolithic SDP from a list of smaller constraints.
Even though CVX takes advantage of that structure, it nevertheless introduces a lot of redundant variables in the process in order to facilitate problem building. So that’s why the preprocessing step remains important.