欢迎访问 生活随笔！
TAG聚合

生活随笔

当前位置： 首页 > 编程资源 > 编程问答 >内容正文

编程问答

UA SIE545 优化理论基础 例题 对偶函数的凸性与次梯度计算

发布时间：2025/4/14 编程问答 28 豆豆
生活随笔 收集整理的这篇文章主要介绍了 UA SIE545 优化理论基础 例题 对偶函数的凸性与次梯度计算 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

UA SIE545 优化理论基础 例题 对偶函数的凸性与次梯度计算

例 考虑对偶函数
θ(u1,u2)=min⁡x12+x22≤4x1(2−u1)+x2(3−u2)\theta(u_1,u_2) = \min_{x_1^2+x_2^2 \le 4} x_1(2-u_1)+x_2(3-u_2)θ(u1​,u2​)=x12​+x22​≤4min​x1​(2−u1​)+x2​(3−u2​)它是凸函数还是凹函数？计算它在(2,3)(2,3)(2,3)处的次梯度。

分析 这个对偶函数对应的原优化问题是
min⁡(x1,x2)∈X2x1+3x2s.t.x1≥0,x2≥0X={(x1,x2):x12+x22≤4}\min_{(x_1,x_2) \in X}2x_1+3x_2 \\ s.t.\ \ x_1 \ge0,x_2 \ge 0 \\ X = \{(x_1,x_2):x_1^2+x_2^2 \le 4\}(x1​,x2​)∈Xmin​2x1​+3x2​s.t.  x1​≥0,x2​≥0X={(x1​,x2​):x12​+x22​≤4}

不难验证这个对偶问题满足强对偶条件，因此原优化与对偶优化的最优值是相等的。

