当前位置:   article > 正文

最优化理论与方法-第十讲-对偶理论的基本性质和割平面法

最优化理论与方法-第十讲-对偶理论的基本性质和割平面法

1. 向量化拉格朗日对偶函数

( D )      max ⁡    d ( λ , μ ) s t .      λ i ≥ 0 , i = 1 , ⋯   , m ,      d ( λ , μ ) = min ⁡ x ∈ X { f ( x ) + ∑ i = 1 m λ i g i ( x ) + ∑ i = 1 l μ i h i ( x ) }

(D)maxd(λ,μ)st.λi0,i=1,,m,d(λ,μ)=minxX{f(x)+i=1mλigi(x)+i=1lμihi(x)}
(D)maxd(λ,μ)st.λi0,i=1,,m,d(λ,μ)=xXmin{f(x)+i=1mλigi(x)+i=1lμihi(x)}

  • 为了方便向量的表达方式,我们记:
         g ( x ) = ( g 1 ( x ) , g 2 ( x ) , ⋯   , g m ( x ) ) T      h ( x ) = ( h 1 ( x ) , h 2 ( x ) , ⋯   , h l ( x ) ) T      λ = ( λ 1 , λ 2 , ⋯   , λ m )      μ = ( μ 1 , μ 2 , ⋯   , μ l )
    g(x)=(g1(x),g2(x),,gm(x))Th(x)=(h1(x),h2(x),,hl(x))Tλ=(λ1,λ2,,λm)μ=(μ1,μ2,,μl)
    g(x)=(g1(x),g2(x),,gm(x))Th(x)=(h1(x),h2(x),,hl(x))Tλ=(λ1,λ2,,λm)μ=(μ1,μ2,,μl)
  • 整理上式可得:
    ( D )      max ⁡    d ( λ , μ ) s t .      λ i ≥ 0 , i = 1 , ⋯   , m ,      d ( λ , μ ) = min ⁡ x ∈ X { f ( x ) + λ T g ( x ) + μ T h ( x ) }
    (D)maxd(λ,μ)st.λi0,i=1,,m,d(λ,μ)=minxX{f(x)+λTg(x)+μTh(x)}
    (D)maxd(λ,μ)st.λi0,i=1,,m,d(λ,μ)=xXmin{f(x)+λTg(x)+μTh(x)}

2. 对偶问题是凹函数

  • 对偶问题(D)问题,对偶函数是函数

  • 这里的函数图像如下:这个定义国内外相反,真有点坑,容易糊涂
    在这里插入图片描述

  • 需要证明对偶函数 d ( λ , μ ) d(\lambda,\mu) d(λ,μ)是凹函数
    d ( λ , μ ) = min ⁡ x ∈ X { f ( x ) + λ T g ( x ) + μ T h ( x ) }

    d(λ,μ)=minxX{f(x)+λTg(x)+μTh(x)}
    d(λ,μ)=xXmin{f(x)+λTg(x)+μTh(x)}

  • 假设X为有限个值 X = { x 1 , x 2 , ⋯   , x n } X=\{x_1,x_2,\cdots,x_n\} X={x1,x2,,xn},那么对偶函数,就是从N个函数中求最小值
    d ( λ , μ ) = min ⁡ i = 1 , ⋯   , n { f ( x i ) + λ T g ( x i ) + μ T h ( x i ) }

    d(λ,μ)=mini=1,,n{f(xi)+λTg(xi)+μTh(xi)}
    d(λ,μ)=i=1,,nmin{f(xi)+λTg(xi)+μTh(xi)}

  • 对于每个函数,一旦 x i x_i xi确定后, d ( λ , μ ) d(\lambda,\mu) d(λ,μ)就只是一个关于 λ , μ \lambda,\mu λ,μ的线性函数,也就是分段最小值函数,详见下图:
    在这里插入图片描述

  • 由上图可得,对偶函数是凹函数,是凸问题。

