Abstract
The strategy of Restricted Simplicial Decomposition is extended to convex programs with convex constraints. The resulting algorithm can also be viewed as an extension of the (scaled) Topkis—Veinott method of feasible directions in which the master problem involves optimization over a simplex rather than the usual line search. Global convergence of the method is proven and conditions are given under which the master problem will be solved a finite number of times. Computational testing with dense quadratic problems confirms that the method dramatically improves the Topkis—Veinott algorithm and that it is competitive with the generalized reduced gradient method.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
J. Abadie and J. Carpentier, “Generalization of the Wolfe reduced gradient method to the case of nonlinear constraints,” in: R. Fletcher, ed.,Optimization (Academic Press, 1969).
J. Abadie, “Methods du gradient redirect generalise: Le code GRGA,” Note HI 1756/00, Electricite de France (Paris, France, 1975).
D.P. Bertsekas, “on the Goldstein—Levitin—Polyak gradient projection method,”IEEE Transactions on Automatic Control AC-21 (1976) 174–184.
D.P. Bertsekas, “Projected Newton methods for optimization problems with simple constraints,”SIAM Journal of Control and Optimization 20 (1982) 221–246.
A.R. Colville, “A comparative study of nonlinear programming codes,” in: H.W. Kuhn, ed.,Proceedings of the Princeton Symposium on Mathematical Programming (Princeton University Press, Princeton, NJ, 1970).
G.E. Forsythe and C.B. Moler,Computer Solution of Linear Algebraic Systems (Prentice-Hall, Englewood Cliffs, NJ, 1967).
P.E. Gill, W. Murray, M.A. Saunders and M.H. Wright, “User's guide for SOL/NPSOL+: A Fortran package for nonlinear programming,” Technical Report SOL 83-12, Systems Optimization Laboratory, Stanford University (Stanford, CA, 1983).
D.W. Hearn, S. Lawphongpanich and J.A. Ventura, “Restricted simplicial decomposition: computation and extensions,”Mathematical Programming Study 31 (1987) 99–118.
D.W. Hearn, S. Lawphongpanich and J.A. Ventura, “Finiteness in restricted simplicial decomposition,”Operations Research Letters 4 (1985) 125–130.
D.E. Knuth,The Art of Computer Programming, Vol. 3 (Addison-Wesley, Reading, MA, 1973).
O.L. Mangasarian,Nonlinear Programming (McGraw-Hill, New York, 1969).
D.M. Topkis and A.F. Veinott, “On the convergence of some feasible direction algorithms for nonlinear programming,”SIAM Journal of Control 5 (1967) 268–279.
W.I. Zangwill,Nonlinear Programming:a Unified Approach (Prentice-Hall, Englewood Cliffs, NJ, 1969).
Author information
Authors and Affiliations
Additional information
This research was supported in part by NSF Grants ECS-8516365 and DDM-8814075.
Rights and permissions
About this article
Cite this article
Ventura, J.A., Hearn, D.W. Restricted simplicial decomposition for convex constrained problems. Mathematical Programming 59, 71–85 (1993). https://doi.org/10.1007/BF01581238
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01581238