2
$\begingroup$

I have an optimization problem with a quadratic objective function

$$\begin{array}{ll} \text{minimize} & f(x) + g(y)\\ \text{subject to} & xy \ge A\\ & x \ge 0\\ & y \ge 0\end{array}$$

Both $f$ and $g$ are convex functions. And there's a bilinear constraint. Is there a general algorithm or convex relaxation techniques to deal with such constraints?

I do get an optimal solution from conventional solvers employing Quadratic Constraint Programming. But can I claim this is a global optimal or unique equilibrium given that the constraints are non-convex? How can I explore the locality of this solution? Should I try different initializations to see if the equilibrium is different? Thank you.

$\endgroup$
  • 2
    $\begingroup$ If $A >0$ then you could separate into two convex problems, one with $x \ge 0, y \ge 0$ and one with $x \le 0 , y \le 0$. $\endgroup$ – copper.hat Oct 25 '17 at 17:28
  • $\begingroup$ @copper.hat I forgot to mention: I also have $x\ge 0$ and $y\ge 0$ $\endgroup$ – SelinH Oct 25 '17 at 17:37
  • 1
    $\begingroup$ In that case the problem is convex and the solution is an optimal one. The feasible region is convex and the cost is convex. $\endgroup$ – copper.hat Oct 25 '17 at 17:39
  • $\begingroup$ Note that if $x,y\geq 0$, then $xy\geq A$ is equivalent to $\sqrt{xy} \geq A$. And that's a form that's useable in nonlinear convex solvers. $\endgroup$ – Michael Grant Oct 25 '17 at 20:09
  • $\begingroup$ @MichaelGrant Didn't you mean $\sqrt{A}$? $\endgroup$ – Rodrigo de Azevedo Oct 26 '17 at 7:30
1
$\begingroup$

$$\begin{array}{ll} \text{minimize} & f(x) + g(y)\\ \text{subject to} & xy \ge a\\ & x \ge 0\\ & y \ge 0\end{array}$$

where both $f$ and $g$ are convex quadratic functions and $a > 0$. The feasible region is convex and, since $a > 0$, also LMI-representable

$$\{ (x,y) \in \mathbb R^2 : x \geq 0 \land y \geq 0 \land x y \geq a \} = \left\{ (x,y) \in \mathbb R^2 : \begin{bmatrix} x & \sqrt{a}\\ \sqrt{a} & y\end{bmatrix} \succeq \mathrm O_2 \right\}$$

Hence, the original optimization problem can be rewritten as follows

$$\begin{array}{ll} \text{minimize} & f(x) + g(y)\\ \text{subject to} & \begin{bmatrix} x & \sqrt{a}\\ \sqrt{a} & y\end{bmatrix} \succeq \mathrm O_2\end{array}$$

Introducing optimization variables $s, t \in \mathbb R$, we rewrite the optimization problem in epigraph form

$$\begin{array}{ll} \text{minimize} & s + t\\ \text{subject to} & f(x) \leq s\\ & g(y) \leq t\\ & \begin{bmatrix} x & \sqrt{a}\\ \sqrt{a} & y\end{bmatrix} \succeq \mathrm O_2\end{array}$$

Let $f$ and $g$ be

$$f (x) := f_0 + f_1 x + f_2 x^2 \qquad\qquad\qquad g (y) := g_0 + g_1 y + g_2 y^2$$

where $f_2, g_2 > 0$ (to ensure convexity). Inequality constraints $f(x) \leq s$ and $g(y) \leq t$ can be written in LMI form, as follows

$$\begin{bmatrix} 1 & \sqrt{f_2} \, x\\ \sqrt{f_2} \, x & s - f_0 - f_1 x\end{bmatrix} \succeq \mathrm O_2$$

$$\begin{bmatrix} 1 & \sqrt{g_2} \, y\\ \sqrt{g_2} \, y & t - g_0 - g_1 y\end{bmatrix} \succeq \mathrm O_2$$

These LMIs introduce inequalities $s - f_0 - f_1 x \geq 0$ and $t - g_0 - g_1 y \geq 0$, which are redundant. Note that lines $s = f_0 + f_1 x$ and $t = g_0 + g_1 y$ are tangent to the graphs of $f$ and $g$, respectively.

Hence, we obtain a semidefinite program (SDP) in variables $x, y, s, t \in \mathbb R$

$$\begin{array}{lc} \\ \text{minimize} & s + t\\\\ \text{subject to} & \begin{bmatrix} 1 & \sqrt{f_2} \, x & & & \\ \sqrt{f_2} \, x & s - f_0 - f_1 x & & & \\ & & 1 & \sqrt{g_2} \, y & \\ & & \sqrt{g_2} \, y & t - g_0 - g_1 y & \\ & & & & x & \sqrt{a}\\ & & & & \sqrt{a} & y\end{bmatrix} \succeq \mathrm O_6\\\\\end{array}$$

which can be solved numerically using any SDP solver.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you, appreciate it! $\endgroup$ – SelinH Oct 26 '17 at 17:38
  • $\begingroup$ @SelinH In case you solve the SDP above, please let me know if you obtain the same solution you initially obtained. $\endgroup$ – Rodrigo de Azevedo Oct 26 '17 at 17:58

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.