Skip to Content
Convex Optimization

Convex Optimization

2019-01-24legacy assets may be incomplete

凸优化

  • 拉格朗日乘子法
    • 约束曲面上任意点 xx, ∇g(x)\nabla g(x) 正交于约束曲面
    • 最优点 x∗x^*, ∇f(x∗)\nabla f(x^*) 正交与约束曲面
    • 拉格朗日乘子 λ≠0\lambda\not=0
    • 拉格朗日函数 L(x,λ)=f(x)+λg(x)L(x,\lambda) = f(x)+\lambda g(x)
      • 优化 f(x)f(x) -> 优化 L(x,λ)L(x,\lambda)
  • 主问题，最优解 p∗p^*
min⁡xf(x)s.t.hi(x)=0(i=1,...,m)gj(x)≤0(j=1,...,n)\begin{aligned} \min_x & f(x) \newline s.t. & h_i(x)=0 & (i=1,...,m) \newline & g_j(x)\leq 0 & (j=1,...,n) \end{aligned}
  • 引入拉格朗日乘子和 KKT 条件 (Karush-Kuhn-Tucker)
min⁡L(x,λ,μ)=f(x)+∑i=1mλihi(x)+∑j=1nμjgj(x)gj(x)≤0μj≥0μjgj(x)=0\begin{aligned} \min L(x,\lambda,\mu)=f(x)+\sum_{i=1}^m\lambda_ih_i(x)+\sum_{j=1}^n\mu_jg_j(x)\newline g_j(x)\leq 0\newline \mu_j\geq0\newline \mu_jg_j(x)=0 \end{aligned}
  • sup⁡\sup 上限函数， inf⁡\inf 下限函数
  • 拉格朗日对偶函数：Γ(λ,μ)=inf⁡x∈DL(x,λ,μ)\Gamma(\lambda,\mu)=\inf_{x\in D}L(x,\lambda,\mu)
    • Γ(λ,μ)≤L(x,λ,mu)≤f(x)≤p∗,x∈D\Gamma(\lambda,\mu)\leq L(x,\lambda,mu)\leq f(x)\leq p^*,x\in D
    • LL 对 xx 求导后令之为 0，带入得对偶问题
  • 对偶问题 （凸优化问题），最优解 d∗d^*
max⁡λ,μΓ(λ,μ)s.t.μ⪰0\begin{aligned} & \max_{\lambda,\mu}\Gamma(\lambda,\mu)\newline s.t. & \mu \succeq 0 \end{aligned}
  • 弱对偶性成立：d∗≤p∗d^*\leq p^*
  • 强对偶性：d∗=p∗d^*=p^*
    • 主问题为凸优化问题，则其可行域中至少有一点使不等式约束严格成立
    • 强对偶性成立时，将 LL 对原变量和对偶变量求导并另其为零，即得到原变量和对偶变量的数值关系

牛顿法

  • 求函数 f(x)f(x) 零点：xn+1=xn−f(x)f′(x)x_{n+1}=x_n-\frac{f(x)}{f'(x)}
  • 最小化：βt+1=βt−(∂2l(β)∂β∂βT)−1∂l(β)∂β\beta^{t+1}=\beta^t-(\frac{\partial^2 l(\beta)}{\partial\beta\partial\beta^T})^{-1}\frac{\partial l(\beta)}{\partial\beta}
  • 缺点
    • 每一步开销大
    • 依赖初始值

梯度下降

  • f(x+Δx)≃f(x)+ΔxT∇f(x)f(x+\Delta x)\simeq f(x)+\Delta x^T\nabla f(x)
  • Δx=−γ∇f(x)\Delta x=-\gamma\nabla f(x)

其它

  • lim⁡x→∞(1+1x)x=e\lim_{x\rightarrow\infty}(1+\frac{1}{x})^x=e