# maximizing a quadratic over linear function

Recently I am trying to solve the following optimization problem: $$\begin{array}{cl} \text{maximize} & \frac{\left(c_1^T x\right)\left(c_2^T x\right)}{d^T x}\\ \text{subject to} & a^Tx\leq b \end{array}$$ where $c_1$, $c_2$, $d$, and $a$ are $n\times1$ real vectors with positive elements, $b\in\mathbb{R}^+$, and $x_i\geq0$ for $i=1,2,...,n$.

The Lagrangian of the optimization problem can be written as $$L=\frac{\left(c_1^T x\right)\left(c_2^T x\right)}{d^T x}+\theta\left(b-a^Tx\right)+\phi^Tx,$$ where $\theta\in \mathbb{R}$, $\theta\geq0$, $\phi$ is a $n\times1$ real vector and $\phi\geq0$. Then the KKT conditions are given by $$\frac{c_1^Tx}{d^Tx}c_2+\frac{c_2^Tx}{d^Tx}c_1-\frac{c_1^Tx}{d^Tx}\frac{c_2^Tx}{d^Tx}d=a^T\theta-\phi,$$ $$\theta\left(b-a^Tx\right)=0,$$ $$\phi^Tx=0,$$ where $\theta\geq0$, $\phi\geq0$, $x\geq0$ and $a^Tx\leq b$.

First, could it be proved that the maximum value will be obtained on the boundary, i.e., $x_1+x_2+\cdots +x_{n} = b$?

Secondly, is it possible to get the optimal solution from the above KKT conditions? If not, can we propose some algorithms to find a sub-optimal solution?

Thank you in advance.

-
For the first question, yes. If you are at point $\mathbf x$ with $\mathbf a^T\mathbf x<b$, you can move to $(1+\epsilon)\mathbf x$ which increases the objective by a factor of $1+\epsilon$ without violating any of the constraints. –  Rahul Jun 29 at 21:46
Hi @Rahul, Thank you! It really helps. –  Chang Jun 30 at 9:52
add comment

## 1 Answer

You can use de Lagrange Teorem and obtain a system with n-equations and n-variables.

-
add comment