×
Al-Sultan, K. S.; Murty, K. G.

Exterior point algorithms for nearest points and convex quadratic programs. (English) Zbl 0787.90066

Math. Program. 57, No. 2 (B), 145-161 (1992).
Summary: We consider the problem of finding the nearest point (by Euclidean distance) in a simplicial cone to a given point, and develop an exterior penalty algorithm for it. Each iteration in the algorithm consists of a single Newton step following a reduction in the value of the penalty parameter. Proofs of convergence of the algorithm are given. Various other versions of exterior penalty algorithms for nearest point problems in nonsimplicial polyhedral cones and for convex quadratic programs, all based on a single descent step following a reduction in the value of the penalty parameter per iteration, are discussed. The performance of these algorithms in large scale computational experiments is very encouraging. It shows that the number of iterations grows very slowly, if at all, with the dimension of the problem.

Cited in 12 Documents

MSC:

90C25 Convex programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming

Keywords:

convex quadratic programs; nearest point; simplicial cone; exterior penalty algorithm; Newton step
Cite Review PDF
Full Text: DOI

References:

[1] K.S. Al-Sultan, ”Nearest point problems: Theory and algorithms,” Ph.D. Dissertation, University of Michigan (Ann Arbor, MI, 1990).
[2] K.S. Al-Sultan and K.G. Murty, ”Nearest points in nonsimplicial cones and LCPs with PSD symmetric matrices,” in: S. Kumar, ed.,Recent Developments in Mathematical Programming, Australian Society for O.R. special publication (Gordon & Breach, Camberwell, Vic., Australia, 1991). · Zbl 0787.90096
[3] M.S. Bazaraa and C.M. Shetty,Nonlinear Programming: Theory and Algorithms (Wiley, New York, 1979).
[4] S.Y. Chang and K.G. Murty, ”The steepest descent gravitational method for linear programming,”Discrete Applied Mathematics 25 (1989) 211–239. · Zbl 0691.90051 · doi:10.1016/0166-218X(89)90002-4
[5] M.B. Daya and C.M. Shetty, ”Polynomial barrier function algorithms for convex quadratic programming,”Arabian Journal for Science and Engineering 15 (1990) 658–670. · Zbl 0723.90061
[6] J.P. Evans, F.J. Gould and J.W. Tolle, ”Exact penalty functions in nonlinear programming,”Mathematical Programming 4 (1973) 72–97. · Zbl 0267.90079 · doi:10.1007/BF01584647
[7] A.V. Fiacco and G.P. McCormick,Nonlinear Programming: Sequential Unconstrained Minimization Techniques (Wiley, New York, 1968). · Zbl 0193.18805
[8] E.G. Gilbert, D.W. Johnson and S.S. Keerthi, ”A fast procedure for computing the distance between complex objects in three-dimensional space,”IEEE Journal of Robotics and Automation 4 (1988) 193–203. · doi:10.1109/56.2083
[9] G.H. Golub and C.F. Van Loan,Matrix Computations (Johns Hopkins University Press, Baltimore, MD, 1989). · Zbl 0733.65016
[10] K. Haskell and R. Hanson, ”An algorithm for linear least squares problems with equality and nonnegativity constraints,”Mathematical Programming 21 (1981) 98–118. · Zbl 0461.90056 · doi:10.1007/BF01584232
[11] N. Karmarkar, ”A new polynomial algorithm for linear programming,”Combinatorica 4 (1984) 373–395. · Zbl 0557.90065 · doi:10.1007/BF02579150
[12] M. Kojima, S. Mizuno and A. Yoshise, ”A polynomial-time algorithm for a class of linear complementarity problems,”Mathematical Programming 44 (1989) 1–26. · Zbl 0676.90087 · doi:10.1007/BF01587074
[13] C.E. Lemke, ”Bimatrix equilibrium points and mathematical programming,”Management Science 11 (1965) 681–689. · Zbl 0139.13103 · doi:10.1287/mnsc.11.7.681
[14] C.E. Lemke, ”On complementary pivot theory,” in: G.B. Dantzig and A. Veinott, eds.,Mathematics of the Decision Sciences (American Mathematical Society, Providence, RI, 1968) pp. 95–115. · Zbl 0208.45502
[15] D.G. Luenberger,Linear and Nonlinear Programming (Addison-Wesley, Menlo Park, CA, 1984, 2nd ed.). · Zbl 0571.90051
[16] K.G. Murty,Linear Complementarity, Linear and Nonlinear Programming (Heldermann, Berlin, 1988). · Zbl 0634.90037
[17] K.G. Murty and Y. Fathi, ”A critical index algorithm for the nearest point problem on simplicial cones,”Mathematical Programming 23 (1982) 206–215. · Zbl 0479.90077 · doi:10.1007/BF01583789
[18] T. Pietrzykowski, ”An exact potential method for constrained maxima,”SIAM Journal on Numerical Analysis 26 (1968) 299–304. · Zbl 0181.46501
[19] B.T. Polyak,Introduction to Optimization (Optimization Software, New York, 1987). · Zbl 0708.90083
[20] J. Renegar, ”A polynomial-time algorithm based on Newton’s method for linear programming,”Mathematical Programming 40 (1988) 59–95. · Zbl 0654.90050 · doi:10.1007/BF01580724
[21] K. Truemper, ”Note on finite convergence of exterior functions,”Management Science 21 (1975) 600–606. · Zbl 0311.90064 · doi:10.1287/mnsc.21.5.600
[22] D.R. Wilhelmsen, ”A nearest point algorithm for convex polyhedral cones and applications to positive linear approximations,”Mathematics of Computation 30 (1976) 48–57. · Zbl 0326.65024
[23] P. Wolfe, ”Finding the nearest point in a polytope,”Mathematical Programming 11 (1976) 128–149. · Zbl 0352.90046 · doi:10.1007/BF01580381
[24] Y. Ye and E. Tse, ”An extension of Karmarkar’s projective algorithm for convex quadratic programming,”Mathematical Programming 44 (1989) 157–181. · Zbl 0674.90077 · doi:10.1007/BF01587086
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.