1
$\begingroup$

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.

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

0

Reset to default

You must log in to answer this question.