解
第一问：判断对偶函数的凸性，有两种方法：

  • 直接法：按照凸性的定义直接验证对偶函数是不是凸函数；
  • 解析法：求解出对偶函数的表达式，再判断对偶函数的凸性。

    • (i) 直接法：考虑u=(u1,u2),v=(v1,v2),λ∈(0,1)u = (u_1,u_2),v=(v_1,v_2), \lambda \in (0,1)u=(u1​,u2​),v=(v1​,v2​),λ∈(0,1)，θ\thetaθ的定义中，目标函数可以写成
    λθ(u)+(1−λ)θ(v)=min⁡x∈Xλ[x1(2−u1)+x2(3−u2)]+min⁡x∈X(1−λ)[x1(2−v1)+x2(3−v2)]≤min⁡x∈Xλ[x1(2−u1)+x2(3−u2)]+(1−λ)[x1(2−v1)+x2(3−v2)]=θ(λu+(1−λ)v)\lambda \theta(u)+(1-\lambda)\theta(v) \\ =\min_{x \in X}\lambda[x_1(2-u_1)+x_2(3-u_2)]+\min_{x \in X}(1-\lambda)[x_1(2-v_1)+x_2(3-v_2)] \\ \le \min_{x \in X} \lambda[x_1(2-u_1)+x_2(3-u_2)]+(1-\lambda)[x_1(2-v_1)+x_2(3-v_2)] \\ = \theta(\lambda u + (1-\lambda)v)λθ(u)+(1−λ)θ(v)=x∈Xmin​λ[x1​(2−u1​)+x2​(3−u2​)]+x∈Xmin​(1−λ)[x1​(2−v1​)+x2​(3−v2​)]≤x∈Xmin​λ[x1​(2−u1​)+x2​(3−u2​)]+(1−λ)[x1​(2−v1​)+x2​(3−v2​)]=θ(λu+(1−λ)v)

    于是θ\thetaθ是凹函数；

    (ii) 解析法：考虑求解θ(u1,u2)\theta(u_1,u_2)θ(u1​,u2​)的表达式，把x1,x2x_1,x_2x1​,x2​消掉，
    θ(u1,u2)=min⁡x12+x22≤4x1(2−u1)+x2(3−u2)\theta(u_1,u_2) = \min_{x_1^2+x_2^2 \le 4} x_1(2-u_1)+x_2(3-u_2)θ(u1​,u2​)=x12​+x22​≤4min​x1​(2−u1​)+x2​(3−u2​)这个优化目标函数是线性函数、可行域是圆，可以用几何法求解，当然也可以用代数法，我们先考虑代数法：

    记v=[2−u1,3−u2]Tv = [2-u_1,3-u_2]^Tv=[2−u1​,3−u2​]T，则
    θ(u1,u2)=min⁡{xTv:∥x∥≤2}\theta(u_1,u_2) = \min\{x^Tv: \left\| x \right\| \le 2\}θ(u1​,u2​)=min{xTv:∥x∥≤2}

    根据Cauchy-Schwarz不等式，−∥x∥∥v∥≤xTv≤∥x∥∥v∥-\left\| x \right\| \left\| v \right\| \le x^Tv \le \left\| x \right\| \left\| v \right\|−∥x∥∥v∥≤xTv≤∥x∥∥v∥，因此
    θ(u1,u2)≥min⁡{−∥x∥∥v∥:∥x∥≤2}=−2∥v∥,∀u1,u2\theta(u_1,u_2) \ge \min\{-\left\| x \right\| \left\| v \right\|: \left\| x \right\| \le 2\}=-2\left\| v \right\|,\forall u_1,u_2θ(u1​,u2​)≥min{−∥x∥∥v∥:∥x∥≤2}=−2∥v∥,∀u1​,u2​当且仅当x=−2v∥v∥x = -\frac{2v}{ \left\| v \right\|}x=−∥v∥2v​时取等。因此
    θ(u1,u2)=−2∥v∥=−2(2−u1)2+(3−u2)2\theta(u_1,u_2)=-2\left\| v \right\| = -2\sqrt{(2-u_1)^2+(3-u_2)^2}θ(u1​,u2​)=−2∥v∥=−2(2−u1​)2+(3−u2​)2​

    不难验证这个是凹函数；

    接下来演示一下几何法求θ(u1,u2)\theta(u_1,u_2)θ(u1​,u2​)的表达式。
    θ(u1,u2)=min⁡x12+x22≤4x1(2−u1)+x2(3−u2)\theta(u_1,u_2) = \min_{x_1^2+x_2^2 \le 4} x_1(2-u_1)+x_2(3-u_2)θ(u1​,u2​)=x12​+x22​≤4min​x1​(2−u1​)+x2​(3−u2​)

    可行域是圆心在原点，半径为2的圆，目标函数是斜率为2−u1u2−3\frac{2-u_1}{u_2-3}u2​−32−u1​​的直线族的斜率，如果2−u1u2−3=0\frac{2-u_1}{u_2-3}=0u2​−32−u1​​=0，则x1=0,x2=2x_1=0,x_2=2x1​=0,x2​=2时函数值最小，此时θ(u1,u2)=6−2u2\theta(u_1,u_2)=6-2u_2θ(u1​,u2​)=6−2u2​；如果2−u1u2−3<0\frac{2-u_1}{u_2-3}<0u2​−32−u1​​<0，则直线与圆在第三象限相切时函数值最小，对于圆而言，
    2x1dx1+2x2dx2=0⇒dx2dx1=−x1x2=2−u1u2−32x_1dx_1+2x_2dx_2 = 0 \Rightarrow \frac{dx_2}{dx_1}=-\frac{x_1}{x_2}=\frac{2-u_1}{u_2-3}2x1​dx1​+2x2​dx2​=0⇒dx1​dx2​​=−x2​x1​​=u2​−32−u1​​

    再根据x12+x22=4x_1^2+x_2^2 = 4x12​+x22​=4，不难解出
    {x12=4(2−u1)2(2−u1)2+(3−u2)2x22=4(3−u2)2(2−u1)2+(3−u2)2\begin{cases} x_1^2 = \frac{4(2-u_1)^2}{(2-u_1)^2+(3-u_2)^2} \\ x_2^2 = \frac{4(3-u_2)^2}{(2-u_1)^2+(3-u_2)^2} \end{cases}{x12​=(2−u1​)2+(3−u2​)24(2−u1​)2​x22​=(2−u1​)2+(3−u2​)24(3−u2​)2​​

    如果2−u1u2−3>0\frac{2-u_1}{u_2-3}>0u2​−32−u1​​>0，则直线与圆在第四象限相切时函数值最小，计算过程与上面这个相同。可以算出
    θ(u1,u2)=−2(2−u1)2+(3−u2)2\theta(u_1,u_2)=-2\sqrt{(2-u_1)^2+(3-u_2)^2}θ(u1​,u2​)=−2(2−u1​)2+(3−u2​)2​

    显然这个比θ(u1,u2)=6−2u2\theta(u_1,u_2)=6-2u_2θ(u1​,u2​)=6−2u2​更小，综上，
    θ(u1,u2)=−2(2−u1)2+(3−u2)2\theta(u_1,u_2)=-2\sqrt{(2-u_1)^2+(3-u_2)^2}θ(u1​,u2​)=−2(2−u1​)2+(3−u2​)2​

    第二问：计算在(2,3)(2,3)(2,3)处的次梯度。次梯度的定义是
    f:S→Rf:S \to \mathbb{R}f:S→R is concave where SSS is a nonempty convex set. Then ξ\xiξ is called subgradient of fff at xˉ\bar xxˉ if
    f(x)≤f(xˉ)+ξT(x−xˉ),∀x∈Sf(x) \le f(\bar x)+\xi^T(x-\bar x),\forall x \in Sf(x)≤f(xˉ)+ξT(x−xˉ),∀x∈S

    根据这个定义，假设ξ\xiξ是次梯度，则
    θ(u1,u2)≤θ(2,3)+ξT[u1−2,u2−3]T≤ξT[u1−2,u2−3]T\theta(u_1,u_2) \le \theta(2,3)+\xi^T[u_1-2,u_2-3]^T \\ \le \xi^T[u_1-2,u_2-3]^Tθ(u1​,u2​)≤θ(2,3)+ξT[u1​−2,u2​−3]T≤ξT[u1​−2,u2​−3]T

    根据第一问的不同证法，第二问也有两种不同的计算方法：

    方法一：如果第一问用的直接法，那么我们观察一下
    θ(u1,u2)=min⁡x12+x22≤4x1(2−u1)+x2(3−u2)⇒∀x12+x22≤4,θ(u1,u2)≤xT[u1−2,u2−3]T\theta(u_1,u_2) = \min_{x_1^2+x_2^2 \le 4} x_1(2-u_1)+x_2(3-u_2) \\ \Rightarrow \forall x_1^2+x_2^2 \le 4,\theta(u_1,u_2) \le x^T[u_1-2,u_2-3]^Tθ(u1​,u2​)=x12​+x22​≤4min​x1​(2−u1​)+x2​(3−u2​)⇒∀x12​+x22​≤4,θ(u1​,u2​)≤xT[u1​−2,u2​−3]T

    把xxx换成ξ\xiξ就是我们需要的结果，于是∥ξ∥≤2\left\| \xi \right\| \le 2∥ξ∥≤2，次梯度为
    {ξ:∥ξ∥≤2}\{\xi:\left\| \xi \right\| \le 2\}{ξ:∥ξ∥≤2}

    方法二：如果第一问用的解析法，那么我们已经知道了θ(u1,u2)=−2(2−u1)2+(3−u2)2\theta(u_1,u_2)=-2\sqrt{(2-u_1)^2+(3-u_2)^2}θ(u1​,u2​)=−2(2−u1​)2+(3−u2​)2​

    于是我们要做的是求解：
    −2(2−u1)2+(3−u2)2≤ξT[u1−2,u2−3]T-2\sqrt{(2-u_1)^2+(3-u_2)^2} \le \xi^T[u_1-2,u_2-3]^T−2(2−u1​)2+(3−u2​)2​≤ξT[u1​−2,u2​−3]T

    也就是2∥v∥≥ξTv2 \left\| v \right\| \ge \xi^Tv2∥v∥≥ξTv，根据Cauchy-Schwarz定理，∥ξ∥≤2\left\| \xi \right\| \le 2∥ξ∥≤2时对所有v∈R2v \in \mathbb{R}^2v∈R2成立，所以次梯度为
    {ξ:∥ξ∥≤2}\{\xi:\left\| \xi \right\| \le 2\}{ξ:∥ξ∥≤2}

    总结

    以上是生活随笔为你收集整理的UA SIE545 优化理论基础 例题 对偶函数的凸性与次梯度计算的全部内容，希望文章能够帮你解决所遇到的问题。

    如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。