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?

  • $\begingroup$ "a variable $sqx_i$"? Is it a product of three variable $s$, $q$ and $x_i$? $\endgroup$
    – John L.
    Dec 21 '18 at 6:30
  • $\begingroup$ Sorry, trying too hard with my variable naming. I changed it to $s_i$. $\endgroup$ Dec 21 '18 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.