3. 对偶问题转换

  • 我们有如下对偶问题:
    ( D )      max ⁡    d ( λ , μ ) s t .      λ i ≥ 0 , i = 1 , ⋯   , m ,      d ( λ , μ ) = min ⁡ x ∈ X { f ( x ) + λ T g ( x ) + μ T h ( x ) }
    (D)maxd(λ,μ)st.λi0,i=1,,m,d(λ,μ)=minxX{f(x)+λTg(x)+μTh(x)}
    (D)maxd(λ,μ)st.λi0,i=1,,m,d(λ,μ)=xXmin{f(x)+λTg(x)+μTh(x)}
  • 定义 θ = d ( λ , μ ) \theta = d(\lambda,\mu) θ=d(λ,μ)
    ( D )      max ⁡    θ s t .      λ i ≥ 0 , i = 1 , ⋯   , m ,      θ = d ( λ , μ ) = min ⁡ x ∈ X { f ( x ) + λ T g ( x ) + μ T h ( x ) }
    (D)maxθst.λi0,i=1,,m,θ=d(λ,μ)=minxX{f(x)+λTg(x)+μTh(x)}
    (D)maxθst.λi0,i=1,,m,θ=d(λ,μ)=xXmin{f(x)+λTg(x)+μTh(x)}
  • 因为最终求 θ \theta θ的最大值,所以可以缩放 θ = d ( λ , μ ) → θ ≤ d ( λ , μ ) \theta=d(\lambda,\mu)\to \theta\le d(\lambda,\mu) θ=d(λ,μ)θd(λ,μ)
    ( D )      max ⁡    θ s t .      λ i ≥ 0 , i = 1 , ⋯   , m ,      θ ≤ d ( λ , μ ) = min ⁡ x ∈ X { f ( x ) + λ T g ( x ) + μ T h ( x ) }
    (D)maxθst.λi0,i=1,,m,θd(λ,μ)=minxX{f(x)+λTg(x)+μTh(x)}
    (D)maxθst.λi0,i=1,,m,θd(λ,μ)=xXmin{f(x)+λTg(x)+μTh(x)}
  • 整理后可得:
    ( D )      max ⁡    θ      θ ≤ min ⁡ x ∈ X { f ( x ) + λ T g ( x ) + μ T h ( x ) } s t .      λ ≥ 0
    (D)maxθθminxX{f(x)+λTg(x)+μTh(x)}st.λ0
    (D)maxθθxXmin{f(x)+λTg(x)+μTh(x)}st.λ0
  • 如果最终存在一个 θ ˉ \bar{\theta} θˉ是上面的最大值,那么就是最优值
    θ ˉ = v ( D )
    θ¯=v(D)
    θˉ=v(D)
  • 假设X有有限个解 X = { x 1 , x 2 , ⋯   , x n } X=\{x_1,x_2,\cdots,x_n\} X={x1,x2,,xn},那么存在n个不等式,可以用scipy的库进行线性规划问题的求解,假设X有无穷多解,那么代表的就是无穷多个线性不等式。
         θ ≤ min ⁡ i = 1 , ⋯   , n { f ( x i ) + λ T g ( x i ) + μ T h ( x i ) } s t .      λ ≥ 0
    θmini=1,,n{f(xi)+λTg(xi)+μTh(xi)}st.λ0
    θi=1,,nmin{f(xi)+λTg(xi)+μTh(xi)}st.λ0
  • 我们假设 X 0 = { x 1 , x 3 } X_0=\{x_1,x_3\} X0={x1,x3},现在只有两个约束,那么这个得到的最大值肯定大于N个约束的的最大值 θ ˉ \bar{\theta} θˉ,因为约束越多,其定义域的范围越小,那么值域就越小,最大值也就越小
    θ 0 ≥ θ ˉ
    θ0θ¯
    θ0θˉ
  • 我们记最优解为 ( λ 0 , μ 0 , θ 0 ) (\lambda_0,\mu_0,\theta_0) (λ0,μ0,θ0),现在求 d ( λ 0 , μ 0 ) d(\lambda_0,\mu_0) d(λ0,μ0)
    d ( λ 0 , μ 0 ) = min ⁡ x ∈ X { f ( x ) + λ 0 T g ( x ) + μ 0 T h ( x ) }
    d(λ0,μ0)=minxX{f(x)+λ0Tg(x)+μ0Th(x)}
    d(λ0,μ0)=xXmin{f(x)+λ0Tg(x)+μ0Th(x)}
  • 假设存在一个 x 0 x_0 x0 满足如下条件:
    g ( x 0 ) ≤ 0 , h ( x 0 ) = 0 , λ 0 T g ( x 0 ) = 0
    g(x0)0,h(x0)=0,λ0Tg(x0)=0
    g(x0)0,h(x0)=0,λ0Tg(x0)=0
  • 反正上面都为0,等式左右相加不影响:
    f ( x 0 ) = f ( x 0 ) + λ 0 T g ( x 0 ) + μ 0 T h ( x 0 )
    f(x0)=f(x0)+λ0Tg(x0)+μ0Th(x0)
    f(x0)=f(x0)+λ0Tg(x0)+μ0Th(x0)
  • 我们定义 x 0 x_0 x0 d ( λ 0 , μ 0 ) d(\lambda_0,\mu_0) d(λ0,μ0)最优解,那么可得:
    d ( x 0 , λ 0 , μ 0 ) = f ( x 0 ) + λ 0 T g ( x 0 ) + μ 0 T h ( x 0 ) = f ( x 0 )
    d(x0,λ0,μ0)=f(x0)+λ0Tg(x0)+μ0Th(x0)=f(x0)
    d(x0,λ0,μ0)=f(x0)+λ0Tg(x0)+μ0Th(x0)=f(x0)
  • 则强对偶定理成立
  • d ( λ 0 , μ 0 ) = θ 0 d(\lambda_0,\mu_0)=\theta_0 d(λ0,μ0)=θ0,可得:
    d ( λ 0 , μ 0 ) = v ( D )
    d(λ0,μ0)=v(D)
    d(λ0,μ0)=v(D)

