Global minimization Problem for $f(x) = \frac{|| Ax+b||^2}{c^Tx+d}$ I am having trouble proving the following and I would appreciate help with it:
Let $A \in \mathbb{R}^{m\times n}$ be of rank $n$, $b \in \mathbb{R}^m, c \in \mathbb{R}^n, d \in \mathbb{R},$ and $\Omega = \{x \in \mathbb{R}^n\;|\; c^Tx+d > 0\}$ . How can I show that the global minimizer of $f:\Omega \to \mathbb{R}$ given by
\begin{align*}
f(x) = \frac{|| Ax+b||^2}{c^Tx+d}
\end{align*}
is given by $x_* = (A^TA)^{-1}(-A^Tb + tc)$, where $t$ is a solution to a quadratic equation.
I would appreciate help with this. I am thinking of showing that $f$ is convex (not sure if it is), and then set the gradient to zero and find an expression for $x_*$, but the algebra is not working out.
 A: $
\def\tss{\mathop{\bigotimes}\limits}
\def\dss{\mathop{\odot}\limits}
\def\bbR#1{{\mathbb R}^{#1}}
\def\a{\alpha}\def\b{\beta}\def\g{\gamma}\def\t{\theta}
\def\l{\lambda}\def\s{\sigma}\def\e{\varepsilon}
\def\LR#1{\left(#1\right)}
\def\vecc#1{\operatorname{vec}\LR{#1}}
\def\diag#1{\operatorname{diag}\LR{#1}}
\def\Diag#1{\operatorname{Diag}\LR{#1}}
\def\trace#1{\operatorname{Tr}\LR{#1}}
\def\qiq{\quad\implies\quad}
\def\h{\tfrac{1}{2}}
\def\hh{\tfrac{\l}{2}}
\def\p{\partial}
\def\grad#1#2{\frac{\p #1}{\p #2}}
\def\cc#1{\color{green}{#1}}
\def\c#1{\color{red}{#1}}
\def\CLR#1{\c{\LR{#1}}}
\def\B{\b^{-1}}
\def\BB{\b^{-2}}
\def\fracLR#1#2{\LR{\frac{#1}{#2}}}
$For ease of typing, define the variables
$$\eqalign{
h &= Ax+b &\qiq dh = A\,dx \\
\a &= h^Th &\qiq d\a = 2h^Tdh = 2h^TA\,dx  \\
\b &= c^Tx + d &\qiq d\b = c^Tdx \\
}$$
Use these variable to write the objective function,
then calculate its gradient,
and finally set the gradient to zero and solve for $x$
$$\eqalign{
f &= \B\a \\
df &= \B\c{d\a} + \a\;d\B \\
 &= \B \CLR{2h^TA\,dx} - \a\BB\c{d\b} \\
 &= \B\LR{2A^Th}^Tdx - \B\a\B\c{c^Tdx} \\
 &= \B\LR{2A^Th - fc}^Tdx \\
\grad fx &= \B\LR{2A^Th - fc} \doteq 0 \\
\\
fc &= 2A^Th \;=\; 2A^T\LR{Ax+b} \\
x &= (A^TA)^+\LR{\h fc} - A^+b \\
  &= f\c{A^+(A^+)^T(\h c)} - \cc{A^+b} \\
  &= f\c{z} - \cc{y} \\
}$$
where $A^+$ denotes the pseudoinverse.
In addition to $\{y,z\},\,$ let's define two more vectors
and their products
$$\eqalign{
w &= (Ay - b), \qquad\quad p = Az = \h(A^+)^Tc \\
\\
p^Tp &= (\h c)^T\c{A^+(A^+)^T(\h c)} \;=\; \h c^Tz \\
p^Tw &= \h c^TA^+(Ay-b) \\
 &= \h c^T(A^+Ay-\cc{A^+b}) \\
 &= \h c^T(Iy-y) \\
 &= 0 \;\;(!) \\
}$$
The expression obtained thus far is not a closed-form solution for $x$ because the $f$ on the RHS is itself is a rather complicated function of
$x\;\big($NB: The expression does represent a rather effective method for solving the problem numerically via iteration$\big)$
However, substituting the $x$ expression back into the objective function will create an implicit equation for
$f$, which we can (hopefully) make explicit, then substitute to produce a closed-form solution for the
$x$ vector.
But in order to carry this out, we'll need a two more scalar variables
$$\eqalign{
&\t = \LR{d-c^Ty}, \qquad &\mu = c^Tz \;=\; 2\,\|p\|^2 \\
}$$
Substituting into the objective function
$$\eqalign{
&f = \frac{\|Ax+b\|^2}{{c^Tx+d}}
  \;=\; \frac{\|fp-w\|^2}{f\mu + \t} \\
&\LR{f\mu + \t}f \;=\; \LR{fp-w}^T\LR{fp-w} \\
&2\,\|p\|^2f^2 + \t f \;=\; \|p\|^2 f^2 + \|w\|^2 \\
&\|p\|^2\c{f^2} + \t\c{f} - \|w\|^2 \;=\; 0 \\
}$$
This quadratic can be solved for the positive root and thence for the desired solution vector
$$\eqalign{
\c{f_{*}} &= \frac{\sqrt{\t^2+4\,\|p\|^2\|w\|^2} - \t}{2\,\|p\|^2} \\
x_{*} &= {f_{*}}A^+(A^+)^T(\h c) - A^+b \\
}$$
It is worth noting that the problem statement obfuscates the fact that the variable
$\,t = \h f,\,$ yet this plays a key role in the solution.
