# Max-min of a nonconvex quadratic problem

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.

Orion

• What is the variable over which the inner minimization carried over? – csTheoryBeginner Nov 30 '17 at 3:35
• 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\}$ – Orion T Nov 30 '17 at 3:48
• 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... – 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.