数学规划

Convex Analysis

Euclidean Space

• Plane and Half-Spaces

• Polyhedron
有限个闭半空间的交，称为多面体

• Line and Convex Combination
是 中两个不同的点，
则 是 决定的线
当 ，称作 的凸组合，是 之间的线段

• Face of a Polyhedron

• Extreme Point of a Polyhedron
是顶点当 不是任何多于一个不同点的凸组合

Convex Set, Separating Hyperplane Theorems

• Convex Set
都有

• Convex Hull
集合 的凸包是包含 的最小凸集

• 或 的解空间都是凸集
多面体都是闭凸集
是凸集，则 是顶点当且仅当

• Caratheodory’s Theorem
令 且 ，则存在最多 个 中的点使得 能够表示成这几个个点的凸组合，即，存在 使得
其中，convex hull of 为

• Convex Cones
是一个cone如果 有
convex cone即是一个cone又是convex set

• Dual Cone and Polar
• Dual Cone
• Self-Dual cone
• Polar

• Second-order cone

• 一个锥 是一个多面体，若 能表示成
一个集合是polyhedral当且仅当它有有限多个extreme points

• Theorem
，凸多面体锥 ，则 有
其中 是从 选择的线性无关的向量

• 是闭集

• Separating Hyperplane

• Proper separation

• Strictly seperated

• Strongly seperated

• Theorem (Separating hyperplane theorem)
为闭凸集，令 ，则存在向量 使得 ，其中 为超平面的法向量

• 为 中的非空锥，则 的极锥的极锥是 当且仅当 是闭且凸的

• Interior and Boundary

• Theorem
是凸集，则 和 都为凸集。若 ，则 和

• Theorem
是凸集，则存在超平面 包含 当且仅当

• Theorem
令 为凸集，则
1. 若 ，则
2. ，

• Theorem
令 为非空凸集， ，则存在向量 使得

• Supporting Hyperplane 支撑超平面
一个超平面，凸集 完全包含在由超平面界定的两个闭半空间之一中且 在超平面上至少有一个边界点，则该超平面称为 的支撑超平面

• Theorem
为凸集， 为 的支撑超平面， ，则 的每一个顶点都是 的顶点
• Corollary
为非空凸集， 。则存在向量 使得
• Corollary
为非空凸集， 。则存在向量 使得

• Theorem (Separating Hyperplane Theorems for Two Convex Sets)
若 为 的两个非空闭凸子集，且 ， 有界，则存在向量 和 使得

• Theorem (Separating Hyperplane Theorems for Two Convex Sets)
若 为 的两个非空凸子集，且 则存在向量 和实数 使得

Convex Function

• Real Functions
• Continuous functions
• The gradient vector
• The Hessian matrix
• Weierstrass theorem
• least upper bound or supremum
• greatest lower bound or infimum
• Vector function
• The Jacobian matrix

• Convex Function
是凸函数当且仅当 ，
如果当 是不等式严格成立，则 是strictly convex

• Level set
的level set为 ，是凸集（相反。。。）

• Theorem (Jensen’s Inequality)
若 凸函数，则 成立，对于任意 满足

• Known Inequalities
• Arithmetic-geometric mean
• Cauchy-Schwarz
• Harmonic

• Theorem
定义在包含线段 的区域，则存在 使得
若 ，则存在 使得

• Theorem
当 开集， ， 可微，则 as
若 ，则 as

• Theorem
，则 在凸集 上为凸函数当且仅当gradient inequality成立，即

• Theorem
，则 在含有内点的凸集 上为凸函数当且仅当 的Hessian矩阵在 上是半正定的

• Epigraph 上方图
为实值函数， 的epigraph定义为
令 为非空凸集，则 是凸函数当且仅当它的epigraph 是凸集

• Theorem (Maximization of Convex Functions)
是定义在有界闭凸集 上的凸函数。如果 在 上有最大值，则在 的顶点处达到

Basic Properties of Linear Programming

• Linear Programming

• Definition
LP（minimize）被称作是bounded，如果存在常数 使得 ，其中 是LP的可行域

• LP Problem可分为三类
• infeasible
• unbounded
• feasible and bounded：存在一个最优解，最优解在可行域的边界上，至少有一个最优的顶点解或最优的无限远点

• Linear Programming Standard Form
其中 ， 有满秩

• Theorem (LP Fundamental Theorem)
给定LP问题，其中 有满行秩
1. 如果存在可行解，则存在基可行解
2. 如果存在最优解，则存在基最优解

Duality Theory of Linear Programming

• Dual of Linear Programming
primal problem
dual problem

• Rules to construct the dual

• Theorem (Weak duality theorem)
LP和LD的可行域 和 均非空，则
• Corollary
若 分别是LP和LD的可行解，且 ，则 分别都是问题的最优解

• Theorem (Strong duality theorem)
非空，则 是LP的最优解当今仅当如下条件满足
2. 有

• Theorem

• Definition
LP的一个基可行解 ，相应的基为 ，则对于基 对偶向量 满足 称为相应的对偶基解

• Theorem
LP有关于基 的最优可行解，则向量 满足 为LD的最优解如果它是对偶可行解。两个问题的最优值相等

• Shadow Price

• Sensitivity on Right-Hand-Side Vector
固定矩阵 和 ，则最优值是关于 的函数

• Theorem
最优值函数 关于 是凸函数，且对偶最优解 是这个函数在 处的sub-gradient，即

• Sensitivity on Objective Coefficient Vector
固定 和 ，则最优值是关于 的函数

• Theorem
最优值函数 关于 是凹函数

• Complementarity Slackness

• Strict complementarity theorem

The Simplex Method