Given a compact bounded convex set $\mathcal C\subseteq\mathbb R^n$ given by $t$ hyperplane inequalities I want to find a point $u\in\mathcal C$ such that for all $v\in\mathcal C$

  1. a convex relation $f(u,v)\leq0$ and

  2. linear inequality condition $B(u,v)^T\leq b$ (note $(u,v)^T$ is transpose of vector of $u$ and $v$ variables)

hold where $f:\mathbb R^{2n}\rightarrow\mathbb R$ is a convex polynomial of degree $2$ and $m$ terms and $B\in\mathbb R^{m'\times2n}$ and $b\in\mathbb R^{m'}$ are known. Is it possibly to do this in $O(poly(ntmm'))$ time?

Is it possible to do this at least in trivial case of $f\equiv$ constant.

  • $\begingroup$ Your question seems to be answered affirmatively by the polynomial time interior point method of Kamarkar $\endgroup$ – Manfred Weis Apr 15 at 3:07
  • $\begingroup$ @ManfredWeis are you sure on this? $\endgroup$ – VS. Apr 17 at 0:32
  • $\begingroup$ That was only about "finding a point on a convex set". $\endgroup$ – Manfred Weis Apr 17 at 13:34

Your Answer

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

Browse other questions tagged or ask your own question.