# Complexity of linear programming with restricted quadratic constraints

A problem instance is a linear program with the following kind of quadratic inequalities allowed: For some of the variables $$x_i$$, there is a variable $$s_i$$ (intuitively for approximating $$x_i^2$$, and distinct from all the $$x_j$$) and positive constants $$l_i,r_i$$, such that the following constraints are also included:

$$l_i ≤ x_i ≤ r_i$$ (confined to boxes; this is the case for every variable in my application)

$$l_i x_i ≤ s_i ≤ r_i x_i$$ (minor improvement over $$l_i^2 ≤ s_i ≤ r_i^2$$)

$$s_i ≥ x_i^2$$ (the approximation is tightly constrained from below, only)

Only the third line is quadratic. I include the first two lines in case they make the problem more tractable.

Is this a convex optimization problem? Can it be formulated as a semidefinite program? I see that the regions confining the values of $$x_i^2$$ are convex, but I doubt that implies the solution space as a whole is. [edit: I was wrong; according to @Vincenzo it is indeed that simple.]

The reason I suspect it might be efficiently solvable is that it seems it can be approximated well (provided the intervals $$[l_i,r_i]$$ are small, which they will be in my case) with increasing numbers of linear constraints over the same variables. In particular, each $$s_i ≥ x_i^2$$ is replaced by some $$k$$ linear constraints defined by

$$s_i ≥$$ line tangent to $$x_i^2$$ at the point $$x_i = a_1$$

...

$$s_i ≥$$ line tangent to $$x_i^2$$ at the point $$x_i = a_k$$

where each $$a_t$$ is a constant in $$[l_i,r_i]$$.

Optional question: In case the set of infeasible such problems is coNP-hard, is there nonetheless some method that is said to work well in practice?

• "a variable $sqx_i$"? Is it a product of three variable $s$, $q$ and $x_i$? Commented Dec 21, 2018 at 6:30
• Sorry, trying too hard with my variable naming. I changed it to $s_i$. Commented Dec 21, 2018 at 13:08

The intersection of convex sets is a convex set, therefore the region defined by your inequalities is convex. Essentially, that implies you can solve the problem efficiently within any fixed positive accuracy $$\epsilon>0$$.