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.

  • $\begingroup$ Have you tried the method of "Lagrange multipliers"? $\endgroup$ – kimchi lover Nov 5 '17 at 15:03
  • $\begingroup$ There is no global minimum. $\endgroup$ – Rodrigo de Azevedo Nov 6 '17 at 10:46
  • $\begingroup$ Define what you mean with "deal with". Solving globaly, locally, optimality certificates? $\endgroup$ – 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}$

  • $\begingroup$ 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? $\endgroup$ – Sourav Mondal Nov 7 '17 at 3:50
  • $\begingroup$ @SouravMondal You´re welcome. On page 6 there is an numerical example. web.sgh.waw.pl/~mantosi/MO/materialy2.pdf $\endgroup$ – callculus Nov 7 '17 at 18:05

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.