Piecewise-Linear Approximation Methods for Nonseparable Convex Optimization

An algorithm is described for the solution of nonseparable convex optimization problems. This method utilizes iterative piecewise-linear approximation of the nonseparable objective function, but requires function values only along a translated set of axes, thereby avoiding the curse of dimensionality commonly associated with grid methods for multi-dimensional problems. A global convergence proof is given under the assumptions that the objective function is Lipschitz continuous and differentiable and that the feasible set is convex and compact. The method is well-suited to linearly constrained large-scale optimization, since the direction-finding problems reduce to linear programs of manageable size. It is particularly appropriate for nonlinear networks, since it preserves the network structure of the constraints. In addition, because the resulting objective function approximation is separable, this approach permits for certain problem classes a decomposition that may be exploited for parallel computation. Some numerical results on the CRYSTAL multicomputer are presented to illustrate this decomposition feature.