# 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$.

Now I just want to do some relaxation to find an algorithm to obtain a sub-optimal solution. But I still have no clues. Could someone help me?

Thanks.

-
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 '14 at 21:46
Hi @Rahul, Thank you! It really helps. – Chang Jun 30 '14 at 9:52