Minimizing a quadratic-over-linear fractional function

Question

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).

Answer 1

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.