User - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T06:00:58Z http://mathoverflow.net/feeds/user/17348 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> http://mathoverflow.net/questions/73525/computing-the-intersection-of-dual-affine-subspaces Comment by 2011-08-24T07:04:41Z 2011-08-24T07:04:41Z Apologies. The first plane is a simple $k$ dimensional affine subspace of $R^d$ of the form $Ax=B$. The other plane is defined depending on the convex function $\phi$ , and is of the form $C \nabla y = D$, where $C$ is a $d−k$ by $d$ dimensional matrix, and $\nabla y$ represents the gradient vector induced by $\phi$ at point $y \in R^d$. This is clearly not an affine plane in the conventional sense and describes some sort of curved surface.However, in the &quot;dual space&quot; obtained by taking the Legendre transform of $(R^n, \phi)$, this will be an affine plane.