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 to technical written.

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

Thanks in advance


Your Answer

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

Browse other questions tagged or ask your own question.