# 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"? Commented Nov 5, 2017 at 15:03
• There is no global minimum. Commented Nov 6, 2017 at 10:46
• Define what you mean with "deal with". Solving globaly, locally, optimality certificates? Commented Nov 6, 2017 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? Commented Nov 7, 2017 at 3:50
• @SouravMondal You´re welcome. On page 6 there is an numerical example. web.sgh.waw.pl/~mantosi/MO/materialy2.pdf Commented Nov 7, 2017 at 18:05