====== 第十三课 ======
**最优化方法**
====== 内容 ======

  * 线性规划
  * 非线性优化
====== 主要参考书： ======

  * 线性规划，张建中，许绍吉，科学出版社
  * 最优化理论与方法，袁亚湘，孙文瑜，科学出版社
====== 基本理论 ======

===== 问题定义  (Linear Programming,LP)=====
在一组线性的等式或不等式约束下，求一个线性函数的最小值或最大值。\\
**形式化的定义：**\\
<jsmath>\min\ c_1x_1+...+c_nx_n </jsmath>
 s.t.
<jsmath>a_{11}x_1+...+a_{1n}x_n\le b_1</jsmath>
<jsmath>...</jsmath>
<jsmath>a_{m1}x_1+...+a_{mn}x_n\le b_m</jsmath>
<jsmath>x_1,...,x_n \ge 0</jsmath>
即：\\
min **c<sup>T</sup>x**\\
s.t. A**x**≤**b**, **x**≥0\\
其中，**c：**价值向量，**A：**约束矩阵，**b：**右端向量，**x：**满足约束条件，称为可行解或可行点\\

**LP问题：**\\
D：所有可行点的集合，称为可行区域\\
D=∅，无解或不可行\\
D≠∅，但目标函数在D上无上界：无界\\
D≠∅，且目标函数有限的最优解：有最优解\\

**线性规划在Matlab中的实现方法**\\
Matlab中规定线性规划的标准形式为:\\
min **c<sup>T</sup>x** s.t. A**x**≤**b**\\
其中，**c**和**x**为n维列向量，**b**为m维列向量，**A**为m*n矩阵\\
基本函数形式为:\\
linprog(c, A, b)\\
返回值是向量x的值\\
调用举例：\\
[x,fval]=linprog(c, A, b, Aeq, beq, LB, UB, X0, OPTIONS)\\
 fval返回目标函数的值，\\
 Aeq、beq对应等式约束，AeqX = beq\\
 LB、UB分别是变量X的下界和上界，X0是X的初始值\\
 OPTIONS是控制参数。\\


<note important> --- //[[1@1|李昌英]]  学号：11021081 2011/06/08//</note>
===== 标准LP问题 =====
从实际中总结出来的LP形式不完全一样：\\
  * 目标函数是最大值或最小值，
  * 约束条件是等式约束或不等式约束，
  * 变量有上界或下界或无界
标准LP问题形式：\\
min z=**c<sup>T</sup>x**\\
s.t. A**x**=**b**, **x**≥**0**\\
将LP问题标准化：
目标函数的转换 $\max\ z->\min\ (-z)$\\
约束条件的转换（引入松弛变量）
<jsmath>\sum_{j=1}^{n}{a_{ij}x_j\le b_{i}}
<=>
\sum_{j=1}^{n}{a_{ij}x_j+x_{n+i}}=b_i,    x_{n+i}\ge 0</jsmath>
变量的非负约束：
<jsmath>x_j\ge l_j
<=>
y_j\ge0, y_j=x_j-l_j</jsmath>
<jsmath>x_j自由变量
<=>u_j\ge0, v_j\ge0, x_j=u_j-v_j</jsmath>


<note important> --- //[[1@1|李昌英]]  学号：11021081 2011/06/08//</note>
====== 可行区域 ======

**定义：** 可行区域是所有满足约束条件的可行点的集合，记为D

D={x| Ax=b, x≥0}\\

首先讨论集合 K={ x | Ax = b }\\
  * **仿射集**：对于集合S⊆E<sup>n</sup>，如果对任意x, y∈S, λ∈E<sup>1</sup>, 都有λx+(1-λ)y∈S,则称S为仿射集。
一般仿射集的特征：给定 mxn 实矩阵 A 和 b∈E<sup>m</sup>，则 K={x∈E<sup>n</sup> | Ax=b} 为 E<sup>n</sup> 中的仿射集，并且E<sup>n</sup>中的任一仿射集均可表成此种形式。\\
集合 K={ x | Ax = b }为 E<sup>n</sup> 仿射集。\\
  * **凸集**：对任意的x, y∈C,λ∈(0,1)，有  λx＋(1-λ)y∈C，则C为凸集。
可行区域 D={x|Ax=b,x≥0}为凸集。\\
  * **界面**：可行区域D的子集D’为D的一个界面当且仅当存在指标集合Q⊆{1,…,n},使得D’={x|Ax=b,x≥0,且xj=0当j∈Q}
               若dim(D)= n-m, D’为D的界面，且dim(D’)=n-m-k，则|Q|≥k.
  * **极点**：凸集C的1维界面称为边（edge）, 0维界面称为极点(extreme point)。若两个极点在同一条边上，称它们是相邻的。
  * **极方向**：设C≠Ø为En中的一个凸集，d∈En,d≠0。若对任一x∈C及λ>0，均有x+λd∈C，则称d为C的一个方向。
                 如果一个方向d不能表成两个方向的正线性组合，就成d是C的极方向（extreme direction）。


<note important> --- //[[1@1|李昌英]]  学号：11021081 2011/06/09//</note>

<note important> --- //[[1@1|桂立业]]  学号：11024012 2011/06/20//</note>

<note important> --- //[[1@1|刘雨]]  学号：10924010 2011/06/21//</note>

====== 基本可行解 ======

  * **基本解：**
假定$rank(A)=m$，则A中必有m个线性无关的列向量——构成满秩方阵B，A中其余各列组成子阵N,即$A=(B, N)$。相应的$x=(x_B, x_N)$，则$Ax=b$可改写成 <jsmath>AX=Bx_B+Nx_N=b</jsmath>\\
因为B为满秩，则B<sup>-1</sup>存在，那么 <jsmath>x_B=B^{-1}b-B^{-1}Nx_N</jsmath>\\
任给一组值$x_N$,则可得到相应的$x_B$,\\ 
<jsmath>(x_B, x_N)</jsmath>
 为$Ax=b$的一个解。\\
 令$x_N=0$, 则$x_B=B^{-1}b$, $x=(B^{-1}b,0)$称为约束方程组的**基本解**。

  * **基本可行解：**
    * 设 $rank(A)=m$
      * A中m个线性无关的列向量构成满秩方阵B
      * A中其余各列组成子阵N
      * A=(B, N)
    * $x=(x_B, x_N)$
      * $Ax=b$ 可改写成 $Bx_B + Nx_N =b$
B称为**基**，B中的m个线性无关的列向量称为**基向量**，$x_B$的m个分量称为**基变量**，其余的变量称为**非基变量**。\\
基本解不一定满足非负条件，故不一定是可行解。对于非负的基本解，称为**基本可行解**，此时B称为**可行基**。

  * 退化：

 基本可行解x，若它所有的基变量都取正值，则x为非退化的(non-degenerated); 反之，为退化的。\\
一个可行基对应一个基本可行解；反之，若一个基本可行解是非退化的，则它也对应着唯一的可行基。\\
若一个基本可行解是退化的，则它可以由不止一个可行基得到。\\
 对应一个LP问题，如果它的所有基本可行解都是非退化，就说该问题是非退化的，否则为退化的。\\
 


<note important> --- //[[1@1|李昌英]]  学号：11021081 2011/06/09//</note>

<note important> --- //[[1@1|郑建靖]]  学号：11024013 2011/06/20//</note>

<note important> --- //[[1@1|桂立业]]  学号：11024012 2011/06/20//</note>