Proximal decomposition via alternating linearization

A new approximate proximal point method for minimizing the sum of two conve x functions is introduced. It replaces the original problem by a sequence o f regularized subproblems in which the functions are alternately represente d by linear models. The method updates the linear models and the prox cente r, as well as the prox coefficient. It is monotone in terms of the objectiv e values and converges to a solution of the problem, if any. A dual version of the method is derived and analyzed. Applications of the methods to mult istage stochastic programming problems are discussed and preliminary numeri cal experience is presented.