Gpower

Rewrite for minimizing a concave function 02/21/15

Consider the problem of maximizing a convex function $f$ on a compact set $\mathbf{X}$. The function is not necessarily differentiable, the constraint set is not necessarily convex. Define $$f^\star\mathop{=}\limits^{\Delta}\max_{x\in\mathcal{X}} f(x).$$ For all $x,y$ and $z\in\partial f(y)$ we have the subgradient inequality $$f(x)\geq f(y)+z'(x-y).$$ Thus the majorization algorithm is $$x^{(k+1)}\in\mathbf{Arg}\mathop{\mathbf{max}}\limits_{x\in\mathcal{X}} z'x,$$ where $z$ is any element of $\partial f(x^{(k)})$.

Define $$\delta(y)\mathop{=}\limits^{\Delta}\max_{x\in\mathcal{X}} z'(x-y)$$ where $z\in\partial f(y)$. Then $\delta(y)\geq 0$ and $\delta(y)$ vanishes only when $z$ is in the normal cone to $\mathbf{conv}(\mathcal{X})$ at $y$. $$f(x^{(k+1)})\geq f(x^{(k)})+\delta(x^{(k)}).$$ It follows that $$f(x^{(k+1)})-f(x^{(0)})=\sum_{i=0}^k(f(x^{(i+1)})-f(x^{(i)}))\geq\sum_{i=0}^k\delta(x^{(i)}),$$ and $$S_k\mathop{=}\limits^{\Delta}\sum_{i=0}^k\delta(x^{(i)})\leq f^\star-f(x^{(0)}).\tag{1}$$ Thus the partial sums $S_k$ define an increasing sequence, which is bounded above and consequently converges. This implies its terms converge to zero. i.e. $$\lim_{k\rightarrow\infty}\delta(x^{(k)})=0.$$ If $$\delta_k\mathop{=}\limits^{\Delta}\min_{0\leq i\leq k}\delta(x^{(i)}),$$ then, from $\text{(1)}$, $$\delta_k\leq\frac{f^*-f(x^{(0)})}{k+1}.$$