<aside> 🧸 罚函数法包括外点罚函数法，内点罚函数法（内点法）

</aside>

• 【罚函数】

  <aside> 📢

  通过一些列无约束优化问题求解获得约束优化问题的解 拉格朗日函数 or 指示函数

  </aside>

  • indicator function 指示函数

    $$ \tau_\Omega(x)=\left\{\begin{aligned}&0&&x\in \Omega\\ &+\infty && otherwise\end{aligned}\right. $$

    直接加到目标含糊上，即可转化为无约束问题（无穷深势阱）。

    数值无法求解（无穷大），需要进行逼近（泰勒，傅里叶，切比雪夫， 埃尔米特，拉盖尔，勒让德）

    

    内逼近→内点法，外逼近→外点法|罚函数法

  • 罚函数$P$

    1. 连续
    2. 非负：指示函数就是非负的，不然等价于无约束这点不显然
    3. 可行点处为零$P(x\in\Omega)=0$：外逼近

    罚参数$\gamma$

    $$ \min f(x)+\gamma P(x),\\ \gamma>0,P:\mathbb R^n\to \R $$

    ---

    一种构造是距离：距离要么是0，要么是投影长度

    $$ dist(x,\Omega)=\left\{\begin{aligned}&0&&x\in \Omega\\ &\lVert x-\Pi (x)\lVert&& otherwise\end{aligned}\right. $$

    $$ dist(\omega,M)=dsit(u,0)+dist(v,\R_-^p),M=\{0,\cdots,0,v_p\le 0\} $$

    任意距离都可以：二范数的距离（二次罚函数），一范数（精确罚函数，不可微约束 ），柯朗逼近（二范数的平方和），广义罚函数

  • 外点法

    $$ \min {x\in\R^n}f(x)+\gamma\left(dist(h(x),0)+dist(g(x),\R-^p)\right) $$

    如求解二次问题得到$\lVert x_\lambda\lVert-1=-\frac {\lambda_{max}}{2\gamma}=O(\frac 1{\gamma})$，罚参数趋近于无穷的速度，就是$x_\lambda$趋近于满足约束的速度。

  ---

  • 内点法：

    $$ \min f(\bm x)\\s.t.\ \bm g(\bm x)\ge 0 $$

    不等式约束，有内点or相对内点

    • 对数罚函数

      $$ \min q(x)=f(x)-\frac 1\gamma\left(\sum_{i=1}^m\log g_i(\bm x)\right) $$

    • 倒数罚函数

      $$ \min q(x)=f(x)-\frac 1\gamma\left(\sum_{i=1}^m \frac 1{ g_i(\bm x)}\right) $$

    配合无约束牛顿法使用

  ---

  缺点：需要求解一个含有$\gamma$的方程组，迭代$\gamma^\prime=\rho\gamma$求解$x_{k+1}=\arg\min_{x=x_k\ to \ x^*}f(x)+\gamma P(x)$ 以使之趋近无穷

• 【精确罚函数】

  是不可微优化