In the following problem, $A$ is a given $\mathbb{R}^{m\times n}$ matrix: \begin{align} \mbox{minimize}\quad & x^TAy \\ \mbox{subject to}\quad & 1^Tx=1^Ty=1, \\ & x\ge 0,y\ge 0. \end{align} Despite the simple formulation, it is not easy at all for me. Hope that somebody can help. Many thanks!
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Would it help at all to use the Schur decomposition for $A$? Then you could reformulate as minimizing $(Px)^{H}\Delta(Py)$ where $P$ is a unitary matrix and $\Delta$ is upper triangular with the eigenvalues of $A$ on the diagonal. Not sure if this gets you anywhere though. $\endgroup$ – Doug Lipinski Jan 29 '15 at 1:47
-
$\begingroup$ @DougLipinski: If $A$ is square, maybe. $A$ may not be square, though. $\endgroup$ – Geoff Oxberry Jan 29 '15 at 3:46
-
$\begingroup$ @DougLipinski: Thanks. I have solved the problem. Please see my answer. $\endgroup$ – Khue Jan 29 '15 at 13:21
Add a comment
|
$\begingroup$
$\endgroup$
1
If there's no mistake then it's much easier than I thought.
We will show that the minimum is equal to the smallest component of $A$, denoted by $a_{i_0j_0}$ where $(i_0,j_0) = \arg\min_{(i,j)} a_{ij}$, and attained when $x_{i_0}=y_{j_0}=1$ and $x_i=y_i=0\quad\forall i\neq i_0,j\neq j_0.$
Indeed, we have \begin{align} x^TAy=\sum_{1\le i\le m}\sum_{1\le j\le n} a_{ij}x_iy_j \ge \sum_{1\le i\le m}\sum_{1\le j\le n} a_{i_0j_0}x_iy_j = a_{i_0j_0}\sum_{1\le i\le m}\sum_{1\le j\le n} x_iy_j = a_{i_0j_0}. \end{align}
Equality is easy to check.
-
$\begingroup$ It's very satisfying that an analytical solution drops out so nicely. I should have seen this based on my comment on Geoff's answer. $\endgroup$ – Doug Lipinski Jan 29 '15 at 18:57
$\begingroup$
$\endgroup$
3
Suppose that $m=n$ and $A = I$. Then your problem reduces to
\begin{align} \mbox{minimize}\quad & \sum_{i=1}^{n}x_{i}y_{i} \\ \mbox{subject to}\quad & \sum_{i=1}^{n}x_{i}=\sum_{i=1}^{n}y_{i}=1, \\ & x\ge 0,y\ge 0. \end{align}
The isolated bilinear terms are typically nonconvex, so solving the problem is challenging and typically requires special, expensive methods in order to calculate a globally $\varepsilon$-optimal solution.
For general $A$, I would expect similar behavior, because I don't see any way to group the bilinear terms to achieve convexity (say, for instance, via a sum-of-squares type formulation).
answered Jan 29 '15 at 1:26
-
$\begingroup$ This doesn't seem useful at all. I can minimize this case easily. If $n=1$ then $x=y=1$ and $x^\intercal A y = 1$. Otherwise the minimum is not unique but any choice where $x$ has at least one 0 and $y$ is non-zero only where $x$ is zero gives $x^\intercal y = 0$. Am I missing something? $\endgroup$ – Doug Lipinski Jan 29 '15 at 1:32
-
$\begingroup$ @DougLipinski: For the case where $n = 1$ and $A = I$, the Hessian is indefinite, which will foil some optimization solvers. When $A$ is more general, the Hessian will be constant, and there could be coefficients that make the resulting problem convex with positive semidefinite Hessian. I wouldn't be surprised if an algorithm returned zero for this case, sure. You're probably more likely to obtain a closed form solution. The point of this answer is to say: I wouldn't use an NLP solver here. $\endgroup$ – Geoff Oxberry Jan 29 '15 at 3:43
-
$\begingroup$ Thanks, @GeoffOxberry. In your problem, the minimum is clearly $0$, right? For example at $x_1=y_2=1$. I have solved my problem, please see my answer. $\endgroup$ – Khue Jan 29 '15 at 13:18
