2018-04-18 白痴学数学系列 - 线性编程 Simple

#Lecture 9: Linear Programming and ALM: Cash-Flow Matching

两种解决办法，其中一种叫Simplex

1. 首先，Simplex的中文是单纯形法

• Linear Programming Theory

  • Formulation
  • Duality
  • Solution Methods
    • Simplex Method
    • Primal-Dual Interior-Point Method

• LP: Asset Liability Manamgement: Cash-Flow Matching

  • Basic setup
  • Example
  • Nonlinear scenario
  • Stochastic liabilities

Formulation

其中A为一个m*n矩阵

若A行满秩

则可以找到基矩阵B，并寻找初始基解。

描述线性规划问题的常用和最直观形式是标准型。标准型包括以下三个部分：

一个需要极大化的线性函数，例如
{\displaystyle c_{1}x_{1}+c_{2}x_{2}}

c_1 x_1 + c_2 x_2

以下形式的问题约束，例如：
{\displaystyle a_{11}x_{1}+a_{12}x_{2}\leq b_{1}} a_{11} x_1 + a_{12} x_2 \le b_1
{\displaystyle a_{21}x_{1}+a_{22}x_{2}\leq b_{2}} a_{21} x_1 + a_{22} x_2 \le b_2
{\displaystyle a_{31}x_{1}+a_{32}x_{2}\leq b_{3}} a_{31} x_1 + a_{32} x_2 \le b_3
和非负变量，例如：
{\displaystyle x_{1}\geq 0} x_1 \ge 0
{\displaystyle x_{2}\geq 0} x_2 \ge 0

• Simpler than any other optimization problem

• With plenty of application (even in Finance)

• Serve as a good starting point

Duality

对偶规划问题

• 对偶规划中：y 为人任意值
• 假设 B 是 (P) 的一个可行基，对应的可行解 x_B

Solution Methods

• Simplex (Dantzig 1947)

• Ellipsoid (Kachian 1979, the first algorithm known to be in polynomial time)

• Interior Point (Karmakar 1984, the first practical polynomial time algorithm)

  • Projection method (Karmakar 1984)
  • Affine Method (Dikin 1967)
  • Log-Barrier Method (many ...)

• Interior Point method has been extended to NLP problems, has been the focus of research for optimization in the last few decades.

• Although asymptotically superior, there is no clear winner between Simplex and Interior Point for LP problems: very much depends on the problem

Algorithm (Simplex Method)

相关链接：
Wiki - 线性规划

Wiki - 单纯形法

内点法介绍（Interior Point Method）