不等式约束的优化问题_欧陆娱乐-欧陆注册登录中心

不等式约束的优化问题

欧陆资讯 | 2024-05-26 09:12

本意是在论文阅读中反复遇到不等式约束条件的类似问题，不过可惜地是每次想用的时候，几乎总是卡壳，不能满意地解决此类问题，故在这汇总，加以整理，以期熟练掌握其中细节。
当然也有可能出现周志成老师博客指出的问题
在优化理论，Karush-Kuhn-Tucker (KKT)条件是非线性规划(nonlinear programming)最佳解的必要条件。KKT条件将Lagrange乘数法(Lagrange multipliers)所处理涉及束缚等式的约束优化问题推广至不等式。在实际应用上，KKT条件(方程组)一般不存在代数解，许多优化算法可供数值计算选用。而我恰好每次试图追寻代数解，这或许是我失败的原因之一。
当然我们可以考虑软件求解，的确是有效策略之一，但是注意也不是万能的，大多数采用人工干预，有时候能化繁为简，反而得到最终求解结果。如果过分依赖反而求不出来，结果有时候也不能轻易相信，至少要适当检验。否则内置算法出现bug造成的后果也不可估量。

由于是自学，本文很大部分依赖网络资源，如有读者，慎重阅读。如有错误，欢迎大佬指正。主要参考下面两篇文章：

周老师博客

Eureka：Karush-Kuhn-Tucker (KKT)条件

十分感谢他们的工作。后面会结合自己体会慢慢写出更好的分析。

解此类不等式当然方法不止一种，比如碰巧可以用一些微调整法。

在数学中，卡罗需-库恩-塔克条件（英文原名：Karush-Kuhn-Tucker Conditions 常见别名：KKT条件，Kuhn-Tucker条件）是在满足一些有规则的条件下，一个非线性规划（Nonlinear Programming）问题能有最优化解法的一个必要条件。这是一个广义化拉格朗日乘数的成果。
我们的问题的模型：考虑以下非线式最优化问题：
$~{\\displaystyle \\min \\limits _{x}\\;\\;f(x)}$
$~~~~~{\\displaystyle{\\mbox{Subject to: }}\\ }$
$~~~~~~~{\\displaystyle g_{i}(x)\\leq 0,h_{j}(x)=0}$
${\\displaystyle f(x)}$ 是需要最小化的函数，其中
${\\displaystyle g_{i}(x)\\ (i=1,\\ldots ,m)}$ 是不等式约束，
${\\displaystyle h_{j}(x)\\ (j=1,\\ldots ,l)}$ 是等式约束，
${\\displaystyle m}$ 和 ${\\displaystyle l}$ 分别为不等式约束和等式约束的数量。
不等式约束问题的必要和充分条件初见于卡罗需（William Karush）的硕士论文，之后在一份由W.库恩（Harold W. Kuhn）及塔克（Albert W. Tucker）撰写的研讨生论文出现后受到重视。

考虑标准约束优化问题(或称非线性规划)：

$\\displaystyle \\begin{array}{lll}\\hbox{min}&f(\\mathbf{x})\\\\ \\hbox{s.t.}&g_j(\\mathbf{x})=0,&j=1,\\ldots,m ,\\\\ &h_k(\\mathbf{x})\\le 0,&k=1,\\ldots,p. \\end{array}\\\\$

定义Lagrangian 函数

$\\displaystyle L\\left(\\mathbf{x},\\{\\lambda_j\\},\\{\\mu_k\\}\\right)=f(\\mathbf{x})+\\sum_{j=1}^m\\lambda_jg_j( \\mathbf{x})+\\sum_{k=1}^p\\mu_kh_k(\\mathbf{x})\\\\$ 其中 $\\lambda_j$ 是对应 $g_j(\\mathbf{x})=0$ 的Lagrange乘数， $\\mu_k$ $是对应 $h_k(\\mathbf{x})\\le 0$ 的Lagrange乘数(或称KKT乘数)。KKT条件包括

