# Minimizing a quadratic-over-linear fractional function

This is from Boyd & Vandenberghe's Convex Optimization:

Show that $$\min_{x \in \left\{x : c^T x +d > 0 \right\}} \ \frac{\|Ax-b\|_2^2}{c^T x + d}$$ has a minimizer $$x^* = x_1 +t x_2$$ where $$x_1 = \left( A^T A \right)^{-1} A^T b, \qquad x_2=\left( A^T A \right)^{-1} c$$ and $$t \in \mathbb{R}$$ is obtained by solving a quadratic equation.

From the structure of the solution, it seems like I am supposed to split the problem into two parts, but apart from that I don't really understad how to solve this. I tried to differentiate to find the minimizer, but I didn't get anything of this form. (In the problem before this, we had to show that $$f$$ is closed, if that is relevant).

• Which section of the book? Mar 29 at 6:00

Let us rewrite the problem to a convex optimization problem by adding a variable $s$: $$\min \{ s||Ax-b||^2 : s = 1/(c^Tx + d) \}$$ and then substituting $y = xs$: $$\min \{ s||A(y/s)-b||^2 : (c^Ty + ds) = 1 \}$$ Note that the objective function is the perspective of a convex function, and is therefore convex. The KKT stationarity conditions for $y$ and $s$ read: $$2(A^TA(y/s)-A^Tb) + \lambda c = 0$$ $$-2\frac{||Ax||^2}{s^2} + b^T b + \lambda d = 0$$ The first condition can be solved for $y/s$: $$x = \frac{y}{s} = (A^TA)^{-1}A^Tb-\frac{1}{2} \lambda (A^TA)^{-1} c$$ Your $t$ is now $-\lambda/2$. To find $\lambda$, consider the KKT stationarity condition for $s$, and plug in $s = 1/(c^Tx + d)$ to obtain the quadratic equation.
• @MichaelGrant if we do not have norm-2 (i.e. $\|.\|^2$) and if $A$ is a vector then according to the LinAlg method the objective function will still be convex. But in Convex Optimization book it is written that it a linear fractional program and the objective function is quasiconvex. Doesn't it mean that there is some contradiction. Mar 5, 2019 at 8:44
• @LinAlg if we do not have norm-2 (i.e. $\|.\|^2$) and if $A$ is a vector then according to the your method the objective function will still be convex. But in Convex Optimization book it is written that it a linear fractional program and the objective function is quasiconvex. Doesn't it mean that there is some contradiction. Mar 5, 2019 at 8:46