Skip to main content
1 of 2
VS.
  • 1.8k
  • 1
  • 10
  • 25

Finding a point on a convex set

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$ a convex relation $f(u,v)\leq0$ holds where $f:\mathbb R^{2n}\rightarrow\mathbb R$ is a convex polynomial of degree $2$ and $m$ terms. Is it possibly to do this in $O(poly(ntm))$ time?

VS.
  • 1.8k
  • 1
  • 10
  • 25