数值优化（Numerical Optimization）(5)约束优化（一）_盛煌-盛煌娱乐-盛煌全球注册认证站

欢迎浏览我公司网站！！

公司动态

数值优化（Numerical Optimization）(5)约束优化（一）

时间: 2024-04-15浏览次数：

之前谈的都是无约束优化问题，这次转入约束优化方法。首先介绍一下什么是约束优化其中，是目标函数，是等式约束的index，是不等式约束的index。可行集：所有满足约束的点组成的集合有效集：激活集为可行集中满足等式约束的点约束优化问题的求解比无约束优化要困难得多，这篇博客主要介绍一些特殊形式的约束优化以及非线性约束优化问题的常见解法。一些简单约束可以通过参数变换转化成无约束问题。求在的最小值，可令，

之前谈的都是无约束优化问题，这次转入约束优化方法。首先介绍一下什么是约束优化

$min\\{x\\in \\arg\\min f(x): c_i(x)=0\\quad \\forall i \\in \\mathcal{I}, c_j(x)\\ge 0\\quad \\forall j \\in \\mathcal{J}\\}$

其中， $f$ 是目标函数， $\\mathcal{I}$ 是等式约束的index， $\\mathcal{J}$ 是不等式约束的index。

可行集：所有满足约束的点组成的集合

$\\Omega=\\{x: c_i(x)=0\\quad \\forall i\\in \\mathcal{I},c_j(x)\\ge 0\\quad \\forall j \\in \\mathcal{J}\\}$

有效集：激活集为可行集中满足等式约束的点

$\\mathcal{A}(x)=\\mathcal{I}\\cup \\{j \\in \\mathcal{J}:c_j(x)=0 \\}$

约束优化问题的求解比无约束优化要困难得多，这篇博客主要介绍一些特殊形式的约束优化以及非线性约束优化问题的常见解法。

一些简单约束可以通过参数变换转化成无约束问题。

求 $f(x)$ 在 $x\\in (0,\\infty)$ 的最小值，可令 $x=e^t,h(u)=f(e^u),u\\in (-\\infty,\\infty)$ ，求得无约束问题的最小值 $\\arg\\min_u h(u)=u^*$ ，则 $x^*=e^{u^*}$ 为 $f(x)$ 在 $(0,\\infty)$ 的最小值。
如果 $x$ 约束在有限开区间 $(a,b)$ ，可以做变换

$x=a+\\frac{b-a}{1+e^{-u}},u\\in (-\\infty,\\infty)$

如果 $x$ 约束在有限闭区间 $[a,b]$ ，可以做变换

$x=a+(b-a)sin^2(u),u\\in (-\\infty,\\infty)$

若仅考虑等式约束，则优化命题为

$min \\quad f(x), \\quad s.t. \\quad c_i(x)=0,i=1,...,l.$

Kuhn-Tucker一阶必要条性条件为：

假设 $x^*$ 是上述等式约束优化问题的局部极小点， $f(x)$ 与 $c_i(x)$ 在 $x^*$ 的某邻域内连续可微。若 $\ abla c_i(x^*)(i=1,2,...,l)$ 线性无关，则存在一组实数 $\\lambda_1^*,...,\\lambda_l^*$ 使得

$\ abla f(x^*)-\\sum_{i=1}^l \\lambda_i^* \ abla c_i(x^*)=0$

我们称 $\\lambda$ 为 Lagrange 乘子向量，

$L(x,\\lambda)=f(x)-\\sum_{i=1}^l \\lambda_i c_i(x)=f(x)-\\lambda^Tc(x)$

为等式约束问题的 Lagrange 函数，其中 $c(x)=(c_1(x),...,c_l(x))^T$ ，计算 $L(x,\\lambda)$ 的梯度得

$\ abla L\\left( x,\\lambda \\right)=\\left( \\begin{array}{c}\ abla _xL\\left( x,\\lambda \\right)\\\\ \ abla _{\\lambda}L\\left( x,\\lambda \\right)\\\\ \\end{array}\\right) \\\\=\\left( \\begin{array}{c}\ abla f\\left( x \\right) -\\sum_{i=1}^l{\\lambda _i\ abla c_i\\left( x \\right)}\\\\ -c\\left( x \\right)\\\\ \\end{array}\\right)$

