最优化方法

• 线性规划
• 非线性优化

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

在一组线性的等式或不等式约束下，求一个线性函数的最小值或最大值。
形式化的定义：

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

线性规划在Matlab中的实现方法
Matlab中规定线性规划的标准形式为:
min c^Tx s.t. Ax≤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是控制参数。

从实际中总结出来的LP形式不完全一样：

• 目标函数是最大值或最小值，
• 约束条件是等式约束或不等式约束，
• 变量有上界或下界或无界

标准LP问题形式：
min z=c^Tx
s.t. Ax=b, x≥0
将LP问题标准化： 目标函数的转换 \max\ z→\min\ (-z)
约束条件的转换（引入松弛变量）

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

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

首先讨论集合 K={ x | Ax = b }

• 仿射集：对于集合S⊆Eⁿ，如果对任意x, y∈S, λ∈E¹, 都有λx+(1-λ)y∈S,则称S为仿射集。

一般仿射集的特征：给定 mxn 实矩阵 A 和 b∈E^m，则 K={x∈Eⁿ | Ax=b} 为 Eⁿ 中的仿射集，并且Eⁿ中的任一仿射集均可表成此种形式。
集合 K={ x | Ax = b }为 Eⁿ 仿射集。

• 凸集：对任意的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）。

• 基本解：

假定rank(A)=m，则A中必有m个线性无关的列向量——构成满秩方阵B，A中其余各列组成子阵N,即A=(B, N)。相应的x=(x_B, x_N)，则Ax=b可改写成

• 基本可行解：
  • 设 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问题，如果它的所有基本可行解都是非退化，就说该问题是非退化的，否则为退化的。