Complexity of linear programming with restricted quadratic constraints

Question

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$?
• Dustin Wehr: Sorry, trying too hard with my variable naming. I changed it to $s_i$.

Answer 1

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