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?
