linear inequalities in semi-definite program

254 Views Asked by At

A standard form of SDP is
$\min_x c^Tx$ s.t. $F(x)\succcurlyeq 0$
where $F(x)=F_0+\sum_{i=1}^m F_m$ and $F_0,F_1,...,F_m$ are symmetric matrices and $\succcurlyeq 0$ indicates that the matrix is positive semidefinite.
It is stated in many notes (such as https://inst.eecs.berkeley.edu/~ee227a/fa10/login/l_conic_sdp.html under the section special cases) that a linear inequality (where inequality corresponding to a vector denotes component-wise inequality) can be re-formulated as an SDP inequality by defining a diagonal matrix with diagonal elements as the components of the vector.
My doubt is suppose in a problem, we have a large number of component-wise inequalities and we reformulate it as an SDP problem, is it even computationally feasible (assuming the constraint also has an SDP inequality, thus, there is a dire need for SDP formulation). I am asking this because in such a scenario we are faced with a large number of sparse matrices and the algorithm may take a lot of memory and time to solve. Or is there any better way to deal with such situations?

1

There are 1 best solutions below

0
On BEST ANSWER

In an actual solver you don't formulate linear inequalities using a diagonal matrix which you work with in the SDP cone, but you work with the elementwise (and socp) cone explicitly. The fact that you could do it using a diagonal matrix is just a way to convince the reader that elementwise constraints are easily dealt with both in theory and practice.