How to find ellipsoid bounding the intersection of an ellipsoid and half-space?

Question

How does one prove that the bounding ellipsoid $E(A', a')$ of the intersection of an ellipsoid $E(A,a) = [ x | (x-a)^TA^{-1}(x-a) ]$ and half-space $H = [x | c^Tx \le c^Ta ]$ is given by the following: (all in n-dimensional space over the reals)

Where $b = (1/\sqrt{c^TAc})Ac$

Where did $A'$ and $a'$ expressions come from? Thanks in advance!

References: http://en.wikipedia.org/wiki/Ellipsoid_method https://www.zib.de/groetschel/pubnew/paper/groetschellovaszschrijver1988.pdf pg.70 is the above image

Answer 1

I do not have the proof for you, but I do have some good reading material: Martin Henk, "Löwner-John Ellipsoids", Documenta Mathematica, Extra Volume: Optimization Stories (2012), pp. 95-106. A PDF of this article can be found here. These are stable links.

A discussion of Khachiyan's ellipsoid algorithm begins on page 101; at the top of this page, you will see a figure depicting the construction of an enclosing ellipsoid. There you will also find several references that discuss the theoretical development of the algorithm; and certainly, in one of those references, you will find a derivation and/or proof of the above formulae.

Perhaps you will find the article a sufficiently interesting treatment of the general topic that you won't need to worry yourself with a specific proof :-)

Answer 2

I found the relevant proofs in Appendix B (p. 1082) of:

http://www.math.uwaterloo.ca/~cswamy/courses/co759/approx-material/ellipsoid-survey.pdf

Which was a reference in the paper posted by Michael Grant. Interestingly, it proves the bounding ellipsoid update formulas for more general cases than my question asked. I.e. for different parameters of alpha the cuts are deep cuts or shallow cuts, etc (interesting because for a deep cut, the new bounding ellipsoid will be lower volume, so possibly faster algorithm convergence).