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的扰动 顶点的个数：一般情况下面可能是指数级别的，(%) 3LP的顶点 考虑max �, � ，约束在� ≔ {�� ≤ �}这个polytope内 顶点可以有3种定义： 1. 边角(corner): 如果不存在� ≠ 0 使得 � + � ∈ � and � − � ∈ �，则称点�是一个边角 2. 极值点: 如果 ∃� 使得�是该目标方向�的唯一最优解，则称点�是一个极值点. 3. 基本解: 如果 �!, � = �! ，我们称第�个约束是紧致 (tight)的 ，其中 �! 是第�行. 对于给定的� ∈ �, 记 �" 为� 中关于 � 紧致的约束组成的子矩阵. 如果�" 是满秩的, i.e. ���� �" = � ，那么我们称�是一个基本解. 事实上，这3种定义是等价的。 LP的稳定性：对c的扰动，对A的扰动 顶点的个数：一般情况下面可能是指数级别的, # $ 3