0
$\begingroup$

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

Improve this question
$\endgroup$
3
  • $\begingroup$ What is the variable over which the inner minimization carried over? $\endgroup$
    – csTheoryBeginner
    Commented Nov 30, 2017 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
    Commented Nov 30, 2017 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
    Commented Nov 30, 2017 at 11:36

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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