A DESCENT ALGORITHM FOR MINIMIZING POLYHEDRAL CONVEX-FUNCTIONS

作     者：CLARK, DI OSBORNE, MR 

作者机构：AUSTRALIAN NATL UNIVINST ADV STUDIESDEPT CARDIOVASCCANBERRAACT 2600AUSTRALIA 

出 版 物：《SIAM JOURNAL ON SCIENTIFIC AND STATISTICAL COMPUTING》 (工业与应用数学会科学计算杂志)

年 卷 期：1983年第4卷第4期

页      面：757-786页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：descent methods projected gradient algorithm nondifferentiable functions subdifferential convex functions proximal transform polyhedral convexity maximum norm approximation piecewise linear functions penalty functions rank regression finite algorithms tableau form orthogonal transformations line search problem generation 

摘      要：The idea of continuation applied to the proximal transform of a polyhedral convex function is used to develop a general procedure for the construction of descent algorithms which has the property that it specializes to variants of the projected gradient method when applied to such problems as $l_1 $ and $l_\infty $ curve fitting and linear programming. The novelty in this approach lies in the application of a generic form for the subdifferential of a polyhedral convex function which provides an explicit representation in terms of a small number of parameters. This is illustrated by applications to $l_\infty $ curve fitting and the minimization of piecewise linear functions, and these examples serve to establish the feasibility of a unified approach. The power of the method is demonstrated by deriving an effective algorithm for the rank regression problem (the existence of such an algorithm makes practical the application of nonparametric procedures based on rank in robust estimation). The new approach also opens up the possibility of common implementation strategies, and a tableau like scheme is decribed based on the use of orthogonal matrix factorizations.