4. 外逼近法

4.1 步骤

  • step 0: 选取X的非空子集 X 1 X^1 X1,其中 X 1 X^1 X1包含有限个元素,令 k = 1 k=1 k=1
  • step 1: 求解线性规划问题:
    ( D )      max ⁡    θ      θ ≤ min ⁡ x ∈ X { f ( x ) + λ T g ( x ) + μ T h ( x ) } , ∀ x ∈ X k s t .      λ ≥ 0 记最优解为 ( λ k , μ k , θ k )
    (D)maxθθminxX{f(x)+λTg(x)+μTh(x)},xXkst.λ0(λk,μk,θk)
    (D)maxθθxXmin{f(x)+λTg(x)+μTh(x)},xXkst.λ0记最优解为(λk,μk,θk)
  • step 2: 求解相应的子问题:
    min ⁡ { f ( x ) + ( λ k ) T g ( x ) + ( μ k ) T h ( x ) ∣ x ∈ X } ;
    min{f(x)+(λk)Tg(x)+(μk)Th(x)|xX}
    min{f(x)+(λk)Tg(x)+(μk)Th(x) xX}
  • 记其最优解为 x k x^k xk,最优值为 d ( λ k , μ k ) d(\lambda^k,\mu^k) d(λk,μk)
  • step 3: x k x^k xk是原问题 ( P ) (P) (P)的可行解,且 ( λ k ) T g ( x k ) = 0 (\lambda^k)^Tg(x^k)=0 (λk)Tg(xk)=0,则算法终止, x k x^k xk ( λ k , μ k ) (\lambda^k,\mu^k) (λk,μk)分别是原问题P和对偶问题D的最优解,且最优值相等,若
    θ k = d ( λ k , μ k )
    θk=d(λk,μk)
    θk=d(λk,μk)

    则算法终止, ( λ k , μ k ) (\lambda^k,\mu^k) (λk,μk)即对偶问题的最优解,且最优值为 θ k \theta^k θk
  • step 4: X k + 1 = X k ∪ { x k } , k : = k + 1 X^{k+1}=X^k\cup\{x^k\},k:= k+1 Xk+1=Xk{xk},k:=k+1,转 step 1

4.2 注意事项

    1. X的子集合点总需要包含一个原问题的可行解,这样能保证 θ \theta θ有一个上界,使得迭代更好收敛。
      θ ≤ f ( x ) + λ T g ( x ) + μ T h ( x ) ≤ f ( x )
      θf(x)+λTg(x)+μTh(x)f(x)
      θf(x)+λTg(x)+μTh(x)f(x)
    1. X包含无穷多个解,为了方便迭代,我们可以动态去掉 X k X^k Xk中多余的解,加速迭代
    1. 割平面法,通过不断加约束来不断地缩小定义域,近似的逼近最优解。就像切西瓜一样,不断地切,最后切成我们想要的形状。
      在这里插入图片描述
  • 在最优解附近具有不稳定性,我们通常通过加正则项的方法进行正则化
  • 后续研究次梯度法和bound method
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/寸_铁/article/detail/863557
推荐阅读
相关标签
  

闽ICP备14008679号