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

生活随笔

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

编程问答

UA SIE545 优化理论基础4 对偶理论简介4 求解对偶问题的割平面算法

发布时间：2025/4/14 编程问答 53 豆豆
生活随笔 收集整理的这篇文章主要介绍了 UA SIE545 优化理论基础4 对偶理论简介4 求解对偶问题的割平面算法 小编觉得挺不错的,现在分享给大家,帮大家做个参考.

UA SIE545 优化理论基础4 对偶理论简介4 求解对偶问题的割平面算法

这一讲我们介绍一个求解对偶问题的算法——割平面算法(cutting plane algorithm)。

假设原问题为
min⁡x∈Xf(x)s.t.g(x)≤0,h(x)=0\min_{x \in X}f(x) \ \ s.t. \ \ g(x) \le 0,h(x)=0x∈Xmin​f(x)  s.t.  g(x)≤0,h(x)=0

假设f,g,hf,g,hf,g,h是连续函数，XXX是紧集。根据定义，这个优化的对偶问题是
max⁡u≥0θ(u,v)=max⁡u≥0min⁡x∈Xf(x)+uTg(x)+vTh(x)\max_{u \ge 0} \theta(u,v)=\max_{u \ge 0}\min_{x \in X} f(x)+u^Tg(x)+v^Th(x)u≥0max​θ(u,v)=u≥0max​x∈Xmin​f(x)+uTg(x)+vTh(x)

我们可以等价地把这个优化改写成：
max⁡z,u,vzs.t.z≤θ(u,v)=min⁡x∈Xf(x)+uTg(x)+vTh(x)u≥0\max_{z,u,v} z \\ s.t. \ z \le \theta(u,v)=\min_{x \in X} f(x)+u^Tg(x)+v^Th(x)\\u \ge 0z,u,vmax​zs.t. z≤θ(u,v)=x∈Xmin​f(x)+uTg(x)+vTh(x)u≥0

进一步，
max⁡z,u,vzs.t.z≤f(x)+uTg(x)+vTh(x),∀x∈Xu≥0\max_{z,u,v} z \\ s.t. \ z \le f(x)+u^Tg(x)+v^Th(x),\forall x \in X\\u \ge 0z,u,vmax​zs.t. z≤f(x)+uTg(x)+vTh(x),∀x∈Xu≥0

