Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.