×

A finite algorithm for finding the projection of a point onto the canonical simplex of \({\mathbb R}^ n\). (English) Zbl 0571.90074

An algorithm of successive location of the solution is developed for the problem of finding the projection of a point onto the canonical simplex in the Euclidean space \({\mathbb{R}}^ n\). This algorithm converges in a finite number of steps. Each iteration consists in finding the projection of a point onto an affine subspace and requires only explicit and very simple computations.

MSC:

90C30 Nonlinear programming
90C55 Methods of successive quadratic programming type
65K05 Numerical mathematical programming methods
90C20 Quadratic programming
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Rosen, J. B.,The Gradient Projection Method of Nonlinear Programming, Part 1, Linear Constraints, SIAM Journal on Applied Mathematics, Vol. 8, pp. 181-217, 1960. · Zbl 0099.36405
[2] Rosen, J. B.,The Gradient Projection Method of Nonlinear Programming, Part 2, Nonlinear Constraints, SIAM Journal on Applied Mathematics, Vol. 9, pp. 414-432, 1961.
[3] Fiacco, A. V., andMcCormick, G. P.,Nonlinear Programming: Sequential Unconstrained Minimization Techniques, John Wiley and Sons, New York, New York, 1968. · Zbl 0193.18805
[4] Bazaraa, M. S., Goode, J. J., andRardin, R. L.,An Algorithm for Finding the Shortest Element of a Polyhedral Set with Application to Lagrangian Duality, Journal of Mathematical Analysis and Applications, Vol. 65, pp. 278-288, 1978. · Zbl 0383.90073
[5] Golub, G. H., andSaunders, M. A.,Linear Least Squares and Quadratic Programming, Integer and Nonlinear Programming, Edited by J. Abadie, North-Holland, Amsterdam, Holland, 1970. · Zbl 0334.90034
[6] Mifflin, R.,A Stable Method for Solving Certain Constrained Least Squares Problems, Mathematical Programming, Vol. 16, pp. 141-158, 1979. · Zbl 0407.90065
[7] Wolfe, P.,Algorithm for a Least-Distance Programming Problem, Mathematical Programming Studies, Vol. 1, pp. 190-205, 1974. · Zbl 0359.90062
[8] Wolfe, P.,Finding the Nearest Point in a Polytope, Mathematical Programming, Vol. 11, pp. 128-149, 1976. · Zbl 0352.90046
[9] Rockafellar, R. T.,Convex Analysis, Princeton University Press, Princeton, New Jersey, 1970. · Zbl 0193.18401
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.