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 21 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 21