|
信赖域方法和线搜索类似都是迭代方法，与其不同的是，每次迭代时，在一个选定的可信赖区域内，选择当前迭代点的近似模型 mkmk ，然后计算最优步长；如果步长不合适，可以对区域进行缩放。该小结主要介绍：
信赖域方法的基本形式在信赖域方法中，可信赖的区域（Region）的选择很重要，一般都会根据上一步结果进行动态变化；如果上一步太大则缩小，否则进行扩大。 基本形式在本节中模型选择为二次近似模型，采用函数二阶泰勒展开，即 f(xk+p)=fk+gTkp+12pT∇2fkpf(xk+p)=fk+gkTp+12pT∇2fkp 一般情况下会用 BkBk 去近似Hessian矩阵，即mk=fk+gTk+12pTBkpmk=fk+gkT+12pTBkp 其中 BkBk为对称矩阵。信赖域的基本形式为： min mk(p)=fk+gTk+12pTBkps.t ||p||≤Δkmin mk(p)=fk+gkT+12pTBkps.t ||p||≤Δk 该问题为关于p的带约束的最优化问题，参数p被限制在一个球形区域内。如果BkBk选择为Hessian，则为TR的牛顿方法。 如果||B−1kgk||≤Δk||Bk−1gk||≤Δk则 pk=−B−1kgkpk=−Bk−1gk为完全步(Full Step)，即球形约束没有作用。 ΔkΔk的选择参数ΔkΔk的选择一般会根据上一步的结果进行调整，定义 ρk=fk−f(xk+pk)mk(0)−mk(pk)ρk=fk−f(xk+pk)mk(0)−mk(pk) 其中分子表示函数实际减小的值；分母表示近似模型减少的值。分析 ρkρk: 1. 如果 ρkρk 小于0，一般情况下分母不可能小于0，因为目标函数求解的是最小值；此时说明分子小于0，即下一个目标点比上一步大，此时需要舍弃。 2. 如果 ρkρk 大于0并且接近1，说明模型和实际的预期比较相符合，此时可以考虑扩大ΔkΔk 3. 如果ρkρk大于0但是明显小于1，此时可以不用调整 4. 如果ρkρk大于0，但是接近0，说明模型变化范围比较大，但是实际改变比较小，此时应该收缩或者减少ΔkΔk 具体算法如下：  子问题的最优解为简化形式，将信赖域问题的子问题表示为： min m(p)=f+gTp+12pTBps.t ||p||≤Δmin m(p)=f+gTp+12pTBps.t ||p||≤Δ 该问题为标准的带不等式约束的二次优化问题，可以根据KKT条件（后面会深入介绍）得到该问题的最优解 定理 如果向量 p∗p∗ 为子问题的最优解，当且仅当满足 p∗p∗ 为可行解，并且存在标量 λλ 满足 (B+λI)=−g(a)λ(Δ−||p∗||)=0(b)(B+λI)正定(c)(B+λI)=−g(a)λ(Δ−||p∗||)=0(b)(B+λI)正定(c) 其中条件（b）为补充条件，即要么λ为0要么Δ=||p∗||λ为0要么Δ=||p∗||。 从下图中可以看出最优解和参数λλ的关系  当参数Δ=Δ1Δ=Δ1时，最优解为p3p3此时相当于没有约束，此时λ=0λ=0 当参数Δ=Δ1或者Δ2Δ=Δ1或者Δ2时，最优解被球形约束限制，此时满足Δ=||p∗||Δ=||p∗||，根据上面条件（a）有 λp∗=−Bp∗−gλp∗=−Bp∗−g 如果能够找到这样的p满足这些条件就能找到最优解。 基于柯西点（Cauchy-Point）的算法在实际求解过程中不一定找到最优解，而是找到一个充分下降的点满足全局收敛即可。柯西点就是满足该条件的点（pckpkc） 柯西点（Caychy-Point）算法求解步骤如下 psk=arg min fk+gTkps.t. ||p||≤Δkpks=arg min fk+gkTps.t. ||p||≤Δk 2. 寻找标量τk>0τk>0满足 min mk(τpsk)min mk(τpks) 同时满足信赖域的约束，即 τk=arg min mk(τpsk)s.t. ||τpsk||≤Δkτk=arg min mk(τpks)s.t. ||τpks||≤Δk 3. pck=τkpskpkc=τkpks 分别解释如下： min m(p)=f+gTp+12pTBps.t ||p||≤Δmin m(τpsk)=f−gTτΔk||gk||gk+12τ2Δk||gk||gTkBkΔk||gk||gks.t. ||τpsk||≤Δkmin m(p)=f+gTp+12pTBps.t ||p||≤Δmin m(τpks)=f−gTτΔk||gk||gk+12τ2Δk||gk||gkTBkΔk||gk||gks.t. ||τpks||≤Δk 是一个关于ττ 的二次函数，如果 1）gTkBkgk≤0gkTBkgk≤0，是一个关于ττ的递减函数，直接得到τ=1τ=1 2)如果gTkBkgk>0gkTBkgk>0 求导可以得到τk=||gk||3ΔkgTkBkgk,同时τ需要满足τ\e1τk=||gk||3ΔkgkTBkgk,同时τ需要满足τ\e1 柯西点很容易计算，但是如果只利用柯西点，相当于只利用了梯度方向，相当于线搜索的扩展而已，即收敛速度为线性收敛。 Dogleg算法该方法适用于当Bk正定时Bk正定时，寻找半径ΔΔ和最优解p∗(Δ)p∗(Δ)之间的关系。 p(τ)={τpu,pu+(τ−1)(pB−pu),0<τ<11<τ<2p(τ)={τpu,0<τ<1pu+(τ−1)(pB−pu),1<τ<2 其中pupu定义为pu=−gTggTBggpu=−gTggTBgg ，沿着梯度方向的最优解。 此为Dogleg方法，即寻找一个折线即两个线段的交点，即一条线段是沿着负梯度方向的最优值；二是沿着pU到pBpU到pB方向。在此折线上寻找最优解。 由定理可以证明||p(τ)||是一个关于τ的递增函数，而m(p(τ))是一个关于τ的递减函数||p(τ)||是一个关于τ的递增函数，而m(p(τ))是一个关于τ的递减函数，又是一个线性函数，因此只要计算p(τ)和||p||=Δp(τ)和||p||=Δ的交点即可。从下图可以清晰看到  二维子空间最优化在DogLeg算法中，可以理解为最优解p∗p∗可以表示为pU和pB的扩展子空间，即p∗=λ1g+λ2B−1gpU和pB的扩展子空间，即p∗=λ1g+λ2B−1g，则原子问题可以表示为： min m(p)=f+gTp+12pTBps.t ||p||≤Δp∈span[g,−B−1g]min m(p)=f+gTp+12pTBps.t ||p||≤Δp∈span[g,−B−1g] 迭代算法根据子问题的最优解形式可以得到 Bp∗=−gB正定||p∗||≠ΔBp∗=−gB正定||p∗||≠Δ 2) 当λ≠0时λ≠0时需要满足 (B+λI)p∗=−gB+λI正定||p∗||=Δ(B+λI)p∗=−gB+λI正定||p∗||=Δ 即||p∗||=||−(B+λI)−1g||=Δ||p∗||=||−(B+λI)−1g||=Δ 通过定义p(λ)=−(B+λI)−1gp(λ)=−(B+λI)−1g，寻找特定的λ使得||p(λ)||=Δλ使得||p(λ)||=Δ 相关定义由于B正定因此可以进行正交分解,B=QΛQT； Λ=diag(λ1,λ2,...,λn)并且λ1≤λ2≤...≤λnB=QΛQT； Λ=diag(λ1,λ2,...,λn)并且λ1≤λ2≤...≤λn B+λI=Q(Λ+λI)QTp(λ)=Q(Λ+λI)−1QTgp(λ)2=−∑1n(qTjg)2(λj+λ)2B+λI=Q(Λ+λI)QTp(λ)=Q(Λ+λI)−1QTgp(λ)2=−∑1n(qjTg)2(λj+λ)2 由于是正交分解因此qiqj=1qiqj=1迭代算法1）由上述定义 p(λ)2=−∑1n(qTjg)2(λj+λ)2p(λ)2=−∑1n(qjTg)2(λj+λ)2 可以看出 2） 当λ>−λ1时λ>−λ1时函数值是一个单调递减函数，特别当limλ→∞(p(λ)2)→0limλ→∞(p(λ)2)→0 3)因此我们需要寻找λ∈(−∞,λ1)使得||p||=Δλ∈(−∞,λ1)使得||p||=Δ  λλ求解在qTig≠0qiTg≠0 ϕ(λ)=||p(λ)||−Δ=0ϕ(λ)=||p(λ)||−Δ=0 2）近似算法求解 ϕ1(λ)=C1λ+λ1+C2phi1(λ)=1Δ−λ+λ3C3ϕ1(λ)=C1λ+λ1+C2phi1(λ)=1Δ−λ+λ3C3 当qTig=0qiTg=0是一个Hard Case，此时可以添加一个误差因子进行近似 p(λ)=Q(Λ+λI)−1QTg+τEp(λ)=Q(Λ+λI)−1QTg+τE 信赖域的其他扩展
总结通过该节需要了解 |
|
|