$(x^*,\\lambda^*)$ 满足一阶必要条件和等式约束条件当且仅当 $(x^*,\\lambda^*)$ 是 Lagrange 函数的驻点。

考虑不等式约束优化问题

$\\min \\quad f(x),\\quad s.t. \\quad c_i(x) \\ge 0,i=1,...,m.$

对于可行域中某个点 $\ ilde{x}$ ，有些约束为 $c_i(\ ilde{x})=0$ ，而另一些约束 $c_i(\ ilde{x})>0$ 使得 $c_i(\ ilde{x})=0$ ，则称不等式约束 $c_i(x)\\ge 0$ 为 $\ ilde{x}$ 的有效约束；若 $c_i(\ ilde{x})>0$ 为 $\ ilde{x}$ 的非有效约束。称所有在 $\ ilde{x}$ 处的有效约束的下标组成的集合为有效集

$I(\ ilde{x})=\\{i|c_i(\ ilde{x})=0\\}$

Kuhn-Tucker一阶必要条性条件为：

假设 $x^*$ 为局部极小点，有效集 $I^*=\\{i|\ abla c_i(x^*)=0,1\\le i \\le m\\}$ ，同时 $f(x)$ 及 $c_i(x)$ 在点 $x^*$ 处可微。若 $\ abla c_i(x^*)(i\\in I^*)$ 形成的向量组线性无关，则存在向量 $\\lambda^*=(\\lambda_1^*,...,\\lambda_m^*)^T$ 使得

$\\begin{cases}\ abla f\\left( x^* \\right) -\\sum_{i=1}^m{\\lambda _{i}^{*}\ abla c_i(x^*)=0}\\\\ \\lambda _{i}^{*}c_i(x^*)=0,\\lambda _{i}^{*}\\ge 0,i=1,2,...,m\\\\ \\end{cases}$

一般约束问题既包含等式约束也包含不等式约束

$\\min f(x) \\\\ s.t.c_i(x)=0,i\\in E=\\{1,...,l\\}, \\\\ c_i(x)\\ge 0,i\\in I=\\{l+1,...,m\\}$

把之前等式约束和不等式约束的结论结合起来，我们可以得到一般约束优化的Kuhn-Tucker一阶必要条性条件：

假设 $x^*$ 为局部极小点， $I^*$ 为 $E$ 与 $x^*$ 的有效集的并，即

$I^</em>=E \\cup{i>l,c_i(x^*)=0 }$

且 $f(x),c_i(x)(i=1,...,m)$ 在 $x^*$ 点可微。若 $\ abla c_i(x^*),i\\in I^*$ 线性无关，则存在向量 $\\lambda^*=\\{\\lambda_1^*,...,\\lambda_m^*\\}^T$ 使得

$\\begin{cases}\ abla f\\left( x^* \\right) -\\sum_{i=1}^m{\\lambda _i^*\ abla c_i\\left( x^* \\right)=0},\\\\ \\lambda _{i}^{*}c_i(x^*)=0,c_i(x^*)\\ge 0,\\lambda _{i}^{*}\\ge 0,i\\in I^*,\\\\ c_i\\left( x^* \\right)=0, i\\in E.\\\\ \\end{cases}$

满足这一条件的 $x^*$ 称为 KT 点，称 $(x^*,\\lambda^*)$ 为 KT 对，其中 $\\lambda^*$ 称为 Lagrange 乘子向量。

条件 $\\lambda_i^* c_i(x^*)=0,(i\\in I)$ 称为互补松弛条件，表明它们不能同时为 0。极小点处的 Lagrange乘子 $\\lambda^*$ 的分量是有区别的， $i\\in E$ 对应的 $\\lambda_i^*$ 可以是任何实数， $i\\in I$ 对应的 $\\lambda_i^* \\ge 0$ ，即要满足非负性。

对于非线性规划，如果目标函数 $f(x)$ 为凸函数，等式约束 $c_i(x)$ 为线性函数，不等式约束 $c_i(x)$ 为凹函数，那么该约束优化为凸规划问题。凸规划问题的 KT 对为全局极小点。

上一篇：seo引擎优化是什么意思

下一篇：【Ansys Workbench】—优化设计简介

粤IP*******