凸集合与凸函数以及案例实现

向右看齐 2022-03-16 00:28 184阅读 0赞

### 1.凸集合(Convex Set) ###

定义：假设对于任意x,y ∈ C and 任意参数 α ∈ \[0,1\]，我们有αx + (1-α)y ∈ C ，集合C为凸集合。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0MzI2MDMwNDM0_size_16_color_FFFFFF_t_70]  
例子：

*  所有的R^n
 *  所有的正数集合
 *  范数 ||x|| <= 1
 *  affine set:线性方程的所有解 Ax = b
 *  halfspace: 不等式的所有解 a^T x <= b

定理：两个凸集的交集也是凸集(intersection of convex set is convex)

### 2.凸函数(Convex Function) ###

定义：函数f的定义域dom f为凸集，对于定义域里的任意x,y，函数满足:  
f(θx + (1-θ)y) <= θf(x) + (1-θ)f(y)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0MzI2MDMwNDM0_size_16_color_FFFFFF_t_70 1]  
假设f为凸函数，则-f为凹函数

例子：

*  线性函数为凸/凹函数
 *  exp x , -log x ,x log x是凸函数
 *  范数为凸函数
 *  x^T \* x/t为凸函数(t > 0)
 *  (x1x2,…,xn)^(1/n)是凹函数(x > 0)

定理：

1.  First order convexity conditions:  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0MzI2MDMwNDM0_size_16_color_FFFFFF_t_70 2]
2.  Second order convexity conditions: ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0MzI2MDMwNDM0_size_16_color_FFFFFF_t_70 3]

例子拓展：  
3. 对于任意PSD矩阵A，符合以下情况的二次方函数(quadratic function)都是凸函数。![在这里插入图片描述][20190225174216103.png]

### 3.案例 ###

###### 最大流问题(Maximum Flow Problem) ######

计算出从源点到经过的所有路径的最终到达汇点的最大流之和  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0MzI2MDMwNDM0_size_16_color_FFFFFF_t_70 4]

1.  首先我们可以定义一个 x\_ij ，意味着从i点到j点的流量，然后就可以推理出以下限制条件：  
    Node1: x\_01 = x\_14 + x\_15 （1点的流量流入和流出相等）  
    Node2: x\_02 = x\_24 + x\_25 + x\_26  
    Node3: x\_03 = x\_35  
    Node4: x\_14 + x\_24 = x47  
    Node5: x\_15 + x\_25 + x\_35 = x\_57  
    Node6: x\_26 = x\_67  
    另外，每一条管道的值，都应该大于等于0，且小于等于可通过的最大值，例如0 <= x\_01 <= 3

然后我们可以将条件带入[scipy.optimize.linprog][]之类的库中进行运算  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0MzI2MDMwNDM0_size_16_color_FFFFFF_t_70 5]  
然后直接打印结果

res = linprog(c, A_eq=A, b_eq=b, bounds=(x0_bounds,x1_bounds,x2_bounds,x3_bounds,x4_bounds,x5_bounds,x6_bounds,x7_bounds,x8_bounds,x9_bounds,x10_bounds,x11_bounds), options={"disp": True})
    print(res

打印结果如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0MzI2MDMwNDM0_size_16_color_FFFFFF_t_70 6]  
可以看到一共循环了11次，找到最小值结果是-6(因为模型是求的最小值，所以做了负数的处理，实际结果就是6)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0MzI2MDMwNDM0_size_16_color_FFFFFF_t_70]: /images/20220316/98cf6129d9a7408ab4986e4004873056.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0MzI2MDMwNDM0_size_16_color_FFFFFF_t_70 1]: /images/20220316/bf37dba808bc411a9a6906b0bf8cfb9c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0MzI2MDMwNDM0_size_16_color_FFFFFF_t_70 2]: /images/20220316/491938785b324f95a1e07aa80db31ff2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0MzI2MDMwNDM0_size_16_color_FFFFFF_t_70 3]: /images/20220316/8e35bc13959c4f37ba4a176aafb8ba72.png
[20190225174216103.png]: /images/20220316/e6bb189fa996482eb824f05fd5302554.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0MzI2MDMwNDM0_size_16_color_FFFFFF_t_70 4]: /images/20220316/bbd4a88804014e08b3ebfa77f9508e2b.png
[scipy.optimize.linprog]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linprog.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0MzI2MDMwNDM0_size_16_color_FFFFFF_t_70 5]: /images/20220316/5702508dca334f83b3ae25f0cb3c4d65.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x0MzI2MDMwNDM0_size_16_color_FFFFFF_t_70 6]: /images/20220316/9c1dae84f58448c6a7862f152cad990f.png