Convex Optimization · Problem 9.2

Equality constrained minimization — Boyd & Vandenberghe

Mathematics — Optimization · minimizing-quadratic-over-linear-fractional-function

Problem

Minimizing a quadratic-over-linear fractional function. Consider the problem of minimizing the function

f : \mathbf{R}^n \to \mathbf{R}

, defined as

f(x) = \frac{\|Ax - b\|_2^2}{c^T x + d}, \qquad \mathbf{dom}\, f = \{x \mid c^T x + d > 0\}.

We assume

\mathbf{rank}\, A = n

and

b \notin \mathcal{R}(A)

. ((a)) Show that

f

is closed. ((b)) Show that the minimizer

x^\star

f

is given by

x^\star = x_1 + t x_2

where

x_1 = (A^T A)^{-1} A^T b

x_2 = (A^T A)^{-1} c

, and

t \in \mathbf{R}

can be calculated by solving a quadratic equation.