$\\displaystyle \\begin{aligned}\ abla_{\\mathbf{x}}L&=\\mathbf{0}\\\\ g_j(\\mathbf{x})&=0,~~j=1,\\ldots,m,\\\\ h_k(\\mathbf{x})&\\le 0,\\\\ \\mu_k&\\ge 0,\\\\ \\mu_k h_k(\\mathbf{x})&=0,~~k=1,\\ldots,p. \\end{aligned}\\\\$

给定一个目标函数 $f:\\mathbb{R}^n\ o\\mathbb{R}$ ，我们希望找到 $\\mathbf{x}\\in\\mathbb{R}^n$ ，在满足约束条件 $g(\\mathbf{x})=0$ 的前提下，使得 $f(\\mathbf{x})$ 有最小值。这个约束优化问题记为

$\\displaystyle \\begin{array}{ll}\\hbox{min}&f(\\mathbf{x})\\\\ \\hbox{s.t.}&g(\\mathbf{x})=0. \\end{array}\\\\$
为方便分析，假设 $f$ 与 $g$ 是连续可导函数。Lagrange乘数法是等式约束优化问题的典型解法。定义Lagrangian函数

$\\displaystyle L(\\mathbf{x},\\lambda)=f(\\mathbf{x})+\\lambda g(\\mathbf{x})\\\\$
其中 $\\lambda$ 称为Lagrange乘数。Lagrange乘数法将原本的约束优化问题转换成等价的无约束优化问题

$\\displaystyle \緻set{\\mathbf{x},\\lambda}{\\hbox{min}}~~L(\\mathbf{x},\\lambda)\\\\$
计算 $L$ 对 $\\mathbf{x}$ 与 $\\lambda$ 的偏导数并设为零，可得最优解的必要条件：

$\\displaystyle \\begin{aligned}\ abla_{\\mathbf{x}}L&=\\frac{\\partial L}{\\partial\\mathbf{x}}=\ abla f+\\lambda\ abla g=\\mathbf{0}\\\\ \ abla_{\\lambda}L&=\\frac{\\partial L}{\\partial\\lambda}=g(\\mathbf{x})=0 \\end{aligned}\\\\$
其中第一式为定常方程式(stationary equation)，第二式为约束条件。解开上面 $n+1$ 个方程式可得 $L(\\mathbf{x},\\lambda)$ 的stationary point $\\mathbf{x}^\\star$ 以及 $\\lambda$ 的值(正负数皆可能)。

当目标函数为2元时候约束情形：假设有函数： ${\\displaystyle f(x,y)}$ ，要求其极值（最大值/最小值），且满足条件 ${\\displaystyle g\\left(x,y\\right)=c}$ ， $c$ 为常数。我们可以给出下面简易证明

设函数 ${\\displaystyle f(x,y)}$ 在 ${\\displaystyle A}$ 点处有极值 ${\\displaystyle \\kappa }$ ，且在 ${\\displaystyle A}$ 点的邻域内连续。则在 ${\\displaystyle A}$ 点处有 ${\\displaystyle f\\left(x,y\\right)=\\kappa }$

另有一常值函数 ${\\displaystyle g\\left(x,y\\right)=c}$ 两函数在 ${\\displaystyle A}$ 点处的全微分为 ${\\displaystyle \\mathrm{d}f={\\frac{\\partial{f}}{\\partial{x}}}\\mathrm{d}x+{\\frac{\\partial{f}}{\\partial{y}}}\\mathrm{d}y=0}\\\\$ ， ${\\displaystyle \\mathrm{d}g={\\frac{\\partial{g}}{\\partial{x}}}\\mathrm{d}x+{\\frac{\\partial{g}}{\\partial{y}}}\\mathrm{d}y=0}\\\\$

由于 ${\\displaystyle \\mathrm{d}x}$ 和 ${\\displaystyle \\mathrm{d}y}$ 是任取的无穷小量，故该线性方程组的系数成比例，有

