On constraint qualifications: Motivation, design and inter-relations

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

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.
[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.
[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.
[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.
[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.
[6]	M. S. Bazaraa, H. D. Sherali and C. M. Shetty, "Nonlinear Programming: Theory and Algorithms,", $3^{rd}$ edition, (2006). doi: 10.1002/0471787779.
[7]	D. P. Bertsekas, "Nonlinear Programming,", $2^{nd}$ edition, (1999).
[8]	D. P. Bertsekas, A. Nedić and A. E. Ozdaglar, "Convex Analysis and Optimization,", Athena Scientific, (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. 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. 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. doi: 10.1137/0304041.
[12]	R. W. Cottle, A theorem of Fritz John in mathematical programming,, RAND Memorandum RM-3858-PR, (1963).
[13]	W. Fenchel, "Convex Cones, Sets and Functions,", Princeton University Press, (1953).
[14]	D. Gale, "The Theory of Linear Economic Models,", McGraw-Hill Book Company, (1960).
[15]	G. Giorgi and A. Guerraggio, On the notion of tangent cone in mathematical programming,, Optimization, 25 (1992), 11. 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. doi: 10.1137/0120021.
[17]	F. J. Gould and J. W. Tolle, Geometry of optimality conditions and constraint qualifications,, Mathematical Programming, 2 (1972), 1. 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. 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. doi: 10.1137/0307016.
[20]	M. R. Hestenes, "Calculus of Variations and Optimal Control Theory,", John Wiley & Sons, (1966).
[21]	M. R. Hestenes, "Optimization Theory: The Finite Dimensional Case,", Pure and Applied Mathematics, (1975).
[22]	L. Hurwicz, Programming in linear spaces,, in, (1958), 38.
[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.
[24]	F. John, Extremum problems with inequalities as subsidiary conditions,, in, (1948), 187.
[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.
[26]	S. Karlin, "Mathematical Methods and Theory in Games, Programming, and Economics,", Addison-Wesley Publishing Co., (1959).
[27]	H. W. Kuhn and A. W. Tucker, Nonlinear programming,, in, (1951), 481.
[28]	L. Kuntz, Constraint qualifications in quasidifferentiable optimization,, Mathematical Programming, 60 (1993), 339. 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. doi: 10.1007/BF02191779.
[30]	S. Lu, Implications of the constant rank constraint qualification,, Mathematical Programming, 126 (2011), 365. doi: 10.1007/s10107-009-0288-3.
[31]	D. Luenberger and Y. Ye, "Linear and Nonlinear Programming,", $3^{rd}$ edition, 116 (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. doi: 10.3934/jimo.2012.8.705.
[33]	O. L. Mangasarian, "Nonlinear Programming,", McGraw-Hill Book Company, (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. 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. doi: 10.1007/BF01580871.
[36]	L. Minchenko and S. Stakhovski, On relaxed constant rank regularity condition in mathematical programming,, Optimization, 60 (2011), 429. 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. doi: 10.1080/10556780410001709420.
[38]	D. W. Peterson, A review of constraint qualifications in finite-dimensional spaces,, SIAM Review, 15 (1973), 639. 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. doi: 10.1137/S1052623497326629.
[40]	K. Ritter, Optimization theory in linear spaces,, Mathematische Annalen, 184 (1970), 133. doi: 10.1007/BF01350314.
[41]	R. T. Rockafellar, "Conjugate Duality and Optimization,", Lectures given at the Johns Hopkins University, (1973). doi: 10.1137/1.9781611970524.
[42]	R. T. Rockafellar, Lagrange multipliers and optimality,, SIAM Review, 35 (1993), 183. 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 (1998). doi: 10.1007/978-3-642-02431-3.
[44]	M. Slater, Lagrange multipliers revisited,, Cowles Foundation Discussion Paper No. 80, (1950).
[45]	M. V. Solodov, Constraint qualifications,, in, (2010). doi: 10.1002/9780470400531.eorms0978.
[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.
[47]	P. Varaiya, Nonlinear programming in Banach space,, SIAM Journal on Applied Mathematics, 15 (1967), 284. doi: 10.1137/0115028.
[48]	W. I. Zangwill, "Nonlinear Programming: A Unified Approach,", Prentice-Hall International Series in Management, (1969).

show all references

References:

[1]	J. Abadie, On the Kuhn-Tucker theorem,, in, (1967), 19.
[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.
[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.
[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.
[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.
[6]	M. S. Bazaraa, H. D. Sherali and C. M. Shetty, "Nonlinear Programming: Theory and Algorithms,", $3^{rd}$ edition, (2006). doi: 10.1002/0471787779.
[7]	D. P. Bertsekas, "Nonlinear Programming,", $2^{nd}$ edition, (1999).
[8]	D. P. Bertsekas, A. Nedić and A. E. Ozdaglar, "Convex Analysis and Optimization,", Athena Scientific, (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. 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. 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. doi: 10.1137/0304041.
[12]	R. W. Cottle, A theorem of Fritz John in mathematical programming,, RAND Memorandum RM-3858-PR, (1963).
[13]	W. Fenchel, "Convex Cones, Sets and Functions,", Princeton University Press, (1953).
[14]	D. Gale, "The Theory of Linear Economic Models,", McGraw-Hill Book Company, (1960).
[15]	G. Giorgi and A. Guerraggio, On the notion of tangent cone in mathematical programming,, Optimization, 25 (1992), 11. 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. doi: 10.1137/0120021.
[17]	F. J. Gould and J. W. Tolle, Geometry of optimality conditions and constraint qualifications,, Mathematical Programming, 2 (1972), 1. 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. 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. doi: 10.1137/0307016.
[20]	M. R. Hestenes, "Calculus of Variations and Optimal Control Theory,", John Wiley & Sons, (1966).
[21]	M. R. Hestenes, "Optimization Theory: The Finite Dimensional Case,", Pure and Applied Mathematics, (1975).
[22]	L. Hurwicz, Programming in linear spaces,, in, (1958), 38.
[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.
[24]	F. John, Extremum problems with inequalities as subsidiary conditions,, in, (1948), 187.
[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.
[26]	S. Karlin, "Mathematical Methods and Theory in Games, Programming, and Economics,", Addison-Wesley Publishing Co., (1959).
[27]	H. W. Kuhn and A. W. Tucker, Nonlinear programming,, in, (1951), 481.
[28]	L. Kuntz, Constraint qualifications in quasidifferentiable optimization,, Mathematical Programming, 60 (1993), 339. 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. doi: 10.1007/BF02191779.
[30]	S. Lu, Implications of the constant rank constraint qualification,, Mathematical Programming, 126 (2011), 365. doi: 10.1007/s10107-009-0288-3.
[31]	D. Luenberger and Y. Ye, "Linear and Nonlinear Programming,", $3^{rd}$ edition, 116 (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. doi: 10.3934/jimo.2012.8.705.
[33]	O. L. Mangasarian, "Nonlinear Programming,", McGraw-Hill Book Company, (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. 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. doi: 10.1007/BF01580871.
[36]	L. Minchenko and S. Stakhovski, On relaxed constant rank regularity condition in mathematical programming,, Optimization, 60 (2011), 429. 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. doi: 10.1080/10556780410001709420.
[38]	D. W. Peterson, A review of constraint qualifications in finite-dimensional spaces,, SIAM Review, 15 (1973), 639. 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. doi: 10.1137/S1052623497326629.
[40]	K. Ritter, Optimization theory in linear spaces,, Mathematische Annalen, 184 (1970), 133. doi: 10.1007/BF01350314.
[41]	R. T. Rockafellar, "Conjugate Duality and Optimization,", Lectures given at the Johns Hopkins University, (1973). doi: 10.1137/1.9781611970524.
[42]	R. T. Rockafellar, Lagrange multipliers and optimality,, SIAM Review, 35 (1993), 183. 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 (1998). doi: 10.1007/978-3-642-02431-3.
[44]	M. Slater, Lagrange multipliers revisited,, Cowles Foundation Discussion Paper No. 80, (1950).
[45]	M. V. Solodov, Constraint qualifications,, in, (2010). doi: 10.1002/9780470400531.eorms0978.
[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.
[47]	P. Varaiya, Nonlinear programming in Banach space,, SIAM Journal on Applied Mathematics, 15 (1967), 284. doi: 10.1137/0115028.
[48]	W. I. Zangwill, "Nonlinear Programming: A Unified Approach,", Prentice-Hall International Series in Management, (1969).

[1]	Adela Capătă. Optimality conditions for strong vector equilibrium problems under a weak constraint qualification. Journal of Industrial & Management Optimization, 2015, 11 (2) : 563-574. doi: 10.3934/jimo.2015.11.563
[2]	Mansoureh Alavi Hejazi, Soghra Nobakhtian. Optimality conditions for multiobjective fractional programming, via convexificators. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-9. doi: 10.3934/jimo.2018170
[3]	Sofia O. Lopes, Fernando A. C. C. Fontes, Maria do Rosário de Pinho. On constraint qualifications for nondegenerate necessary conditions of optimality applied to optimal control problems. Discrete & Continuous Dynamical Systems - A, 2011, 29 (2) : 559-575. doi: 10.3934/dcds.2011.29.559
[4]	Ying Gao, Xinmin Yang, Kok Lay Teo. Optimality conditions for approximate solutions of vector optimization problems. Journal of Industrial & Management Optimization, 2011, 7 (2) : 483-496. doi: 10.3934/jimo.2011.7.483
[5]	Jing Quan, Zhiyou Wu, Guoquan Li. Global optimality conditions for some classes of polynomial integer programming problems. Journal of Industrial & Management Optimization, 2011, 7 (1) : 67-78. doi: 10.3934/jimo.2011.7.67
[6]	Yuhua Sun, Laisheng Wang. Optimality conditions and duality in nondifferentiable interval-valued programming. Journal of Industrial & Management Optimization, 2013, 9 (1) : 131-142. doi: 10.3934/jimo.2013.9.131
[7]	Xian-Jun Long, Jing Quan. Optimality conditions and duality for minimax fractional programming involving nonsmooth generalized univexity. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 361-370. doi: 10.3934/naco.2011.1.361
[8]	Xiao-Bing Li, Qi-Lin Wang, Zhi Lin. Optimality conditions and duality for minimax fractional programming problems with data uncertainty. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1133-1151. doi: 10.3934/jimo.2018089
[9]	José M. Arrieta, Simone M. Bruschi. Very rapidly varying boundaries in equations with nonlinear boundary conditions. The case of a non uniformly Lipschitz deformation. Discrete & Continuous Dynamical Systems - B, 2010, 14 (2) : 327-351. doi: 10.3934/dcdsb.2010.14.327
[10]	Ziye Shi, Qingwei Jin. Second order optimality conditions and reformulations for nonconvex quadratically constrained quadratic programming problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 871-882. doi: 10.3934/jimo.2014.10.871
[11]	Jinchuan Zhou, Changyu Wang, Naihua Xiu, Soonyi Wu. First-order optimality conditions for convex semi-infinite min-max programming with noncompact sets. Journal of Industrial & Management Optimization, 2009, 5 (4) : 851-866. doi: 10.3934/jimo.2009.5.851
[12]	Xiuhong Chen, Zhihua Li. On optimality conditions and duality for non-differentiable interval-valued programming problems with the generalized (F, ρ)-convexity. Journal of Industrial & Management Optimization, 2018, 14 (3) : 895-912. doi: 10.3934/jimo.2017081
[13]	Ram U. Verma. General parametric sufficient optimality conditions for multiple objective fractional subset programming relating to generalized $(\rho,\eta,A)$ -invexity. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 333-339. doi: 10.3934/naco.2011.1.333
[14]	Vladimir Gaitsgory, Alex Parkinson, Ilya Shvartsman. Linear programming based optimality conditions and approximate solution of a deterministic infinite horizon discounted optimal control problem in discrete time. Discrete & Continuous Dynamical Systems - B, 2019, 24 (4) : 1743-1767. doi: 10.3934/dcdsb.2018235
[15]	B. Bonnard, J.-B. Caillau, E. Trélat. Second order optimality conditions with applications. Conference Publications, 2007, 2007 (Special) : 145-154. doi: 10.3934/proc.2007.2007.145
[16]	Yong Xia. New sufficient global optimality conditions for linearly constrained bivalent quadratic optimization problems. Journal of Industrial & Management Optimization, 2009, 5 (4) : 881-892. doi: 10.3934/jimo.2009.5.881
[17]	Liwei Zhang, Jihong Zhang, Yule Zhang. Second-order optimality conditions for cone constrained multi-objective optimization. Journal of Industrial & Management Optimization, 2018, 14 (3) : 1041-1054. doi: 10.3934/jimo.2017089
[18]	Mariane Bourgoing. Viscosity solutions of fully nonlinear second order parabolic equations with $L^1$ dependence in time and Neumann boundary conditions. Existence and applications to the level-set approach. Discrete & Continuous Dynamical Systems - A, 2008, 21 (4) : 1047-1069. doi: 10.3934/dcds.2008.21.1047
[19]	J.-P. Raymond, F. Tröltzsch. Second order sufficient optimality conditions for nonlinear parabolic control problems with state constraints. Discrete & Continuous Dynamical Systems - A, 2000, 6 (2) : 431-450. doi: 10.3934/dcds.2000.6.431
[20]	Luong V. Nguyen. A note on optimality conditions for optimal exit time problems. Mathematical Control & Related Fields, 2015, 5 (2) : 291-303. doi: 10.3934/mcrf.2015.5.291

2017 Impact Factor: 0.994

American Institute of Mathematical Sciences