Majorization on the Sphere

The problem of minimizing $f$ over a closed set $\mathcal{X}$ can be formulated as $$\inf_{r\geq 0}\min_{x\in\mathcal{X}\cap\mathcal{S}_r} f(x),$$ where $\mathcal{S}_r\mathop{=}\limits^{\Delta}\{x\mid x'x=r\}$. The set $\mathcal{X}\cap\mathcal{S}_r$ is compact so the inner minimum $f_r=\min_{x\in\mathcal{X}\cap\mathcal{S}_r} f(x)$ is attained for continuous $f$.

If $f$ is continuously differentiable on the ball $\mathcal{T}_r\mathop{=}\limits^{\Delta}\{x\mid x'x\leq r\}$ then $$h_r(y)\mathop{=}\limits^{\Delta}\max_{z\in\mathcal{T}_r}\max_{0\leq\lambda\leq 1} z'\mathcal{D}^2f(y+\lambda z))z$$ is well-defined. If $x,y\in\mathcal{S}_r$ then $y+\lambda(x-y)\in\mathcal{T}_r$ for all $0\leq\lambda\leq 1$. So $$f(x)\leq f(y)+(x-y)'\mathcal{D}f(y)+h_r(y)(r-x'y),$$ and we have a linear majorization on $\mathcal{S}_r$. The corresponding majorization algorithm is $$x^{(k+1)}=\mathcal{P}_r(x^{(k)}-\frac{1}{h_r(x^{(k)})}\mathcal{D}f(x^{(k)})),$$ with $\mathcal{P}_r$ projection on the sphere $\mathcal{S}_r$.

S-majorization by a quadratic. The sublevel set for $$g(x,y)=f(y)+(x-y)'b+\frac12(x-y)'A(x-y)$$ with $A$ positive definite is the ellipse $$\mathcal{L}(y)=\{x\mid (x-z(y))'A(x-z(y))\leq b'A^{-1}b\},$$ with $z\mathop{=}\limits^{\Delta}y-A^{-1}b.$ Thus for S-majorization we need to choosed $A$ and $b$ in such a way that $g$ majorizes $f$ on $\mathcal{L}(y).$ The problem is simplified, of course, if we choose $b=\mathcal{D}f(y).$