Convert problem into SDP

114 Views Asked by At

I have a optimization problem like: $$min_{R,z} -\log det R $$ $$s.t. R > 0, \quad (c_i - z)^TR(c_i - z) \leq 1 \quad (i=1,\dots,k)$$.

In above problem, $c_i$ is constant $R^n$.

How can I convert the problem in the form of SDP (semidefinite programming)?

1

There are 1 best solutions below

2
On

I am not going to show how to convert it to a pure SDP problem, as the conversion of the geometric mean operator (to replace logdet unless you use an SDP solver which handles logdet term natively, currently only SDPT3 as far as I know) is absolutely horrendous. Instead, I simply give the initial start required to linearize the model.

The constraints $(c_i - z)^TR(c_i - z) \leq 1 $ can be written as $(R(c_i - z))^TR^{-1}R(c_i - z) \leq 1 $ which means a Schur complement leads you to $\begin{bmatrix}1 & (R(c_i-z))^T\\ R(c_i-z) & R\end{bmatrix}\succeq 0$. Define new variable $q = Rz$ and the constraint is a linear semidefinite constraint, and you have a so called MAXDET problem in $(R,q)$.

If you use a modelling layer, all the boring stuff around the logdet/geomean operator will be taken care of. If you use YALMIP in MATLAB (disclaimer: developed by me) and SDPT3 as a solver, it will be solved natively using the logdet objective, and for any other SDP solver the objective is converted to a geometric mean. https://yalmip.github.io/tutorial/maxdetprogramming/