American Institute of Mathematical Sciences

Advanced
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

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]

in "Nonlinear Programming" (ed. J. Abadie), North-Holland Pub. Co., (1967), 19-36.  Google Scholar

[2]

Mathematical Programming, 135 (2012), 255-273. doi: 10.1007/s10107-011-0456-0.  Google Scholar

[3]

Journal of Optimization Theory and Applications, 125 (2005), 473-483. doi: 10.1007/s10957-004-1861-9.  Google Scholar

[4]

Naval Research Logistics Quarterly, 8 (1961), 175-191. doi: 10.1002/nav.3800080206.  Google Scholar

[5]

Management Science, 18 (1972), 567-573. doi: 10.1287/mnsc.18.9.567.  Google Scholar

[6]

$3^{rd}$ edition, Wiley-Interscience, Hoboken, NJ, 2006. doi: 10.1002/0471787779.  Google Scholar

[7]

$2^{nd}$ edition, Athena Scientific, 1999.  Google Scholar

[8]

Athena Scientific, Belmont, MA, 2003.  Google Scholar

[9]

Journal of Optimization Theory and Applications, 114 (2002), 287-343. doi: 10.1023/A:1016083601322.  Google Scholar

[10]

Mathematical Programming, 35 (1986), 83-96. doi: 10.1007/BF01589443.  Google Scholar

[11]

SIAM Journal on Control, 4 (1966), 528-547. doi: 10.1137/0304041.  Google Scholar

[12]

RAND Memorandum RM-3858-PR, RAND Corporation, 1963. Google Scholar

[13]

Princeton University Press, Princeton, 1953. Google Scholar

[14]

McGraw-Hill Book Company, Inc., New York-Toronto-London, 1960.  Google Scholar

[15]

Optimization, 25 (1992), 11-23. doi: 10.1080/02331939208843804.  Google Scholar

[16]

SIAM Journal on Applied Mathematics, 20 (1971), 164-172. doi: 10.1137/0120021.  Google Scholar

[17]

Mathematical Programming, 2 (1972), 1-18. doi: 10.1007/BF01584534.  Google Scholar

[18]

SIAM Journal on Control and Optimization, 28 (1990), 925-935. doi: 10.1137/0328051.  Google Scholar

[19]

SIAM Journal on Control, 7 (1969), 232-241. doi: 10.1137/0307016.  Google Scholar

[20]

John Wiley & Sons, Inc., New York-London-Sydney, 1966.  Google Scholar

[21]

Pure and Applied Mathematics, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1975.  Google Scholar

[22]

in "Studies in Linear and Non-linear Programming" (eds. K. J. Arrow, L. Hurwicz and H. Uzawa), Stanford University Press, (1958), 38-102. Google Scholar

[23]

Mathematical Programming Studies, 21 (1984), 110-126. doi: 10.1007/BFb0121214.  Google Scholar

[24]

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.  Google Scholar

[25]

Journal of Optimization Theory and Applications, 81 (1994), 533-548. doi: 10.1007/BF02193099.  Google Scholar

[26]

Addison-Wesley Publishing Co., Inc., Reading, Mass.-London, 1959.  Google Scholar

[27]

in "Second Berkeley Symposium on Mathematical Statistics and Probability," University of California Press, Berkeley and Los Angeles, (1951), 481-492.  Google Scholar

[28]

Mathematical Programming, 60 (1993), 339-347. doi: 10.1007/BF01580618.  Google Scholar

[29]

Journal of Optimization Theory and Applications, 82 (1994), 59-75. doi: 10.1007/BF02191779.  Google Scholar

[30]

Mathematical Programming, 126 (2011), 365-392. doi: 10.1007/s10107-009-0288-3.  Google Scholar

[31]

$3^{rd}$ edition, International Series in Operations Research & Management Science, 116, Springer, 2008.  Google Scholar

[32]

