5
$\begingroup$

I have an optimization problem with a quadratic objective function and a bilinear constraint.

$$\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. Is there a general algorithm or convex relaxation technique 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$
7
  • 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
    Commented Oct 25, 2017 at 17:28
  • $\begingroup$ @copper.hat I forgot to mention: I also have $x\ge 0$ and $y\ge 0$ $\endgroup$
    – SelinH
    Commented Oct 25, 2017 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
    Commented Oct 25, 2017 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$ Commented Oct 25, 2017 at 20:09
  • $\begingroup$ @MichaelGrant Didn't you mean $\sqrt{A}$? $\endgroup$ Commented Oct 26, 2017 at 7:30

1 Answer 1

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

$\endgroup$
2
  • $\begingroup$ Thank you, appreciate it! $\endgroup$
    – SelinH
    Commented Oct 26, 2017 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$ Commented Oct 26, 2017 at 17:58

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .