优化 | 浅谈约束规范性条件(Constraint Qualification)

Baste

编者按：本文浅谈了什么是约束规范性条件(constraint qualification)，并列举了一些常见的CQ和它们之间的关系。

作者：门泊东吴
责任编辑：门泊东吴
文章发表于微信公众号【运筹OR帷幄】：优化 | 浅谈约束规范性条件(Constraint Qualification)
欢迎原链接转发，转载请私信@运筹OR帷幄获取信息，盗版必究。
敬请关注和扩散本专栏及同名公众号，会邀请全球知名学者发布运筹学、人工智能中优化理论等相关干货、知乎Live及行业动态
更多精彩文章，欢迎访问我们的机构号：@运筹OR帷幄

看了之前公众号推送的文章《【学界】关于KKT条件的深入讨论》，忽然发现自己以前学的constraint qualification(简称CQ)的知识，因为太久不用，好多都不记得了；此处忽然又想起以前一个教授在课堂上说过的话，"真正理解透彻的东西，根本不用费心记忆，你忘了就代表你当时压根儿就没理解"，汗颜... 专门讨论CQ的文章并不是很多，遂写之，主要想通过这篇文章和大家一起温故而知新，重新理解一下CQ到底在刻画什么？学艺不精，一知半(不)解，欢迎大家批评指正。
一、数学铺垫：定义三个锥

• 可行方向锥(feasible direction cone, Definition 4.6.1 in [1])
  

• 切线锥(tangent cone, Definition 4.6.2 in [1])
  

可行方向锥和切线锥之间有下面两个关系：(Proposition 4.6.2 in [1])


下面这张图摘自[1]的4.6节，分别说明了这两个关系。

• 极锥(polar cone, Section 3.1 of [1])
  

二、局部最优解的必要条件

CQ和KKT条件的关系密不可分，正如王源在文章《【学界】关于KKT条件的深入探讨》里所述，CQ完善了KKT条件的严谨性，在满足CQ的条件下，KKT条件才是带约束的优化问题的局部最优解的必要条件，否则应该用Fritz John条件。我们先来简单回顾一下KKT条件，考虑如下带约束的优化问题：


(详见文章《【学界】关于KKT条件的深入探讨》中第3节的例子)，那有了CQ为什么就可以避免这种情况呢？回到文章最开始的问题，所谓CQ，字面意思是约束的规范性条件，它究竟刻画了什么？
我们再来看看，局部最优解的必要条件还有哪些别的表述形式？Bertsekas在[1]的4.7节里推导了对于具有三种不同性质(主要是目标函数的光滑性)的带约束的优化问题的局部最优解的必要条件：Proposition 4.7.1-4.7.3，我们只简单看一下Proposition 4.7.1。


接下来，我们试着从这个等价条件出发，看看如何引出CQ。重新看回到问题(CP)，第一步，先只考虑线性等式约束，即：


第二步，考虑一般的等式约束问题，即：


三、经典CQ和它们之间的关系

这一小节，我们来重温一下一些常见的经典CQ。考虑如下带约束的优化问题：

• Abadie CQ (ACQ)
  

• Guignard CQ (GCQ)
  

• Linear Independence CQ (LICQ)
  

• Mangasarian-Fromovitz CQ (MFCQ)
  

• Slater CQ (SLCQ)
  更常见的表述是Slater's Condition，考虑如下带约束的凸优化问题：
  

还有其他许许多多的CQ，推荐阅读[3]，真的有好多，嗯，开卷有益。最后，用[3]里面两张有趣的图来结束这一小节：第一张图是一般情况下CQ之间的关系(谁implies谁)，第二张图是约束集为凸的情况下CQ之间的关系。




这两张图里，我们都可以观察到，GCQ、ACQ确实在比较上方，说明比较弱；我们常用的SLCQ、LICQ、MFCQ都在比较下方，算是比较强的了。

四、写在最后

像CQ这种很基础的概念，作为优化领域的小学生，平时钻研得比较少，即使碰到也多是用现成的理论，若有错误理解或疏漏，欢迎大家讨论补充；在大牛们一些比较fundamental的工作里，我也确实看到过他们自己定义一些新的CQ来fertilize他们的算法理论，对数学的要求蛮高的，可能越是具有奠基性的工作就越是先要从基础下铲子吧~

参考文献：
[1] D. P. Bertsekas, A. Nedic and A. E. Ozdaglar, Convex Analysis And Optimization, Athena Scientific Belmont, 2003.
[2] J. V. Burke, Constraint Qualifications for Nonlinear Programming. Numerical Optimization Course Notes, AMath/Math 516, University of Washington, Spring Term 2012.
[3] D. W. Peterson, A Review of Constraint Qualifications in Finite-dimensional Spaces, SIAM Review, 15(3):639-654, 1973.
<hr/>更多精彩文章欢迎关注我们的机构号@运筹OR帷幄
扫二维码关注『运筹OR帷幄』公众号：

zifa2003293

温故知新，百看不厌
[干杯]

fwalker

看不懂，一知半解的，看这个是不是需要哪些基础知识？

johnsoncodehk

太多了，哈哈~ 欢迎加 @运筹OR帷幄 学术群交流~