1
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ Maybe this question is clear to the experts, but I could sure use some clarification. For example, what is meant by the intersection of two planes when one is "in the original space" and the other is "in the dual space"? And what does that have to do with $\phi$ and its Legendre transform? $\endgroup$
    – Andreas Blass
    Commented Aug 24, 2011 at 0:52
  • 1
    $\begingroup$ 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 "dual space" obtained by taking the Legendre transform of $(R^n, \phi)$, this will be an affine plane. $\endgroup$
    – user17348
    Commented Aug 24, 2011 at 7:04

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .