8
$\begingroup$

I am faced with the problem of finding the ellipsoid $B$ ($B$ is a symmetric positive definite matrix) of maximal volume within a convex set $C$ given as a set of linear inequalities $C=\{x| a_i^T x \leq b_i, i=1,\dots,m\}$. I understood how it is formalized as a convex optimization problem $$ \min_{B,d}\quad[\log\det B^{-1}]\\ \mbox{s.t.:}\quad ||Ba_i||_2+a_i^Td\leq b_i, \qquad i=1,\dots, m $$ as is given in "Convex Optimization,Stephen Boyd and Lieven Vandenberghe, Cambridge University Press, 2004" [pdf version]. My approach would be to use interior point methods, introduce an accuracy parameter $t>0$ and incorporate the constrains into the objective via a logarithmic barrier function as explained in chapter 11 of the above book and try to minimize the resulting uncontrained problem $$ \min_{B,d}\quad \underbrace{\left[\log\det B^{-1} - \frac{1}{t}\sum_{i=1}^m\log(b_i-||Ba_i||_2-a_i^Td)\right]}_{= f(B,d)}. $$ Therefore I would take partial derivatives of $f$: $$ \frac{\partial f}{\partial B} = B^{-1}+\frac{1}{t}\sum_{i=1}^m\left(\frac{\frac{Ba_ia_i^T}{||Ba_i||}}{b_i-||Ba_i||_2-a_i^Td}\right) $$ which is a matrix and $$ \frac{\partial f}{\partial d}=\frac{1}{t}\sum_{i=1}^m\left(\frac{a_i}{b_i-||Ba_i||_2-a_i^Td}\right) $$ which is a vector. And then starting from an initial (feasible) point $(B^0,d^0)$ I would iteratively update the actual solution $(B^k,d^k)$ according the negative partial derivates: $$ B^{k+1} = B^k - s_B \frac{\partial f(B^k,d^k)}{\partial B}\\ d^{k+1} = d^k - s_d \frac{\partial f(B^k,d^k)}{\partial d} $$ where $s_B>0$ and $s_d>0$ are step size parameters until a predefined stoping criterum is fullfilled.\ I am not sure whether this is a correct way to solve the problem? It seems to me very awkward and not very elegant. I am not an expert in optimization techniques and I am not sure whether I put all the ingredients (partial derivatives, interior-point-method, unconstrained minization, etc.) together in the right way. I wonder how an expert would solve this problem. In the above mentioned book this task was shown as an example for a convex problem, but as far as I can see there was so explicit algorithm given for solving the task. Although I think Mr. Boyd has somewhere a Matlab-script on his pages for solving the task, but I want to understand the basic techniques first before using a "black-box"-algorithm. There seem to be other approaches in "Interior-Point Polynomial Algorithms in Convex Programming; Yurii Nesterov and Arkadii Nemirovskii, SIAM studies in applied mathematics; vol.13, 1994" and "On the complexity of approximating the maximal inscribed ellipsoid for a polytope, Leonid G. Khachiyan and Michael J. Todd, Mathematical Programming 61 (1993), 137-159" but I don't understand them because they are written to technical for me.

By the way: How does the dual problem of the first problem look like? And how is it derived?

Thanks in advance

$\endgroup$
  • 1
    $\begingroup$ There are solvers that will do all of these things for you. Is there any reason you want to do them yourself instead? Speaking as someone who has, at one point, learned about interior-point methods, and has worked in an optimization lab, and has coded some of the methods in MATLAB (for homework assignments), I'd still use the black-box solver. $\endgroup$ – Geoff Oxberry Jun 7 '12 at 21:41
  • 1
    $\begingroup$ I stick to the principle to understand/implement at least a basic version of a method before using off-the-shelf routines. I think this principle comes with two favorable aspects: 1) It comes with an immense learning effect and deeper understanding of the methods. 2) In most applications a basic version of an mathematical-algorithm is enough (at least for the applications I am confronted with). So you can keep your code small and simple and don't have to worry about license stuff (in case you want to earn some money with it). $\endgroup$ – Denis K. Jun 8 '12 at 16:17
1
$\begingroup$

Well, you are sort of on the right track. There is no magic to solving these problems using interior-point methods, they are iterative in nature and based on linearizations etc.

However, a typical interior-point algorithm for these problems would not take a step in the gradient direction, but compute second-order information too, and thus take a Newton step. Hence, a line-search is performed along the Newton direction, an optimal step is taken, and the procedure is repeated. Once converged (too some suitably defined precision), the barrier parameter is decreased (with some suitable factor), and the procedure is repeated again.

To get it to work in practice, you have to carefully think about how you do the parameter updates, and most often you would perform everything in the primal-dual space.

If you google for sillysdp, you find a simple implementation of a SDP solver implementing, essentially, example 11.9 in the Boyd & Vandenberghe reference which you are reading. Maybe a start for inspiration (since semidefinite programming is a generalization of an SOCP which you are solving, neglecting the logdet term in the objective, which doesn't complicate things really)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.