Abstract
Most of the descent methods developed so far suffer from the computational burden due to a sequence of constrained quadratic subproblems which are needed to obtain a descent direction. In this paper we present a class of proximal-type descent methods with a new direction-finding subproblem. Especially, two of them have a linear programming subproblem instead of a quadratic subproblem. Computational experience of these two methods has been performed on two well-known test problems. The results show that these methods are another very promising approach for nondifferentiable convex optimization.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
A. Auslender, “Numerical methods for nondifferentiable convex optimization,”Mathematical Programming Study 30 (1987) 102–126.
D.P. Bertsekas and S.K. Mitter, “A descent numerical method for optimization problems with nondifferentiable cost functions,”SIAM Journal on Control 11 (1973) 637–652.
V.F. Demyanov and L.V. Vasil'ev,Nondifferentiable Optimization (Optimization Software, New York, 1985).
M. Fukushima, “A descent algorithm for nonsmooth convex optimization,”Mathematical Programming 30 (2) (1984) 163–175.
M. Gaudioso and M.F. Monaco, “A bundle type approach to the unconstrained minimization of convex nonsmooth functions,”Mathematical Programming 23 (2) (1982) 216–226.
J.E. Kelly, “The cutting plane method for solving convex programs,”Journal of the SIAM 8 (4) (1960) 703–712.
S. Kim and H. Ahn, “Convergence of a generalized subgradient method for nondifferentiable convex optimization,”Mathematical Programming 50 (1) (1991) 75–80.
S. Kim, H. Ahn and S.-C. Cho, “Variable target value subgradient method,”Mathematical Programming 49 (3) (1991) 359–369.
K.C. Kiwiel, “An ellipsoid trust region bundle method for nonsmooth convex minimization,”SIAM Journal on Control and Optimization 27 (1989) 737–757.
K.C. Kiwiel, “Proximity control in bundle methods for convex nondifferentiable minimization,”Mathematical Programming 46 (1) (1990) 105–122.
C. Lemaréchal, “Nonsmooth optimization and descent methods,” Research Report RR-78-4, IIASA (Laxenburg, Austria, 1977).
C. Lemaréchal and R. Mifflin, eds.,Nonsmooth Optimization (Pergamon Press, Oxford, 1978).
C.E. Lemke, “A method of solution for quadratic programs,”Management Science 8 (1962) 442–453.
R. Mifflin, “A modification and an extension of Lemarechal's algorithm for nonsmooth minimization,”Mathematical Programming Study 17 (1982) 77–90.
B.T. Polyak, “Minimization of unsmooth functionals,”Computational Mathematics and Mathematical Physics 9 (1969) 14–29.
R.T. Rockafellar,Convex Analysis (Princeton University Press, Princeton, NJ, 1970).
R.T. Rockafellar, “Monotone operators and the proximal point algorithm,”SIAM Journal on Control and Optimization 14 (1976) 877–898.
H.L. Royden,Real Analysis (Macmillan, New York, 1968).
N.Z. Shor,Minimization Methods for Nondifferentiable Functions (Springer, Berlin, 1985).
P. Wolfe, “A method of conjugate subgradients for minimizing nondifferentiable functions,”Mathematical Programming Study 3 (1975) 145–173.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Kim, S., Chang, KN. & Lee, JY. A descent method with linear programming subproblems for nondifferentiable convex optimization. Mathematical Programming 71, 17–28 (1995). https://doi.org/10.1007/BF01592242
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01592242