keynote:lesson14
Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
keynote:lesson14 [2010/07/01 19:40] 10921047 |
keynote:lesson14 [2023/08/19 21:02] (current) |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ====== 第十四课 ====== | ====== 第十四课 ====== | ||
| - | **非线性最优化** | + | **1.非线性最优化** |
| + | |||
| * 最优化的问题的一般形式为 | * 最优化的问题的一般形式为 | ||
| | | ||
| Line 7: | Line 9: | ||
| <jsm>f(x) </jsm>为目标函数， <jsm>X∈E</jsm><sup>n</sup> 为可行域。\\ | <jsm>f(x) </jsm>为目标函数， <jsm>X∈E</jsm><sup>n</sup> 为可行域。\\ | ||
| - | 如 <jsm>X= E</jsm><sup>n</sup>，则以上最优化问题为无约束最优化问题。\\ | + | 如 <jsm>X= E</jsm><sup>n</sup>，则以上最优化问题为无约束最优化问题。 |
| - | + | * 约束最优化问题通常写为\\ | |
| - | 约束最优化问题通常写为\\ | + | |
| Min <jsm>f(x)</jsm>\\ | Min <jsm>f(x)</jsm>\\ | ||
| Line 16: | Line 17: | ||
| <jsm>c</jsm><sub>i</sub><jsm>(x)>=0</jsm>, <jsm>i∈I</jsm>,\\ | <jsm>c</jsm><sub>i</sub><jsm>(x)>=0</jsm>, <jsm>i∈I</jsm>,\\ | ||
| 其中$E$, $I$分别为等式约束的指标集和不等式约束的指标集，$c$<sub>i</sub>$(x)$是约束函数。 | 其中$E$, $I$分别为等式约束的指标集和不等式约束的指标集，$c$<sub>i</sub>$(x)$是约束函数。 | ||
| - | * 可行点，可行域 | + | * 可行点，可行域 |
| - | * 极小，全局极小（总体极小点），全局严格极小，局部极小，局部严格极小 | + | * 极小，全局极小（总体极小点），全局严格极小，局部极小，局部严格极小 |
| - | * 积极与非积极，积极约束，非积极约束 | + | * 积极与非积极，积极约束，非积极约束 |
| - | * 可行方向集，线性可行方向集，序列可行方向集 | + | * 可行方向集，线性可行方向集，序列可行方向集 |
| - | * Farkas引理与K-T条件 | + | * 引理与K-T条件 |
| - | * 以上参见《最优化理论与方法》第八章 | + | * 以上参见《最优化理论与方法》第八章 |
| - | **无约束二次最优化** | + | **2.无约束二次最优化** |
| min $f(x) = ½ x$<sup>T</sup>$Hx+c$<sup>T</sup>$x$, $x∈R$<sup>n</sup> | min $f(x) = ½ x$<sup>T</sup>$Hx+c$<sup>T</sup>$x$, $x∈R$<sup>n</sup> | ||
| - | H是对称阵\\ | + | * H是对称阵\\ |
| - | 基本解法：求导然后找局部极值。 | + | * 基本解法：求导然后找局部极值。 |
| - | + | ||
| - | **二次规划的一般形式** | + | **3.二次规划的一般形式** |
| min $f(x) = ½ x$<sup>T</sup>$Hx+c$<sup>T</sup>$x$, $x∈R$<sup>n</sup>\\ | min $f(x) = ½ x$<sup>T</sup>$Hx+c$<sup>T</sup>$x$, $x∈R$<sup>n</sup>\\ | ||
| Line 38: | Line 39: | ||
| * 特别，当H//**正定**//时，目标函数为凸函数，线性约束下可行域又是凸集。上式被称为//**凸二次规划**//。 | * 特别，当H//**正定**//时，目标函数为凸函数，线性约束下可行域又是凸集。上式被称为//**凸二次规划**//。 | ||
| - | **二次规划的性质** | + | **4.二次规划的性质** |
| * QP是一种最简单的非线性规划。QP有如下良好的性质，当H是半正定时： | * QP是一种最简单的非线性规划。QP有如下良好的性质，当H是半正定时： | ||
| Line 44: | Line 45: | ||
| * 局部最优解就是全局最优解。 | * 局部最优解就是全局最优解。 | ||
| - | **等式约束下的二次规划** | + | **5.等式约束下的二次规划** |
| min $f(x) = ½ x$<sup>T</sup>$Hx+c$<sup>T</sup>$x$, $x∈R$<sup>n</sup>\\ | min $f(x) = ½ x$<sup>T</sup>$Hx+c$<sup>T</sup>$x$, $x∈R$<sup>n</sup>\\ | ||
| s.t. $Ax=b（2）$ | s.t. $Ax=b（2）$ | ||
| - | 求解方法：Lagrange乘子法，求解以下无约束二次最优化问题。 | + | * 求解方法：Lagrange乘子法，求解以下无约束二次最优化问题。 |
| $L(x,λ) = ½ x$<sup>T</sup>$Hx+c$<sup>T</sup>$x+λ$<sup>T</sup>$(Ax-b)$ | $L(x,λ) = ½ x$<sup>T</sup>$Hx+c$<sup>T</sup>$x+λ$<sup>T</sup>$(Ax-b)$ | ||
| Line 61: | Line 62: | ||
| 可解得x，即为上式的解。 | 可解得x，即为上式的解。 | ||
| - | **二次规划的有效集方法** | + | **6.二次规划的有效集方法** |
| * 直观解释：将不起作用约束去掉，将起作用约束作为等式约束，\\ 通过解一系列等式约束的二次规划来实现不等式约束的优化 | * 直观解释：将不起作用约束去掉，将起作用约束作为等式约束，\\ 通过解一系列等式约束的二次规划来实现不等式约束的优化 | ||
| Line 73: | Line 74: | ||
| 的最优解，其中$a$<sub>i</sub>是A的第$i$行，$I$为起作用约束指标集（有效集）。 | 的最优解，其中$a$<sub>i</sub>是A的第$i$行，$I$为起作用约束指标集（有效集）。 | ||
| - | * 反之，若$x$为（1）的可行解，又是（3）的K-T点，且相应的乘子$λ$<sub>i</sub>$≥ 0$，则$x$为（1）的最优解。 | + | * 反之，若$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$，用乘子法求解 | + | *设当前迭代点为$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)$\\ | min $½(x$<sub>k</sub>$+d)$<sup>T</sup>$H(x$<sub>k</sub>$+d)+c$<sup>T</sup>$(x$<sub>k</sub>$+d)$\\ | ||
| Line 82: | Line 83: | ||
| * 若所得最优值$d$<sub>k</sub>$=0$，则$x$<sub>k</sub>是（3）的最优解。 | * 若所得最优值$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）的最优解。 | * 为判断它是否（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> | + | * 若最优值$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$加入有效集 | + | * 如果存在$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$ | + | * 如果存在$I$<sub>k</sub>中的指标$q$，使得$λ$<sub>i</sub>$< 0$, 则$x(k)$不是最优解，从有效集中去掉$q$。 |
| + | |||
| + | <note important>王文宏 2010-07-01</note> | ||
| + | |||
| + | <note important>朱朝艳 2011-06-19</note> | ||
keynote/lesson14.1277984405.txt.gz · Last modified: 2023/08/19 21:01 (external edit)
Page Tools
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Noncommercial-Share Alike 4.0 International
