×

On the minimum norm solution of linear programs. (English) Zbl 1043.90046

Summary: This paper describes a new technique to find the minimum norm solution of a linear program. The main idea is to reformulate this problem as an unconstrained minimization problem with a convex and smooth objective function. The minimization of this objective function can be carried out by a Newton-type method which is shown to be globally convergent. Furthermore, under certain assumptions, this Newton-type method converges in a finite number of iterations to the minimum norm solution of the underlying linear program.

MSC:

90C05 Linear programming
90C53 Methods of quasi-Newton type
90C20 Quadratic programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] BERTSIMAS, D., and TSITSIKLIS, J.N., Introduction to Linear Optimization, Athena Scientific, Belmont, Messachusetts, 1997.
[2] WRIGHT, S. J., Primal-Dual Interior-Point Methods, SIAM, Philadelphia, Pennsylvania, 1997. · Zbl 0863.65031
[3] TIKHONOV, A. N., and ARSENIN, V.Y., Solutions of Ill-Posed Problems, Halsted Press, Wiley, New York, NY, 1977. · Zbl 0354.65028
[4] MANGASARIAN, O. L., and MEYER, R.R., Nonlinear Perturbation of Linear Programs, SIAM Journal on Control and Optimization, Vol. 17, pp. 745-757, 1979. · Zbl 0432.90047 · doi:10.1137/0317052
[5] SMITH, P. W., and WOLKOWICZ, H., A Nonlinear Equation for Linear Programming, Mathematical Programming, Vol. 34, pp. 235-238, 1986. · Zbl 0593.90049 · doi:10.1007/BF01580588
[6] MANGASARIAN, O. L., Normal Solutions of Linear Programs, Mathematical Programming, Vol. 22, pp. 206-216, 1984. · Zbl 0588.90058
[7] MANGASARIAN, O.L., Nonlinear Programming, McGraw-Hill, New York, NY, 1969; reprinted by SIAM, Philadelphia, Pennsylvania, 1994.
[8] QI, L., Convergence Analysis of Some Algorithms for Solving Nonsmooth Equations, Mathematics of Operations Research, Vol. 18, pp. 227-244, 1993. · Zbl 0776.65037 · doi:10.1287/moor.18.1.227
[9] CLARKE, F.H., Optimization and Nonsmooth Analysis, John Wiley and Sons, New York, N.Y., 1983; reprinted by SIAM, Philadelphia, Pennsylvania, 1990. · Zbl 0582.49001
[10] DE LUCA, T., FACCHINEI, F., and KANZOW, C., A Semismooth Equation Approach to the Solution of Nonlinear Complementarity Problems, Mathematical Programming, Vol. 75, pp. 407-439, 1996. · Zbl 0874.90185
[11] FISCHER, A., and KANZOW, C., On Finite Termination of an Iterative Method for Linear Complementarity Problems, Mathematical Programming, Vol. 74, pp. 279-292, 1996. · Zbl 0855.90125
[12] QI, L., and SUN, J., A Nonsmooth Version of Newton’s Method, Mathematical Programming, Vol. 58, pp. 353-367, 1993. · Zbl 0780.90090 · doi:10.1007/BF01581275
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.