Journal of Industrial and Management Optimization, 8 (2012), 705-726. doi: 10.3934/jimo.2012.8.705.  Google Scholar

[33]

McGraw-Hill Book Company, Inc., New York-London-Sydney, 1969.  Google Scholar

[34]

Journal of Mathematical Analysis and Applications, 17 (1967), 37-47. doi: 10.1016/0022-247X(67)90163-1.  Google Scholar

[35]

Mathematical Programming, 47 (1990), 389-405. doi: 10.1007/BF01580871.  Google Scholar

[36]

Optimization, 60 (2011), 429-440. doi: 10.1080/02331930902971377.  Google Scholar

[37]

Optimization Methods and Software, 19 (2004), 493-506. doi: 10.1080/10556780410001709420.  Google Scholar

[38]

SIAM Review, 15 (1973), 639-654. doi: 10.1137/1015075.  Google Scholar

[39]

SIAM Journal on Optimization, 10 (2000), 963-981. doi: 10.1137/S1052623497326629.  Google Scholar

[40]

Mathematische Annalen, 184 (1970), 133-154. doi: 10.1007/BF01350314.  Google Scholar

[41]

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.  Google Scholar

[42]

SIAM Review, 35 (1993), 183-238. doi: 10.1137/1035044.  Google Scholar

[43]

Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 317, Springer-Verlag, Berlin, 1998. doi: 10.1007/978-3-642-02431-3.  Google Scholar

[44]

Cowles Foundation Discussion Paper No. 80, Cowles Foundation for Research in Economics, Yale University, 1950. Google Scholar

[45]

in "Wiley Encyclopedia of Operations Research and Management Science," John Wiley & Sons, Inc., 2010. doi: 10.1002/9780470400531.eorms0978.  Google Scholar

[46]

Journal of Optimization Theory and Applications, 121 (2004), 647-671. doi: 10.1023/B:JOTA.0000037607.48762.45.  Google Scholar

[47]

SIAM Journal on Applied Mathematics, 15 (1967), 284-293. doi: 10.1137/0115028.  Google Scholar

[48]

Prentice-Hall International Series in Management, Prentice-Hall, Inc., Englewood Cliffs, NJ, 1969.  Google Scholar

show all references

References:
[1]

in "Nonlinear Programming" (ed. J. Abadie), North-Holland Pub. Co., (1967), 19-36.  Google Scholar

[2]

Mathematical Programming, 135 (2012), 255-273. doi: 10.1007/s10107-011-0456-0.  Google Scholar

[3]

Journal of Optimization Theory and Applications, 125 (2005), 473-483. doi: 10.1007/s10957-004-1861-9.  Google Scholar

[4]

Naval Research Logistics Quarterly, 8 (1961), 175-191. doi: 10.1002/nav.3800080206.  Google Scholar

[5]

Management Science, 18 (1972), 567-573. doi: 10.1287/mnsc.18.9.567.  Google Scholar

[6]

$3^{rd}$ edition, Wiley-Interscience, Hoboken, NJ, 2006. doi: 10.1002/0471787779.  Google Scholar

[7]

$2^{nd}$ edition, Athena Scientific, 1999.  Google Scholar

[8]

Athena Scientific, Belmont, MA, 2003.  Google Scholar

[9]

Journal of Optimization Theory and Applications, 114 (2002), 287-343. doi: 10.1023/A:1016083601322.  Google Scholar

[10]

Mathematical Programming, 35 (1986), 83-96. doi: 10.1007/BF01589443.  Google Scholar

[11]

SIAM Journal on Control, 4 (1966), 528-547. doi: 10.1137/0304041.  Google Scholar

[12]

RAND Memorandum RM-3858-PR, RAND Corporation, 1963. Google Scholar

[13]

Princeton University Press, Princeton, 1953. Google Scholar

[14]

McGraw-Hill Book Company, Inc., New York-Toronto-London, 1960.  Google Scholar

[15]

Optimization, 25 (1992), 11-23. doi: 10.1080/02331939208843804.  Google Scholar

[16]

SIAM Journal on Applied Mathematics, 20 (1971), 164-172. doi: 10.1137/0120021.  Google Scholar

[17]

Mathematical Programming, 2 (1972), 1-18. doi: 10.1007/BF01584534.  Google Scholar

[18]

SIAM Journal on Control and Optimization, 28 (1990), 925-935. doi: 10.1137/0328051.  Google Scholar

[19]

SIAM Journal on Control, 7 (1969), 232-241. doi: 10.1137/0307016.  Google Scholar

[20]

John Wiley & Sons, Inc., New York-London-Sydney, 1966.  Google Scholar

[21]

Pure and Applied Mathematics, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1975.  Google Scholar

[22]

in "Studies in Linear and Non-linear Programming" (eds. K. J. Arrow, L. Hurwicz and H. Uzawa), Stanford University Press, (1958), 38-102. Google Scholar

[23]

Mathematical Programming Studies, 21 (1984), 110-126. doi: 10.1007/BFb0121214.  Google Scholar

[24]

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.  Google Scholar

[25]

Journal of Optimization Theory and Applications, 81 (1994), 533-548. doi: 10.1007/BF02193099.  Google Scholar

[26]

Addison-Wesley Publishing Co., Inc., Reading, Mass.-London, 1959.  Google Scholar

[27]

in "Second Berkeley Symposium on Mathematical Statistics and Probability," University of California Press, Berkeley and Los Angeles, (1951), 481-492.  Google Scholar

[28]

Mathematical Programming, 60 (1993), 339-347. doi: 10.1007/BF01580618.  Google Scholar

[29]

Journal of Optimization Theory and Applications, 82 (1994), 59-75. doi: 10.1007/BF02191779.  Google Scholar

[30]

Mathematical Programming, 126 (2011), 365-392. doi: 10.1007/s10107-009-0288-3.  Google Scholar

[31]

$3^{rd}$ edition, International Series in Operations Research & Management Science, 116, Springer, 2008.  Google Scholar

[32]

Journal of Industrial and Management Optimization, 8 (2012), 705-726. doi: 10.3934/jimo.2012.8.705.  Google Scholar

[33]

McGraw-Hill Book Company, Inc., New York-London-Sydney, 1969.  Google Scholar

[34]

Journal of Mathematical Analysis and Applications, 17 (1967), 37-47. doi: 10.1016/0022-247X(67)90163-1.  Google Scholar

[35]

Mathematical Programming, 47 (1990), 389-405. doi: 10.1007/BF01580871.  Google Scholar

[36]

Optimization, 60 (2011), 429-440. doi: 10.1080/02331930902971377.  Google Scholar

[37]

Optimization Methods and Software, 19 (2004), 493-506. doi: 10.1080/10556780410001709420.  Google Scholar

[38]

SIAM Review, 15 (1973), 639-654. doi: 10.1137/1015075.  Google Scholar

[39]

SIAM Journal on Optimization, 10 (2000), 963-981. doi: 10.1137/S1052623497326629.  Google Scholar

[40]

Mathematische Annalen, 184 (1970), 133-154. doi: 10.1007/BF01350314.  Google Scholar

[41]

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.  Google Scholar

[42]

SIAM Review, 35 (1993), 183-238. doi: 10.1137/1035044.  Google Scholar

[43]

Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], 317, Springer-Verlag, Berlin, 1998. doi: 10.1007/978-3-642-02431-3.  Google Scholar

[44]

Cowles Foundation Discussion Paper No. 80, Cowles Foundation for Research in Economics, Yale University, 1950. Google Scholar

[45]

in "Wiley Encyclopedia of Operations Research and Management Science," John Wiley & Sons, Inc., 2010. doi: 10.1002/9780470400531.eorms0978.  Google Scholar

[46]

