User Tools

Site Tools


keynote:lesson14

第十四课

1.非线性最优化

  • 最优化的问题的一般形式为

Min f(x) s.t. x∈X
f(x) 为目标函数, X∈En 为可行域。

X= En,则以上最优化问题为无约束最优化问题。

  • 约束最优化问题通常写为

Min f(x)
s.t.
ci(x)=0, i∈E,
ci(x)>=0, i∈I,
其中E, I分别为等式约束的指标集和不等式约束的指标集,ci(x)是约束函数。

  • 可行点,可行域
  • 极小,全局极小(总体极小点),全局严格极小,局部极小,局部严格极小
  • 积极与非积极,积极约束,非积极约束
  • 可行方向集,线性可行方向集,序列可行方向集
  • 引理与K-T条件
  • 以上参见《最优化理论与方法》第八章

2.无约束二次最优化

min f(x) = ½ xTHx+cTx, x∈Rn

  • H是对称阵
  • 基本解法:求导然后找局部极值。

3.二次规划的一般形式

min f(x) = ½ xTHx+cTx, x∈Rn
s.t. Ax≤b(1)

  • 当H为对称矩阵时,被称为二次规划(Quadratic Programming,记作QP)。
  • 特别,当H正定时,目标函数为凸函数,线性约束下可行域又是凸集。上式被称为凸二次规划

4.二次规划的性质

  • QP是一种最简单的非线性规划。QP有如下良好的性质,当H是半正定时:
    • K-T条件不仅是最优解的必要条件,而且是充分条件;
    • 局部最优解就是全局最优解。

5.等式约束下的二次规划

min f(x) = ½ xTHx+cTx, x∈Rn
s.t. Ax=b(2)

  • 求解方法:Lagrange乘子法,求解以下无约束二次最优化问题。

L(x,λ) = ½ xTHx+cTx+λT(Ax-b)

L(x,λ)xλ的导数为零,得线性方程组

Hx+cT+ATλ=0

Ax-b=0

可解得x,即为上式的解。

6.二次规划的有效集方法

  • 直观解释:将不起作用约束去掉,将起作用约束作为等式约束,
    通过解一系列等式约束的二次规划来实现不等式约束的优化
  • 基本原理:若x为问题(1)的最优解,则它也是问题

min ½ xTHx+cTx

s.t. aiTx=bi,i∈I

的最优解,其中ai是A的第i行,I为起作用约束指标集(有效集)。

  • 反之,若x为(1)的可行解,又是(3)的K-T点,且相应的乘子λi≥ 0
    x为(1)的最优解。
  • 算法步骤(迭代法):
    • 设当前迭代点为xk,它也是(1)的可行解。该点的有效集记作Ik
      为寻求xk点的迭代方向d,用乘子法求解。

min ½(xk+d)TH(xk+d)+cT(xk+d)

s.t. aiTd=0,i∈Ik

  • 若所得最优值dk=0,则xk是(3)的最优解。
    • 为判断它是否(1)的最优解,考察对应于有效约束的乘子λi≥ 0是否成立。
      若成立,则xk是K-T点,由二次规划性质xk是(1)的最优解。
  • 若最优值dk≠ 0,则取xk+1=xk+αdk,在xk+1为可行点的条件下确定dk方向的步长αk
    • 如果存在p不在Ik中,使得apxk+1=bp,则将p加入有效集。
  • 如果存在Ik中的指标q,使得λi< 0, 则x(k)不是最优解,从有效集中去掉q

王文宏 2010-07-01

朱朝艳 2011-06-19

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