# Optimization of linear objective with non-convex quadratic constraint

Is there any technique to deal with a problem where we have a linear objective function and one or many quadratic non-convex function(s) like the problem below?

$$\begin{array}{ll} \text{minimize} & c_1 x + c_2 y\\ \text{subject to} & xy = c\end{array}$$

where $c$, $c_1$ and $c_2$ are arbitrary real constants.

• Have you tried the method of "Lagrange multipliers"? – kimchi lover Nov 5 '17 at 15:03
• There is no global minimum. – Rodrigo de Azevedo Nov 6 '17 at 10:46
• Define what you mean with "deal with". Solving globaly, locally, optimality certificates? – Johan Löfberg Nov 6 '17 at 21:46

You can apply the Lagrange multiplier method.

$\mathcal L=c_1x+c_2y+\lambda[c-xy]$

$\frac{\partial \mathcal L}{\partial x}=c_1-\lambda y=0\Rightarrow c_1=\lambda y\quad (1)$

$\frac{\partial \mathcal L}{\partial y}=c_2-\lambda x=0\Rightarrow c_2=\lambda x \quad (2)$

$\frac{\partial \mathcal L}{\partial \lambda}=c-xy=0\Rightarrow c=xy \quad (3)$

Dividing (1) by (2):

$\frac{c_1}{c_2}=\frac{y}{x}\Rightarrow y=\frac{c_1}{c_2}x$

Inserting the term for $c$ in $(3)$

$c= \frac{c_1}{c_2}x^2$

$x_1= \sqrt{c\frac{c_2}{c_1}}, x_2=-\sqrt{c\frac{c_2}{c_1}}$

$\Rightarrow y_1=\frac{c_1}{c_2} \sqrt{c\frac{c_2}{c_1}}, y_2=-\frac{c_1}{c_2} \sqrt{c\frac{c_2}{c_1}}$

The two stationary points $(x_1/y_1)$ and $(x_2/y_2)$ can be local maximums or local minimums. Insert the corresponding values into the $\texttt{bordered Hessian}$ to evaluate what kind of stationary points the are.

$$\tilde H=\left( \begin{array}{} 0 & \frac{\partial^2 \mathcal L}{\partial \lambda\partial x}& \frac{\partial^2 \mathcal L}{\partial \lambda\partial y} \\ \frac{\partial^2 \mathcal L}{\partial \lambda\partial x} & \frac{\partial^2 \mathcal L}{\partial x\partial x} & \frac{\partial^2 \mathcal L}{\partial x\partial y} \\ \frac{\partial^2 \mathcal L}{\partial \lambda\partial y} & \frac{\partial^2 \mathcal L}{\partial x\partial y} & \frac{\partial^2 \mathcal L}{\partial y\partial y} \end{array}\right)$$

If $det \ \tilde H(x_0,y_0) >0 \Rightarrow \texttt{it´s a (local) maximum}$

If $det \ \tilde H(x_0,y_0) <0 \Rightarrow \texttt{it´s a (local) minimum}$

• Thanks a lot for the elaborate solution. This would be of help for my work. Could you please point out to any reference as well for more details? – Sourav Mondal Nov 7 '17 at 3:50
• @SouravMondal You´re welcome. On page 6 there is an numerical example. web.sgh.waw.pl/~mantosi/MO/materialy2.pdf – callculus Nov 7 '17 at 18:05