Legendre Transformation

勒让德变换：用 $f^{ * }(p)$ 表示凸、可导函数 $f(x)$ 的变换，其中 $p$ 是 $f(x)$ 导数

$$f^{*}(p) = p^T x - f(x)|_{\frac {d(p^T x - f(x))} {dx} = 0}$$

• $x$：参数，满足 $\frac {d(p^T x - f(x))} {dx} = 0$，随 $p$ 取值改变
• 可导：有导数；凸：导数唯一

• 勒让德变换是实变量的实值凸函数的对合变换
  • 把定义在线性空间上的函数变换至对偶空间的函数
  • 是点、（切）线之间对偶关系的应用
    • 严格凸函数中，切线、导数一一对应
    • 函数关系 $f(x)$ 可使用 $(x, y=f(x))$ 点集表示，也可用切线集合表示

• involution 对合：对合函数 $f$ 的反函数的为自身，即 $f(f(x))=x$；对合线性变换 $V$ 满足 $V^2 = E$

Legendre 变换理解（按 Fenchel 共轭）

• $f^{*}(p)$：可理解为斜率为 $p$、同 $f(x)$ 有交点 $x_0$ 的直线在零点处值（截距）和 $f(x_0)$ 的最大差

  

• $x$：可以理解为函数 $f(x)$ 上距离给定斜率为 $p$、过原点的直线 $f(x)=px$ 竖直距离最大的点

  

  • 类似一个端点为 $0$ 的 Bregman 散度

• Legendre 变换为对合变换，进行两次的变换得到原函数

  

  $$\begin{align*} f^{**}(x) & = \sup_{p \in dom(f^{*})} [x^T p - f^{*}(p)] \\ & = \sup_{u \in dom(f)}[x^T \nabla f(u) - \nabla f(u)^T u + f(u)] \\ & = \sup_{u \in dom(f)}[f(u) + \nabla f(u)^T (x-u)] \\ & = f(x) \end{align*}$$

• 若视凸函数 $f(x)$ 视为积分，则其共轭 $f^{ * }(x)$ 为对另一轴积分，二者导函数互为反函数

  $$f(x) + f^{*}(p) = xp, p = \frac {df(x)} {dx}$$

• 以上性质均按 Fenchel 共轭，但要求 $f(x)$ 为凸、可导函数，故等价于 Legendre 变换

Legendre 变换最大值式定义

$$\begin{align*} L(p, x) &= px - f(x) \\ \frac {\partial (px - f(x))} {\partial x} &= p - \frac {df(x)} {dx} = 0 \\ \Rightarrow & p = \frac {df(x)} {dx} \end{align*}$$

• Legendre 变换可以视为寻找 $px-f(x)$ 最大值（如前述）
  • $f(x)$ 为凸函数，则 $p=\frac {df(x)} {dx}$ 是最大值点
  • 则将 $f(x)$ 导函数的反函数 $x=f^{-1}(p)$ 带入即可

Legendre 变换数学性质

• 标度性质

  $$\begin{align*} f(x) & = a g(x) \rightarrow f^{*}(p) = a g^{*}(\frac p a) \\ f(x) & = g(ax) \rightarrow f^{*}(p) = g^{*}(\frac p a) \end{align*}$$

  由此，$r$次齐次函数的勒让德变换是$s$次齐次函数，满足

  $$\frac 1 r + \frac 1 s = s$$

• 平移性质

  $$\begin{align*} f(x) & = g(x) + b \rightarrow f^{*}(p) = g^{*}(p) - b f(x) & = g(x+y) \rightarrow f*^{*}(p) = g^{*}(p) - py \end{align*}$$

• 反演性质

  $$f(x) = g^{-1}(x) \rightarrow f^{*}(p) = -p g^{*}(\frac 1 p)$$

• 线性变换性质

  $$(Af)^{*} = f^{*}A^{*}$$

  • $f$：$R^n$上的凸函数
  • $A$：$R^n \rightarrow R^m$的线性变换
  • $A^{}: <Ax, y^{}> = $：$A$伴随算子

Fenchel Conjugate / 凸共轭

$$f^{*}(p) = \sup_{x \in R}{p^Tx - f(x)}$$

• Fenchel 共轭是对 Legendre 变换的扩展，不再局限于凸、可导函数
  • Fenchel 共轭可类似 Legendre 理解，但是适用范围更广
  • 对凸函数 Fenchel 共轭的共轭即为原函数，对非凸函数 Fenchel 共轭得到原函数凸包
  • 用罗尔中值定理描述极值、导数关系：兼容 Legendre 变换中导数支撑面

• 非凸函数线性外包络是凸函数

Fenchel-Young不等式

$$f(x) + f^{*}(p) \geq <p, x>$$

• 证明

  $$\begin{align*} f(x) + f^{*}(p) & = f(x) + \sup_{x \in dom(f)} {(x^T p - f(x))} \\ & \geq f(x) + x^T p - f(x) = x^T p \end{align*}$$

• 按积分理解，仅$p$为$x$共轭时取等号

  

Fenchel Conjugate 推导 Lagrange Duality

• 原问题 Prime

  $$\begin{align*} & \min {f(x)} \\ s.t. & g(x) \leq 0 \\ \end{align*}$$

• 约束条件 $g(x) \leq 0$ 扰动函数化、求 Fenchel 共轭

  $$\begin{align*} p(u) & = \inf_{x \in X, g(x) \leq u} f(x) \\ p^{*}(y) & = \sup_{y \in R^r} \{u^T y - p(u)\} \end{align*}$$

• 记 $\lambda = -y$，并将 $y=-\lambda$ 带入 $-p^{*}(y)$ 中得到

  $$\begin{align*} -p^{*}(y) & = \inf_{u \in R^r} \{p(u) - u^T y\} \\ d(\lambda) & = \inf_{u \in R^r} \{p(u) + u^T \lambda\} \\ & = \inf_{u \in R^r} \{\inf_{x \in X, g(x) \leq u} f(x) + \lambda^T u\} \end{align*}$$

  • $\lambda = -y$

