[Csdp] Minimum volume inscribed ellipsoid problem

[Brian Borchers]

On Sat, Dec 9, 2017 at 4:16 AM, G Chandramouli <gcmouli1 at gmail.com> wrote:

> Hello all,
> This is  my first time with CSDP solver. I want to know whether the
> problem of finding minimum volume inscribed ellipsoid can be solved in
> CSDP. One of its formulation is:
>
> Max  log det(M)
> st: (Ma_i-z)^T (Ma_i-z) <= 1   for i=1,...,m
>      M >0
>
> Actually a_i for i=1,2....m are given points in R^n space.  I want to fit
> an ellipsoid with minimum volume to cover all those points. The problem is
> convex. The objective function is maximizing  the log determinant of M.
> However the CSDP manual says only about tr(M). Can this problem be solved
> using CSDP ?
>

Although it's relatively easy to add this feature to a primal-dual interior
point method for SDP, most solvers historically haven't supported it.  One
reason is that the commonly used SDPA file format for SDP problems doesn't
include a way to specify a log(det()) term in the objective.

CSDP can't directly solve problems involving the log(det()) function.
However, it is possible to solve such problems by solving a sequence of
SDP's.  See for example:

Hamza Fawzi, James Saunderson, Pablo A. Parrilo. Semidefinite
approximations of the matrix logarithm.  ArXiv preprint 1705.00812.
<https://arxiv.org/abs/1705.00812>

CVX uses a similar scheme with it's SDP solvers- however, I don't believe
that this scheme was ever formally published.  If anyone does have a
published reference for that scheme, I'd love to read it.

It is possible to directly solve log(det()) problems with the MATLAB based
SDPT3 solver, but you've asked for something in C or Fortran.

Another option that might work is the Splitting Cone Solver (SCS)
<https://github.com/cvxgrp/scs>.  As I recall, it can handle log(det())
problems.  This is a first order method, which is capable of handling
larger problems than the primal-dual interior point methods, but the
accuracy of the solutions is typically not as good.

-- 
Brian Borchers                          borchers at nmt.edu
Department of Mathematics      http://www.nmt.edu/~borchers/
New Mexico Tech                       Phone: (575) 322-2592
Socorro, NM 87801                   FAX: (575) 835-5366
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.coin-or.org/pipermail/csdp/attachments/20171209/6b65a574/attachment.html>