I have a question: What is the time complexity for solving a convex feasibility problem (particularly, this question focuses on the linear feasibility problem)? Specifically, the feasibility problem considered is expressed as follows: \begin{align} \mathrm {find} ~&\mathcal{P} \\ \mathrm {s.t.~} &\sum_{n=1}^{N} P_{n}^{A} g_{n} \geq \gamma\left(\sum_{n=1}^{N} P_{n}^{B} g_{n}+\sigma\right), \\ &P_{l}^{B} g_{l} \geq v\left(\sum_{n \neq l} P_{n}^{B} g_{n}+\sigma\right), \\ &P_{n}^{A}+P_{n}^{B} \leq P_{n}, \forall n \in\{1, \cdots, N\}, \end{align} where $\mathcal{P} \triangleq\left\{P_{1}^{A}, \cdots, P_{N}^{A}, P_{1}^{B}, \cdots, P_{N}^{B}\right\}$ are the variables; $\left\{g_{1}, \cdots, g_{N}\right\}, \gamma, \sigma, v, l,\left\{P_{1}, \cdots, P_{N}\right\}$ are constants.
This is a feasibility problem for a linear program, and I solved it using the CVX toolbox. In my opinion, in CVX, it seems that the feasibility problem mentioned above is also solved by SDPT3 via interior-point method. Therefore, the time complexity for solving this feasibility problem is the time complexity of interior-point method, which is $\mathcal{O}\left(N^{3.5}\right) $, where $N$ is the number of variables.
Is this opinion correct? If it is not correct, what is the time complexity for solving this feasibility problem?
Thanks!
In general, linear programming (LP) can be cast as a linear feasibility (LF) problem by encoding primal/dual feasibility of the polyhedra and strong duality. So there is a polynomial (trivial) reduction from LP to LF, which shows that LP is no harder than LF. On the other hand, LF is no harder than LP since we can set the objective to 0 in LP to recover LF (another trivial reduction).
Unless you know something more about your problem, it appears (to me) to be the same complexity as LP.