On constraint qualifications: Motivation,       design and inter-relations

Ziteng Wang; Shu-Cherng Fang; Wenxun Xing

doi:10.3934/jimo.2013.9.983

Article Contents

2013, Volume 9, Issue 4: 983-1001. Doi: 10.3934/jimo.2013.9.983

This issue Previous Article Channel coordination mechanism with retailers having fairness preference ---An improved quantity discount mechanism Next Article

On constraint qualifications: Motivation, design and inter-relations

1.
Edward P. Fitts Department of Industrial and Systems Engineering, North Carolina State University, Raleigh, NC, 27695
2.
Department of Industrial and System Engineering, North Carolina State University, Raleigh, NC 27695
3.
Department of Mathematical Sciences, Tsinghua University, Beijing, 100084

Received: January 31, 2013

Revised: February 28, 2013

Published: September 2013

Abstract Related Papers Cited by

Abstract

Constraint qualification (CQ) is an important concept in nonlinear programming. This paper investigates the motivation of introducing constraint qualifications in developing KKT conditions for solving nonlinear programs and provides a geometric meaning of constraint qualifications. A unified framework of designing constraint qualifications by imposing conditions to equate the so-called ``locally constrained directions" to certain subsets of ``tangent directions" is proposed. Based on the inclusion relations of the cones of tangent directions, attainable directions, feasible directions and interior constrained directions, constraint qualifications are categorized into four levels by their relative strengths. This paper reviews most, if not all, of the commonly seen constraint qualifications in the literature, identifies the categories they belong to, and summarizes the inter-relationship among them. The proposed framework also helps design new constraint qualifications of readers' specific interests.

Keywords:

Mathematics Subject Classification: Primary: 90C30; Secondary: 90C46.

Citation:

Related Papers

Cited by

References

[1]	J. Abadie, On the Kuhn-Tucker theorem, in "Nonlinear Programming" (ed. J. Abadie), North-Holland Pub. Co., (1967), 19-36.
[2]	R. Andreani, G. Haeser, M. L. Schuverdt and P. J. S. Silva, A relaxed constant positive linear dependence constraint qualification and applications, Mathematical Programming, 135 (2012), 255-273.doi: 10.1007/s10107-011-0456-0.
[3]	R. Andreani, J. M. Martinez and M. L. Schuverdt, On the relation between constant positive linear dependence condition and quasinormality constraint qualification, Journal of Optimization Theory and Applications, 125 (2005), 473-483.doi: 10.1007/s10957-004-1861-9.
[4]	K. J. Arrow, L. Hurwicz and H. Uzawa, Constraint qualifications in maximization problems, Naval Research Logistics Quarterly, 8 (1961), 175-191.doi: 10.1002/nav.3800080206.
[5]	M. S. Bazaraa, J. J. Goode and C. M. Shetty, Constraint qualifications revisited, Management Science, 18 (1972), 567-573.doi: 10.1287/mnsc.18.9.567.
[6]	M. S. Bazaraa, H. D. Sherali and C. M. Shetty, "Nonlinear Programming: Theory and Algorithms," $3^{rd}$ edition, Wiley-Interscience, Hoboken, NJ, 2006.doi: 10.1002/0471787779.
[7]	D. P. Bertsekas, "Nonlinear Programming," $2^{nd}$ edition, Athena Scientific, 1999.
[8]	D. P. Bertsekas, A. Nedić and A. E. Ozdaglar, "Convex Analysis and Optimization," Athena Scientific, Belmont, MA, 2003.
[9]	D. P. Bertsekas and A. E. Ozdaglar, Pseudonormality and a Lagrange multiplier theory for constrained optimization, Journal of Optimization Theory and Applications, 114 (2002), 287-343.doi: 10.1023/A:1016083601322.
[10]	J. M. Borwein and H. Wolkowicz, A simple constraint qualification in infinite dimensional programming, Mathematical Programming, 35 (1986), 83-96.doi: 10.1007/BF01589443.
[11]	M. Canon, C. Cullum and E. Polak, Constrained minimization problems in finite-dimensional spaces, SIAM Journal on Control, 4 (1966), 528-547.doi: 10.1137/0304041.
[12]	R. W. Cottle, A theorem of Fritz John in mathematical programming, RAND Memorandum RM-3858-PR, RAND Corporation, 1963.
[13]	W. Fenchel, "Convex Cones, Sets and Functions," Princeton University Press, Princeton, 1953.
[14]	D. Gale, "The Theory of Linear Economic Models," McGraw-Hill Book Company, Inc., New York-Toronto-London, 1960.
[15]	G. Giorgi and A. Guerraggio, On the notion of tangent cone in mathematical programming, Optimization, 25 (1992), 11-23.doi: 10.1080/02331939208843804.
[16]	F. J. Gould and J. W. Tolle, A necessary and sufficient qualification for constrained optimization, SIAM Journal on Applied Mathematics, 20 (1971), 164-172.doi: 10.1137/0120021.
[17]	F. J. Gould and J. W. Tolle, Geometry of optimality conditions and constraint qualifications, Mathematical Programming, 2 (1972), 1-18.doi: 10.1007/BF01584534.
[18]	M. Gowda and M. Teboulle, A comparison of constraint qualifications in infinite-dimensional convex programming, SIAM Journal on Control and Optimization, 28 (1990), 925-935.doi: 10.1137/0328051.
[19]	M. Guignard, Generalized Kuhn-Tucker conditions for mathematical programming problems in a Banach space, SIAM Journal on Control, 7 (1969), 232-241.doi: 10.1137/0307016.
[20]	M. R. Hestenes, "Calculus of Variations and Optimal Control Theory," John Wiley & Sons, Inc., New York-London-Sydney, 1966.
[21]	M. R. Hestenes, "Optimization Theory: The Finite Dimensional Case," Pure and Applied Mathematics, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1975.
[22]	L. Hurwicz, Programming in linear spaces, in "Studies in Linear and Non-linear Programming" (eds. K. J. Arrow, L. Hurwicz and H. Uzawa), Stanford University Press, (1958), 38-102.
[23]	R. Janin, Directional derivative of the marginal function in nonlinear programming. Sensitivity, stability and parametric analysis, Mathematical Programming Studies, 21 (1984), 110-126.doi: 10.1007/BFb0121214.
[24]	F. John, Extremum problems with inequalities as subsidiary conditions, in "Studies and Essays Presented to R. Courant on his 60th Birthday, January 8, 1948" (eds. K. O. Friedrichs, O. E. Neugebauer and J. J. Stoker), Wiley-Interscience New York, (1948), 187-204.
[25]	A. Jourani, Constraint qualifications and Lagrange multipliers in nondifferentiable programming problems, Journal of Optimization Theory and Applications, 81 (1994), 533-548.doi: 10.1007/BF02193099.
[26]	S. Karlin, "Mathematical Methods and Theory in Games, Programming, and Economics," Addison-Wesley Publishing Co., Inc., Reading, Mass.-London, 1959.
[27]	H. W. Kuhn and A. W. Tucker, Nonlinear programming, in "Second Berkeley Symposium on Mathematical Statistics and Probability," University of California Press, Berkeley and Los Angeles, (1951), 481-492.
[28]	L. Kuntz, Constraint qualifications in quasidifferentiable optimization, Mathematical Programming, 60 (1993), 339-347.doi: 10.1007/BF01580618.
[29]	L. Kuntz and S. Scholtes, A nonsmooth variant of the Mangasarian-Fromovitz constraint qualification, Journal of Optimization Theory and Applications, 82 (1994), 59-75.doi: 10.1007/BF02191779.
[30]	S. Lu, Implications of the constant rank constraint qualification, Mathematical Programming, 126 (2011), 365-392.doi: 10.1007/s10107-009-0288-3.
[31]	D. Luenberger and Y. Ye, "Linear and Nonlinear Programming," $3^{rd}$ edition, International Series in Operations Research & Management Science, 116, Springer, 2008.
[32]	C. Ma, X. Li, K. F. C. Yiu, Y. Yang and L. Zhang, On an exact penalty function method for semi-infinite programming problems, Journal of Industrial and Management Optimization, 8 (2012), 705-726.doi: 10.3934/jimo.2012.8.705.
[33]	O. L. Mangasarian, "Nonlinear Programming," McGraw-Hill Book Company, Inc., New York-London-Sydney, 1969.
[34]	O. L. Mangasarian and S. Fromovitz, The Fritz John necessary optimality conditions in the presence of equality and inequality constraints, Journal of Mathematical Analysis and Applications, 17 (1967), 37-47.doi: 10.1016/0022-247X(67)90163-1.
[35]	R. R. Merkovsky and D. E. Ward, General constraint qualifications in nondifferentiable programming, Mathematical Programming, 47 (1990), 389-405.doi: 10.1007/BF01580871.
[36]	L. Minchenko and S. Stakhovski, On relaxed constant rank regularity condition in mathematical programming, Optimization, 60 (2011), 429-440.doi: 10.1080/02331930902971377.
[37]	A. E. Ozdaglar and D. P. Bertsekas, The relation between pseudonormality and quasiregularity in constrained optimization, Optimization Methods and Software, 19 (2004), 493-506.doi: 10.1080/10556780410001709420.
[38]	D. W. Peterson, A review of constraint qualifications in finite-dimensional spaces, SIAM Review, 15 (1973), 639-654.doi: 10.1137/1015075.
[39]	L. Qi and Z. Wei, On the constant positive linear dependence condition and its application to SQP methods, SIAM Journal on Optimization, 10 (2000), 963-981.doi: 10.1137/S1052623497326629.
[40]	K. Ritter, Optimization theory in linear spaces, Mathematische Annalen, 184 (1970), 133-154.doi: 10.1007/BF01350314.
[41]	R. T. Rockafellar, "Conjugate Duality and Optimization," Lectures given at the Johns Hopkins University, Baltimore, Md., June, 1973, Conference Board of the Mathematical Sciences Regional Conference Series in Applied Mathematics, No. 16, Society for Industrial and Applied Mathematics, Philadelphia, Pa., 1974.doi: 10.1137/1.9781611970524.
[42]	R. T. Rockafellar, Lagrange multipliers and optimality, SIAM Review, 35 (1993), 183-238.doi: 10.1137/1035044.
[43]	R. T. Rockafellar and R. J. B. Wets, "Variational Analysis," Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 317, Springer-Verlag, Berlin, 1998.doi: 10.1007/978-3-642-02431-3.
[44]	M. Slater, Lagrange multipliers revisited, Cowles Foundation Discussion Paper No. 80, Cowles Foundation for Research in Economics, Yale University, 1950.
[45]	M. V. Solodov, Constraint qualifications, in "Wiley Encyclopedia of Operations Research and Management Science," John Wiley & Sons, Inc., 2010.doi: 10.1002/9780470400531.eorms0978.
[46]	O. Stein, On constraint qualifications in nonsmooth optimization, Journal of Optimization Theory and Applications, 121 (2004), 647-671.doi: 10.1023/B:JOTA.0000037607.48762.45.
[47]	P. Varaiya, Nonlinear programming in Banach space, SIAM Journal on Applied Mathematics, 15 (1967), 284-293.doi: 10.1137/0115028.
[48]	W. I. Zangwill, "Nonlinear Programming: A Unified Approach," Prentice-Hall International Series in Management, Prentice-Hall, Inc., Englewood Cliffs, NJ, 1969.