I am trying to solve the following problem, which is a simplification of our original question:

$\max\limits_{x,y}\min \{x_iy_i-b_i \mbox{ for } i=1,\ldots, n: x,y\in \Delta_n\}$

where $\Delta_n$ is n-dimensional unit simplex and $b_i$'s are arbitrary nonnegative numbers. $x_i,y_i$ is the $i^\mbox{th}$ entry of $x,y$ resp..

When all $b_i=0$, I can argue the optimum is $\frac1{n^2}$. But in general I have no progress. On the other hand, it would also be nice to show that this problem is NP-hard, but I am unable to think of a reduction from a combinatorial problem. It would be awesome to hear some suggestions! Thanks in advance.


  • $\begingroup$ What is the variable over which the inner minimization carried over? $\endgroup$ – csTheoryBeginner Nov 30 '17 at 3:35
  • $\begingroup$ it is a max-min problem, another way to state it is $\max\limits_{x,y\in\Delta_n} \{u: u\leq x_iy_i-b_i\forall i\}$ $\endgroup$ – Orion T Nov 30 '17 at 3:48
  • $\begingroup$ Hi D.W. when I say simplex I mean a unit simplex. Thanks for pointing this out. Note those n constraints $u \leq x_iy_i - b_i$ are all nonconvex. And Vavasis's approximation for indefinite matrix works when objective is a quadratic form and constraints are linear. Boyd observes when each constraint matrix only has one negative eigenvalue then it can be reduced to solving a set of second-order cone programs. But our constraint matrix does not have this property either... $\endgroup$ – Orion T Nov 30 '17 at 11:36

I assume that your "unit simplex" is the set of all nonnegative points whose coordinates sum to 1, $\{x: x_i\ge 0, \sum x_i = 0\}.$

Note that the max occurs when $x=y$ as $x_iy_i\le \left(\frac{x_i+y_i}2\right)^2$. This makes your problem easy to solve, as at the optimal $x$ either $x_i^2-b_i$ is the solution, or $x_i=0$ and the solution is less than $-b_i$, so a binary search on the sorted $b_i$ should get your answer quickly.


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.