Optimization

Introduction

1. 最优化：在满足一系列约束条件下，获得目标函数或指标获得一个最大值（最小值）

Linear programs（线性规划）

1. 线性函数 (linear function) $f(x) = a^T x$
2. 仿射函数 (affine function $f(x) = a^T x + β$

所有线性函数都是仿射函数$(if β==0)$，反之则不然，

Integer programs （整数规划）

1. 整数规划指的是，在一个线性规划中，添加了其变量的非空子集必须取整数的限制条件。
2. 当所有的变量都要求是整数时，叫做纯整数规划(pure integer program)。否则就叫混合整数规划(mixed integer program)。

Solving linear program

1. 对于一个线性规划问题，如果目标函数是求最大值的线性规划，结果只会有一个最大值，但可能会有多个不同的解，但结果都是相同的最大值，最小值同理。

Possible outcomes

1. 对于一个线性规划(LP)问题，一定有如下3种可能的结果：

   • 不可解
   • 有一个最优解
   • 无界

   这三种结果，同一个问题最多只能出现一种

Standard equality form

1. 如果LP是一个标准等式(SEF)，它必须满足一下的条件：

   • 它是一个最大值问题
   • 所有的变量必须是非负的
   • 如果非负的限制，所有的限制条件都应该是等式

2. 我们将会设计一个算法，对于 LPinSEF（标准等式表示的线性规划问题），我们证明这个问题是那种结果，但不是所有LP都是SEF，我们希望能将任意LP转化成LPinSEF，然后在LPinSEF使用这个算法，他们两个需要有相同的回答。更准确的说，需要满足一下条件

   • LP无解，当且仅当LPinSEF也无解
   • LP无界，当且仅当LPinSEF也无界
   • 给定一个LP的最优解，可以构建出一个LPinSEF的最优解，反之亦然。

3. 将LP转成LPinSEF的步骤

• 如果目的函数是最小值 $min C^T X$ ，改成最大值$max (-C^T) X$
• 如果 $x_i$ 没有非负限制，则$x_i = x^+_i- x^-_i \ \ where \ \ x^+_i,x^-_i\ge 0$，用$x^+_i,x^-_i$代替$x_i$
• 对于 $\sum^n_{i=1}a_ix_i\ge \beta$，则$\sum^n_{i=1}a_ix_i + x_{n+1}=\beta \ where\ x_{n+1}\ge 0$，在限制条件中添加$x_{n+1}$
  这样就可以将线性规划转化成标准的线性规划

A simplex iteration

Bases and canonical forms （基与规范型）

1. identity matrix ：单位矩阵

2. nonsingular matrix ：非奇异矩阵，性质：满秩，行列式不为0，可逆，也可称可逆矩阵就是非奇异矩阵

3. a basis ：列子集中的最大线性无关组，并且是非奇异矩阵

4. 规范形式(canonical forms) :对于LPinSEF $\ max\{c^Tx = \bar{z}:Ax=b,x\ge 0 \}$，B是basis,规范形式需要满足

   • $A_B$ 是单位矩阵
   • $C_B = 0$

• 对于第一个条件，只需要左乘$A_B^{-1}$，得$A_B^{-1}Ax=A_B^{-1}b$，$A_B^{-1}A$中的$A_B$就是单位矩阵了。
• 对于第二个条件，
  将$Ax=b$两边分别乘$y^T$，得$y^TAx=y^Tb\ \xRightarrow\ y^TAx-y^Tb=0$
  加到$z(x)$，得到$z(x) = y^Tb + \bar{z} + (c^T- y^TA)x$
  令 $\bar{c}^T = c^T - y^TA$，我们需要$\bar{c}^T = c^T - y^TA = 0$，故 $y = A_B^{-T}c_B$
• 综上，$z(x) = y^Tb + \bar{z} + (c^T- y^TA)x$
  $A_B^{-1}Ax=A_B^{-1}b,x\ge 0,\ where\ y = A_B^{-T}c_B$

The simplex algorithm （单纯形法）

步骤

1. 获取规范的形式后，选择$k\in N$，并且$c_k>0$，
2. 将$x_B$和$x_N$中的其他值设为0后代入到$Ax=b$中获得$x_k$能得到的最大值，
3. 再将$x_k$代回$Ax=b$得到$x_B$，求得max后
4. 更新B和N，
5. 继续迭代，直到$c_N\le 0$,最终获得一个最优上界

规范化步骤

1. 规范形式：$max\ \ z(x) = \bar{z} + c_N^T x_N \ \ \ \ subject\ to\ \ x_B +A_Nx_N = b,x\ge 0$
   其中 $\bar{z}$ 是确定的值，并且 $b\ge 0$
2. 如果$c_N\le 0$ , $\bar{x}$则是一个最优的解
3. 选择 $k\in N$并且$c_k>0$，然后通过$t$定义$x'_N$，对于$x'_j\in x'_N$有$x'_j = \begin{cases} t &\text{if } j=k \\ 0 &\text{if } j\in N \setminus\{k\} \end{cases}$
4. 如果$A_k\le 0$，则线性规划无界（因为t是无限制的）
5. 因为$x_B +A_Nx_N = b$，得到$x'_B = b - tA_k$，我们需要找到满足$x'_B\ge 0$的 $t$，所以$tA_k\le b$，得到$t=min\{ {\frac {b_i} {A_ik}}:A_ik>0\}$
6. 根据上一条，$x_B'$中的第 r 行为0，则 l 表示 B 中第 r 个基 ，选择$B' = B\cup \{k\} \setminus \{l\}$ ，$N' = N\cup \{l\}\setminus \{k\}$，更新 $B'$ 和 $N'$
7. 然后返回第一步执行，直到结束

当$t=0$时，对于多次迭代，我们会获得相同的解，这可能永远也无法结束(known as cycling)
解决方法 布兰德规则(bland’rule):

• 第三步中，选择一个满足条件的最小的$k$
• 第五步中，选择最小的 $r \in B\ with\ A_{rk} >0$，然后$\frac {b_r} {A_{rl}} = t$

Finding feasible solutions

对于LP问题 $\ max\{c^Tx :Ax=b,x\ge 0 \}$ A有m行n列

Phase 1 构造求解 auxiliary LP

1. 先将b中的所有值转化成非负数，如果是负数，所在行乘-1即可转化成正数
2. 构造：$min\ w=x_{n+1} +...+ x_{n+m}$
   $subject\ \begin{pmatrix} A|I \end{pmatrix} \begin{pmatrix} x_1 \\ ...\\ x_{n+m} \end{pmatrix} = b,(x_1,...,x_{n+m})^T\ge0$ ，其中I是m阶单位矩阵
3. 转化成标准式 $min\ w=x_{n+1} +...+ x_{n+m}\xRightarrow\ max\ w=-x_{n+1} -...- x_{n+m}$
4. 其中 $(x_1,...,x_n)^T=0, (x_{n+1},...x_{n+m})^T=b$是一个可行解
5. 使用单纯形法求解上述LP问题，

• 求得 w=0， $(x_1,...,x_n)T$原式中的一个可行解，进行阶段2
• 若w>0，则此问题无解

Phase 2

1. 根据 phase 1 获得的可行解，用单纯形法求解原问题

Simplex via tableaus

Pivoting(主元)

1. 对于mxn的矩阵T，让元素$T_{i,j}$做主元得到T’：对T进行行变换，使得矩阵中第j列除第i个元素为1，其他全为0
   $T'_k = \begin{cases} \frac 1 {T_{i,j}} T_k &\text{if}\ k=j \\ T_k - \frac {T_{k,j}} {T_{i,j}} T_i &\text{if}\ k \not= j \end{cases}$

Tableaus

1. 把 $max\{ z = \bar{z} + c^T x , Ax = b,x\ge 0\}$ 写成矩阵形式 $z -c^T x = \bar{z}$
   $T=\begin{pmatrix} 1 & -c^T & \bar{z} \\ \hline 0 & A & b \end{pmatrix}$
2. 在T中选择一列k，$c_k>0$，在T中就是 $T_{k,0}<0$，计算t，对于$b_i-tT_{i,k}=0$的，进行上节中的主元变换，直到所有的$c_k<0$，也就是$-c^T>0$，最终的$\bar{z}$就是结果
3. 整个过程原理其实和单纯形法是一样的，这个只是转化成了矩阵的形式进行计算

Geometry

Feasible region of LPs and polyhedr

1. $\{H={x\in n : a^Tx = β\}}$ is a hyperplane(超平面), $\{F={x\in n : a^Tx \le β\}}$ is a halfspace(半空间)

2. rank(A) ：矩阵A的秩

3. LP的解的区域是一个多面体，或者有限个版空间的交集

Convexity

1. Convexity（凸性）：对于一个区域内的任意两点形成的线段，如果这个线段上的任意点也都在这个区域内，就称这个区域是凸性的。
2. 任意个（infinite）凸集的交集还是凸集
3. Polyhedra are convex 多面体都是凸集

Extreme points

1. Extreme points 极点：这个点在凸集中，并且这个点不属于任意凸集中的线段，这个点就叫极点，例如三角形的三个顶点、圆形区域边上的每个点
2. 多面体(apolyhedron)中的极点(extreme point)
   符号表示：对于不等式系统$Ax \le β$，如果$α^T\bar{x}=\beta$,则$Ax \le \beta$中的约束$a^Tx \le β$对$\bar{x}$是严格的，把$Ax \le \beta$中所有对$\bar{x}$严格约束记作$A^=x \le b^=$。
   定理：$P = \{x\in R^n : Ax \le b\}$是一个多面体 $\bar{x} \in P$，$A^=x \le b^=$是对$\bar{x}$严格约束集合，当$rank(A^=)=n$时，$\bar{x}$是极点
   定理：$P = \{x : Ax = b, x\ge 0 \}$, $\bar{x} \in P$，当且仅当$\bar{x}$是$Ax = b$的解时，\bar{x}$是极点

Geometric interpretation of the simplex algorithm

Duality(对偶) through examples

The shortest path problem

1. 可行性条件：对于E中的每个边e，st-cuts中包含边e的width和应该小于等于e的length，
2. 最短路径最优化的条件：如果st-cut都是可行的，所有st-cuts的width和是最短路径的下界，也就是说，如果最短路径的长度等于st-cuts的和，那么这个路径就是最短路径

Minimum cost perfect matching in bipartite graphs

1. 匹配：图G的一个边集M，若M中的任意两条边都没有公共端点，M是一个匹配
2. 完美匹配：若一个匹配M覆盖了图中的所有节点，则称M为图的完美匹配
3. 我们想要找到所有的完美匹配中代价和最小的那个
4. 方法是，先给顶点赋值，然后让边的权重减去它两个点的值得到一个新的权重，新权重需要大于等于0，最后可以从权重为0的边中选择出完美匹配

An intuitive lower bound

1. 给所有顶点u赋值$y_u$，边uv的代价为$c_{uv}$，削减后，边uv的代价:$\bar{c_{uv}}=c_{uv}-y_u-y_v$
2. 因为所有的y是定值，如果M的削减代价$\bar{c}$是最小的，那个它原始代价也是最小的。因为$\sum\bar{c} = \sum c -\sum y$
3. 如果削减代价$\bar{c_{uv}}=0$，那么边uv是关于y的等价边
4. 可行性条件：对于任意边$e \in E$，如果$\bar{c_{uv}} \ge 0$，那么y是可行的
5. 如果y是可行的，并且等价与M中所有的边，那么M就是代价最小的完美匹配集

A general argument–weak duality

• 对于一个最小化问题，下界值越大越接近真实的下界值（最优解）
  1. 对于LP $\ min\{c^Tx : Ax=b,x\ge 0 \}$
  2. 首先给约束条件两边乘$y^T$，得到$y^TAx=y^Tb\ \xRightarrow\ y^Tb-y^TAx=0$
  3. $z(x)=c^Tx+y^Tb-y^TAx =y^Tb+(c^T-y^TA)x$
  4. 假设$(c^T-y^TA)x \ge0$，$\bar{x}$为可行解，所以有 $z(x) \ge y^Tb$， $y^Tb$是目标函数的下界值
  5. 可以转化成 $\ max\{b^Ty : A^Ty \le c\}$，y为无约束的变量

Weak duality–special form (弱对偶-特殊形式)：下面一对LPs
$\ min\{c^Tx : Ax=b,x\ge 0 \}$ P
$\ max\{b^Ty : A^Ty \le c\}$ D
让$\bar{x},\bar{y}$分别作为P，D的解，$c^T\bar{x} \ge b^T\bar{y}$，如果等号成立，$\bar{x}$ 就是最优解
D被定义为P的对偶

Revisiting the intuitive lower bound

• 最小完美匹配的图问题，我们可以写成整数规划的形式:
  1. E为所有边的集合，$c_e$为边e的权重，$x_e$是是否选择这条边
  2. $min \sum(c_ex_e:e\in E)$
  3. subject to $\sum(x_e:e \in \delta(v)=1,(v \in V)$ 一个顶点只能有一条边相连
  4. $x_e \ge 0 , (e \in E)$
  5. $x_e$ integer $(e \in E)$ 是否选择这条边，0 or 1

1. LP relaxation：对于一个整数规划，移除变量必须取整数的条件，叫做IP的线性规划松弛（LP relaxation）
2. 如果D是 IP 的LP relaxation的对偶，那么任意D的可行解都是IP的下界，原因：把 P 作为上面 IP 的 LP relaxation，IP是个最小化问题，所以IP的最优解是大于等于P的最优解的，D作为P的对偶，P的最最优解一定大于等于任意D的解
3. 给定一个一般的完美匹配问题，我们可以将它的LP relaxation写作
   1. $min \{c^Tx:Ax =1,x\ge0\}$
   2. 其中c是边的权重，矩阵A是：
      • A的行是图的顶点
      • A的列是图的边
      • 对于每行每列有 $A[v,e]= \begin{cases} 1 &\text{if v是e的一个端点} \\ 0 &\text{ otherwise } \end{cases}$
   3. 上式的对偶为 $max \{1^Ty:A^Ty<c\}$
   4. 也可以写成 $max \sum(y_v:v\in V)$,subject to $y_u +y_v\le c_{uv}\ (uv\in E)$

An algorithmIn

1. bipartite graph :二分图，图中顶点可以分为两个不相交的顶点集UW，U和W他们内部任意两个顶点没有边相连，任意的边的一个端点在U内，则另一个在W内。
2. 如果一个二分图有完美匹配，必须满足|U|=|W|，也就是U和W中的顶点数目相同
3. 一个二分图G=(V,E)，有分割UW，把顶点的子集记作S，S的邻居节点集合记作$N_G(S)$，如果有$|S|>N_G(S)$，则G中没有完美匹配，叫做缺陷集(deficient set)
4. Hall’s theorem: 二分图G=(V,E)有分割UW，|U|=|W|，当且仅当G中没有缺陷集$S\in U$时，G中有完美匹配M，此外存在多项式时间的算法，对于给定G要么求得它的完美匹配，要么求得缺陷集
5. 算法步骤
   1. 二分图G=(V,E)，有分割UW，|U|=|W|，边的权重c，求最优完美匹配或缺陷集
   2. 初始化$\bar{y}_v= \frac 1 2 min\{c_e:e\in E\}$
   3. 构建图H，H中含有V中所有顶点，但只含有的$\{uv \in E :c_{uv} = \bar{y}_u+\bar{y}_v \}$的边
   4. 如果H有完美匹配M（匹配了所有节点），结束
   5. 否则，求得$S\in U$为H的缺陷集
   6. 若图G中的所有的边都满足：如果边的一个端点是S，另一个端点在$N_H(S)$中，则S是G的缺陷集
   7. $\epsilon = min\{c_{uv} - \bar{y}_u - \bar{y}_v:uv\in E,u\in S,v\notin N_H(S) \}$
   8. 更新 $\bar{y}_v \begin{cases} \bar{y}_v + \epsilon &\text{for } v \in S \\ \bar{y}_v - \epsilon &\text{for } v \in N_H(S) \\ \bar{y}_v &\text{otherwise } \end{cases}$
   9. 返回第三步继续执行

Correctness of the algorithm

Finding perfect matchings in bipartite graphs*

1. M-alternating：匹配集$M\in E$图G中的一条路径P，若路径P上的边交替的处于匹配集中和非匹配集中，或者P\M是匹配集，则称P是交替路径(M-alternating)
2. M-covered,M-exposed：顶点v，M中有连接到v的边，称v是被M覆盖的(M-covered)，否则v是未被覆盖(M-exposed)
3. M-augmenting：一个交替路径P，如果路径P的两个端点都是未被M覆盖的，则P是M的扩充(M-augmenting)
4. 只要给定了个扩充路径，我们都能重新构建一个新的匹配M’，|M’|=|M|+1
5. $A\triangle B$：元素在$A\cup B$中但并不在$A\cap B$中。$A\triangle B = (A-B) \cup (B-A) = A\cup B-A\cap B$
6. maximum matching：最大匹配是有最多的边的匹配

完美匹配和最大匹配之间的关系：一个完美匹配必定是一个最大匹配，但并非所有图都有完美匹配（例如奇数个点的图就没有完美匹配）

1. 若M是图G的匹配集，P是M的扩充路径，$M' = M \triangle P$是一个匹配集并且，|M’|=|M|+1，另外M不是最大匹配集
2. definition
   • cycle 一个边的序列$C=v_1 v_2 v_3 ... v_{k-1} v_k,k \ge 4$ 且$v_1 v_2 v_3 ... v_{k-1}$是不同的顶点，$v_1 = v_k$
   • connection 在图中，任意不同的两点之间存在路径，则这个图是连通图
   • tree 一个图是连通图但图中不含有环
3. 在一个树中，任意两点之间都存在唯一的一条路径
4. graph G(V,E)，matching M and $r \in V$ ，G中的树T，是根节点为r的关于M的交替树(M-alternating tree) 需满足：
   • r是T的一个节点，且未被图G中的匹配M覆盖
   • T中除r以外的所有节点都被M覆盖
   • 对于任意T中顶点u($u \not = r$)，唯一的路径ru是关于M的交替路径
5. 完美匹配算法步骤：
   1. 图H(V,E)，有顶点集UW且$|U|=|W| \ge 1$，求完美匹配或缺陷集（树T中的顶点分为A(T)和B(T)。B(T)中的顶点到根节点r的路径中含有的边的个数为偶数，A(T)中的顶点到根节点r的路径中含有的边的个数为奇数）
   2. 初始化：完美匹配$M=\{\empty\}$，交替树$T=({r},\empty)$，r是任意未覆盖的顶点
   3. 如果存在边uv，$u \in B(T)\ and\ v\notin V(T)$
      • 如果v是未覆盖的
        • 路径P = 交替树T中的路径$T_{ru} \cup \{uv\}$
        • 匹配集$M = M \triangle P$
        • 如果M是一个完美匹配，结束算法
        • 交替树$T=({r},\empty)$，r是任意M未覆盖的顶点
      • 否则 让$vw \in M \ w\in V$，$T= (V(T)\cup\{v,w\},E(T) \cup \{uv,vw\})$
      • 继续第三步
   4. 否则$B(T) \in U$是一个缺陷集

Duality theory

归纳概括上一节的内容，提出通用的理论框架

Weak duality

1. 原始对偶对(primal dual paris)

min	≥ constrain	= constrain	≤ constrain	variable ≥ 0	variable free	variable ≤ 0
max	variable ≥ 0	variable free	variable ≤ 0	≤ constrain	= constrain	≥ constrain

1. Weak duality theorem : P和D是一对原始对偶对，P是最大化问题，Q是最小化问题，$\bar x$和$\bar y$ 分别是P和D的可行解，有
   • $c^T\bar x \le b^T\bar y$
   • 若$c^T\bar x = b^T\bar y$，$\bar x,\bar y$分别是P和D的最优解

Strong duality

1. 强对偶(Strong duality)：P和D是一个对偶对，如果P和D存在相同的最优解，则是强对偶
2. 强对偶-可行性 ：P和D是一个对偶对，如果P和D都存在可行解，P和D存在目标值相同的最优解

A geometric characterization of optimality

Complementary slackness(互补松弛)

1. 对于线性规划的原始对偶对$max\{c^Tx:Ax<b\}\ P$ 和 $min\{b^Ty:A^Ty=c,y\ge 0\}\ D$ ，P添加松弛变量s后可写为 $max\{c^Tx:Ax+s=b,s\ge 0\}\ Q$
2. 若$\bar x,\bar y$分别为P、D的可行解，那么$\bar s=b-A\bar x$为Q的可行解，所以$b^T\bar y = \bar y^Tb =\bar y^T(A\bar x + \bar s)=c^T\bar x + \bar y^T\bar s$
3. 当且仅当$c^T\bar x = b^T\bar y\ or\ \bar y^T\bar s=0$ 时$\bar x,\bar y$分别时最优解
4. $y^T\bar s = \sum^m_{i=1}\bar s_i \bar y_i$ ，因为$\bar s_i\ge 0, \bar y_i\ge 0$，所以$\bar s_i = 0\ or\ \bar y_i = 0$，如果$s_i=0$，原式取 ‘=’，可以称这个约束对 $\bar x$ 是严格的(tight)。
5. 互补松弛-特例：对于P、D的可行解，当且仅当任意 i 都有$\bar s_i = 0\ or\ \bar y_i = 0$时，可行解是最优解
6. 互补松弛条件(complementary slackness CS)
   • $every\ x_j\ of\ P_{max}$ 需要满足$x_j = 0$或者相关的约束条件 $j\ of\ P_{min}$ 满足等式
   • $every\ y_i\ of\ P_{min}$ 需要满足$y_i = 0$或者相关的约束条件 $i\ of\ P_{max}$ 满足等式
7. 互补松弛定理(omplementary slackness theorem)：P、D是任意原始对偶对，当且仅当满足互补松弛条件时，可行解是最优解

Geometry

1. $a^{(1)},a^{(2)}...a^{(k)}$为$R^n$中的向量集合，定义由上述集合产生的锥形$C=\{\sum^k_{i=1}\lambda _i a^{(i)}:\lambda _i \ge 0\}$

2. 实例如下图
   

3. $P=\{x:Ax\le b\}$ 是一个多面体，$\bar x \in P$，$J(\bar x)$ 定义为A中约束条件取等号的行的索引，例如$row_i(A)\bar x = b_i -> i \in J(\bar x)$，定义$\bar x$的严格约束锥形为A的严格约束行$C = cone\{row_i(A)^T:i\in J(\bar x)\}$

4. 若 $\bar x$ 是 $max\{c^Tx:Ax\le b\}$的可行解，当且仅当c在关于$\bar x$的严格约束锥形内时，$\bar x$是最优解

5. 例如对于问题 $max (\frac 3 2,\frac 1 2)x$，约束$\begin{pmatrix} 1 & 0 \\ 1 & 1 \\ 0 & 1 \end{pmatrix} x \le \begin{pmatrix} 2 \\ 3 \\ 2 \end{pmatrix}$，解$\bar x = (2,1)^T$是一个可行解，严格限制锥形为$C=cone \begin{Bmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix}, \begin{pmatrix} 1 \\ 1 \end{pmatrix} \end{Bmatrix}$，可知，c在锥形C内，也就是说c可以由C内的元素表示，如下图所示
   

Farkas’ lemma

1. Farkas 引理：A为一个m x n 的矩阵，b是一个m维向量，一下只有一个是正确的
   • $Ax=b,x \ge 0$，有解
   • 存在向量y，使得$A^Ty \ge 0\ and\ b^Ty < 0$

Applications of duality

Approximation algorithm for set-cover（集覆盖的近似算法）

1. set cover problem （集覆盖问题 npc）：给定一个全集U，一个集合T，集合T中的元素集合S是U的子集，T中所有元素的并集是U，集合覆盖问题是找到T的最小子集，使子集的并集为全集U（覆盖）
   • 本书给每个S添加了一个代价$c_S$，所以原来需要求的最少元素的子集变成了代价和最少的子集。
   • $min \sum(c_Sx_S:S\in T)\ subject\ to\ \sum(x_S:S\in T\ where\ e\in S) \ge1\ (e\in U),\ x\ge0,x\ integer$
2. 近似算法：找到一个高效的算法A，对于任意的实例I，可以得到一个最多$\alpha OPT(I)$的结果，这样的算法叫做近似算法，$\alpha$叫做近似性能比

A primal–dual algorithm

1. $y_e$：对U中的每个元素e设置的一个变量，集合T,集合$S\in T$的代价（约束）$c_S$，S中所有元素的y值之和不能超过这个约束$c_S$

2. 对偶的求解可以参考3.2.1

3. 问题：$max\sum(y_e:e\in U)$ subject to $\sum(y_e:e\in S)\le c_S (S\in T)$

4. 有点像之前的最小完美匹配问题的求解算法步骤

   1. 算法输入: 元素U，集合T，$c_S : S \in T$
   2. 输出：集合$C \in T$覆盖U，$y_e$
   3. 初始化 $y=0,C=\empty$
   4. 当U中存在没有被C中的任意一个集合覆盖的元素e时：
      1. 在保持满足约束条件下，尽可能的增加$y_e$,通过 $\epsilon= min \{c_S-\sum(y_{e'}:e'\in S):S\in T\ where\ e\in S\}$
      2. 让S成为一个严格的集合，覆盖S
      3. 把这个S添加到C中
   5. 返回集合C和可行的y

5. 定义 $f_e$ 为在集合T包含元素元素$e\in U$ 的集合数量，f为所有上述的最大值 $f=max_{e\in U}f_e$, 上述算法是一个近似性能比为f的近似算法

6. 对于图中的向量覆盖问题，改算法的近似性能比为2。（其中元素为图的边，一条边只能有两个顶点，所以性能比最多是2）

Greed is good … at least sometimes

1. 贪婪算法，如果没有代价，我们可以每次都选择包含未覆盖元素最多的集合，直到包含所有的元素，拓展到有代价的问题时，我们需要平衡两个目标：

   • 覆盖尽可能多先前未覆盖到的元素
   • 花费尽可能小的代价

2. 方法：将花费除以新覆盖元素的数量，每次都选择上述值的最大集合加入

3. 贪婪算法：

   1. 输入：元素U，集合T，$c_S : S \in T$
   2. 输出：集合$C \in T$ 覆盖 U
   3. 初始化 $C=\empty$
   4. 当U中存在没有被C中的任意一个集合覆盖的元素e时：
      1. 选择具有 $min (c_S/num(S\backslash U_{s'\in C}s'))$ 的集合S
      2. 将S添加到C中
   5. 结束，返回C

4. 上面算法是近似性能比为$H_m = \sum_{i=1}^m \frac 1 i$的算法

5. 证明：

   • 假设算法选择的集合为$S_1,...,S_p$ ,对于$1\le i \le p$ 有$U_i= S_i \backslash \cup_{j=1}^{i-1}S_j$, 对于$e\in U_i$有$y_e = \frac {c_Si} {|U_i|}$
   • 令$e_1,...e_l$为集合S中的元素，按照他们被贪婪算法覆盖的顺序排序，因为$|U_j|\ge l-i+1\ (|U_j|=l)$ 所以 $y_{e_i} \le \frac {c_S} {l-i+1}$
   • 所以对于选中每个集合S都有 $\sum(y_{e_i}:1\le i\le l)\le \sum(\frac {c_s} {l-i+1}:1\le i \le l) \le H_mc_S$
   • 综上，对于所有选中的S之和都有 $\le H_m OPT(I)$

Discussion

1. 第一种明显更适合于当每个元素都在几个集合时
2. 第二种当最大重复频率高时更有效

Economic interpretationd

The maximum-flow–minimum-cut theorem

1. Maximum-flow-minimum-cut ：一个有向图G=(V,E),容量(capacities) $c\ge 0$ 对于一个st-flow问题，st-flow的最大流量（值）和图中的任意一个st-cut 的最小容量相等
2. $\delta^+(q)$：尾（入射点）是q的边集，$\delta^-(q)$：头（出射点）是q的边集，
3. 定义 $f_x(q) = \sum (x_a:a\in \delta^+(q))- \sum (x_a:a\in \delta^-(q))$ , $x_a$ 是边a的值（流量）
4. s为起点，t为终点
5. LP： $max\ f_x(s)\ subject\ to\ f_x(q)=0\ (q\in V\backslash\{s,t\})\ 0\le x\le c$

Totally unimodular matrices （全幺模矩阵）

1. Totally unimodular matrices （全幺模矩阵）：如果A是 m x n 的整数矩阵，并且A的所有子方阵的行列式为1或-1，称A为 unimodular matrices （幺模矩阵），如果A是幺模矩阵，而且有其各阶子式的行列式全等于0，1或-1，则A称为全幺模矩阵

2. 上述定义暗示：全幺模矩阵的所有元素均为0，1或-1

3. 设A为有向图顶点和边的相关矩阵 $A_{v,e} = \begin{cases} +1 &\text{if } v\ is\ the\ tail\ of\ e \\ -1 &\text{if } v\ is\ the\ head\ of\ e \\ 0 &\text otherwise \end{cases}$

4. 如果M是全幺模矩阵，对于下面几个线性规划，如果有最优解，它的最优解是整数

   • $max{c^Tx:Mx=b,x\ge 0}$ , b int
   • $max{d^Tx:Mx=0,0\le x\le c}$ , c int
   • $max{c^Tx:M^ty +x\ge d,x\ge 0}$ , d int

Applications to st-flows

1. 矩阵M为矩阵A去掉行s和行t，$d_e = \begin{cases} +1 &\text{if } e\in \delta^+(s) \\ -1 &\text{if } e\in \delta^-(s) \\ 0 &\text otherwise \end{cases}$
2. 之前的LP可以重新写成 $max\{ d^Tx\}\ subject\ to\ Mx=0,0\le x\le c$

Solving integer programs

1. 解整数规划一般有两个策略
   1. 去掉整数规划中变量的证书限制，转化成线性规划求解，称为割平面法(cutting palne)
   2. 分而治之的方法，称为分支定界(branch and bound)
2. 实际上，两种策略可以结合起来使用，称为分支剪界(branch and cut)

Integer programs versus linear programs

1. 对于一个多面体 $P=\{x\in R^n:Ax\le b\}$ 当A和b中的项是有理数时，设S为P中所有整数点的集合，那么S的凸包是一个多面体Q，这个多面体可以通过一个项全都是有理数的矩阵和向量来表述
2. IP问题 $max\ c^Tx\ subject\ to\ Ax\le b \ x\ integer$ ，可以转化成LP问题 $max\ c^Tx\ subject\ to\ A’x\le b'$
3. 上面两个之前需要满足
   1. 当且仅当LP无解时IP无解
   2. 当且仅当LP无界时IP无界
   3. 所有IP的最优解都是LP的最优解
   4. 所有LP最优解中的极点都是IP的最优解
4. 一般来说LP比IP大得多（指数级）

Cutting planes （割平面法）

1. cutting palne，满足如下条件的不等式（简称 * ）叫做割平面cutting palne

   1. 对于IP来说 * 是有效的，也就是说，IP的所有可行解都满足*
   2. 当前LP（IP松弛化操作后）的可行解不满足 *

2. 假设P2是P1的松弛问题

   1. 如果P2无解，P1也无解
   2. 如果x是P2的最优解，且x在P1中也是可行的，那么x也是P1的最优解
   3. 如果x是P2的最优解，$c^Tx$是P1的上界

3. Cutting plane algorithm 问题： $max\ c^Tx\ subject\ to\ Ax\le b,x\ge0,x\ integer$

   1. 设LP为 $max\{c^Tx:Ax\le b\}$
   2. 如果LP无解，IP也无解，结束算法
   3. 解得 $\bar x$ 为LP问题的最优解
   4. 如果$\bar x$是整数，那么它也是IP的最优解，结束算法
   5. 对于当前解$\bar x$，找到一个 cutting plane $a^Tx\le \beta$
   6. 把限制 $a^Tx\le \beta$ 添加到 $Ax\le b$系统中
   7. 返回步骤2继续执行

4. 寻找 cutting plane 的流程

   1. 对于IP问题 $max\ c^Tx\ subject\ to\ Ax=b,x\ge 0,integer$
   2. 用简单形法解决IP的松弛化LP，如果LP无解，IP也无解
   3. 假设得到LP的一个基，我们将LP重写为规范式$max\ \bar z+\bar c_N^Tx_N\ subject\ to\ x_B+\bar A_Nx_N=\bar b,x\ge 0$
   4. 上述的基础解$\bar x$为$\bar x_B=\bar b,\bar x_N=0$ ,如果 $\bar b$ 是整数，此解也是IP的最优解
   5. 如果b中的某一项是分数，如 $b_i$ 此行为 $x+\sum \bar A_{ij}x_j=\bar b_i$
   6. 每个变量都是非负的，因此下面不等式也满足 $x+\sum \lfloor \bar A_{ij}\rfloor x_j=\bar b_i$
   7. 因为左边的都是整数，所以$x+\sum \lfloor \bar A_{ij}\rfloor x_j=\lfloor \bar b_i\rfloor$

Branch and bound （分枝定界）

1. 首先解IP问题松弛化操作后的LP问题，得到一个最优解
2. 如果最优解中有分数，则将其分支，分为两个子问题，并分别添加对这个变量大于分数向上取整和小于分数向下取整的限制
3. 分别解这两个子问题，看最优解是否为整数，在进行上一步
4. 在各个步骤中比较整数最优解的目标值，丢弃低于下界的枝

Traveling salesman problem(TSP) and a separation algorithm

1. 旅行商问题：有一系列节点集合，找到一条从一个结点出发，一次不重复的经过所有节点，最后回到该节点的最短路径。
2. $x_{ij}=1$ 表示选择这条路径，而且每个城市必须进入一次，离开一次，这样可以将这个问题转化成IP
3. 但上述操作形成的IP，对TSP问题来说是不对的。因为它可能会形成两个不相连的子回路，我们需要添加消除子回路的约束。
4. 每个回路必须能够离开任意一个这些节点的非平凡子集（除空集和本身外的子集）

Nonlinear optimization

1. 非线性规划的形式： $min\ z=f(x)\ s.t.\ g_1(x)\le 0, g_1(x)\le 0,...,g_n(x)\le 0$

Some examples

1. 非线性规划的例子： $f(x)=x_2,and g_1(x)=-x_1^2-x_2=2,g_2(x)=x_2-\frac 3 2,g_3(x)=x_1-\frac 3 2,g_4(x)=-x_1-2$ 这个非线性规划的可行解区域不是凸的，甚至不是连续的

Some nonlinear programs are very hard

NLP versus 0,1 integer programming

1. 非线性最优化问题一般来说是非常困难的
2. 例如对于限制 $x_j^2-x_j\le 0,-x_j^2+x_j\le 0$ ,这个限制定义的可行解区域和 $x_j^2=x_j$ 二次等式相同，为 $\{0,1\}$，这个限制等价于 0，1 整数限制
3. 如果我们再加上 $Ax\le b$， 所以任意的 0，1 线性规划问题都可以被看作NLP
4. 0，1 整数规划是NP-hard，所以非线性规划至少也是NP-hard

Hard small-dimensional instances

1. 费马最后的理论： 不存在整数 $x\ge 0,y\ge 0 ,z\ge 0,n\ge 3$ 使得 $x^n+y^n=z^n$
2. $f(x) = (x_1^{x_4}+x_2^{x_4}+x_3^{x_4})^2+(sin\pi x_1)^2+ (sin\pi x_2)^2 +(sin\pi x_3)^2,g_1(x)=1-x_1,g_2(x)=1-x_2,g_3(x)=1-x_4,g_4(x)=3-x_4,S=\{x\in R^4:x_1\ge 1,x_2\ge 1,x_3\ge 1,x_4\ge 3\}$ 其中$f(x)\ge 0$ ，只有当费马最后的理论是错误的时候f(x)才可能等于0
3. 一些非线性最优化问题是非常困难的，即使其中的变量非常少，或者变量很小，或者非线性规划是有界的