${\\displaystyle{\\dfrac{\\dfrac{\\partial{f}}{\\partial{x}}}{\\dfrac{\\partial{g}}{\\partial{x}}}}={\\dfrac{\\dfrac{\\partial{f}}{\\partial{y}}}{\\dfrac{\\partial{g}}{\\partial{y}}}}=-\\lambda }\\\\$

即

${\\displaystyle{\\frac{\\partial{f}}{\\partial{x}}}+\\lambda \\cdot{\\frac{\\partial{g}}{\\partial{x}}}=0}\\\\$

${\\displaystyle{\\frac{\\partial{f}}{\\partial{y}}}+\\lambda \\cdot{\\frac{\\partial{g}}{\\partial{y}}}=0}\\\\$

将上二式分别乘以 ${\\displaystyle \\mathrm{d}x}$ 和 ${\\displaystyle \\mathrm{d}y}$ ，再相加并积分，得到一新函数

${\\displaystyle{\\mathcal{L}}(x,y,\\lambda )=f(x,y)+\\lambda \\cdot g(x,y)}\\\\$

那么，求原函数极值的问题就转化为求该函数极值的问题。
类似地，这种求极值的方法也可以推广到多维函数 ${\\displaystyle f\\left(x_{1},\\ldots ,x_{n}\\right)}$ 。

求此方程的最小值：

${\\displaystyle f(x,y)=x^{2}y}\\\\$

同时未知数满足

${\\displaystyle x^{2}+y^{2}=1}\\\\$

因为只有一个未知数的限制条件，我们只需要用一个乘数 ${\\displaystyle \\lambda }$

${\\displaystyle g(x,y)=x^{2}+y^{2}-1}\\\\$

${\\displaystyle \\Phi (x,y,\\lambda )=f(x,y)+\\lambda g(x,y)=x^{2}y+\\lambda (x^{2}+y^{2}-1)}\\\\$

将所有 ${\\displaystyle \\Phi }$ 方程的偏微分设为零，得到一个方程组，最小值是以下方程组的解中的一个：

${\\displaystyle 2xy+2\\lambda x=0}\\\\$

${\\displaystyle x^{2}+2\\lambda y=0}\\\\$

${\\displaystyle x^{2}+y^{2}-1=0}\\\\$

接下来就是解方程，这里可以采用Mathematica软件

s1=Solve[{2 x*y + 2 l*x==0, x^2 + 2 l*y==0, 
    x^2 + y^2 - 1==0},{x, y, l}];
