# 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$$

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.

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