This shows you the differences between two versions of the page.
keynote:lesson14 [2014/05/22 16:34] |
keynote:lesson14 [2023/08/19 21:02] (current) |
||
---|---|---|---|
Line 1: | Line 1: | ||
+ | ====== 第十四课 ====== | ||
+ | |||
+ | **1.非线性最优化** | ||
+ | |||
+ | |||
+ | * 最优化的问题的一般形式为 | ||
+ | | ||
+ | Min <jsm>f(x)</jsm> s.t. <jsm> x∈X</jsm>\\ | ||
+ | <jsm>f(x) </jsm>为目标函数, <jsm>X∈E</jsm><sup>n</sup> 为可行域。\\ | ||
+ | |||
+ | 如 <jsm>X= E</jsm><sup>n</sup>,则以上最优化问题为无约束最优化问题。 | ||
+ | * 约束最优化问题通常写为\\ | ||
+ | |||
+ | Min <jsm>f(x)</jsm>\\ | ||
+ | s.t. \\ | ||
+ | <jsm>c</jsm><sub>i</sub><jsm>(x)=0</jsm>, <jsm>i∈E</jsm>,\\ | ||
+ | <jsm>c</jsm><sub>i</sub><jsm>(x)>=0</jsm>, <jsm>i∈I</jsm>,\\ | ||
+ | 其中$E$, $I$分别为等式约束的指标集和不等式约束的指标集,$c$<sub>i</sub>$(x)$是约束函数。 | ||
+ | * 可行点,可行域 | ||
+ | * 极小,全局极小(总体极小点),全局严格极小,局部极小,局部严格极小 | ||
+ | * 积极与非积极,积极约束,非积极约束 | ||
+ | * 可行方向集,线性可行方向集,序列可行方向集 | ||
+ | * 引理与K-T条件 | ||
+ | * 以上参见《最优化理论与方法》第八章 | ||
+ | |||
+ | **2.无约束二次最优化** | ||
+ | |||
+ | min $f(x) = ½ x$<sup>T</sup>$Hx+c$<sup>T</sup>$x$, $x∈R$<sup>n</sup> | ||
+ | |||
+ | * H是对称阵\\ | ||
+ | * 基本解法:求导然后找局部极值。 | ||
+ | |||
+ | **3.二次规划的一般形式** | ||
+ | |||
+ | min $f(x) = ½ x$<sup>T</sup>$Hx+c$<sup>T</sup>$x$, $x∈R$<sup>n</sup>\\ | ||
+ | s.t. $Ax≤b(1)$ | ||
+ | |||
+ | * 当H为对称矩阵时,被称为//**二次规划**//(Quadratic Programming,记作QP)。 | ||
+ | * 特别,当H//**正定**//时,目标函数为凸函数,线性约束下可行域又是凸集。上式被称为//**凸二次规划**//。 | ||
+ | |||
+ | **4.二次规划的性质** | ||
+ | |||
+ | * QP是一种最简单的非线性规划。QP有如下良好的性质,当H是半正定时: | ||
+ | * K-T条件不仅是最优解的必要条件,而且是充分条件; | ||
+ | * 局部最优解就是全局最优解。 | ||
+ | |||
+ | **5.等式约束下的二次规划** | ||
+ | |||
+ | min $f(x) = ½ x$<sup>T</sup>$Hx+c$<sup>T</sup>$x$, $x∈R$<sup>n</sup>\\ | ||
+ | s.t. $Ax=b(2)$ | ||
+ | |||
+ | * 求解方法:Lagrange乘子法,求解以下无约束二次最优化问题。 | ||
+ | |||
+ | $L(x,λ) = ½ x$<sup>T</sup>$Hx+c$<sup>T</sup>$x+λ$<sup>T</sup>$(Ax-b)$ | ||
+ | |||
+ | 令$L(x,λ)$对$x$和$λ$的导数为零,得线性方程组 | ||
+ | |||
+ | $Hx+c$<sup>T</sup>$+A$<sup>T</sup>$λ=0$ | ||
+ | |||
+ | $Ax-b=0$ | ||
+ | |||
+ | 可解得x,即为上式的解。 | ||
+ | |||
+ | **6.二次规划的有效集方法** | ||
+ | |||
+ | * 直观解释:将不起作用约束去掉,将起作用约束作为等式约束,\\ 通过解一系列等式约束的二次规划来实现不等式约束的优化 | ||
+ | * 基本原理:若x为问题(1)的最优解,则它也是问题 | ||
+ | |||
+ | |||
+ | min $½ x$<sup>T</sup>$Hx+c$<sup>T</sup>$x$ | ||
+ | |||
+ | s.t. $a$<sub>i</sub><sup>T</sup>$x=b$<sub>i</sub>,$i∈I$ | ||
+ | |||
+ | 的最优解,其中$a$<sub>i</sub>是A的第$i$行,$I$为起作用约束指标集(有效集)。 | ||
+ | |||
+ | * 反之,若$x$为(1)的可行解,又是(3)的K-T点,且相应的乘子$λ$<sub>i</sub>$≥ 0$,\\ 则$x$为(1)的最优解。 | ||
+ | |||
+ | * **算法步骤(迭代法):** | ||
+ | *设当前迭代点为$x$<sub>k</sub>,它也是(1)的可行解。该点的有效集记作$I$<sub>k</sub>,\\ 为寻求$x$<sub>k</sub>点的迭代方向$d$,用乘子法求解。 | ||
+ | min $½(x$<sub>k</sub>$+d)$<sup>T</sup>$H(x$<sub>k</sub>$+d)+c$<sup>T</sup>$(x$<sub>k</sub>$+d)$\\ | ||
+ | |||
+ | s.t. $a$<sub>i</sub><sup>T</sup>$d=0$,$i∈I$<sub>k</sub> | ||
+ | * 若所得最优值$d$<sub>k</sub>$=0$,则$x$<sub>k</sub>是(3)的最优解。 | ||
+ | * 为判断它是否(1)的最优解,考察对应于有效约束的乘子$λ$<sub>i</sub>$≥ 0$是否成立。\\ 若成立,则$x$<sub>k</sub>是K-T点,由二次规划性质$x$<sub>k</sub>是(1)的最优解。 | ||
+ | * 若最优值$d$<sub>k</sub>$≠ 0$,则取$x$<sub>k</sub>$+1=x$<sub>k</sub>$+αd$<sub>k</sub>,在$x$<sub>k</sub>$+1$为可行点的条件下确定$d$<sub>k</sub>方向的步长$α$<sub>k</sub>。 | ||
+ | * 如果存在$p$不在$I$<sub>k</sub>中,使得$a$<sub>p</sub>$x$<sub>k</sub>$+1=b$<sub>p</sub>,则将$p$加入有效集。 | ||
+ | * 如果存在$I$<sub>k</sub>中的指标$q$,使得$λ$<sub>i</sub>$< 0$, 则$x(k)$不是最优解,从有效集中去掉$q$。 | ||
+ | |||
+ | <note important>王文宏 2010-07-01</note> | ||
+ | |||
+ | <note important>朱朝艳 2011-06-19</note> | ||