Journal of Optimization Theory and Applications, 121 (2004), 647-671. doi: 10.1023/B:JOTA.0000037607.48762.45.  Google Scholar

[47]

SIAM Journal on Applied Mathematics, 15 (1967), 284-293. doi: 10.1137/0115028.  Google Scholar

[48]

Prentice-Hall International Series in Management, Prentice-Hall, Inc., Englewood Cliffs, NJ, 1969.  Google Scholar

[1]

Wei Wang, Wanbiao Ma, Xiulan Lai. Sufficient conditions for global dynamics of a viral infection model with nonlinear diffusion. Discrete & Continuous Dynamical Systems - B, 2021, 26 (7) : 3989-4011. doi: 10.3934/dcdsb.2020271
[2]

Pengyu Chen. Non-autonomous stochastic evolution equations with nonlinear noise and nonlocal conditions governed by noncompact evolution families. Discrete & Continuous Dynamical Systems, 2021, 41 (6) : 2725-3737. doi: 10.3934/dcds.2020383
[3]

Claudia Lederman, Noemi Wolanski. An optimization problem with volume constraint for an inhomogeneous operator with nonstandard growth. Discrete & Continuous Dynamical Systems, 2021, 41 (6) : 2907-2946. doi: 10.3934/dcds.2020391
[4]

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
[5]

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
[6]

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
[7]

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
[8]

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
[9]

Valery Y. Glizer. Novel Conditions of Euclidean space controllability for singularly perturbed systems with input delay. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 307-320. doi: 10.3934/naco.2020027
[10]

Xiaofei Liu, Yong Wang. Weakening convergence conditions of a potential reduction method for tensor complementarity problems. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021080
[11]

Vandana Sharma. Global existence and uniform estimates of solutions to reaction diffusion systems with mass transport type boundary conditions. Communications on Pure & Applied Analysis, 2021, 20 (3) : 955-974. doi: 10.3934/cpaa.2021001
[12]

Jihoon Lee, Nguyen Thanh Nguyen. Gromov-Hausdorff stability of reaction diffusion equations with Robin boundary conditions under perturbations of the domain and equation. Communications on Pure & Applied Analysis, 2021, 20 (3) : 1263-1296. doi: 10.3934/cpaa.2021020
[13]

Elimhan N. Mahmudov. Second order discrete time-varying and time-invariant linear continuous systems and Kalman type conditions. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021010
[14]

Amru Hussein, Martin Saal, Marc Wrona. Primitive equations with horizontal viscosity: The initial value and The time-periodic problem for physical boundary conditions. Discrete & Continuous Dynamical Systems, 2021, 41 (7) : 3063-3092. doi: 10.3934/dcds.2020398
[15]

Jan Březina, Eduard Feireisl, Antonín Novotný. On convergence to equilibria of flows of compressible viscous fluids under in/out–flux boundary conditions. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3615-3627. doi: 10.3934/dcds.2021009
[16]

Chonghu Guan, Xun Li, Rui Zhou, Wenxin Zhou. Free boundary problem for an optimal investment problem with a borrowing constraint. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021049
[17]

Mohammed Abdelghany, Amr B. Eltawil, Zakaria Yahia, Kazuhide Nakata. A hybrid variable neighbourhood search and dynamic programming approach for the nurse rostering problem. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2051-2072. doi: 10.3934/jimo.2020058
[18]

Vladimir Gaitsgory, Ilya Shvartsman. Linear programming estimates for Cesàro and Abel limits of optimal values in optimal control problems. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021102
[19]

Eduardo Casas, Christian Clason, Arnd Rösch. Preface special issue on system modeling and optimization. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021008
[20]

Sarra Delladji, Mohammed Belloufi, Badreddine Sellami. Behavior of the combination of PRP and HZ methods for unconstrained optimization. Numerical Algebra, Control & Optimization, 2021, 11 (3) : 377-389. doi: 10.3934/naco.2020032

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (339)
  • HTML views (0)
  • Cited by (4)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences