User Tools

Site Tools


keynote:2011-lesson13

第十三课

最优化方法

内容

  • 线性规划
  • 非线性优化

主要参考书:

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

基本理论

问题定义 (Linear Programming,LP)

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

\min\ c_1x_1+…+c_nx_n
s.t.
a_{11}x_1+…+a_{1n}x_n\le b_1
a_{m1}x_1+…+a_{mn}x_n\le b_m
x_1,…,x_n \ge 0
即:
min cTx
s.t. Axb, x≥0
其中,c:价值向量,A:约束矩阵,b:右端向量,x:满足约束条件,称为可行解或可行点

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

线性规划在Matlab中的实现方法
Matlab中规定线性规划的标准形式为:
min cTx s.t. Axb
其中,cx为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是控制参数。

李昌英 学号:11021081 2011/06/08

标准LP问题

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

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

标准LP问题形式:
min z=cTx
s.t. Ax=b, x0
将LP问题标准化: 目标函数的转换 \max\ z→\min\ (-z)
约束条件的转换(引入松弛变量)

\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
变量的非负约束:
x_j\ge l_j ⇔ y_j\ge0, y_j=x_j-l_j
x_j自由变量 ⇔u_j\ge0, v_j\ge0, x_j=u_j-v_j

李昌英 学号:11021081 2011/06/08

可行区域

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

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

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

  • 仿射集:对于集合S⊆En,如果对任意x, y∈S, λ∈E1, 都有λx+(1-λ)y∈S,则称S为仿射集。

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

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

李昌英 学号:11021081 2011/06/09

桂立业 学号:11024012 2011/06/20

刘雨 学号:10924010 2011/06/21

基本可行解

  • 基本解:

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

AX=Bx_B+Nx_N=b

因为B为满秩,则B-1存在,那么
x_B=B^{-1}b-B^{-1}Nx_N

任给一组值x_N,则可得到相应的x_B,
(x_B, x_N)
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问题,如果它的所有基本可行解都是非退化,就说该问题是非退化的,否则为退化的。

李昌英 学号:11021081 2011/06/09

郑建靖 学号:11024013 2011/06/20

桂立业 学号:11024012 2011/06/20

keynote/2011-lesson13.txt · Last modified: 2014/05/22 08:34 (external edit)