当给定xxx的值时，这个优化就是一个简单的线性规划，为了让这种替代可行，我们希望XXX是一个有限集，这样才能在有限步内结束循环。但一般XXX都不会是有限集，这时我们可以先给定一个xxx的初值，然后在每一次做完这个优化后，再去求解min⁡x∈Xf(x)+uTg(x)+vTh(x)\min_{x \in X} f(x)+u^Tg(x)+v^Th(x)minx∈X​f(x)+uTg(x)+vTh(x)这个问题，从而得到一个新的xxx，这样就避免了去遍历无限集XXX。基于这个思想，我们可以定义下面的算法：

  • 初始化：定义k=1k=1k=1，选择初值x0x_0x0​使得x0∈Xx_0 \in Xx0​∈X, g(x0)≤0,h(x0)=0g(x_0) \le 0,h(x_0)=0g(x0​)≤0,h(x0​)=0
  • 求解Master Program：(zk,uk,vk)=arg max⁡z,u,vzs.t.z≤f(x)+uTg(x)+vTh(x),∀x=x0,x1,⋯,xk−1u≥0(z_k,u_k,v_k)=\argmax_{z,u,v} z \\ s.t. z \le f(x)+u^Tg(x)+v^Th(x),\forall x=x_0,x_1,\cdots,x_{k-1} \\ u \ge 0(zk​,uk​,vk​)=z,u,vargmax​zs.t.z≤f(x)+uTg(x)+vTh(x),∀x=x0​,x1​,⋯,xk−1​u≥0
  • 求解subproblem: xk=arg min⁡x∈Xf(x)+ukTg(x)+vkTh(x)x_k = \argmin_{x \in X}f(x)+u^T_kg(x)+v^T_kh(x)xk​=x∈Xargmin​f(x)+ukT​g(x)+vkT​h(x)
  • 停止准则：如果zk=θ(uk,vk)=f(xk)+ukTg(xk)+vkTh(xk)z_k=\theta(u_k,v_k)=f(x_k)+u^T_kg(x_k)+v^T_kh(x_k)zk​=θ(uk​,vk​)=f(xk​)+ukT​g(xk​)+vkT​h(xk​)则停止循环，返回(uk,vk)(u_k,v_k)(uk​,vk​)；如果zk>θ(uk,vk)z_k>\theta(u_k,v_k)zk​>θ(uk​,vk​), 赋值k=k+1k=k+1k=k+1，回到第二步。

    • 例 用割平面法求解下面的优化的对偶问题
    min⁡(x1,x2)∈Xf(x1,x2)=(x1−2)2+x224s.t.g(x1,x2)=x1−72x2−1≤0X={(x1,x2):2x1+3x2=4}\min_{(x_1,x_2) \in X} f(x_1,x_2)= (x_1-2)^2+\frac{x_2^2}{4} \\ s.t. g(x_1,x_2)=x_1-\frac{7}{2}x_2-1 \le 0 \\ X = \{(x_1,x_2):2x_1+3x_2=4\}(x1​,x2​)∈Xmin​f(x1​,x2​)=(x1​−2)2+4x22​​s.t.g(x1​,x2​)=x1​−27​x2​−1≤0X={(x1​,x2​):2x1​+3x2​=4}

    找一个初始值x0=(54,12)x_0=(\frac{5}{4},\frac{1}{2})x0​=(45​,21​)，

    第一次循环：

    求解Master Problem
    max⁡z,u,vzs.t.z≤f(x0)+uTg(x0)+vTh(x0)=58−32uu≥0\max_{z,u,v} z \\ s.t. \ z \le f(x_0)+u^Tg(x_0)+v^Th(x_0)=\frac{5}{8}-\frac{3}{2}u\\u \ge 0z,u,vmax​zs.t. z≤f(x0​)+uTg(x0​)+vTh(x0​)=85​−23​uu≥0

    最优解为(z1,u1)=(58,0)(z_1,u_1)=(\frac{5}{8},0)(z1​,u1​)=(85​,0)。

    求解subproblem
    x1=arg min⁡x∈Xf(x)+ukTg(x)+vkTh(x)=arg min⁡x∈Xf(x)=(2,0)x_1 = \argmin_{x \in X}f(x)+u^T_kg(x)+v^T_kh(x) \\ =\argmin_{x \in X}f(x) = (2,0)x1​=x∈Xargmin​f(x)+ukT​g(x)+vkT​h(x)=x∈Xargmin​f(x)=(2,0)

    判断是否停止
    z1=58>θ(u1)=f(x1)=0z_1 = \frac{5}{8} >\theta(u_1)=f(x_1) = 0z1​=85​>θ(u1​)=f(x1​)=0，所以算法继续。

    第二次循环：
    求解Master Problem
    max⁡z,u,vzs.t.z≤f(x0)+uTg(x0)+vTh(x0)=58−32uz≤f(x1)+uTg(x1)+vTh(x1)=uu≥0\max_{z,u,v} z \\ s.t. \ z \le f(x_0)+u^Tg(x_0)+v^Th(x_0)=\frac{5}{8}-\frac{3}{2}u \\ z \le f(x_1)+u^Tg(x_1)+v^Th(x_1)= u \\u \ge 0z,u,vmax​zs.t. z≤f(x0​)+uTg(x0​)+vTh(x0​)=85​−23​uz≤f(x1​)+uTg(x1​)+vTh(x1​)=uu≥0

    最优解为(z2,u2)=(14,14)(z_2,u_2)=(\frac{1}{4},\frac{1}{4})(z2​,u2​)=(41​,41​)。

    。。。。

    然后按步骤继续循环即可！

    总结

    以上是生活随笔为你收集整理的UA SIE545 优化理论基础4 对偶理论简介4 求解对偶问题的割平面算法的全部内容，希望文章能够帮你解决所遇到的问题。

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