ReplaceAll[x^2 y, #]& /@ s1
s1[[3]]
s1[[5]]

我们可知道 $\\left\\{x\ o -\\sqrt{\\frac{2}{3}},y\ o -\\frac{1}{\\sqrt{3}},l\ o \\frac{1}{\\sqrt{3}}\\right\\},\\\\$

或者

$\\left\\{x\ o \\sqrt{\\frac{2}{3}},y\ o -\\frac{1}{\\sqrt{3}},l\ o \\frac{1}{\\sqrt{3}}\\right\\}\\\\$

函数 ${\\displaystyle f(x,y)=x^{2}y}$ 取得最小值。

当然也可以用Mathematica求解

Minimize[{x^2 y, x^2 + y^2==1},{x, y}]

$\\left\\{-\\frac{2}{3 \\sqrt{3}},\\left\\{x\ o -\\sqrt{\\frac{2}{3}},y\ o -\\frac{1}{\\sqrt{3}}\\right\\}\\right\\}\\\\$

接下来我们将约束等式 $g(\\mathbf{x})=0$ 推广为不等式 $g(\\mathbf{x})\\le 0$ 。考虑这个问题

$\\displaystyle \\begin{array}{ll}\\hbox{min}&f(\\mathbf{x})\\\\ \\hbox{s.t.}&g(\\mathbf{x})\\le 0. \\end{array}\\\\$
约束不等式 $g(\\mathbf{x})\\le 0$ 称为原始可行性(primal feasibility)，据此我们定义可行域(feasible region) $K={\\mathbf{x}\\in\\mathbb{R}^n|g(\\mathbf{x})\\le 0}$ 。假设 $\\mathbf{x}^\\star$ 为满足约束条件的最佳解，分开两种情况讨论：

(1) $g(\\mathbf{x}^\\star)<0$ ，最佳解位于 $K$ 的内部，称为内部解(interior solution)，这时约束条件是无效的(inactive)；

(2) $g(\\mathbf{x}^\\star)=0$ ，最佳解落在 $K$ 的边界，称为边界解(boundary solution)，此时约束条件是有效的(active)。

这两种情况的最佳解具有不同的必要条件。

(1)内部解：在约束条件无效的情形下， $g(\\mathbf{x})$ 不起作用，约束优化问题退化为无约束优化问题，因此驻点 $\\mathbf{x}^\\star$ 满足 $\ abla f=\\mathbf{0}$ 且 $\\lambda=0$ 。

(2)边界解：在约束条件有效的情形下，约束不等式变成等式 $g(\\mathbf{x})=0$ ，这与前述Lagrange乘数法的情况相同。我们可以证明驻点 $\\mathbf{x}^\\star$ 发生于 $\ abla f\\in\\hbox{span}{\ abla g}$ ，换句话说，存在 $\\lambda$ 使得 $\ abla f=-\\lambda\ abla g$ ，但这里 $\\lambda$ 的正负号是有其意义的。因为我们希望最小化 $f$ ，梯度 $\ abla f$ (函数 $f$ 在点 $\\mathbf{x}$ 的最陡上升方向)应该指向可行域 $K$ 的内部(因为你的最优解最小值是在边界取得的)，但 $\ abla g$ 指向 $K$ 的外部(即 $g(\\mathbf{x})>0$ 的区域，因为你的约束是小于等于0)，因此 $\\lambda\\ge 0$ ，称为对偶可行性(dual feasibility)。

因此，不论是内部解或边界解， $\\lambda g(\\mathbf{x})=0$ 恒成立，称为互补松弛性(complementary slackness)。整合上述两种情况，最佳解的必要条件包括Lagrangian函数 $L(\\mathbf{x},\\lambda)$ 的定常方程式、原始可行性、对偶可行性，以及互补松弛性：

$\\displaystyle \\begin{aligned}\ abla_{\\mathbf{x}}L&=\ abla f+\\lambda\ abla g=\\mathbf{0}\\\\ g(\\mathbf{x})&\\le 0\\\\ \\lambda& \\ge 0\\\\ \\lambda g(\\mathbf{x})&=0. \\end{aligned}\\\\$
这些条件合称为Karush-Kuhn-Tucker (KKT)条件。如果我们要最大化 $f(\\mathbf{x})$ 且受限于 $g(\\mathbf{x})\\le 0$ ，那么对偶可行性要改成 $\\lambda\\le 0$ 。

上面结果可推广至多个约束等式与约束不等式的情况。

考虑标准约束优化问题(或称非线性规划)：

$\\displaystyle \\begin{array}{lll}\\hbox{min}&f(\\mathbf{x})\\\\ \\hbox{s.t.}&g_j(\\mathbf{x})=0,&j=1,\\ldots,m ,\\\\ &h_k(\\mathbf{x})\\le 0,&k=1,\\ldots,p. \\end{array}\\\\$

定义Lagrangian 函数

考虑这个问题

$\\displaystyle \\begin{array}{ll}\\hbox{min}&x_1^2+x_2^2,\\\\ \\hbox{s.t.}&x_1+x_2=1\\\\ &x_2\\le\\alpha,\\end{array}\\\\$
其中 $(x_1,x_2)\\in\\mathbb{R}^2，\\alpha$ 为实数。写出Lagrangigan函数

$\\displaystyle L(x_1,x_2,\\lambda,\\mu)=x_1^2+x_2^2+\\lambda(1-x_1-x_2)+\\mu(x_2- \\alpha)\\\\$
KKT 方程组如下：

$\\displaystyle \\begin{aligned}\\frac{\\partial L}{\\partial x_i}&=0,~~i=1,2,\\\\ x_1+x_2&=1\\\\ x_2-\\alpha&\\le 0\\\\ \\mu&\\ge 0\\\\ \\mu (x_2-\\alpha)&=0. \\end{aligned}\\\\$
求偏导可得 $\\frac{\\partial L}{\\partial x_1}=2x_1-\\lambda=0$ 且 $\\frac{\\partial L}{\\partial x_2}=2x_2-\\lambda+\\mu=0$ ，分别解出 $x_1=\\frac{\\lambda}{2}$ 且 $x_2=\\frac{\\lambda}{2}-\\frac{\\mu}{2}$ 。代入约束等式 $x_1+x_2=\\lambda-\\frac{\\mu}{2}=1$ 或 $\\lambda=\\frac{\\mu}{2}+1$ 。合并上面结果，

$\\displaystyle x_1=\\frac{\\mu}{4}+\\frac{1}{2},~~~~x_2=-\\frac{\\mu}{4}+\\frac{1}{2}\\\\$
最后再加入约束不等式 $-\\frac{\\mu}{4}+\\frac{1}{2}\\le\\alpha$ 或 $\\mu\\ge 2-4\\alpha$ 。底下分开三种情况讨论。

(1) $\\alpha>\\frac{1}{2}$ ：不难验证 $\\mu=0>2-4\\alpha$ 满足所有的KKT条件，约束不等式是无效的， $x^\\star_1=x^\\star_2=\\frac{1}{2}$ 是内部解，目标函数的极小值是 $\\frac{1}{2}$ 。

(2) $\\alpha=\\frac{1}{2}$ ：如同1， $\\mu=0=2-4\\alpha$ 满足所有的KKT条件， $x^\\star_1=x^\\star_2=\\frac{1}{2}$ 是边界解，因为 $x^\\star_2=\\alpha$ 。

(3) $\\alpha < \\frac{1}{2}$ ：这时约束不等式是有效的， $\\mu=2-4\\alpha>0$ ，则 $x^\\star_1=1-\\alpha$ 且 $x^\\star_2=\\alpha$ ，目标函数的极小值是 $(1-\\alpha)^2+\\alpha^2$ 。

源自下面链接，有兴趣可以检验正确性。在文末我们试着做第一问。

http://www.math.ubc.ca/~israel/m340/kkt2.pdf http://www2.imm.dtu.dk/courses/02711/lecture3.pdf

对于参考文献1我们采用方法如下：
注意文中将求最大值作为标准型，我们还是按照自己的思路来；只需将目标函数改为 $-xy$ 即可。我们构建KKT辅助条件

$-xy+\\lambda_1(x+y^2-2)+\\lambda_2(-x)+\\lambda_3(-y)\\\\$

KKT条件如下：

$-y+\\lambda_1-\\lambda_2=0\\\\$

$-x+2\\lambda_1y-\\lambda_3=0\\\\$

$\\lambda_1(x+y^2-2)=0\\\\$

$\\lambda_1(-x)=0\\\\$

$\\lambda_2y=0\\\\$

$\\lambda_1\\geq0,\\lambda_2\\geq0,\\lambda_3\\geq0.\\\\$

我们进行求解即可，当然可以按照文中那样正规分析，此时也可以借助数学软件求解：

s1=Solve[-y + \\[Lambda]1 - \\[Lambda]2==0 && -x + 2 \\[Lambda]1*y - \\[Lambda]3==0 && \\[Lambda]1 (x + y^2 - 2)==0 && \\[Lambda]2*x==0 && \\[Lambda]3*y==0,{x, y, \\[Lambda]1, \\[Lambda]2, \\[Lambda]3}]

注意这个警告，可能漏解。

改成

Reduce[-y + \\[Lambda]1 - \\[Lambda]2==0 && -x + 2 \\[Lambda]1*y - \\[Lambda]3==0 && \\[Lambda]1 (x + y^2 - 2)==0 && \\[Lambda]2*x==0 && \\[Lambda]3*y==0,{x, y, \\[Lambda]1, \\[Lambda]2, \\[Lambda]3}]

较好。