凸分析是研究凸函数凸集性质的数学分支,其应用称作凸优化,是最优化理论的子分支。

3维凸多面体。凸分析不仅包括欧氏空间凸子集的研究,还包含抽象空间上凸函数的研究。

凸集

向量空间X的子集 ,若满足下列任意一条等价条件,就称其是的(convex):

  1.  是实数, ,则 [1]
  2.  是实数,  
 
区间上的凸函数

 始终是以扩展实数线 为值域、以某向量空间的凸子集 定义域的映射。 映射 ,若

 (凸性 

对所有实数 、所有 都成立,称映射f凸函数。若此不等式被替换为严格不等式

 (凸性 

f仍成立,则称f严格凸的。[1] 凸函数与凸集有关。特别地,当且仅当函数f上图(epigraph)

 
当且仅当函数(黑色)的上图(即函数图像上方区域,绿色)是凸集时,函数是凸的。
 
二元凸函数 的图像
 

是凸集时,函数f是凸的。[2]扩展实值函数的上图在凸分析中的作用类似于实值函数图像实分析中的作用。特别地,扩展实值函数的上图提供了几何直觉,可用于形式化或证明猜想。

函数 的定义域记作 有效域则是集合[2]

 

函数 ,当且仅当 ,称函数是真凸函数[2]这意味着在f的定义域中存在x使 f也永远不等于  。换句话说,若函数的定义域非空、永远不取 、不等于 ,则就是真凸函数。若 真凸函数,则存在向量 、实数 使得

 

其中 表示向量的点积

凸共轭

扩展实值函数 (不必凸)的凸共轭是来自X的(连续)对偶空间函数 [3]

 

其中,括号 表示规范对偶性 f的双共轭是映射 ,定义为 X上的Y值函数记作 ,则 定义的映射 乘坐勒让德-芬切尔变换。

次微分集与芬切尔-扬不等式

 ,则次微分集(subdifferential set)为

 

例如,在 X上的范数这一重要特例中,可以证明[proof 1]

 ,则此定义可简化为:

  

 这就是芬切尔-扬不等式,当且仅当 时是等式。正是通过这种方式,次微分集 与凸共轭 直接相关。

双共轭

函数 的双共轭是共轭的共轭,一般写作 。双共轭有助于显示强对偶弱对偶何时成立(通过扰动函数)。

 不等式 符合芬切尔-扬不等式。对紧合(proper)的函数当且仅当f是凸的下半连续函数时, 芬切尔–莫罗定理)。[3][4]

凸最小化

凸最小化(主)问题形如

给定凸函数 与凸子集 ,求 

对偶问题

优化理论中,对偶原则(duality principle)指出,优化问题可以从两个角度分别视作主问题与对偶问题。

一般来说,给定一对分离的局部凸空间  ,以及函数 ,可以把主问题定义为求x使得

 

可令 (其中I示性函数)将约束嵌入f。那么让 扰动函数,使得 [5]

关于所选扰动函数的对偶问题由下式给出:

 

其中 F两个变量的凸共轭。

对偶间隙是不等式左右两式的差[6][5][7]

 

此原理同弱对偶。若两侧相等,则问题满足强对偶。 强对偶成立的条件有很多,如

  •  ,其中F是连接主问题与对偶问题的扰动函数 F的双共轭;[來源請求]
  • 主问题是线性规划问题;
  • 凸优化问题的斯莱特条件[8][9]

拉格朗日对偶性

对不等式约束的凸最小化问题,

  subject to  ,其中 

其拉格朗日对偶问题是

  subject to  ,其中 

其中目标函数 是如下定义的拉格朗日对偶函数:

 

另见

注释

  1. ^ 1.0 1.1 Rockafellar, R. Tyrrell. Convex Analysis. Princeton, NJ: Princeton University Press. 1997 [1970]. ISBN 978-0-691-01586-6. 
  2. ^ 2.0 2.1 2.2 Rockafellar & Wets 2009,第1-28頁.
  3. ^ 3.0 3.1 Zălinescu 2002,第75-79頁.
  4. ^ Borwein, Jonathan; Lewis, Adrian. Convex Analysis and Nonlinear Optimization: Theory and Examples  2. Springer. 2006: 76–77. ISBN 978-0-387-29570-1. 
  5. ^ 5.0 5.1 Boţ, Radu Ioan; Wanka, Gert; Grad, Sorin-Mihai. Duality in Vector Optimization. Springer. 2009. ISBN 978-3-642-02885-4. 
  6. ^ Zălinescu 2002,第106-113頁.
  7. ^ Csetnek, Ernö Robert. Overcoming the failure of the classical generalized interior-point regularity conditions in convex optimization. Applications of the duality theory to enlargements of maximal monotone operators. Logos Verlag Berlin GmbH. 2010. ISBN 978-3-8325-2503-3. 
  8. ^ Borwein, Jonathan; Lewis, Adrian. Convex Analysis and Nonlinear Optimization: Theory and Examples 2. Springer. 2006. ISBN 978-0-387-29570-1. 
  9. ^ Boyd, Stephen; Vandenberghe, Lieven. Convex Optimization (PDF). Cambridge University Press. 2004 [2011-10-03]. ISBN 978-0-521-83378-3. (原始内容存档 (PDF)于2021-05-09). 
  1. ^  则结论是直接的(平凡),所以假设不这样(非平凡)。固定 ,将f换成范数,给出 。若 是实数,则 给出 特别地取 则有 ,而取 则有 于是 ;若还 则因 对偶范数的定义可知 由于 其等价于 可知 于是 从这些事实,可以得到结论。∎

参考文献

外部链接

参考资料

  1. ^ Bauschke & Combettes 2017,第1-2頁.
  2. ^ Boyd & Vandenberghe 2004,第1-2頁.
  3. ^ Rockafellar & Wets 2009.
  4. ^ Rudin 1991.
  5. ^ Zălinescu 2002,第1-2頁.