On constraint qualifications: Motivation,       design and inter-relations

Ziteng Wang; Shu-Cherng Fang; Wenxun Xing

doi:10.3934/jimo.2013.9.983

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

October 2013, 9(4): 983-1001. doi: 10.3934/jimo.2013.9.983

On constraint qualifications: Motivation, design and inter-relations

Ziteng Wang ^1, , Shu-Cherng Fang ^2, and Wenxun Xing ^3,

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

Received February 2013 Revised March 2013 Published August 2013

Abstract
Related Papers

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: optimality conditions, nonlinear programming, Constraint qualification, KKT conditions., optimization.

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

Citation: Ziteng Wang, Shu-Cherng Fang, Wenxun Xing. On constraint qualifications: Motivation, design and inter-relations. Journal of Industrial & Management Optimization, 2013, 9 (4) : 983-1001. doi: 10.3934/jimo.2013.9.983

References:

[1]	J. Abadie, On the Kuhn-Tucker theorem,, in, (1967), 19. Google Scholar
[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. doi: 10.1007/s10107-011-0456-0. Google Scholar
[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. doi: 10.1007/s10957-004-1861-9. Google Scholar
[4]	K. J. Arrow, L. Hurwicz and H. Uzawa, Constraint qualifications in maximization problems,, Naval Research Logistics Quarterly, 8 (1961), 175. doi: 10.1002/nav.3800080206. Google Scholar
[5]	M. S. Bazaraa, J. J. Goode and C. M. Shetty, Constraint qualifications revisited,, Management Science, 18 (1972), 567. doi: 10.1287/mnsc.18.9.567. Google Scholar
[6]	M. S. Bazaraa, H. D. Sherali and C. M. Shetty, "Nonlinear Programming: Theory and Algorithms,", $3^{rd}$ edition, (2006). doi: 10.1002/0471787779. Google Scholar
[7]	D. P. Bertsekas, "Nonlinear Programming,", $2^{nd}$ edition, (1999). Google Scholar
[8]	D. P. Bertsekas, A. Nedić and A. E. Ozdaglar, "Convex Analysis and Optimization,", Athena Scientific, (2003). Google Scholar
[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. doi: 10.1023/A:1016083601322. Google Scholar
[10]	J. M. Borwein and H. Wolkowicz, A simple constraint qualification in infinite dimensional programming,, Mathematical Programming, 35 (1986), 83. doi: 10.1007/BF01589443. Google Scholar
[11]	M. Canon, C. Cullum and E. Polak, Constrained minimization problems in finite-dimensional spaces,, SIAM Journal on Control, 4 (1966), 528. doi: 10.1137/0304041. Google Scholar
[12]	R. W. Cottle, A theorem of Fritz John in mathematical programming,, RAND Memorandum RM-3858-PR, (1963). Google Scholar
[13]	W. Fenchel, "Convex Cones, Sets and Functions,", Princeton University Press, (1953). Google Scholar
[14]	D. Gale, "The Theory of Linear Economic Models,", McGraw-Hill Book Company, (1960). Google Scholar
[15]	G. Giorgi and A. Guerraggio, On the notion of tangent cone in mathematical programming,, Optimization, 25 (1992), 11. doi: 10.1080/02331939208843804. Google Scholar
[16]	F. J. Gould and J. W. Tolle, A necessary and sufficient qualification for constrained optimization,, SIAM Journal on Applied Mathematics, 20 (1971), 164. doi: 10.1137/0120021. Google Scholar
[17]	F. J. Gould and J. W. Tolle, Geometry of optimality conditions and constraint qualifications,, Mathematical Programming, 2 (1972), 1. doi: 10.1007/BF01584534. Google Scholar
[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. doi: 10.1137/0328051. Google Scholar
[19]	M. Guignard, Generalized Kuhn-Tucker conditions for mathematical programming problems in a Banach space,, SIAM Journal on Control, 7 (1969), 232. doi: 10.1137/0307016. Google Scholar
[20]	M. R. Hestenes, "Calculus of Variations and Optimal Control Theory,", John Wiley & Sons, (1966). Google Scholar
[21]	M. R. Hestenes, "Optimization Theory: The Finite Dimensional Case,", Pure and Applied Mathematics, (1975). Google Scholar
[22]	L. Hurwicz, Programming in linear spaces,, in, (1958), 38. Google Scholar
[23]	R. Janin, Directional derivative of the marginal function in nonlinear programming. Sensitivity, stability and parametric analysis,, Mathematical Programming Studies, 21 (1984), 110. doi: 10.1007/BFb0121214. Google Scholar
[24]	F. John, Extremum problems with inequalities as subsidiary conditions,, in, (1948), 187. Google Scholar
[25]	A. Jourani, Constraint qualifications and Lagrange multipliers in nondifferentiable programming problems,, Journal of Optimization Theory and Applications, 81 (1994), 533. doi: 10.1007/BF02193099. Google Scholar
[26]	S. Karlin, "Mathematical Methods and Theory in Games, Programming, and Economics,", Addison-Wesley Publishing Co., (1959). Google Scholar
[27]	H. W. Kuhn and A. W. Tucker, Nonlinear programming,, in, (1951), 481. Google Scholar
[28]	L. Kuntz, Constraint qualifications in quasidifferentiable optimization,, Mathematical Programming, 60 (1993), 339. doi: 10.1007/BF01580618. Google Scholar
[29]	L. Kuntz and S. Scholtes, A nonsmooth variant of the Mangasarian-Fromovitz constraint qualification,, Journal of Optimization Theory and Applications, 82 (1994), 59. doi: 10.1007/BF02191779. Google Scholar
[30]	S. Lu, Implications of the constant rank constraint qualification,, Mathematical Programming, 126 (2011), 365. doi: 10.1007/s10107-009-0288-3. Google Scholar
[31]	D. Luenberger and Y. Ye, "Linear and Nonlinear Programming,", $3^{rd}$ edition, 116 (2008). Google Scholar
[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. doi: 10.3934/jimo.2012.8.705. Google Scholar
[33]	O. L. Mangasarian, "Nonlinear Programming,", McGraw-Hill Book Company, (1969). Google Scholar
[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. doi: 10.1016/0022-247X(67)90163-1. Google Scholar
[35]	R. R. Merkovsky and D. E. Ward, General constraint qualifications in nondifferentiable programming,, Mathematical Programming, 47 (1990), 389. doi: 10.1007/BF01580871. Google Scholar
[36]	L. Minchenko and S. Stakhovski, On relaxed constant rank regularity condition in mathematical programming,, Optimization, 60 (2011), 429. doi: 10.1080/02331930902971377. Google Scholar
[37]	A. E. Ozdaglar and D. P. Bertsekas, The relation between pseudonormality and quasiregularity in constrained optimization,, Optimization Methods and Software, 19 (2004), 493. doi: 10.1080/10556780410001709420. Google Scholar
[38]	D. W. Peterson, A review of constraint qualifications in finite-dimensional spaces,, SIAM Review, 15 (1973), 639. doi: 10.1137/1015075. Google Scholar
[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. doi: 10.1137/S1052623497326629. Google Scholar
[40]	K. Ritter, Optimization theory in linear spaces,, Mathematische Annalen, 184 (1970), 133. doi: 10.1007/BF01350314. Google Scholar
[41]	R. T. Rockafellar, "Conjugate Duality and Optimization,", Lectures given at the Johns Hopkins University, (1973). doi: 10.1137/1.9781611970524. Google Scholar
[42]	R. T. Rockafellar, Lagrange multipliers and optimality,, SIAM Review, 35 (1993), 183. doi: 10.1137/1035044. Google Scholar
[43]	R. T. Rockafellar and R. J. B. Wets, "Variational Analysis,", Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 317 (1998). doi: 10.1007/978-3-642-02431-3. Google Scholar
[44]	M. Slater, Lagrange multipliers revisited,, Cowles Foundation Discussion Paper No. 80, (1950). Google Scholar
[45]	M. V. Solodov, Constraint qualifications,, in, (2010). doi: 10.1002/9780470400531.eorms0978. Google Scholar
[46]	O. Stein, On constraint qualifications in nonsmooth optimization,, Journal of Optimization Theory and Applications, 121 (2004), 647. doi: 10.1023/B:JOTA.0000037607.48762.45. Google Scholar
[47]	P. Varaiya, Nonlinear programming in Banach space,, SIAM Journal on Applied Mathematics, 15 (1967), 284. doi: 10.1137/0115028. Google Scholar
[48]	W. I. Zangwill, "Nonlinear Programming: A Unified Approach,", Prentice-Hall International Series in Management, (1969). Google Scholar

show all references

References:

[1]	J. Abadie, On the Kuhn-Tucker theorem,, in, (1967), 19. Google Scholar
[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. doi: 10.1007/s10107-011-0456-0. Google Scholar
[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. doi: 10.1007/s10957-004-1861-9. Google Scholar
[4]	K. J. Arrow, L. Hurwicz and H. Uzawa, Constraint qualifications in maximization problems,, Naval Research Logistics Quarterly, 8 (1961), 175. doi: 10.1002/nav.3800080206. Google Scholar
[5]	M. S. Bazaraa, J. J. Goode and C. M. Shetty, Constraint qualifications revisited,, Management Science, 18 (1972), 567. doi: 10.1287/mnsc.18.9.567. Google Scholar
[6]	M. S. Bazaraa, H. D. Sherali and C. M. Shetty, "Nonlinear Programming: Theory and Algorithms,", $3^{rd}$ edition, (2006). doi: 10.1002/0471787779. Google Scholar
[7]	D. P. Bertsekas, "Nonlinear Programming,", $2^{nd}$ edition, (1999). Google Scholar
[8]	D. P. Bertsekas, A. Nedić and A. E. Ozdaglar, "Convex Analysis and Optimization,", Athena Scientific, (2003). Google Scholar
[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. doi: 10.1023/A:1016083601322. Google Scholar
[10]	J. M. Borwein and H. Wolkowicz, A simple constraint qualification in infinite dimensional programming,, Mathematical Programming, 35 (1986), 83. doi: 10.1007/BF01589443. Google Scholar
[11]	M. Canon, C. Cullum and E. Polak, Constrained minimization problems in finite-dimensional spaces,, SIAM Journal on Control, 4 (1966), 528. doi: 10.1137/0304041. Google Scholar
[12]	R. W. Cottle, A theorem of Fritz John in mathematical programming,, RAND Memorandum RM-3858-PR, (1963). Google Scholar
[13]	W. Fenchel, "Convex Cones, Sets and Functions,", Princeton University Press, (1953). Google Scholar
[14]	D. Gale, "The Theory of Linear Economic Models,", McGraw-Hill Book Company, (1960). Google Scholar
[15]	G. Giorgi and A. Guerraggio, On the notion of tangent cone in mathematical programming,, Optimization, 25 (1992), 11. doi: 10.1080/02331939208843804. Google Scholar
[16]	F. J. Gould and J. W. Tolle, A necessary and sufficient qualification for constrained optimization,, SIAM Journal on Applied Mathematics, 20 (1971), 164. doi: 10.1137/0120021. Google Scholar
[17]	F. J. Gould and J. W. Tolle, Geometry of optimality conditions and constraint qualifications,, Mathematical Programming, 2 (1972), 1. doi: 10.1007/BF01584534. Google Scholar
[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. doi: 10.1137/0328051. Google Scholar
[19]	M. Guignard, Generalized Kuhn-Tucker conditions for mathematical programming problems in a Banach space,, SIAM Journal on Control, 7 (1969), 232. doi: 10.1137/0307016. Google Scholar
[20]	M. R. Hestenes, "Calculus of Variations and Optimal Control Theory,", John Wiley & Sons, (1966). Google Scholar
[21]	M. R. Hestenes, "Optimization Theory: The Finite Dimensional Case,", Pure and Applied Mathematics, (1975). Google Scholar
[22]	L. Hurwicz, Programming in linear spaces,, in, (1958), 38. Google Scholar
[23]	R. Janin, Directional derivative of the marginal function in nonlinear programming. Sensitivity, stability and parametric analysis,, Mathematical Programming Studies, 21 (1984), 110. doi: 10.1007/BFb0121214. Google Scholar
[24]	F. John, Extremum problems with inequalities as subsidiary conditions,, in, (1948), 187. Google Scholar
[25]	A. Jourani, Constraint qualifications and Lagrange multipliers in nondifferentiable programming problems,, Journal of Optimization Theory and Applications, 81 (1994), 533. doi: 10.1007/BF02193099. Google Scholar
[26]	S. Karlin, "Mathematical Methods and Theory in Games, Programming, and Economics,", Addison-Wesley Publishing Co., (1959). Google Scholar
[27]	H. W. Kuhn and A. W. Tucker, Nonlinear programming,, in, (1951), 481. Google Scholar
[28]	L. Kuntz, Constraint qualifications in quasidifferentiable optimization,, Mathematical Programming, 60 (1993), 339. doi: 10.1007/BF01580618. Google Scholar
[29]	L. Kuntz and S. Scholtes, A nonsmooth variant of the Mangasarian-Fromovitz constraint qualification,, Journal of Optimization Theory and Applications, 82 (1994), 59. doi: 10.1007/BF02191779. Google Scholar
[30]	S. Lu, Implications of the constant rank constraint qualification,, Mathematical Programming, 126 (2011), 365. doi: 10.1007/s10107-009-0288-3. Google Scholar
[31]	D. Luenberger and Y. Ye, "Linear and Nonlinear Programming,", $3^{rd}$ edition, 116 (2008). Google Scholar
[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. doi: 10.3934/jimo.2012.8.705. Google Scholar
[33]	O. L. Mangasarian, "Nonlinear Programming,", McGraw-Hill Book Company, (1969). Google Scholar
[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. doi: 10.1016/0022-247X(67)90163-1. Google Scholar
[35]	R. R. Merkovsky and D. E. Ward, General constraint qualifications in nondifferentiable programming,, Mathematical Programming, 47 (1990), 389. doi: 10.1007/BF01580871. Google Scholar
[36]	L. Minchenko and S. Stakhovski, On relaxed constant rank regularity condition in mathematical programming,, Optimization, 60 (2011), 429. doi: 10.1080/02331930902971377. Google Scholar
[37]	A. E. Ozdaglar and D. P. Bertsekas, The relation between pseudonormality and quasiregularity in constrained optimization,, Optimization Methods and Software, 19 (2004), 493. doi: 10.1080/10556780410001709420. Google Scholar
[38]	D. W. Peterson, A review of constraint qualifications in finite-dimensional spaces,, SIAM Review, 15 (1973), 639. doi: 10.1137/1015075. Google Scholar
[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. doi: 10.1137/S1052623497326629. Google Scholar
[40]	K. Ritter, Optimization theory in linear spaces,, Mathematische Annalen, 184 (1970), 133. doi: 10.1007/BF01350314. Google Scholar
[41]	R. T. Rockafellar, "Conjugate Duality and Optimization,", Lectures given at the Johns Hopkins University, (1973). doi: 10.1137/1.9781611970524. Google Scholar
[42]	R. T. Rockafellar, Lagrange multipliers and optimality,, SIAM Review, 35 (1993), 183. doi: 10.1137/1035044. Google Scholar
[43]	R. T. Rockafellar and R. J. B. Wets, "Variational Analysis,", Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 317 (1998). doi: 10.1007/978-3-642-02431-3. Google Scholar
[44]	M. Slater, Lagrange multipliers revisited,, Cowles Foundation Discussion Paper No. 80, (1950). Google Scholar
[45]	M. V. Solodov, Constraint qualifications,, in, (2010). doi: 10.1002/9780470400531.eorms0978. Google Scholar
[46]	O. Stein, On constraint qualifications in nonsmooth optimization,, Journal of Optimization Theory and Applications, 121 (2004), 647. doi: 10.1023/B:JOTA.0000037607.48762.45. Google Scholar
[47]	P. Varaiya, Nonlinear programming in Banach space,, SIAM Journal on Applied Mathematics, 15 (1967), 284. doi: 10.1137/0115028. Google Scholar
[48]	W. I. Zangwill, "Nonlinear Programming: A Unified Approach,", Prentice-Hall International Series in Management, (1969). Google Scholar

[1]	Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023
[2]	Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[3]	Madalina Petcu, Roger Temam. The one dimensional shallow water equations with Dirichlet boundary conditions on the velocity. Discrete & Continuous Dynamical Systems - S, 2011, 4 (1) : 209-222. doi: 10.3934/dcdss.2011.4.209
[4]	Valery Y. Glizer. Novel Conditions of Euclidean space controllability for singularly perturbed systems with input delay. Numerical Algebra, Control & Optimization, 2020 doi: 10.3934/naco.2020027
[5]	Samir Adly, Oanh Chau, Mohamed Rochdi. Solvability of a class of thermal dynamical contact problems with subdifferential conditions. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 91-104. doi: 10.3934/naco.2012.2.91
[6]	Elvise Berchio, Filippo Gazzola, Dario Pierotti. Nodal solutions to critical growth elliptic problems under Steklov boundary conditions. Communications on Pure & Applied Analysis, 2009, 8 (2) : 533-557. doi: 10.3934/cpaa.2009.8.533
[7]	Yanqin Fang, Jihui Zhang. Multiplicity of solutions for the nonlinear Schrödinger-Maxwell system. Communications on Pure & Applied Analysis, 2011, 10 (4) : 1267-1279. doi: 10.3934/cpaa.2011.10.1267
[8]	Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017
[9]	Olena Naboka. On synchronization of oscillations of two coupled Berger plates with nonlinear interior damping. Communications on Pure & Applied Analysis, 2009, 8 (6) : 1933-1956. doi: 10.3934/cpaa.2009.8.1933
[10]	Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024
[11]	Irena PawŃow, Wojciech M. Zajączkowski. Global regular solutions to three-dimensional thermo-visco-elasticity with nonlinear temperature-dependent specific heat. Communications on Pure & Applied Analysis, 2017, 16 (4) : 1331-1372. doi: 10.3934/cpaa.2017065
[12]	Xiaoming Wang. Quasi-periodic solutions for a class of second order differential equations with a nonlinear damping term. Discrete & Continuous Dynamical Systems - S, 2017, 10 (3) : 543-556. doi: 10.3934/dcdss.2017027

2019 Impact Factor: 1.366

American Institute of Mathematical Sciences

On constraint qualifications: Motivation, design and inter-relations

References:

References:

Tools

Metrics

Other articles
by authors

Tools

Metrics

Other articles
by authors

American Institute of Mathematical Sciences

On constraint qualifications: Motivation, design and inter-relations

References:

References:

Tools

Metrics

Other articlesby authors

Tools

Metrics

Other articlesby authors

Other articles
by authors

Other articles
by authors