回顾 上节课: ·随机游走的碰撞时间(Hitting time)和返程时间 (commute time) ·线性规划LP,顶点的不同定义 这节课: ·对偶性 ·零和游戏 2
回顾 上节课: • 随机游走的碰撞时间(Hitting time)和返程时间 (commute time) • 线性规划 LP,顶点的不同定义 这节课: • 对偶性 • 零和游戏 2
LP的顶点 考虑max(c,x),约束在P={Ax≤b这个polytopel内 顶点可以有3种定义: 1. 边角corner)山:如果不存在y≠0使得x+y∈P and x-y∈P,则称点x是一个边角 2. 极值点:如果c使得x是该目标方向c的唯一最优解,则称点x是一个极值点 3. 基本解:如果(A,x)=b:,我们称第i个约束是紧致(tight)的,其中A:是第行 对于给定的x∈P,记A为A中关于x紧致的约束组成的子矩阵 如果A=是满秩的,i.e.rank(A=)=n,那么我们称x是一个基本解 事实上,这3种定义是等价的。 LP的稳定性:对c的扰动,对A的扰动 顶点的个数:一般情况下面可能是指数级别的,(%) 3
LP的顶点 考虑max �, � ,约束在� ≔ {�� ≤ �}这个polytope内 顶点可以有3种定义: 1. 边角(corner): 如果不存在� ≠ 0 使得 � + � ∈ � and � − � ∈ �,则称点�是一个边角 2. 极值点: 如果 ∃� 使得�是该目标方向�的唯一最优解,则称点�是一个极值点. 3. 基本解: 如果 �!, � = �! ,我们称第�个约束是紧致 (tight)的 ,其中 �! 是第�行. 对于给定的� ∈ �, 记 �" 为� 中关于 � 紧致的约束组成的子矩阵. 如果�" 是满秩的, i.e. ���� �" = � ,那么我们称�是一个基本解. 事实上,这3种定义是等价的。 LP的稳定性:对c的扰动,对A的扰动 顶点的个数:一般情况下面可能是指数级别的, # $ 3
LP的顶点 考虑maxc,x),约束在P={Ax≤b}这个polytope内 1边角corner):如果不存在y≠0使得x+y∈P andx-y∈P,则称点x是一个边角 3基本邂:紧致的约束组成的子矩阵A=是满秩的,i.e.rank(A=)=n 1)→3):或者说是3)→1) 假设存在rank(A=)<n,i.e,y≠0,A-y=0 考虑x+Ey,x-ey,注意到 A-(x+cy)=Ax A=(x-Ey)=A-x 取足够小,使得其它的不等式约束不被违反 则有x+ey∈P,x-ey∈P 4
LP的顶点 考虑max �, � ,约束在� ≔ {�� ≤ �}这个polytope内 1.边角(corner): 如果不存在� ≠ 0 使得 � + � ∈ � and � − � ∈ �,则称点�是一个边角 3.基本解: 紧致的约束组成的子矩阵�! 是满秩的, i.e. ���� �! = � 1) ⇒ 3): 或者说是¬3) ⇒ ¬1) 假设存在 ���� �! < �, �. �., ∃� ≠ 0, �!y = 0 考虑� + ��, � − ��,注意到 �! � + �� = �!� �! � − �� = �!� 取�足够小,使得其它的不等式约束不被违反 则有� + �� ∈ �, � − �� ∈ � 4
LP的顶点 考虑max(c,x),约束在P:={Ax≤b}这个polytoper内 1边角(corner山:如果不存在y≠0使得x+y E P andx-y∈P,则称点x是一个 边角 3.基本解:紧致的约束组成的子矩阵A=是满秩的,i.e.rank(A-)=n 3)→1):或者说是1)→3) 假设有y≠0使得x+yEP,x-y∈P A=(x+y)≤b= AF(x-y)≤b= 其中A=x=b= 因此有A=y≤0,A=y≥0进而A=y=0 5
LP的顶点 考虑max �, � ,约束在� ≔ {�� ≤ �}这个polytope内 1.边角(corner): 如果不存在� ≠ 0 使得 � + � ∈ � and � − � ∈ �,则称点�是一个 边角 3.基本解: 紧致的约束组成的子矩阵�; 是满秩的, i.e. ���� �; = � 3) ⇒ 1): 或者说是¬1) ⇒ ¬3) 假设有� ≠ 0使得� + � ∈ �, � − � ∈ � �; � + � ≤ �; �; � − � ≤ �; 其中 �;� = �; 因此有 �;� ≤ 0, �;� ≥ 0进而 �;� = 0 5
LP的顶点 考虑max(c,x),约束在P:={Ax≤b}这个polytope内 顶点可以有3种等价的定义: 边角corner山:如果不存在y≠0使得x+y∈P and x-y∈P,则称点x是一个边角 2 极值点:如果3c使得x是该目标方向c的唯一最优解,则称点x是一个极值点. 基本蟹:如果(4,x)-b:,我们称第i个约束是紧致ght的,其中A:是第行 对于给定的x∈P,记A为A中关于x紧致的约束组成的子矩阵 如果A=是满秩的,i.e.rank(A=)=n,那么我们称x是一个基本解 Simplex算法:从一个顶点开始:找下一个顶点,如果目标函数更优,则选择移到该顶点:重复: 邻居的选择:最多(m-n)n 如果所有邻居都更差,则当前必定是最优的解:对于凸优化问题,局部最优即是全局最优 最坏情况下面,Simplex算法可能需要指数时间。但是实践中表现往往不错,smoothed analysis 多项式算法:Ellipsoid algorithm,interior point methods 6
LP的顶点 考虑max �, � ,约束在� ≔ {�� ≤ �}这个polytope内 顶点可以有3种等价的定义: 1. 边角(corner): 如果不存在� ≠ 0 使得 � + � ∈ � and � − � ∈ �,则称点�是一个边角 2. 极值点: 如果 ∃� 使得�是该目标方向�的唯一最优解,则称点�是一个极值点. 3. 基本解: 如果 �!, � = �! ,我们称第�个约束是紧致 (tight)的 ,其中 �! 是第�行. 对于给定的� ∈ �, 记 �" 为� 中关于 � 紧致的约束组成的子矩阵. 如果�" 是满秩的, i.e. ���� �" = � ,那么我们称�是一个基本解. Simplex算法:从一个顶点开始;找下一个顶点,如果目标函数更优,则选择移到该顶点;重复; 邻居的选择: 最多(m-n)n 如果所有邻居都更差,则当前必定是最优的解:对于凸优化问题,局部最优即是全局最优 最坏情况下面, Simplex算法可能需要指数时间。但是实践中表现往往不错,smoothed analysis 多项式算法; Ellipsoid algorithm, interior point methods 6