Computing the intersection of dual affine subspaces - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T01:46:48Z http://mathoverflow.net/feeds/question/73525 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/73525/computing-the-intersection-of-dual-affine-subspaces Computing the intersection of dual affine subspaces unknown (google) 2011-08-23T21:22:22Z 2011-08-24T13:01:08Z <p>Suppose we have a convex function , $\phi(x): R^d \to R$. It is well known that the Legendre transform of $\phi$ is also a convex function, and can (loosely) be thought of as the dual or derivative space.</p> <p>Given a hyperplane in the original space of the form $Ax =B$ where $A$ is a $k$ by $d$ matrix in the original space and another hyperplane $C y = D$ in the dual space (where C is a $d-k$ by $d$ matrix), how can I go about computing the unique point determined by the intersection of the two planes? I believe that it is impossible to compute analytically,for example, for the function $\phi(x) = \sum_{i=1}^{d} x_i \log x_i$. However, I'm thinking on finding a good numerical algorithm.</p> <p>There are generic numerical optimization methods - start with a point on one plane, move in the direction of the gradient towards the other - but I've found poor performance trying to do this with the MATLAB toolbox and it also doesn't seem too geometrically insightful. I'm thinking on whether there exists a solution that could somehow exploit the dual nature of the two spaces.</p> <p>Additional comments: Broader comments on the geometry of the situation, or suggestions on how to approach this are also very helpful. Understanding the geometric structure is as important to me as a solution :). Also, if it might ease analysis, consider that the $d$ rows of $A$ and $C$ taken together form an orthogonal basis of $R^d$.</p> <p>Edit: Added some more explanation in the second comment below.</p>