Return to Question

added 68 characters in body

Source Link

edited Aug 24, 2011 at 13:01

111
2

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.

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.

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.

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$.

Edit: Added some more explanation in the second comment below.

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.

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.

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.

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$.

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.

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.

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.

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$.

Edit: Added some more explanation in the second comment below.

Source Link

asked Aug 23, 2011 at 21:22

111
2

Computing the intersection of dual affine subspaces

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.

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.

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.

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$.

convex-geometry convexity