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.