t补充：Von-Neumann Minimax Theorem Von-Neumann Minimax Theorem. 器盟xAy=热盟器xAy 证明(cont'd):把它们都转化为标准形式 max t min r m n t- xa≤0j=1,…,n ×yj aiyy≥0 i=1,…,m ×xi m x:=1 Xr yi=1 ×t i=1 x:≥0 i=1,,m y≥0 i=1,.,n Equality follows directly from strong duality! 2
补充：Von-Neumann Minimax Theorem Von-Neumann Minimax Theorem. max !∈#! min $∈#" �%�� = min $∈#" max !∈#! �%�� 证明(cont’d)：把它们都转化为标准形式 2 min � � − - &'( ) �*& �& ≥ 0 ∀� = 1, … , � - *'( ) �* = 1 �* ≥ 0 ∀� = 1, … , � max � � − - *'( + �*�*& ≤ 0 ∀� = 1, … , � - *'( + �* = 1 �* ≥ 0 ∀� = 1, … , � × � × �& × � × �* Equality follows directly from strong duality!
Strong duality theorem 强对偶性：假设primal和dual LP都存在可行解，则它们的最优解 相等 证明方法很多，其中包括分析单纯形算法的 这节课：通过凸优化分析(Farkas lemma)给出证明 参考资料： Understanding and Using Linear Programming Understanding By Jiri Matousek,Bernd Gartner and Using Linear Programming
Strong duality theorem 强对偶性：假设primal和dual LP都存在可行解, 则它们的最优解 相等 证明方法很多, 其中包括分析单纯形算法的 这节课：通过凸优化分析(Farkas lemma)给出证明 参考资料: Understanding and Using Linear Programming By Jiří Matoušek , Bernd Gärtner 3
Separation theorem 凸几何的性质：Separation theorem 定义：一个集合S,,如果对Vx,y∈S,a∈[0,1]都有x+ (1-)y∈S,则称S为凸集(convex set) 定义：如果S中的所有的点列的极限点都在S中，则称集合S 为闭集(closed set) 给定一个闭的凸集S二Rn,和集合外的点v度S。 w∈Rn使得w,v〉>w,x〉对任意xES成立 4
Separation theorem 凸几何的性质：Separation theorem 定义：一个集合�，如果对∀�, � ∈ �, ∀� ∈ [0,1]都有�� + 1 − � � ∈ �，则称�为凸集(convex set) 定义：如果�中的所有的点列的极限点都在�中, 则称集合� 为闭集(closed set) 给定一个闭的凸集� ⊆ ℝ! ，和集合外的点� ∉ �。 ∃� ∈ ℝ! 使得 �, � > �, � 对任意� ∈ �成立 4
Separation theorem 给定一个闭的凸集S∈Rn,和集合外的点vS。 w∈R”使得w,v)>(w,x)对任意x∈S成立 证明(sketch:找到唯一的x,∈S,使得与v最接近 1. 存在性：由于S是闭集，由Weierstrass定理，可知其最接近v的点可以在s中取到 2. 唯一性：假设有两个点，考虑它们的中点，只会与v更加接近 3. x,为最接近的点当且仅当x∈S,(x一x,v-x)≤0 考虑y=(1-t)x+tx∈S,则 ly-v陉=x-v-t(x幸-x)匠 =lv-x,陉-2t(x-x,v-x〉+t2‖x-x匠 x为最接近的点台一2t(x-x,v-x)+t2‖x-x陉≥0，x,t>0 台lx-x3≥(x-x,v-x,x,t>0 台0≥(x-x,v-x*),x 令w=v-x,由v-x3>0可知（巴，v-x〉>(x,v-x),进而(，w)>(x,w） 另一方面，前面已经证明x∈S,(x一x,v-x)≤0 这意味着(x,D-x〉≤(x,D-x,即(x,w〉≤(x,w),因此（巴，w〉>(x,w〉≥(x,w）,x∈S
Separation theorem 给定一个闭的凸集� ⊆ ℝ# ，和集合外的点� ∉ �。 ∃� ∈ ℝ# 使得 �, � > �, � 对任意� ∈ �成立 证明(sketch)：找到唯一的�∗ ∈ �，使得与�最接近 1. 存在性：由于�是闭集，由Weierstrass定理，可知其最接近�的点可以在�中取到 2. 唯一性：假设有两个点，考虑它们的中点，只会与�更加接近 3. �∗为最接近的点当且仅当∀� ∈ �, � − �∗, � − �∗ ≤ 0 考虑� ≔ 1 − � �∗ + � � ∈ �，则 � − � % % = �∗ − � − �(�∗ − �) % % = � − �∗ % % − 2� � − �∗, � − �∗ + �% � − �∗ % % �∗为最接近的点⟺ −2� � − �∗, � − �∗ + �% � − �∗ % % ≥ 0, ∀�,� > 0 ⟺ & % � − �∗ % % ≥ � − �∗, � − �∗ , ∀�,� > 0 ⟺ 0 ≥ � − �∗, � − �∗ , ∀� 令 � = � − �∗，由 � − �∗ % % > 0可知 �, � − �∗ > �∗, � − �∗ ，进而 �, � > �∗, � 另一方面，前面已经证明∀� ∈ �, � − �∗, � − �∗ ≤ 0 这意味着 �, � − �∗ ≤ �∗, � − �∗ ，即 �, � ≤ �∗, � ，因此 �, � > �∗, � ≥ �, � , ∀� ∈ �
Farkas Lemma Ax=b,x≥0无解当且仅当存在y使得yTA≥0且yTb)考虑S={Ax:x≥0.S是闭的凸集.无解意味着bES. 由Separation theorem,存在w∈Rn使得(w,b〉>(w,s〉对任意s∈S 成立。令y=-w,则有yTb<yTAx,x≥0 由于0∈S,因此yTb<0 另一方面，yTA≥0，否则可以找到x≥0使得yTAx=-o,与 yTb<yAx矛盾 6
Farkas Lemma �� = �, � ≥ 0无解当且仅当存在 � 使得�)考虑 S = ��: � ≥ 0 . �是闭的凸集. 无解意味着� ∉ �. 由Separation theorem，存在� ∈ ℝ= 使得 �, � > �, � 对任意� ∈ � 成立。令� = −�，则有 �<� < �<��, ∀� ≥ 0 由于 0 ∈ �，因此�<� < 0 另一方面，�<� ≥ 0，否则可以找到� ≥ 0使得 �<�� = −∞，与 �<� < �<��矛盾 6
Strong LP duality 假设primal和dual LP都存在可行解，则它们的最优解相等 证明： max(c,x）) min (b,y) Ax=b yTA≥c x≥0. 只需要证明，如果primall的objective小于t,则dual objective也小于t “primal objective小于t”本身可以表示成LP (c,x〉-s=t Ax=b [41)= x≥0，s≥0 x≥0，s≥0 这个x和s的方程组有解当且仅当“primal objective大于等于t” 这个x和s的方程组无解当且仅当“primal objective小于t” 7
Strong LP duality 假设primal和dual LP都存在可行解, 则它们的最优解相等 证明： 只需要证明，如果primal的objective小于�，则dual objective也小于� “primal objective小于�”本身可以表示成LP �, � − � = � �� = � � ≥ 0, � ≥ 0 这个�和�的方程组有解当且仅当“primal objective大于等于�” 这个�和�的方程组无解当且仅当“primal objective小于�” 7 max �, � �� = � � ≥ 0. min �, � �<� ≥ � � 0 �< −1 � � = � � � ≥ 0, � ≥ 0
Strong LP duality 假设primal和dual LP都存在可行解，则它们的最优解相等 证明(cont'd):由Farkas lemma [41)=8) 无解当且仅当存在y,z使得 x≥0，s≥0 r)()<0 即yTA+zcT≥0，-z≥0，yTb+zt<0 考虑z=0,则有yTA≥0，yTb<0,primal not feasible; 考虑z≠0则有y”A≥c,是之yrb<t,因此号zy为dual LP中的可行解，且目标函数值<t。 8
Strong LP duality 假设primal和dual LP都存在可行解, 则它们的最优解相等 证明(cont’d)：由Farkas lemma 即�"� + ��" ≥ 0, −� ≥ 0, �"� + �� < 0 考虑� = 0，则有�!� ≥ 0, �!� < 0，primal not feasible; 考虑� ≠ 0，则有 " #$ �!� ≥ �! , # $% �!� < �，因此 - ./ �"为dual LP中的可行解，且目标函数值< �。 8 � 0 �< −1 � � = � � � ≥ 0, � ≥ 0 无解当且仅当存在 �, � 使得 �< � � 0 �< −1 ≥ 0 �! � � � < 0
课程回顾 核心思想： 收敛性： 能合理近似的算法，至少需要收敛 。 复杂性：计算复杂性 ·条件性（鲁棒性） 一回顾条件数的定义 压缩性 -SVD 正交性 一正交多项式 一共轭 15
课程回顾 核心思想： • 收敛性：能合理近似的算法，至少需要收敛 • 复杂性：计算复杂性 • 条件性 (鲁棒性) – 回顾条件数的定义 • 压缩性 – SVD • 正交性 – 正交多项式 – 共轭 15
课程回顾 课程话题 插值与拟合 一方程求根：二分法，不动点迭代法，牛顿法 一拉格朗日插值：误差分析 - Chebyshev插值 -Chebyshev多项式：极值性质 一函数空间上的线性代数、不同的范数及比较 一最小二乘法：几何推导、微积分推导 -正交化过程：Gram-Schmidt 一正交系统中的最小二乘法：三角级数、函数逼近 一傅里叶变换：多项式的两种表示，正交性与FFT算法 ·特征值与随机游走（线性代数方法) 。 最优化与线性规划 16
课程回顾 课程话题 • 插值与拟合 – 方程求根：二分法, 不动点迭代法，牛顿法 – 拉格朗日插值：误差分析 – Chebyshev插值 – Chebyshev多项式：极值性质 – 函数空间上的线性代数、不同的范数及比较 – 最小二乘法：几何推导、微积分推导 – 正交化过程：Gram-Schmidt – 正交系统中的最小二乘法：三角级数、函数逼近 – 傅里叶变换：多项式的两种表示，正交性与FFT算法 • 特征值与随机游走（线性代数方法） • 最优化与线性规划 16
课程回顾 课程话题 ·插值与拟合 特征值与随机游走（线性代数方法) 一求解线性方程组—一一种特殊的方程求根问题 -解决线性方程组的通用方法一高斯消元法：pivoting - 矩阵的算子范数：作为线性映射对长度的改变 - 线性方程组的条件数（比较：根的敏感性） 解决线性方程组的选代方法：Jacobi,Gauss--Seidel,Richardson,Conjugate- gradient 分析线性迭代方程：谱半径 - 特征值的min-max刻画(Courant-Fischer) 一矩阵的多项式：线性迭代方程，Cayley-Hami Iton,.逆矩阵的多项式，幂迭代 - 计算特征值与特征向量、Singular value decomposition(SVD) ·最优化与线性规划 17
课程回顾 课程话题 • 插值与拟合 • 特征值与随机游走（线性代数方法） – 求解线性方程组——一种特殊的方程求根问题 – 解决线性方程组的通用方法—高斯消元法：pivoting – 矩阵的算子范数：作为线性映射对长度的改变 – 线性方程组的条件数（比较：根的敏感性） – 解决线性方程组的迭代方法：Jacobi，Gauss-Seidel，Richardson，Conjugate- gradient – 分析线性迭代方程：谱半径 – 特征值的min-max刻画 (Courant-Fischer) – 矩阵的多项式：线性迭代方程，Cayley-Hamilton，逆矩阵的多项式，幂迭代 – 计算特征值与特征向量、Singular value decomposition (SVD) – … • 最优化与线性规划 17