• 将 $\inf_{x \in X, g(x) \leq u}$ 外提，并考虑到约束 $g(x) \leq u$（即 $u \geq g(x)$），则

  $$\begin{align*} \lambda \geq 0 & \Rightarrow \lambda^T g(x) \leq \lambda u \\ d(\lambda) & = \left \{ \begin{array}{l} \inf_{x \in X} \{f(x) + \lambda^T g(x)\}, & \lambda \geq 0 \\ -\infty, & otherwise \end{array} \right. \end{align*}$$

• 考虑 Fenchel 不等式

  $$\begin{align*} p(u) + p^{*}(-y) & \geq u^T (-y) \\ p(0) + p^{*}(-y) & \geq 0 \\ p(0) & \geq -p^{*}(-y) \\ p(0) & \geq d(\lambda) \end{align*}$$

• 则可得 Lagrange 对偶 Prime、Dual 最优关系

  $$L(x, \lambda) = f(x) + \lambda^T g(x), \lambda \geq 0 \\ D^{*} := \max_{\lambda \geq 0} \min_x L(x, \lambda) \leq \min_x \max_{\lambda \geq 0} L(x, \lambda) =: P^{*}$$

  

Lagrange Duality 推导 Fenchel 对偶

• Fenchel 对偶可以视为 Lagrange 对偶的应用

• 原问题、等价问题

  $$\begin{align*} & \min_x & f(x) - g(x) \\ \Leftrightarrow & \min_{x,z} & f(x) - g(z) \\ & s.t. & x = z \end{align*}$$

• 对上式取 Lagrange 对偶 $L(u)$、等价得到

  $$\begin{align*} L(u) &= \min_{x,z} f(x) - g(z) + u^T(z-x) \\ &= -(f^{*}(u) - g^{(-u)}) \end{align*}$$

• Fenchel 对偶：寻找截距差值最大的平行切线

Fourier Transformation

（连续）傅里叶变换：将时域映射到频域的变换

$$F(\xi) = \int_{-\infty}^{+\infty} f(x) e^{-2\pi ix \xi} dx$$

• $x$：自变量，多表示时间
• $F(\xi)$：频率

傅里叶变换理解

• 将自变量 $x$ 线性映射为极坐标系中角度，调整线性映射的比例（即频率），即可绘制出不同的曲线

  

• 计算不同频率下曲线围成的图像的质心（径向）坐标

  • 质心的角度坐标只需原函数沿 $x$ 轴平移即可改变
  • 若原图像不关于 $x$ 轴对称，则质心在频率 0 点处有较大值

  

• 据以上：周期函数映射在极坐标系下图像，其质心位置在对应频率下取波峰值

• https://charlesliuyx.github.io/2018/02/18/%E3%80%90%E7%9B%B4%E8%A7%82%E8%AF%A6%E8%A7%A3%E3%80%91%E8%AE%A9%E4%BD%A0%E6%B0%B8%E8%BF%9C%E5%BF%98%E4%B8%8D%E4%BA%86%E7%9A%84%E5%82%85%E9%87%8C%E5%8F%B6%E5%8F%98%E6%8D%A2%E8%A7%A3%E6%9E%90/

傅里叶变换计算

• 利用复数项 $e^{-2\pi ix \xi}$ 表示在复平面中的旋转角度

  • $x$ 为函数自变量，$\xi$ 为频率（即自变量映射比例）
  • 傅里叶变换中旋转为缺省为顺时针，所以补足负号
  • 函数在复平面中则表示为 $f(x) e^{-2\pi ix \xi}$

• 函数围成的曲线质心则为 $\frac 1 {x2 - x_1} \int{x_1}^{x_2} f(x) e^{-2\pi ix \xi} dx$

  • 系数 $\frac 1 {x_2 - x_1}$ 将积分结果放缩回质心，可省略
  • 将原积分区域外函数值定为 0，积分上下限扩展至 $-\infty, \infty$ 不影响积分结果
  • 函数有效取值部分越长，质心波动约迅速

傅里叶变换

Discrete Fourier Transformation

DFT：归一化二维离散傅里叶变换

$$\begin{align*} F(u,v) & = \frac 1 {\sqrt{NM}} \sum_{x=0}^{N-1} \sum_{y=0}^{M-1} f(x,y) e^{-\frac {2\pi i} N ux} e^{-\frac {2\pi i} M vy} \\ f(x,y) & = \frac 1 {\sqrt{NM}} \sum_{u=0}^{N-1} \sum_{v=0}^{M-1} F(u,v) e^{\frac {2\pi i} N ux} e^{\frac {2\pi i} M vy} \\ \end{align*}$$

Discrete Consine Transformation

余弦变换

• 在给定区间为满足狄利克雷条件的连续实对称函数，可以展开为 仅含余弦项的傅里叶级数

• 对于定义在正实数域上的函数，可以通过偶延拓、或奇延拓满足 上述条件

离散余弦变换

• $(x,y) or (u,v) = (0,0)$时

  $$\begin{align*} F(u,v) & = \frac 1 N \sum_{x=0}^{N-1} \sum_{y=0}^{N-1} f(x,y) cos[\frac \pi N u(x + \frac 1 2)] cos[\frac \pi N v(y + \frac 1 2)] \\ f(x,y) & = \frac 1 N \sum_{u=0}^{N-1} \sum_{v=0}{N-1} F(u,v) cos[\frac \pi N u(x + frac 1 2)] cos[\frac \pi N v(y + \frac 1 2)] \end{align*}$$

• 其他

  $$\begin{align*} F(u,v) & = \frac 1 {2N} \sum_{x=0}^{N-1} \sum_{y=0}^{N-1} f(x,y) cos[\frac \pi N u(x + \frac 1 2)] cos[\frac \pi N v(y + \frac 1 2)] \\ f(x,y) & = \frac 1 {2N} \sum_{u=0}^{N-1} \sum_{v=0}{N-1} F(u,v) cos[\frac \pi N u(x + frac 1 2)] cos[\frac \pi N v(y + \frac 1 2)] \end{align*}$$

Projected Gradient Descent

受限优化问题

$$\min_{x \in C} f(x)$$

• $C \subseteq R^d$：受限凸集

投影梯度下降：采用后处理的方式，将迭代位置拉回到约束条件内

• 使用一般下降算法进行位置更新，新位置$x_{t+1}^{‘}$可能 不再满足约束条件

• 为使新位置$x{t+1}^{‘}$符合受限集合，可以选择在$L_2$范数 下距离受限集合$C$最近的的点 $x{t+1}=\arg\min{x \in C} |x - x{t+1}^{‘}|$作为下步 真正迭代位置

线性约束

Projection Matrix

• 投影矩阵：矩阵$P \in R^{n*n}$，若满足$P^T = P, P^2 = P$
• 若$A \in R^{m*n}$为行满秩矩阵，则$A$的零空间为 $L_A = {x \in R^{n} | Ax = 0}$，对应正交空间为 $L_A^{\perp} = {A^T y | y \in R^m}$

对$\forall x \in R^n$进行正交分解

$$\begin{align*} \forall x \in R^n, x & = x_1 + x_2, x_1 \in L_A, x_2 \in L_A^{\perp} \\ x_1 & = P_A x \end{align*}$$

• $P_A = I - A^T (A A^T)^{-1} A$：$A$的投影矩阵
• 投影矩阵$P_A$可由点对线性约束的投影定义，利用拉格朗日 求解

证明

$$\begin{align*} x_1 & = x - x_2 = x - A^T y \\ A x_1 & = A x - A A^T y \\ \Rightarrow y & = (A A^T)^{-1} A (x - x_1) \\ \Rightarrow x_1 & = x - A^T[(A A^T)^{-1} A (x - x_1)] \\ & = x - A^T (A A^T)^{-1} A x - A^T (A A^T)^{-1} A x_1 \\ & = (I - A^T (A A^T)^{-1} A) x = P_A x \end{align*}$$

• 投影矩阵$P$对值应用多次线性变换和只应用一次结果相同， 保持像不变

Projection Operator

$$\begin{array}{l} \min & f(x) \\ s.t. & A_1 x \leq b_1 \\ & A_2 x = b_2 \end{array}$$

• 设$x^{k}$为当前迭代点，记$A{11}$、$A{12}$分别为紧、松 约束，即

  $$\begin{align*} A_1 & = \begin{bmatrix} A_{1,1} \\ A_{1,2} \end{bmatrix}, & b_1 & = \begin{bmatrix} b_{1,1} \\ b_{1,2} \end{bmatrix} \\ A_{1,1} x^k & = b_{1,1}, & A_{1,2} x^k & \leq b_{1,2} \end{align*}$$

• 记$M = [A_{1,1}^T, A_2^T]^T$，则$s \in L_M$时是可行方向

• 对负梯度$\nabla f(x^k)$，通过$M$的投影矩阵$P_M$将其投影 至$L_M$上即得可行下降方向$s^k = -P_M \nabla f(x^k)$

  • $s^k \neq 0$：为$x^k$处可行下降方向
  • $s^k = 0$：作如下讨论

投影方向为0

• 记$w = [u, v]^T = -(M M^T)^{-1}M \nabla f(x^k)$，则有

  $$\begin{align*} 0 & = \nabla f(x^k) + M^T w \\ & = \nabla f(x^k) + [A_{1,1}^T, A_2^T] \begin{bmatrix} u \\ v \end{bmatrix} \\ & = \nabla f(x^k) + A_{1,1}^T u + A_2^T v \end{align*}$$

• 若$u \geq 0$，则$x^{k}$是KKT点

  $$\nabla f(x^k) + A_{1,1}^T u + A_{1,2}^T v = 0 \Rightarrow x^k 为KKT点$$

• 否则若$u$中有负分量，可设$u0 < 0$，记$\bar M$为$M$中 去除对应列矩阵，则$\bar s^k = -P{\bar M}\nabla f(x^k)$ 为$x^k$可行下降方向

  • 先反证法证明$\bar s^k \neq 0$，若$\bar s^k = 0$

    $$\begin{align*} 0 & = \nabla f(x^k) - \bar M^T (\bar M \bar M^T)^{-1} \bar M \nabla f(x^k) \\ & = \nabla f(x^k) + \bar M^T \beta \\ \beta & = -(\bar M \bar M^T)^{-1} \bar M \nabla f(x^k) \end{align*}$$

    考虑到

    $$\begin{align*} 0 & = \nabla f(x^k) + M^T w \\ & = \nabla f(x^k) + u_0 \alpha_0 + \bar M^T \bar w \end{align*}$$

    • $\alpha_0$：$M$中$u_0$对应行

    则有

    $$u_0 \alpha_0 + \bar M^T (\bar w - \beta) = 0$$

    与$M$行满秩条件矛盾，故$\bar s^k \neq 0$

  • 证明$\bar s^k$为下降方向

    $$\begin{align*} \nabla f(x^k)^T \bar s^k & = -\nabla f(x^k) P_{\bar M} \nabla f(x^k) \\ & = -\nabla f(x^k) P_{\bar M}^T P_{\bar M} \nabla f(x^k) \\ & = -\|P_{\bar M} \nabla f(x^k)\|_2^2 \leq 0 \end{align*}$$

  • 证明$\bar s^k$方向可行（满足约束）

    • 由$P{\bar M}$定义：$\bar M P{\bar M} = 0$，则

      $$\begin{align*} \bar M \bar s^k & = -\bar M \bar P_{\bar M} \nabla f(x^k) \\ & = \begin{bmatrix} \bar A_{1,1} \\ A_2 \end{bmatrix} \bar s^k = 0 \end{align*}$$

    • 则只需证明$\alpha_0^T \bar s^k < 0$

      $$\begin{align*} 0 & = \nabla f(x^k) + M^T w \\ & = \nabla f(x^k) + u_0 \alpha_0 + \bar M^T \bar w \\ \Rightarrow & = \nabla f(x^k)^T \bar s^k + u_0 \alpha_0^T \bar s^k + \bar w^T \bar M \bar s^k \\ & = \nabla f(x^k)^T \bar s^k + u_0 \alpha_0^T \bar s^k \end{align*}$$

      考虑到$u_0 < 0$，则$\alpha_0^T \bar s^k < 0$

  • 即此时有紧约束变为松约束

算法

• 初始化：初始点$x^0$、$k=0$、精度参数$\epsilon > 0$

• 构造$M = [A_{1,1}^T, A_2^T]^T$

  • 若$M=0$（在可行域内），令$s^k = -\nabla f(x^k)$为 迭代方向
  • 否则令$s^k = -P_M \nabla f(x^k)$为迭代方向

• 若$|s^k|_2^2 \geq \epsilon$

  • 若$M$为空（无可下降方向），停止
  • 若$M$非空、$u > 0$，停止
  • 否则，构建$M = \bar M$继续

• 若$|s^k|_2^2 > \epsilon$，确定步长$\lambda_k$

  • 显然只需保证$A_2 x_k + \lambda_k A_2 d_k \leq b_2$ 即可

  • 若$A_2 d_k < 0$，则$\lambda_k$无约束，否则

    $$\lambda_k = \max \{\frac {(b_2 - A_2 x_k)_i} {(A_2 d_k)_i}\}$$

  • 即单纯型法中确定步长方法

• 得到新迭代点$x^{k+1} = x^k + \lambda_k s^k$、$k=k+1$

约束问题局部解

$$\begin{array}{l} \min & f(x), x \in R^n \\ s.t. & c_i(x) = 0, i \in E = \{1,2,\cdots,l\}, \\ & c_i(x) \leq 0, i \in I = \{l,l+1,\cdots,l+m\} \end{array}$$

• 对于一般约束优化问题，记其可行域为

  $$D = \{x| c_i(x) = 0, i \in E, c_i(x) \leq 0, i \in I\}$$

• 若 $\forall x^{} \in D, \exists \epsilon$，使得当 $x \in D, |x - x^{}| \leq \epsilon$ 时，总有

  $$f(x) \geq f(x^{*})$$

  则称$x^{*}$为约束问题的局部解，简称为最优解

• 若 $x \in D, 0 < |x - x^{*}| \leq \epsilon$ 时，总有

  $$f(x) > f(x^{*})$$

  则称$x^{*}$是约束问题的严格局部最优解

约束问题局部解一阶必要条件

定理1

• 设 $a_1,a_2,\cdots,a_m$ 和 $w \in R^n$，$C$ 定义如下 $$

    C = \{v |\sum_{i=1}^m \lambda_i a_i, \lambda_i \geq 0,
    i=1,2,\cdots,m \}
  

  $$若 $w \notin C$，则存在超平面 $d^T w = 0$，分离 $C$ 和 $w$，即$$ \begin{align*}

    d^T w & \leq 0 \\
    d^T w & > 0
  

  \end{align*}$$

• 显然C是闭凸集，则$\exists d \in R^n, d \neq 0$， $\alpha \in R$，使得

  $$\begin{array}{l} d^T x \leq \alpha, & \forall x \in C \\ d^T w > \alpha & \end{array}$$

• 又C是锥，有$0 \in C$，所以$\alpha \geq 0$，即$d^T w > 0$

• 若$\exists \bar x \in C, d^T \bar x > 0$，则 $\forall \lambda \geq 0, \lambda \bar x \in C$，则有

  $$\lambda d^T \bar x \leq \alpha$$

  而$\lambda \rightarrow \infty$，左端趋于无穷，矛盾

Farkas引理

• 设$a_1,a_2,\cdots,a_m$和$w \in R^n$，则以下两个系统有且 仅有一个有解

  • 系统I：存在$d$满足 $$\begin{align*} a_i^T d & \leq 0, & i=1,2,\cdots,m \\ w^T d & > 0 \end{align*}$$
  • 系统II：存在非负常数$\lambda_1,\cdots,\lambda_m$使得 $$w =\sum_{i=1}^m \lambda_i a_i$$

• 若系统II有解，则系统I无解

  • 若系统II有解，即存在$\lambda_1,…,\lambda_m$且 $\lambda_i \geq 0,i=1,2,\cdot,m$，使得

    $$w = \sum_{i=1}^m \lambda_i a_i$$

  • 若系统I有解，则有

    $$0 < w^T d = \sum_{i=1}^m \lambda_i a_i^T d \leq 0$$

    矛盾，因此系统I无解

• 若系统II无解，则系统I有解

  • 系统II误解，构造闭凸锥

    $$C = \{v |\sum_{i=1}^m \lambda_i a_i, \lambda_i \geq 0, i=1,2,\cdots,m \}$$

    显然$w \notin C$

  • 由定理1，存在d满足

    $$\begin{array}{l} d^T x \leq 0, & \forall x \in C, \\ d^T w & > 0 \end{array}$$

• 此定理就是点要么在凸锥C内、边缘（系统II），要么在凸锥 外（系统I）

推论1

• 设$a_1,a_2,\cdots,a_m$和$w \in R^n$，则以下系统有且仅有 一个有解

  • 系统I：存在d满足 $$\begin{array}{l} a_i^T d \leq 0, & i=1,2,\cdots,m \\ d_j \geq 0, & j=1,2,\cdots,n \\ w^T d > 0 & \end{array}$$
  • 系统II：存在非负常数$\lambda_1,…,\lambda_m$使得 $$w \leq \sum_{i=1}^m \lambda_i a_i$$

• 若系统II有解，则系统I无解

  • 若系统I有解，取d带入矛盾

• 若系统II无解，则系统I有解

  • 若系统I无解

    todo

推论2

• 设$a1,a_2,\cdots,a{l+m}$和$w \in R^n$，则以下两个系统 有且进一有一个存在解

  • 存在d满足 $$\begin{array}{l} a_i^T d = 0, & i=1,2,\cdots,l \\ a_i^T d \leq 0, & i=l+1,l+2,\cdots,l+m \\ w^T d > 0 \end{array}$$
  • 存在常数$\lambda1,\lambda_2,\cdots,\lambda{l+m}$ 且$\lambda_i \geq 0, i=l+1, l+2, \cdots, l+m$使得 $$w = \sum_{i+1}^{l+m} \lambda_i a_i$$

迭代求解

参数部分更新

参数部分更新：每次更新一个或一组待估参数

• 应用场合

  • 适合待估参数较少、同时估计较慢，待估参数较多可能更新 速度慢，往往需要多次迭代更新参数
  • 一般用在机器学习算法中比较多

• 特点（某些算法）

  • 良好的并行特性：能够同时更新多个参数

    • Alternating Direction Method of Multipliers

  • 采用贪心策略的算法：可能无法得到最优解

    • 前向回归
    • 深度学习：网络层次太深，有些算法采用固化部分 网络结构，估计剩余部分

  • 能够平衡全局、局部：得到较好的解

    • LARS

Norm

$\mathcal{L_p}$ 范数

• $\mathcal{L_p}$ 范数

  $$\|x\|_p = (|x_1|^p + |x_2|^p + \cdots + |x_N|^p)^{1/p}$$

  • $x \in R^n$

• $\mathcal{L_p}$ Dual Norm 对偶范数

  $$\|x\|^{*} = \mathop \sup_{z}{x^Tz|\|z\| \leq 1}$$

  • $x \in R^N$
  • $|x|$：$x$的某个范数

无约束局部解

$$minf(x), x \in R^n$$

• 若存在$x^{ } \in R^n, \epsilon > 0, \forall x \in R^n$ 使得$|x - x^{ }| < \epsilon$时，恒有
• $f(x) \geq f(x^{ })$：则称$x^{ }$为f(x)的 local minimum point/solution（局部极小点/局部解）
• $f(x) > f(x^{ })$：则称$x^{ }$为f(x)的 严格局部极小点/局部解

最优性条件

First-Order Necessary Condtion

• 无约束问题局部解的一阶必要条件：设f(x)有连续的一阶偏导， 弱$x^{ * }$是无约束问题的局部解，则 $$\triangledown f(x{* }) = 0$$

Second-Order Necessary Condition

• 无约束问题局部解的二阶必要条件：设f(x)有连续二阶偏导， 若$x^{ * }$是无约束问题的局部解，则

  • $$\triangledown f(x^{ * }) = 0$$
  • $$\triangledown^2 f(x^{ * })半正定$$

Second-Order Sufficient Condition

• 无约束问题局部解的二阶充分条件：设f(x)有连续二阶偏导， 若在$x^{ }$处满足以下，则x^{ }是无约束问题的 严格局部解

  • $$\triangledown f(x^{ * }) = 0$$
  • $$\triangledown^2 f(x^{ * })正定$$

下降算法

迭代算法：将当前迭代点向正确方向移动一定步长，然后 检验目标值是否满足一定要求

• 方向、步长就是不同优化算法主要关心的两个方面
• 还关心算法的rate of convergence（收敛速率）

一般下降算法框架

1. 取初始点$x^{(1)}$，置精度要求$\epsilon$，置k=1

2. 若在点$x^{(k)}$处满足某个终止准则，则停止计算，得无约束 优化问题最优解$x^{(k)}$，否则适当地选择$x^{(k)}$处 搜索方向

3. 进行适当的一维搜索，求解一维问题

   $$\arg\min_{\alpha} \phi(\alpha) = f(x^{(k)} + \alpha d^{(k)})$$

4. 置k=k+1，转2

要使下降算法可行，需要确定

• 某点出搜索方向
  • 负梯度方向
  • Newton方向：求方向的时候已确定步长，也可用做步长搜索
  • 拟Newton方向
• 求步长地一维搜索方式
  • 试探法
    • 0.618法
    • Fibonacci方法（分数法）
    • 二分法
  • 插值法
    • 三点二次插值法
    • 二点二次插值法
    • 两点三次插值法
  • 非精确一维搜索方法
    • Glodstein方法
    • Armijo方法
    • Wolfe-Powell方法

• 算法终止准则

  • $|\triangledown f(x^{(k)})| < \epsilon$
  • $|x^{(k+1)} - x^{(k)}| < \epsilon$
  • $|f(x^{(k+1)}) - f(x^{(k)})| < \epsilon$

  • 实际计算中最优解可能永远无法迭代达到，应该采用较弱 终止准则

算法收敛性

• 收敛：序列${x^{(k)}}$或其一个子列（仍记${x^{(k)}}$） 满足 $$\lim_{k \rightarrow \infty} x^{(k)} = x^{ * }$$

  • $x^{ * }$：无约束问题局部解

但是这样强的结果难以证明

• 往往只能证明${x^{(k)}}$的任一聚点的稳定点
• 或是更弱的 $$\lim_{k \rightarrow \infty} inf \|\triangledown f(x^{(k)}) \| = 0$$

• 局部收敛算法：只有初始点充分靠近极小点时，才能保证产生 序列收敛
• 全局收敛算法：对任意初始点，产生序列均能收敛

收敛速率

设序列${x^{(k)}}$收敛到$x^{ * }$，若以下极限存在

$$\lim _ {k \rightarrow \infty} \frac {\|x^{(k+1)} - x^{*}\|} {\|x^{(k)} - x^{*}\|} = \beta$$

• $0 < \beta < 1$：线性收敛
• $\beta = 0$：超线性收敛
• $\beta = 1$：次线性收敛（收敛速率太慢，一般不考虑）

算法的二次终止性

• 二次终止性：若某算法对任意正定二次函数，从任意初始点出发 ，都能经过有限步迭代达到其极小点，则称该算法有二次终止性

具有二次终止性的算法被认为时好算法，否则计算效果较差，原因

• 正定二次目标函数有某些好的性质，好的算法应该能在有限步内 达到其极小点

• 对于一个一般的目标函数，若其在极小点处的Hesse矩阵 $\triangledown f(x^{( * )})$，则由泰勒展开式得到

  $$\begin{align*} f(x) & = f(x^{*}) + \triangledown f(x^ {*})^T(x - x^{*}) \\ & + \frac 1 2 (x - x^{*})^T \triangledown^2 f(x^{*}) (x - x^{*}) \\ & + o(\|x - x^{*}\|^2) \end{align*}$$

  即目标函数f(x)在极小点附近与一个正定二次函数近似，所以对 正定二次函数好的算法，对一般目标函数也应该具有较好的性质

Linear Programming

数学模型

一般数学模型

线性规划问题（LP）可以抽象为一般的数学模型

$$\begin{array}{l} (\min_x, \max_x) & S=c_1 x_1 + c_2 x_2 + \cdots + c_n x_n \\ s.t. & \left \{ \begin{array} {l} a_{1,1} x_1 + a_{1,2} x_2 + \cdots + a_{1,n} x_n (\geq = \leq) b_1 \\ a_{2,1} x_1 + a_{2,2} x_2 + \cdots + a_{2,n} x_n (\geq = \leq) b_2 \\ \vdots \\ a_{m,1} x_1 + a_{m,2} x_2 + \cdots + a_{m,n} x_n (\geq = \leq) b_m \end{array} \right. \end{array}$$

• $S = c_1 x_1 + c_2 x_2 + \cdots + c_n x_n$：目标函数
• $x_1, x_2, …, x_n$：待求解变量
• $bi、c_i、a{ij}$：实常数
• $(\geq = \leq)$：在三种符号中取一种

标准形式

$$\begin{array}{l} \min_x & S=c_1 x_1 + c_2 x_2 + \cdots + c_n x_n \\ s.t. & a_{1,1} x_1 + a_{1,2} x_2 + \cdots + a_{1,n} x_n = b_1 \\ & \vdots \\ & a_{t,1} x_1 + a_{t,2} x_2 + \cdots + a_{t,n} x_n = b_t \\ & a_{t+1,1} x_1 + a_{t+1,2} x_2 + \cdots + a_{t+1, n} x_n \leq b_{t+1} \\ & \vdots \\ & a_{t+l,1} x_1 + a_{t+l,2} x_2 + \cdots + a_{t+l, n} x_n \leq b_{t+l} \\ \end{array}$$

• $\max_x$：目标函数取翻转换为$\min_x$

• $\geq$：不等式左右取反转换为$\leq$

• 线性规划一般模式都可以等价转换为标准形式

Simplex Method

单纯型法：利用线性规划极值点必然在单纯型顶点取得，不断迭代顶点求出极值

算法

• 初始化：标准化线性规划问题，建立初始表格
  • 最小化目标函数：目标函数系数取反，求极大
  • 不等式约束：加入松弛变量（代表不等式两端差值）
  • 变量非负：定义为两个非负变量之差
• 最优测试
  • 若目标行系数都为非负，得到最优解，迭代停止
  • 基变量解在右端列中，非基变量解为 0
• 确定主元列
  • 从目标行的前 $n$ 个单元格中选择一个非负单元格，确定主元列
  • 选择首个非负：解稳定，若存在最优解总是能取到
  • 选择绝对值最大：目标函数下降快，但有可能陷入死循环，无法得到最优解（不满足最优条件）

• 确定主元（分离变量）（行）

  • 对主元列所有正系数，计算右端项和其比值 $\Theta$ 比率
  • 最小 $\Theta$ 比率确定主元（行）（类似的为避免死循环，总是选择首个最小者）

• 转轴变换（建立新单纯形表）

  • 主元变 1：主元行所有变量除以主元
  • 主元列变 0：其余行减去其主元列倍主元行
  • 交换基变量：主元行变量标记为主元列对应变量

特点

• 算法时间效率
  • 极点规模随着问题规模指数增长，所以最差效率是指数级
  • 实际应用表明，对 $m$ 个约束、$n$ 个变量的问题，算法迭代次数在 $m$ 到 $3m$ 之间，每次迭代次数正比于 $nm$
• 迭代改进

Two-Phase Simplex Method

两阶段单纯形法：单纯型表中没有单元矩阵，无法方便找到基本可行解时使用

• 在给定问题的约束等式中加入人工变量，使得新问题具有明显可行解
• 利用单纯形法求解最小化新的线性规划问题

其他一些算法

• 大 M 算法
• Ellipsoid Method 椭球算法
  • 算法时间效率
    • 可以在多项式时间内对任意线性规划问题求解
    • 实际应用效果较单纯形法差，但是最差效率更好
• Karmarkar 算法
  • 内点法（迭代改进）

凸优化

$$\begin{array}{l} \min_x & f(x) \\ s.t. & g_i(x) \leq 0, i=1，2,\cdots,k \\ & h_i(x) = 0, i=1,2,\cdots,l \end{array}$$

• $f(x), g(x)$：$R^n$ 上连续可微的凸函数
• $h_i(x)$：$R^n$ 上仿射函数
• 仿射函数：满足 $f(x)=ax+b, a \in R^n, b \in R, x \in R^n$

二次规划

$$\begin{array}{l} \min_x & f(x)=\frac 1 2 x^TGx + c^Tx \\ s.t. & Ax \leq b \end{array}$$

• $G \in R^{n * n}$：$n$ 阶实对称矩阵
• $A \in R^{m n}$：$m n$ 实矩阵
• $b \in R^m$
• $c \in R^n$

• $G$ 正定

  • 此时目标函数 $f(x)$ 为凸函数
  • 凸二次规划
  • 问题有唯一全局最小值
  • 问题可可由椭球法在多项式时间内求解

• $G$ 半正定

  • 此时目标函数 $f(x)$ 为凸函数
  • 半定规划
  • 若约束条件可行域不空，且目标函数在此可行域有下界，则问题有全局最小值

• $G$非正定

  • 目标函数有多个平稳点（局部极小），NP-hard 问题

求解

• 椭球法
• 内点法
• 增广拉格朗日法
• 投影梯度法

二阶锥规划

$$\begin{array}{l} \min_x & f^Tx \\ s.t. & \|A_ix + b_i \|_2 \leq c_i^Tx + d_i, i=1,2,\cdots,m \\ & Bx=g \end{array}$$

• $f \in R^n$
• $A_i \in R^{n_i * n}$，$b_i \in R^{n_i}$，$c_i \in R^{n_i}$，$d_i \in R$
• $B \in R^{p * n}$，$g \in R^n$

• $A_i=0,i=1,\cdots,m$：退化为线性规划

• 一般的二阶规划可以转换为二阶锥规划

  $$X^TAX + qTX + C \leq 0 \Rightarrow \|A^{1/2}x + \frac 1 2 A^{-1/2}q\|^{1/2} \leq -\frac 1 4 q^TA^{-1}q - c$$

• 二阶锥规划可以使用内点法很快求解（多项式时间）

非线性最小二乘

$$\begin{align*} f(x) & = \frac 1 2 \sum_{i=1}^m r^2_i(x) \\ & = \frac 1 2 r(x) r^T(x) \end{align*}$$

• $r_i(x)$：通常为非线性函数
• $r(x) = (r_1(x), \cdots, r_n(x))^T$
• $x \in R^n, m \geq n$

• 考虑目标函数梯度、Hesse 矩阵

  $$\begin{align*} \nabla f(x) & = \sum_{i=1}^m \nabla r_i(x) r_i(x) \\ & = J(x)^T r(x) \\ \nabla^2 f(x) & = \sum_{i=1}^m \nabla r_i(x) r_i(x) + \sum_{i=1}^m r_i \nabla^2 r_i(x) \\ & = J(x)^T J(x) + \sum_{i=1}^m r_i(x) \nabla^2 r_i(x) \end{align*}$$

• $$J(x) = \begin{bmatrix} \frac {\partial r_1} {\partial x_1} & \frac {\partial r_1} {\partial x_2} & \cdots & \frac {\partial r_1} {\partial x_n} \\ \frac {\partial r_2} {\partial x_1} & \frac {\partial r_2} {\partial x_2} & \cdots & \frac {\partial r_2} {\partial x_n} \\ \vdots & \vdots & \ddots & \vdots \\ \frac {\partial r_m} {\partial x_1} & \frac {\partial r_m} {\partial x_2} & \cdots & \frac {\partial r_m} {\partial x_n} \end{bmatrix} = \begin{bmatrix} \nabla r_1(x)^T \\ \nabla r_2(x)^T \\ \vdots \\ \nabla r_m(x)^T \\ \end{bmatrix}$$ 为$r(x)$的 Jacobi 矩阵

Gauss-Newton 法

• 为简化计算，略去 Newton 法中 Hesse 矩阵中 $\sum_{i=1}^m r_i(x) \nabla^2 r_i(x)$ 项，即直接求解方程组

  $$J(x^{(k)})^T J(x^{(k)}) d = -J(x^{(k)})^T r(x^{(k)})$$

• 求解同一般 Newton 法

特点

• 实际问题中

  • 局部解 $x^{ }$ 对应的目标函数值 $f(x^{ })$ 接近 0 时，采用 Gauss-Newton 法效果较好，此时
    • $|r(x^{(k)})|$ 较小
    • 曲线$r_i(x)$接近直线
    • $\nabla^2 r_i(x) \approx 0$
  • 否则效果一般

• 矩阵 $J(x^{(k)})^T J(x^{(k)})$ 是半正定矩阵

  • 当 Jacobi 矩阵列满秩时为正定矩阵，此时虽然 $d^{(k)}$ 是下降方向，但仍需类似修正牛顿法增加一维搜索策略保证目标函数值不上升

Levenberg-Marquardt 方法

• 考虑到 $J(x^{(k)})$ 中各列线性相关、接近线性相关，求解 Newton-Gauss 方法中的方程组会出现困难，可以改为求解

  $$(J(x^{(k)})^T J(x^{(k)}) + vI) d = -J(x^{(k)})^T r(x^{(k)})$$

• $v$：迭代过程中需要调整的参数，LM 方法的关键即如何调整

定理1

• 若 $d(v)$ 是以上方程组的解，则 $|d(v)|^2$ 是 $v$ 的连续下降函数，且 $v \rightarrow +\infty, |d(v)| \rightarrow 0$

• $J(x^{(k)})^T J(x^{(k)})$ 是对称半正定矩阵，则存在正交阵

  $$(P^{(k)})^T J(x^{(k)})^T J(x^{(k)}) P^{(k)} = \Lambda^{(k)}$$

• 则可以解出 $|d(v)|^2$

• 增大 $v$ 可以限制 $|d^{(k)}|$，所以 LM 方法也被称为阻尼最小二乘法

定理2

• 若 $d(v)$ 是以上方程的解，则 $d(v)$ 是 $f(x)$ 在 $x^{(k)}$ 处的下降方向，且 $v \rightarrow + \infty$ 时，$d(v)$ 的方向与 $-J(x^{(k)})^T r(x^{(k)})$ 方向一致

• 下降方向：$\nabla f(x^{(k)}) d(v) < 0$ 即可
• 方向一致：夹角余弦

• $v$充分大时，LM 方法产生的搜索方向 $d^{(k)}$ 和负梯度方向一致

参数调整方法

• 使用梯度、近似 Hesse 矩阵定义二次函数 $$q(d) = f(x^{(k)}) + (J(x^{(k)})^T r(x^{(k)}))^T d + \frac 1 2 d^T (J(x^{(k)})^T J(x^{(k)})) d$$

• 其增量为

  $$\begin{align*} \Delta q^{(k)} & = q(d^{(k)}) - q(0) \\ & = (J(x^{(k)})^T r(x^{(k)}))^T d^{(k)} + \frac 1 2 (d^{(k)})^T (J(x^{(k)})^T J(x^{(k)})) d^{(k)} \end{align*}$$

• 目标函数增量

  $$\begin{align*} \Delta f^{(k)} & = f(x^{(k)} + d^{(k)}) - f(x^{(k)}) \\ & = f(x^{(k+1)}) - f(x^{(k)}) \end{align*}$$

• 定义$\gamma_k = \frac {\Delta f^{(k)}} {\Delta q^{(k)}}$

  • $\gamma_k$接近1说明$\Delta f^{(k)}$接近$\Delta q^{(k)}$

    • 即$f(x^{(k)} + d^{(k+1)})$接近$q(d^{(k)})$
    • 即$f(x)$在$x^{(k)}$附近接近二次函数
    • 即使用Gauss-Newton方法求解最小二乘问题效果较好
    • 即LM方法求解时$v$参数应该较小

  • $\gamma_k$接近0说明$\Delta f^{(k)}$与$\Delta q^{(k)}$ 近似程度不好

    • $d^{(k)}$不应取得过大，应减少$d^{(k)}$得模长
    • 应该增加参数$v$进行限制
    • 迭代方向趋近于负梯度方向

  • $\gamma_k$适中时，认为参数$v$选取合适，不做调整

    • 临界值通常为0.25、0.75

算法

1. 初始点 $x^{(1)}$、初始参数 $v$（小值）、精度要求 $\epsilon$，置 $k=k+1$

2. 若 $|J(x^{(k)})^T r(x^{(k)})| < \epsilon$，则停止计算，得到问题解 $x^{(k)}$，否则求解线性方程组

   $$(J(x^{(k)})^T J(x^{(k)}) + v_kI) d = -J(x^{(k)})^T r(x^{(k)})$$

   得到 $d^{(k)}$

3. 置 $x^{(k+1)} = x^{(k)} + d^{(k)}$，计算 $\gamma_k$

4. 考虑 $\gamma$

   • $\gamma < 0.25$，置$v_{k+1} = 4 v_k$
   • $\gamma > 0.75$，置$v_{k+1} = v_k / 2$
   • 否则置$v_{k+1} = v_k$

5. 置k=k+1，转2

其他问题

整形规划

整形规划：求线性函数的最值，函数包含若干整数变量，并且满足线性等式、不等式的有限约束

Unregularized Least Squares Learning Problem

$$w_T = \frac \gamma n \sum_{i=0}^{T-1} (I - \frac \gamma n {\hat X}^T \hat X)^i {\hat X}^T \hat Y$$

• $\gamma$：被引入保证 $|I - \frac \gamma n {\hat X}^T \hat X| < 1$

策略

• 考虑

  $$\min_w I_s(w) = \frac 1 {2n} \|\hat X w - \hat Y\|^2$$

• 将$w_{t+1}$带入$I_s(w)$即可证明每次迭代$I_s(w)$减小

  $$w_0 = 0 \\ w_{t+1} = (I - \frac \gamma n {\hat X}^T \hat X)w_t + \frac \gamma n {\hat X}^T \hat Y$$

正定二次目标函数

$$min f(x) = \frac 1 2 x^T G x + r^T x + \sigma$$

非线性最小二乘

$$\begin{align*} f(x) & = \frac 1 2 \sum_{i=1}^m r^2_i(x) \\ & = \frac 1 2 r(x) r^T(x) \end{align*}$$

• $r_i(x)$：通常为非线性函数
• $r(x) = (r_1(x), \cdots, r_n(x))^T$
• $x \in R^n, m \geq n$

则

$$\begin{align*} \nabla f(x) & = \sum_{i=1}^m \nabla r_i(x) r_i(x) \\ & = J(x)^T r(x) \\ \nabla^2 f(x) & = \sum_{i=1}^m \nabla r_i(x) r_i(x) + \sum_{i=1}^m r_i \nabla^2 r_i(x) \\ & = J(x)^T J(x) + \sum_{i=1}^m r_i(x) \nabla^2 r_i(x) \end{align*}$$

• $$J(x) = \begin{bmatrix} \frac {\partial r_1} {\partial x_1} & \frac {\partial r_1} {\partial x_2} & \cdots & \frac {\partial r_1} {\partial x_n} \\ \frac {\partial r_2} {\partial x_1} & \frac {\partial r_2} {\partial x_2} & \cdots & \frac {\partial r_2} {\partial x_n} \\ \vdots & \vdots & \ddots & \vdots \\ \frac {\partial r_m} {\partial x_1} & \frac {\partial r_m} {\partial x_2} & \cdots & \frac {\partial r_m} {\partial x_n} \end{bmatrix} = \begin{bmatrix} \nabla r_1(x)^T \\ \nabla r_2(x)^T \\ \vdots \\ \nabla r_m(x)^T \\ \end{bmatrix}$$ 为$r(x)$的Jacobi矩阵

Gauss-Newton法

Newton法中为简化计算，略去其Hesse矩阵中 $\sum_{i=1}^m r_i(x) \nabla^2 r_i(x)$项，即直接求解 方程组

$$J(x^{(k)})^T J(x^{(k)}) d = -J(x^{(k)})^T r(x^{(k)})$$

算法

同Newton法，仅求解Newton方程改为求解以上方程组

特点

• 实际问题中

  • 局部解$x^{ }$对应的目标函数值$f(x^{ })$接近0 时，$|r(x^{(k)})|$较小
  • 曲线$r_i(x)$接近直线， $\nabla^2 r_i(x) \approx 0$

  采用Gauss-Newton法效果较好，否则效果一般

• 矩阵$J(x^{(k)})^T J(x^{(k)})$是半正定矩阵，当Jacobi矩阵 列满秩时为正定矩阵，此时虽然$d^{(k)}$是下降方向，但仍需 类似修正牛顿法增加一维搜索策略保证目标函数值不上升

Levenberg-Marquardt方法

但$J(x^{(k)})$中各列线性相关、接近线性相关，则求解 Newton-Gauss方法中的方程组会出现困难，可以改为求解

$$(J(x^{(k)})^T J(x^{(k)}) + vI) d = -J(x^{(k)})^T r(x^{(k)})$$

• $v$：迭代过程中需要调整的参数，LM方法的关键即如何调整

定理1

• 若$d(v)$是以上方程组的解，则$|d(v)|^2$是$v$的连续下降 函数，且$v \rightarrow +\infty, |d(v)| \rightarrow 0$

• $J(x^{(k)})^T J(x^{(k)})$是对称半正定矩阵，则存在正交阵

  $$(P^{(k)})^T J(x^{(k)})^T J(x^{(k)}) P^{(k)} = \Lambda^{(k)}$$

• 则可以解出$|d(v)|^2$

• 增大$v$可以限制$|d^{(k)}|$，所以LM方法也被称为阻尼最小 二乘法

定理2

• 若$d(v)$是以上方程的解，则$d(v)$是$f(x)$在$x^{(k)}$处的 下降方向，且$v \rightarrow + \infty$时，$d(v)$的方向与 $-J(x^{(k)})^T r(x^{(k)})$方向一致

• 下降方向：$\nabla f(x^{(k)}) d(v) < 0$即可
• 方向一致：夹角余弦

• $v$充分大时，LM方法产生的搜索方向$d^{(k)}$和负梯度方向 一致

参数调整方法

使用梯度、近似Hesse矩阵定义二次函数

$$q(d) = f(x^{(k)}) + (J(x^{(k)})^T r(x^{(k)}))^T d + \frac 1 2 d^T (J(x^{(k)})^T J(x^{(k)})) d$$

• 其增量为

  $$\begin{align*} \Delta q^{(k)} & = q(d^{(k)}) - q(0) \\ & = (J(x^{(k)})^T r(x^{(k)}))^T d^{(k)} + \frac 1 2 (d^{(k)})^T (J(x^{(k)})^T J(x^{(k)})) d^{(k)} \end{align*}$$

• 目标函数增量

  $$\begin{align*} \Delta f^{(k)} & = f(x^{(k)} + d^{(k)}) - f(x^{(k)}) \\ & = f(x^{(k+1)}) - f(x^{(k)}) \end{align*}$$

• 定义$\gamma_k = \frac {\Delta f^{(k)}} {\Delta q^{(k)}}$

• $\gamma_k$接近1说明$\Delta f^{(k)}$接近$\Delta q^{(k)}$

  • 即$f(x^{(k)} + d^{(k+1)})$接近$q(d^{(k)})$
  • 即$f(x)$在$x^{(k)}$附近接近二次函数
  • 即使用Gauss-Newton方法求解最小二乘问题效果较好
  • 即LM方法求解时$v$参数应该较小

• $\gamma_k$接近0说明$\Delta f^{(k)}$与$\Delta q^{(k)}$ 近似程度不好

  • $d^{(k)}$不应取得过大，应减少$d^{(k)}$得模长
  • 应该增加参数$v$进行限制
  • 迭代方向趋近于负梯度方向

• $\gamma_k$适中时，认为参数$v$选取合适，不做调整

  • 临界值通常为0.25、0.75

算法

1. 初始点$x^{(1)}$、初始参数$v$（小值）、精度要求$\epsilon$ ，置k=k+1

2. 若$|J(x^{(k)})^T r(x^{(k)})| < \epsilon$，则停止计算， 得到问题解$x^{(k)}$，否则求解线性方程组

   $$(J(x^{(k)})^T J(x^{(k)}) + v_kI) d = -J(x^{(k)})^T r(x^{(k)})$$

   得到$d^{(k)}$

3. 置$x^{(k+1)} = x^{(k)} + d^{(k)}$，计算$\gamma_k$

4. 若

   • $\gamma < 0.25$，置$v_{k+1} = 4 v_k$
   • $\gamma > 0.75$，置$v_{k+1} = v_k / 2$
   • 否则置$v_{k+1} = v_k$

5. 置k=k+1，转2