Differences

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>

Applied Mathematics for Computer Science

User Tools

Site Tools

Differences

Page Tools