# A “divide-and-conquer” iterative procedure for minimizing a sum of convex functions

For simplicity, let's assume $$f_i: \mathbb{R} \to \mathbb{R}$$ is convex and define

$$g(x) := \sum_{i=1}^{n}f_i(x)$$

Suppose we want to compute

$$x^* := \arg\min_{x \in \mathbb{R}} g(x)$$

The Newton-Raphson iterations take the following form

$$x_{t+1} = x_t - \left(\sum_{i=1}^{n}f''_i(x_t)\right)^{-1}\left(\sum_{i=1}^{n}f'_i(x_t)\right)$$

I was playing around and happened on the following idea. Suppose we solve \begin{align*} f_i'(x_i^*) = 0 \implies x_i^* = [f_i']^{-1}(0) \end{align*} Then, perform a Taylor series expansion for $$f_i$$ around $$x_i^*$$: \begin{align*} f_i(x) &\approx f_i(x_i^*) + f'_i(x_i^*)(x - x_i^*) + \frac{1}{2}f''_i(x_i^*)(x - x_i^*)^2 \\ &= f_i(x_i^*) + \frac{1}{2}f''_i(x_i^*)(x - x_i^*)^2 \end{align*} And so \begin{align*} g(x) \approx \sum_{i=1}^{n}[f_i(x_i^*) + \frac{1}{2}f''_i(x_i^*)(x - x_i^*)^2] \end{align*} and this approximation is minimized at

$$\widetilde{x} = \frac{\displaystyle\sum_{i=1}^{n}f''_i(x_i^*)x_i^*}{\displaystyle\sum_{i=1}^{n}f''_i(x_i^*)}$$

From this, I had the idea to define $$x_0 = \widetilde{x}$$ and continue iterations of this manner:

$$x_{t+1} = \dfrac{\displaystyle\sum_{i=1}^{n}f''_i(x_t)x_i^*}{\displaystyle\sum_{i=1}^{n}f''_i(x_t)}$$

How does this procedure compare against Newton-Raphson?

• Are you assuming that you know the minimum of each $f_i$? – Hans Engler May 16 at 1:33
• Yes, $x_i^*$ is the minimum of each $f_i$. – Tom Chen May 16 at 2:52
• First things first, do you know if $x^*$ is even a fixed point of your procedure, i.e. if $x_t=x^*$, is $x_{t+1}=x^*$ as well? – Rahul May 19 at 6:58