分类目录归档：Optimization Theory

约束最优化方法

发表于 由
1

约束最优化问题的求解要比无约束问题的求解复杂得多, 也困难得多, 因而求解方法也更多种多样, 内容更为丰富. 这里只讨论可行方向方法中的简约梯度法和增广目标函数方法中的惩罚函数法. 一: 约束优化问题的最优性条件 KKT最优化条件是Karush[1939]以及Kuhn和Tucker[1951]先后独立发表出來的. 这组最优化条件在Kuhn和Tucker 发表之后才逐渐受到重视, 因此许多书只记载成「Kuhn-Tucker 最优化条件(Kuhn-Tucker conditions)」. KKT条件处理不等式约束时, 可以把它变换成一组等式约束. KTT条件是指在满足一些有规则的条件下, 一个非线性规划(Nonlinear Programming)问题能有最优化解法的一个必要和充分条件. 这是一个广义化拉格朗日乘数的成果. 一般地, 一个最优化数学模型的列标准形式如式(1), 所谓 Karush-Kuhn-Tucker 最优化条件，就是指上式的最优点\({{\bf{x}}^ * }\)必须满足下面的条件: 1). 约束条件满足\({g_i}({{\bf{x}}^ * }) \le 0,i = 1,2,…,p\), 以及\(,{h_j}({{\bf{x}}^ * }) = 0,j = … 继续阅读 →

拟牛顿法

发表于 由
回复

牛顿法成功的关键是利用了Hesse矩阵提供的曲率信息, 而计算Hesse矩阵工作量大, 并且有的目标函数的Hesse矩阵很难计算, 甚至不好求出来, 这就导致仅用目标函数的一阶导数的方法, 拟牛顿法就是利用目标函数值和一阶导数信息, 构造出目标函数的曲率近似, 而不需要明显形成Hesse矩阵, 同时具有收敛速度快的优点. 一: 拟牛顿法条件 目标函数\(f\)在\({x_{k + 1}}\)附近的二次近似为: \[f(x) \approx f({x_{k + 1}}) + g_{k + 1}^T(x - {x_{k + 1}}) + \frac{1}{2}{(x - {x_{k + 1}})^T}{G_{k + 1}}(x - {x_{k + 1}})\] 对上面的式子两边求导, … 继续阅读 →

共轭梯度法

发表于 由
回复

一: 共轭方向法 共轭方向法是介于最速下降法与牛顿法之间的一个方法, 它仅需利用一阶导数信息, 但克服了最速下降法收敛慢的缺点, 又避免了存储和计算牛顿法所需要的二阶导数信息. 共轭方向法是从研究二次函数的极小化产生的, 但是它可以推广到处理非二次函数的极小化问题. 最典型的共轭方向法是共轭梯度法. 而拟牛顿法也是共轭方向法的一种. 共轭方向的概念是这么定义的: 设\(G\)是\(n \times n\)对称矩阵, \({d_1},{d_2}\)是\(n\)维非零向量, 如果\(d_1^TG{d_2} = 0\), 则称向量\({d_1},{d_2}\)是\(G – \)共轭的. 类似地, 设\({d_1},{d_2},…,{d_m}\)是\({R^n}\)中的任意一组非零向量. 若有\(d_i^TG{d_j} = 0,(i \ne j)\), 则称\({d_1},{d_2},…,{d_m}\)是\(G – \)共轭的. 显然地, 当\(G\)是\(n\)阶单位矩阵时, \(d_i^T{d_j} = 0,(i \ne j)\), 即是正交向量组. 因而共轭概念是正交概念的推广. … 继续阅读 →

牛顿法

发表于 由
回复

一: 最速下降法 下降法的迭代格式为\({x_{k + 1}} = {x_k} – {\alpha _k}{d_k}\), 其中\({d_k}\)为下降方向, 设\({g_k} = \nabla f({x_k}) \ne 0\), 则下降方向要满足\(d_k^T{g_k} < 0\). 当步长确定时, \(d_k^T{g_k}\)的值越小, 即\({\rm{ - }}d_k^T{g_k}\)的值越大, 函数下降得越快. 由Cauchy-Schwartz不等式\(\left| {d_k^T{g_k}} \right| \le \left\| {{d_k}} \right\|\left\| {{g_k}} \right\|\), 当且仅当\({d_k} = - {g_k}\)时, \(d_k^T{g_k}\)的值最小. … 继续阅读 →

一维搜索linesearch

发表于 由
回复

一: 精确搜索-区间分割方法 1). 0.618法 对于一个单谷函数想通过迭代不断缩小该区间的长度, 当区间长度充分小时, 可取这个小区间中的一点作为\(\varphi (t)\)的一个近似极小点. 每次迭代时在搜索区间中任取两个点, 然后比较这两个点的函数值定下新的搜索区间. 当我们想在第二迭代开始时每次只搜索一个点, 即要把上一次迭代被抛弃的点利用上, 并且限制住收缩比相同. 则可以推出0.618法. 2). Fibonacci法 问题的提出: 在0.618法中, 经过N-1次迭代后的搜索区间\(\left[ {{a_N},{b_N}} \right]\)的长度为\({b_N}{\rm{ – }}{a_N} = {\tau ^{N – 1}}({b_1} – {a_1})\), 那么, 如果事先给定了搜索算法的迭代次数N, 按那种规则选取试探点可以使给定的搜索区间长度做最快分割呢? 上面的问题可以转化为一个优化问题: \[\begin{array}{*{20}{c}} {\min }&{{\tau _1}{\tau _2} \cdots … 继续阅读 →

最优化方法结构

发表于 由
回复

一：无约束问题的最优性条件 对于一个无约束问题\(\min f(x),x \in {R^n}\). 它的极小点类型有局部极小和总体极小两种. 而且一般来说, 总体求总体极小点是一个相当困难的任务, 很多实际问题中求局部极小点已满足了问题的要求. 当研究的问题是具有某种凸性时, 局部极小点就是全局极小点. 设\(f\)的一阶导数和二阶导数存在, 且分别表示为\(g(x) = \nabla f(x),G(x) = {\nabla ^2}f(x),\) 则 1. 收敛点的一阶必要条件: \(g({x^{\rm{*}}}) = 0\); 2. 收敛点的二阶必要条件: \(g({x^{\rm{*}}}) = 0,G({x^{\rm{*}}}) \ge 0\); 3. 收敛点的二阶充分条件: \(g({x^{\rm{*}}}) = 0,G({x^{\rm{*}}})\)是正定矩阵; 4. 如果目标函数为凸函数, 那么全局极小值点的充分必要条件就是\(g({x^{\rm{*}}}) … 继续阅读 →

共轭梯度法在SVM原问题参数优化中的应用

发表于 由
回复

1. 共轭性 关于共轭先了解一下其基本性质, 共轭性的定义为: 设\(A \in {R^{n \times n}}\)是对称正定矩阵. 称\({{\bf{p}}_1},{{\bf{p}}_2}\)是 -共轭的, 是指 \({\bf{p}}_1^TA{{\bf{p}}_2}{\rm{ = }}0,\begin{array}{*{20}{c}} {} \end{array}{\bf{p}}_1^TA{{\bf{p}}_1} > 0,\begin{array}{*{20}{c}} {} \end{array}{\bf{p}}_2^TA{{\bf{p}}_2} > 0\) 那么它的性质有: 1). 设有\({{\bf{p}}_1},{{\bf{p}}_2},…,{{\bf{p}}_m}(m < n)\)是彼此共轭的\(n\)维向量, 即 \[{\bf{p}}_i^TA{{\bf{p}}_j}\left\{ {\begin{array}{*{20}{c}} { = 0,\begin{array}{*{20}{c}} {} \end{array}i \ne j,}\\ { > … 继续阅读 →

Jacobian矩阵和Hessian矩阵

发表于 由
29

1. Jacobian 在向量分析中, 雅可比矩阵是一阶偏导数以一定方式排列成的矩阵, 其行列式称为雅可比行列式. 还有, 在代数几何中, 代数曲线的雅可比量表示雅可比簇：伴随该曲线的一个代数群, 曲线可以嵌入其中. 它们全部都以数学家卡尔·雅可比(Carl Jacob, 1804年10月4日－1851年2月18日)命名；英文雅可比量”Jacobian”可以发音为[ja ˈko bi ən]或者[ʤə ˈko bi ən]. 雅可比矩阵 雅可比矩阵的重要性在于它体现了一个可微方程与给出点的最优线性逼近. 因此, 雅可比矩阵类似于多元函数的导数. 假设\(F\): \({R_n} \to {R_m}\)是一个从欧式n维空间转换到欧式m维空间的函数. 这个函数由m个实函数组成: y1(x1,…,xn), …, ym(x1,…,xn). 这些函数的偏导数(如果存在)可以组成一个m行n列的矩阵, 这就是所谓的雅可比矩阵： \begin{bmatrix} \frac{\partial y_1}{\partial x_1} & \cdots & \frac{\partial … 继续阅读 →