3
$\begingroup$

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!

$\endgroup$
  • $\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
5
$\begingroup$

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.

$\endgroup$
  • $\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
2
$\begingroup$

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

$\endgroup$
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.