精华内容
下载资源
问答
  • 约束规划——拉格朗日乘数法

    千次阅读 2020-04-15 20:12:49
    拉格朗日乘数法(Lagrange Multiplier Method)是一种优化算法,拉格朗日乘子法主要用于解决约束优化问题,它的基本思想就是通过引入拉格朗日乘子来将含有n个变量和k个约束条件的约束优化问题转化为含有(n+k)个...

    拉格朗日乘数法

    拉格朗日乘数法的基本思想

    拉格朗日乘数法(Lagrange Multiplier Method)是一种优化算法,拉格朗日乘子法主要用于解决约束优化问题,它的基本思想就是通过引入拉格朗日乘子来将含有n个变量和k个约束条件的约束优化问题转化为含有(n+k)个变量的无约束优化问题。拉格朗日乘子背后的数学意义是其为约束方程梯度线性组合中每个向量的系数。

    如何将一个含有n个变量和k个约束条件的约束优化问题转化为含有(n+k)个变量的无约束优化问题?拉格朗日乘数法从数学意义入手,通过引入拉格朗日乘子建立极值条件,对n个变量分别求偏导对应了n个方程,然后加上k个约束条件(对应k个拉格朗日乘子)一起构成包含了(n+k)变量的(n+k)个方程的方程组问题,这样就能根据求方程组的方法对其进行求解。

    解决的问题模型为约束优化问题:

    m i n / m a x f ( x , y , z ) min/max f(x,y,z) min/maxf(x,y,z)
    s . t . s.t. s.t. g ( x , y , z ) = 0 g(x,y,z)=0 g(x,y,z)=0

    数学实例

    首先,我们先以麻省理工学院数学课程的一个实例来作为介绍拉格朗日乘数法的引子。求双曲线xy=3上离远点最近的点。

    解:首先,我们根据问题的描述来提炼出问题对应的数学模型,即:

    m i n f ( x , y ) = x 2 + y 2 min f(x,y)=x^2+y^2 minf(x,y)=x2+y2
    s . t . s.t. s.t. x y = 3 xy=3 xy=3

    (两点之间的欧氏距离应该还要进行开方,但是这并不影响最终的结果,所以进行了简化,去掉了平方)

    根据上式我们可以知道这是一个典型的约束优化问题,其实我们在解这个问题时最简单的解法就是通过约束条件将其中的一个变量用另外一个变量进行替换,然后代入优化的函数就可以求出极值。我们在这里为了引出拉格朗日乘数法,所以我们采用拉格朗日乘数法的思想进行求解。

    我们将 x 2 + y 2 = c x^2+y^2=c x2+y2=c的曲线族画出来,如下图所示,当曲线族中的圆与 x y = 3 xy=3 xy=3曲线进行相切时,切点到原点的距离最短。也就是说,当 f ( x , y ) = c f(x,y)=c f(x,y)=c的等高线和双曲线 g ( x , y ) g(x,y) g(x,y)相切时,我们可以得到上述优化问题的一个极值(注意:如果不进一步计算,在这里我们并不知道是极大值还是极小值)。

    在这里插入图片描述
    现在原问题可以转化为求当f(x,y)和g(x,y)相切时,x,y的值是多少?

    如果两个曲线相切,那么它们的切线相同,即法向量是相互平行的: ▽ f / / ▽ g ▽f//▽g f//g
    ▽ f / / ▽ g ▽f//▽g f//g可以得到, ▽ f = λ ▽ g ▽f=λ▽g f=λg

    这时,我们将原有的约束优化问题转化为了一种无约束的优化问题,如下所示:

    原问题(约束优化问题)
    m i n f ( x , y ) = x 2 + y 2 min f(x,y)=x^2+y^2 minf(x,y)=x2+y2
    s . t . s.t. s.t. x y = 3 xy=3 xy=3

    无约束方程组问题:
    ▽ f / / ▽ g ▽f//▽g f//g可以得到

    ∂ f ∂ x = λ ∂ g ∂ x \frac{\partial f}{\partial x} =λ \frac{\partial g}{\partial x} xf=λxg
    ∂ f ∂ y = λ ∂ g ∂ y \frac{\partial f}{\partial y} =λ \frac{\partial g}{\partial y} yf=λyg
    x y = 3 xy=3 xy=3

    通过求解上面的无约束方程组我们可以获取原问题的解:

    2 x = λ y 2x=\lambda y 2x=λy
    2 y = λ x 2y = \lambda x 2y=λx
    x y = 3 xy=3 xy=3

    通过求解上式可得, λ = 2 λ=2 λ=2或者是 − 2 -2 2
    λ = 2 λ=2 λ=2时, ( x , y ) = ( 3 , 3 ) (x,y)=(\sqrt3, \sqrt3) (x,y)=(3 ,3 )或者 ( − 3 , − 3 ) (-\sqrt3, -\sqrt3) (3 ,3 )
    λ = − 2 λ=-2 λ=2时,无解。

    所以原问题的解为 ( x , y ) = ( 3 , 3 ) (x,y)=(\sqrt3, \sqrt3) (x,y)=(3 ,3 )或者 ( − 3 , − 3 ) (-\sqrt3, -\sqrt3) (3 ,3 )

    通过举上述这个简单的例子就是为了体会拉格朗日乘数法的思想,即通过引入拉格朗日乘子 λ \lambda λ将原来的约束优化问题转化为无约束的方程组问题。

    拉格朗日乘数法的基本形态

    求函数 f ( x , y ) f(x,y) f(x,y)在满足 g ( x , y ) = c g(x,y)=c g(x,y)=c下的条件极值,可以转化为函数 L ( x , y , λ ) = f ( x , y ) + λ ( g ( x , y ) − c ) L(x,y,\lambda)=f(x,y)+\lambda (g(x,y)-c) L(x,y,λ)=f(x,y)+λ(g(x,y)c)的无条件极值问题。

    我们可以画图来辅助思考。
    在这里插入图片描述
    绿线标出的是约束g(x,y)=c的点的轨迹。蓝线是f(x,y)的等高线。箭头表示斜率,和等高线的法线平行。

    从图上可以直观地看到在最优解处,f和g的斜率平行。

    ▽ [ f ( x , y ) + λ ( g ( x , y ) − c ) ] = 0 , λ ≠ 0 ▽[f(x,y)+λ(g(x,y)−c)]=0, λ≠0 [f(x,y)+λ(g(x,y)c)]=0,λ=0

    一旦求出λ的值,将其套入下式,易求在无约束极值和极值所对应的点。

    L ( x , y ) = f ( x , y ) + λ ( g ( x , y ) − c ) L(x,y)=f(x,y)+λ(g(x,y)−c) L(x,y)=f(x,y)+λ(g(x,y)c)

    新方程 F ( x , y ) F(x,y) F(x,y)在达到极值时与 f ( x , y ) f(x,y) f(x,y)相等,因为 L ( x , y ) L(x,y) L(x,y)达到极值时 g ( x , y ) − c g(x,y)−c g(x,y)c总等于零。

    例1

    给定椭球 x 2 a 2 + y 2 b 2 + z 2 c 2 = 1 \frac{x^2}{a^2}+\frac{y^2}{b^2}+\frac{z^2}{c^2}=1 a2x2+b2y2+c2z2=1,求这个椭球的内接长方体的最大体积。

    这个问题实际上就是条件极值问题,即在条件 x 2 a 2 + y 2 b 2 + z 2 c 2 = 1 \frac{x^2}{a^2}+\frac{y^2}{b^2}+\frac{z^2}{c^2}=1 a2x2+b2y2+c2z2=1下求 f ( x , y , z ) = 8 x y z f(x,y,z)= 8xyz f(x,y,z)=8xyz的最大值。

    当然这个问题实际可以先根据条件消去 z z z,然后带入转化为无条件极值问题来处理。但是有时候这样做很困难,甚至是做不到的,这时候就需要用拉格朗日乘数法了。通过拉格朗日乘数法将问题转化为:

    L ( x , y , z , λ ) = f ( x , y , z ) + λ g ( x , y , z ) = 8 x y z + λ ( x 2 a 2 + y 2 b 2 + z 2 c 2 − 1 ) L(x,y,z,\lambda)=f(x,y,z)+\lambda g(x,y,z)=8xyz+\lambda(\frac{x^2}{a^2}+\frac{y^2}{b^2}+\frac{z^2}{c^2}-1) L(x,y,z,λ)=f(x,y,z)+λg(x,y,z)=8xyz+λ(a2x2+b2y2+c2z21)

    L ( x , y , z , λ ) L(x,y,z,\lambda) L(x,y,z,λ)求偏导:

    ∂ x L ( x , y , z , λ ) ∂ x = 8 y z + 2 λ x a 2 = 0 \frac{\partial xL(x,y,z,\lambda)}{\partial x} =8yz+\frac{2\lambda x}{a^2}=0 xxL(x,y,z,λ)=8yz+a22λx=0
    ∂ x L ( x , y , z , λ ) ∂ y = 8 x z + 2 λ y b 2 = 0 \frac{\partial xL(x,y,z,\lambda)}{\partial y} =8xz+\frac{2\lambda y}{b^2}=0 yxL(x,y,z,λ)=8xz+b22λy=0
    ∂ x L ( x , y , z , λ ) ∂ z = 8 x y + 2 λ z c 2 = 0 \frac{\partial xL(x,y,z,\lambda)}{\partial z} =8xy+\frac{2\lambda z}{c^2}=0 zxL(x,y,z,λ)=8xy+c22λz=0
    ∂ x L ( x , y , z , λ ) ∂ λ = x 2 a 2 + y 2 b 2 + z 2 c 2 − 1 = 0 \frac{\partial xL(x,y,z,\lambda)}{\partial \lambda} =\frac{x^2}{a^2}+\frac{y^2}{b^2}+\frac{z^2}{c^2}-1=0 λxL(x,y,z,λ)=a2x2+b2y2+c2z21=0

    最终得到 x = 3 3 a , y = 3 3 b , z = 3 3 c x=\frac{\sqrt 3}{3}a,y=\frac{\sqrt 3}{3}b,z=\frac{\sqrt 3}{3}c x=33 a,y=33 b,z=33 c

    最大体积为 V m a x = f ( 3 3 a , 3 3 b , 3 3 c ) = 8 3 9 a b c V_{max}=f(\frac{\sqrt 3}{3}a,\frac{\sqrt 3}{3}b,\frac{\sqrt 3}{3}c)=\frac{8\sqrt 3}{9}abc Vmax=f(33 a,33 b,33 c)=983 abc

    多约束的拉格朗日乘数法

    上面我们讨论的都是单约束的拉格朗日乘数法,当存在多个等式约束时(其实不等式约束也是一样的),我们进行一些推广:

    m i n / m a x f ( x , y , z ) min/max f(x,y,z) min/maxf(x,y,z)
    s . t . s.t. s.t. g i ( x , y , z ) = 0 , i = 1 , 2 , . . . , N g_i(x,y,z)=0, i = 1,2,...,N gi(x,y,z)=0,i=1,2,...,N

    多约束拉格朗日乘数法的函数表达形式为:
    L ( x , y , z , λ ) = f ( x , y , z ) + Σ i N λ i g i ( x , y , z ) L(x,y,z,\lambda)=f(x,y,z)+\Sigma_i^N\lambda_ig_i(x,y,z) L(x,y,z,λ)=f(x,y,z)+ΣiNλigi(x,y,z)

    广义拉格朗日乘数法(Generalized Lagrange multipliers)

    以上我们的拉格朗日乘数法解决了等式约束的最优化问题,但是在存在不等式的最优化问题,因此学者提出了广义拉格朗日乘数法,用与解决含有不等式约束的最优化问题。

    首先,我们先一般化我们的问题:

    m i n x , y , z f ( x , y ) min_{x,y,z}f(x,y) minx,y,zf(x,y)
    s . t . s.t. s.t. g i ( x , y ) ≤ 0 , i = 1 , 2 , . . . , N g_i(x,y)\le0,i=1,2,...,N gi(x,y)0,i=1,2,...,N
    h i ( x , y ) = 0 , i = 1 , 2 , . . . , M h_i(x,y)=0,i=1,2,...,M hi(x,y)=0,i=1,2,...,M

    类似于拉格朗日乘数法,我们用 α i \alpha_i αi β i \beta_i βi作为不等式约束和等式约束的拉格朗日乘子,得出如下:

    L ( x , y , α , β ) = f ( x , y ) + Σ i N α i g i ( x , y ) + Σ i M β i h i ( x , y ) L(x,y,\alpha,\beta)=f(x,y)+\Sigma_i^N\alpha_ig_i(x,y)+\Sigma_i^M\beta_ih_i(x,y) L(x,y,α,β)=f(x,y)+ΣiNαigi(x,y)+ΣiMβihi(x,y)

    KKT

    KKT条件(Karush–Kuhn–Tucker conditions)指出,当满足以下几个条件的时候,其解是问题最优解的候选解(摘自wikipedia)。

    1、Stationarity(稳定性)

    对于最小化问题就是:
    ▽ f ( x , y ) + Σ i N α i ▽ g i ( x , y ) + Σ i M β i ▽ h i ( x , y ) = 0 ▽f(x,y)+\Sigma_i^N\alpha_i▽g_i(x,y)+\Sigma_i^M\beta_i▽h_i(x,y)=0 f(x,y)+ΣiNαigi(x,y)+ΣiMβihi(x,y)=0

    对于最大化问题就是:
    ▽ f ( x , y ) − ( Σ i N α i ▽ g i ( x , y ) + Σ i M β i ▽ h i ( x , y ) ) = 0 ▽f(x,y)-(\Sigma_i^N\alpha_i▽g_i(x,y)+\Sigma_i^M\beta_i▽h_i(x,y))=0 f(x,y)(ΣiNαigi(x,y)+ΣiMβihi(x,y))=0

    2、Primal feasibility(原始可行性)

    g i ( x , y ) ≤ 0 , i = 1 , 2 , . . . , N g_i(x,y)\le0,i=1,2,...,N gi(x,y)0,i=1,2,...,N
    h i ( x , y ) = 0 , i = 1 , 2 , . . . , M h_i(x,y)=0,i=1,2,...,M hi(x,y)=0,i=1,2,...,M

    3、Dual feasibility(对偶可行性)

    α i ≥ 0 , i = 1 , 2 , . . . , N \alpha_i\ge0,i=1,2,...,N αi0,i=1,2,...,N

    4、Complementary slackness(互补松弛)

    α i g i ( x , y ) = 0 , i = 1 , 2 , . . . , N \alpha_ig_i(x,y)=0,i=1,2,...,N αigi(x,y)=0,i=1,2,...,N

    其中的Stationarity(稳定性)与我们的拉格朗日乘数法的含义是相同的,就是梯度共线的意思;而Primal feasibility(原始可行性)条件就是主要约束条件,自然是需要满足的;有趣的和值得注意的是Dual feasibility(对偶可行性)和Complementary slackness(互补松弛),接下来我们探讨下这两个条件,以及为什么不等式约束会多出这两个条件。

    为了接下来的讨论方便,我们将N设为3,并且去掉等式约束,这样我们的最小化问题的广义拉格朗日函数就变成了:

    L ( x , y , α , β ) = f ( x , y ) + Σ i 3 α i g i ( x , y ) L(x,y,\alpha,\beta)=f(x,y)+\Sigma_i^3\alpha_ig_i(x,y) L(x,y,α,β)=f(x,y)+Σi3αigi(x,y)

    绘制出来的示意图如下所示:

    在这里插入图片描述
    其中 d i > d j d_i>d_j di>dj,当 I > j I>j I>j,而蓝线为最优化寻路过程。

    让我们仔细观察式子 α i ≥ 0 \alpha_i\ge0 αi0 α i g i ( x , y ) = 0 \alpha_ig_i(x,y)=0 αigi(x,y)=0,我们不难发现,因为 α i ≤ 0 , g i ( x , y ) ≤ 0 \alpha_i\le0, g_i(x,y)\le0 αi0,gi(x,y)0,而 α i g i ( x , y ) = 0 \alpha_ig_i(x,y)=0 αigi(x,y)=0,所以 α i \alpha_i αi g i ( x , y ) g_i(x,y) gi(x,y)之中必有一个为0。

    我们从上面的示意图入手理解并且记好公式 ▽ f ( x , y ) + Σ i N α i ▽ g i ( x , y ) + Σ i M β i ▽ h i ( x , y ) = 0 ▽f(x,y)+\Sigma_i^N\alpha_i▽g_i(x,y)+\Sigma_i^M\beta_i▽h_i(x,y)=0 f(x,y)+ΣiNαigi(x,y)+ΣiMβihi(x,y)=0

    让我们假设初始化一个点A, 这个点A明显不处于最优点,也不在可行域内,可知 g 2 ( x , y ) > 0 g_2(x,y)>0 g2(x,y)>0,违背了 g i ( x , y ) ≤ 0 g_i(x,y)\le0 gi(x,y)0,为了满足约束 α i g i ( x , y ) = 0 \alpha_ig_i(x,y)=0 αigi(x,y)=0,有 α 2 = 0 \alpha_2=0 α2=0,导致 α i ▽ g i ( x , y ) = 0 \alpha_i▽g_i(x,y)=0 αigi(x,y)=0

    而对于 i = 1 , 3 i=1,3 i=1,3,因为满足约束条件而且 g 1 ( x , y ) ≠ 0 , g 3 ( x , y ) ≠ 0 g_1(x,y)≠0,g_3(x,y)≠0 g1(x,y)=0,g3(x,y)=0,所以 α 1 = 0 , α 3 = 0 \alpha_1=0,\alpha_3=0 α1=0,α3=0。这样我们的式子 ▽ f ( x , y ) + Σ i N α i ▽ g i ( x , y ) + Σ i M β i ▽ h i ( x , y ) = 0 ▽f(x,y)+\Sigma_i^N\alpha_i▽g_i(x,y)+\Sigma_i^M\beta_i▽h_i(x,y)=0 f(x,y)+ΣiNαigi(x,y)+ΣiMβihi(x,y)=0就只剩下 ∇ f ( x , y ) ∇f(x,y) f(x,y)

    因此对着 ∇ f ( x , y ) ∇f(x,y) f(x,y)进行优化,也就是沿着 f ( x , y ) f(x,y) f(x,y)梯度方向下降即可,不需考虑其他的条件(因为还完全处于可行域之外)。因此,A点一直走啊走,从A到B,从B到C,从C到D,这个时候因为D点满足 g 2 ( x , y ) = 0 g_2(x,y)=0 g2(x,y)=0,因此 α 2 > 0 \alpha_2>0 α2>0
    ,所以 α 2 ∇ g 2 ( x , y ) ≠ 0 \alpha_2∇g_2(x,y)≠0 α2g2(x,y)=0,因此 ▽ f ( x , y ) + Σ i N α i ▽ g i ( x , y ) + Σ i M β i ▽ h i ( x , y ) = 0 ▽f(x,y)+\Sigma_i^N\alpha_i▽g_i(x,y)+\Sigma_i^M\beta_i▽h_i(x,y)=0 f(x,y)+ΣiNαigi(x,y)+ΣiMβihi(x,y)=0就变成了 ∇ f ( x , y ) + α 2 ∇ g 2 ( x , y ) ∇f(x,y)+\alpha_2∇g_2(x,y) f(x,y)+α2g2(x,y)

    所以在优化下一个点E的时候,就会考虑到需要满足约束 g 2 ( x , y ) ≤ 0 g_2(x,y)≤0 g2(x,y)0的条件,朝着向 g 2 ( x , y ) g_2(x,y) g2(x,y)减小,而且 f ( x , y ) f(x,y) f(x,y)减小的方向优化。因此下一个优化点就变成了E点,而不是G点。因此没有约束的情况下其优化路径可能是A→B→C→D→G→H,而添加了约束之后,其路径变成了A→B→C→D→E→F。

    这就是为什么KKT条件引入了Dual feasibility(对偶可行性)和Complementary slackness(互补松弛),就是为了在满足不等式约束的情况下对目标函数进行优化。让我们记住这个条件,因为这个条件中某些 α i = 0 \alpha_i=0 αi=0的特殊性质,将会在SVM中广泛使用,而且正是这个性质定义了支持向量(SV)。

    参考文献

    最优化方法:拉格朗日乘数法
    拉格朗日乘数法和KKT条件的直观解释

    展开全文
  • 约束规划问题的罚函数解法

    万次阅读 2017-11-13 10:59:07
    罚函数法是利用目标函数 $f(x)$ 和约束函数 $c(x)$,构造具有惩罚性质的函数 $P(x)=\bar{P}(f(x), c(x))$ ,使得原约束优化问题转化为求 $P(x)$ 最优解的无约束优化问题。以下讨论中,我们假设**所有函数都是连续的*...

    本文中我们考虑如下有约束的一般优化问题的求解方法:
    min ⁡ f ( x ) s. t.  c i ( x ) = 0 , i ∈ E = { 1 , 2 , … , l } c i ( x ) ≤ 0 , i ∈ I = { l + 1 , l + 2 , … , l + m } x ∈ R n \begin{aligned} &\min f(x) \\ \text{s. t. } &c_{i}(x) = 0, i\in E=\{1,2,\dots, l\}\\ & c_{i}(x)\leq 0, i\in I = \{l+1, l+2,\dots,l+m\} \\ & x\in \mathbb{R}^{n} \end{aligned} s. t. minf(x)ci(x)=0,iE={1,2,,l}ci(x)0,iI={l+1,l+2,,l+m}xRn 其中,可行域 D D D 记为:
    D = { x ∣ c i ( x ) = 0 , i ∈ E ; c i ( x ) ≤ 0 , i ∈ I ; x ∈ R n } D=\{x | c_{i}(x)=0, i\in E; c_{i}(x)\leq 0, i\in I; x\in\mathbb{R}^{n}\} D={xci(x)=0,iE;ci(x)0,iI;xRn}

    求解约束优化问题要比求解无约束优化问题复杂困难得多。一般来说,求解约束优化问题的方法大致分两类:一类是此文中介绍的直接求解法,另一类是本文中即将介绍的罚函数法。

    罚函数法是利用目标函数 f ( x ) f(x) f(x) 和约束函数 c ( x ) c(x) c(x),构造具有惩罚性质的函数 P ( x ) = P ˉ ( f ( x ) , c ( x ) ) P(x)=\bar{P}(f(x), c(x)) P(x)=Pˉ(f(x),c(x)) ,使得原约束优化问题转化为求 P ( x ) P(x) P(x) 最优解的无约束优化问题。以下讨论中,我们假设所有函数都是连续的

    外罚函数法

    外罚函数是一类不可行点的方法,其基本思想是:在求解约束优化的问题时,通过对不可行的迭代点施加惩罚,并随着迭代点的进展,增大惩罚量,迫使迭代点逐步向可行域靠近。

    等式约束的优化问题

    min ⁡ f ( x ) , x ∈ R n s. t.  c i ( x ) = 0 , i = 1 , 2 , … , l \begin{aligned} &\min f(x), x\in\mathbb{R}^{n} \\ \text{s. t. }& c_{i}(x)=0, i=1,2,\dots,l \end{aligned} s. t. minf(x),xRnci(x)=0,i=1,2,,l P ~ ( x ) = ∑ i = 1 l ∣ c i ( x ) ∣ β , β ≥ 1 \tilde{P}(x)=\sum_{i=1}^{l}|c_{i}(x)|^{\beta},\quad \beta\geq 1 P~(x)=i=1lci(x)β,β1定义如下形式的外罚函数 P ( x , σ ) = f ( x ) + σ P ~ ( x ) = f ( x ) + σ ∑ i = 1 l ∣ c i ( x ) ∣ β , β ≥ 1 \begin{aligned} P(x,\sigma) &= f(x)+\sigma \tilde{P}(x) \\ &= f(x)+\sigma\sum_{i=1}^{l}|c_{i}(x)|^{\beta},\quad \beta\geq 1 \end{aligned} P(x,σ)=f(x)+σP~(x)=f(x)+σi=1lci(x)β,β1其中 σ > 0 \sigma>0 σ>0 是一个参数。显然,当 x x x 为可行点时, P ~ ( x ) = 0 \tilde{P}(x)=0 P~(x)=0 ;当 x x x 不是可行点时 P ~ ( x ) > 0 \tilde{P}(x)>0 P~(x)>0 ,于是 P ( x , σ ) > f ( x ) P(x,\sigma)>f(x) P(x,σ)>f(x) 。特别的,随着 σ \sigma σ 增大, P ( x ) P(x) P(x) 也在增大。所以,要使 P ( x , σ ) P(x,\sigma) P(x,σ) 取到极小值, P ~ ( x ) \tilde{P}(x) P~(x) 应充分小,即 P ( x , σ ) P(x,\sigma) P(x,σ) 的极小点应充分逼近可行域。于是,上述等式约束优化问题转化为无约束优化的问题
    min ⁡ x { P ( x , σ ) = f ( x ) + σ P ~ ( x ) } \min_{x}\{P(x,\sigma)=f(x)+\sigma\tilde{P}(x) \} xmin{P(x,σ)=f(x)+σP~(x)}通常取 β = 2 \beta=2 β=2

    例 1:求解下列约束优化问题 min ⁡ { f ( x ) = x 1 + x 2 } s. t.  c ( x ) = x 2 − x 1 2 = 0 \begin{aligned}\min\{f(x)=x_{1}+x_{2}\}\\\text{s. t. } c(x)=x_{2}-x_{1}^{2} =0 \end{aligned} min{f(x)=x1+x2}s. t. c(x)=x2x12=0解:构造外罚函数 P ( x , σ ) = x 1 + x 2 + σ ( x 2 − x 1 2 ) 2 P(x,\sigma)=x_{1}+x_{2}+\sigma(x_{2}-x_{1}^{2})^{2} P(x,σ)=x1+x2+σ(x2x12)2利用解析法求解 ∂ P ∂ x 1 = 1 − 4 σ x 1 ( x 2 − x 1 2 ) , ∂ P ∂ x 2 = 1 + 2 σ ( x 2 − x 1 2 ) \frac{\partial P}{\partial x_{1}}=1-4\sigma x_{1}(x_{2}-x_{1}^{2}), \frac{\partial P}{\partial x_{2}}=1+2\sigma(x_{2}-x_{1}^{2}) x1P=14σx1(x2x12),x2P=1+2σ(x2x12) ∇ x P ( x , σ ) = 0 \nabla_{x}P(x,\sigma)=0 xP(x,σ)=0得到 x 1 ( σ ) = − 1 2 , x 2 ( σ ) = 1 4 − 1 2 σ x_{1}(\sigma)=-\frac{1}{2}, x_{2}(\sigma)=\frac{1}{4}-\frac{1}{2\sigma} x1(σ)=21,x2(σ)=412σ1再令 σ → + ∞ \sigma\to+\infty σ+ x ( σ ) = ( − 1 2 , 1 4 ) T = x ∗ P ( x ( σ ) , σ ) = − 1 4 = f ( x ∗ ) \begin{aligned}x(\sigma)=\left(-\frac{1}{2}, \frac{1}{4} \right)^{T}=x^{*} \\ P(x(\sigma), \sigma)=-\frac{1}{4}=f(x^{*})\end{aligned} x(σ)=(21,41)T=xP(x(σ),σ)=41=f(x)

    不等式约束的优化问题

    我们考虑如下不等式约束的优化问题
    min ⁡ f ( x ) , x ∈ R n s. t.  c i ( x ) ≤ 0 , i = 1 , 2 , … , l \begin{aligned} &\min f(x), x\in\mathbb{R}^{n} \\ \text{s. t. }& c_{i}(x)\leq 0, i=1,2,\dots,l \end{aligned} s. t. minf(x),xRnci(x)0,i=1,2,,l P ~ ( x ) = ∑ i = 1 l [ max ⁡ ( 0 , c i ( x ) ) ] α , α ≥ 1 \tilde{P}(x)=\sum_{i=1}^{l}[\max(0, c_{i}(x))]^{\alpha},\quad \alpha\geq 1 P~(x)=i=1l[max(0,ci(x))]α,α1定义如下形式的外罚函数
    P ( x , σ ) = f ( x ) + σ ∑ i = 1 l [ max ⁡ ( 0 , c i ( x ) ) ] α α ≥ 1 P(x,\sigma)=f(x)+\sigma\sum_{i=1}^{l}[\max(0, c_{i}(x))]^{\alpha}\quad \alpha\geq 1 P(x,σ)=f(x)+σi=1l[max(0,ci(x))]αα1此时的外罚函数性质与上一节类似,通常取 α = 2 \alpha=2 α=2

    一般约束的优化问题

    考虑一般的约束优化问题
    min ⁡ f ( x ) s. t.  c i ( x ) = 0 , i ∈ E = { 1 , 2 , … , l } c i ( x ) ≤ 0 , i ∈ I = { L + 1 , l + 2 , … , l + m } x ∈ R n \begin{aligned} &\min f(x) \\ \text{s. t. } &c_{i}(x) = 0, i\in E=\{1,2,\dots, l\}\\ & c_{i}(x)\leq 0, i\in I = \{L+1, l+2,\dots,l+m\} \\ & x\in \mathbb{R}^{n} \end{aligned} s. t. minf(x)ci(x)=0,iE={1,2,,l}ci(x)0,iI={L+1,l+2,,l+m}xRn P ~ ( x ) = ∑ i = 1 l ∣ c i ( x ) ∣ β + ∑ i = 1 l [ max ⁡ ( 0 , c i ( x ) ) ] α , α ≥ 1 , β ≥ 1 \tilde{P}(x)=\sum_{i=1}^{l}|c_{i}(x)|^{\beta}+\sum_{i=1}^{l}[\max(0, c_{i}(x))]^{\alpha},\quad \alpha\geq 1,\beta\geq 1 P~(x)=i=1lci(x)β+i=1l[max(0,ci(x))]α,α1,β1类似地,定义如下形式的外罚函数 P ( x , σ ) = f ( x ) + σ ∑ i = 1 l ∣ c i ( x ) ∣ β + ∑ i = 1 l [ max ⁡ ( 0 , c i ( x ) ) ] α , α ≥ 1 , β ≥ 1 P(x,\sigma)=f(x)+\sigma\sum_{i=1}^{l}|c_{i}(x)|^{\beta}+\sum_{i=1}^{l}[\max(0, c_{i}(x))]^{\alpha},\quad \alpha\geq 1,\beta\geq 1 P(x,σ)=f(x)+σi=1lci(x)β+i=1l[max(0,ci(x))]α,α1,β1上述罚函数性质与之前的讨论类似。通常 α = β = 2 \alpha=\beta =2 α=β=2。可见,外罚函数的最优解在 σ → + ∞ \sigma\to+\infty σ+的过程中一直在可行域外部取点,直到趋近最优解 x ∗ x^{*} x。所以之中方法为外罚函数法,简称外点法 P ( x , σ ) P(x,\sigma) P(x,σ) 为外罚函数,或叫增广目标函数, σ \sigma σ为惩罚因子, P ~ ( x ) \tilde{P}(x) P~(x)为惩罚项。

    对于比较复杂的约束,通常采用迭代的方法:

    1. 给定初始点 x 0 x^{0} x0,设 ϵ > 0 , c > 1 \epsilon >0, c>1 ϵ>0,c>1 为给定实数,选择序列 { σ k } \{\sigma_{k}\} {σk},使得 σ k → + ∞ \sigma_{k}\to+\infty σk+,令 k = 1 k=1 k=1
    2. x k − 1 x^{k-1} xk1 为初始点,求解无约束优化问题 min ⁡ { P ( x , σ k ) = f ( x ) + σ k P ~ ( x ) } \min\{P(x,\sigma_{k})=f(x)+\sigma_{k}\tilde{P}(x) \} min{P(x,σk)=f(x)+σkP~(x)}得到最优解 x k x^{k} xk
    3. σ k P ~ ( x k ) &lt; ϵ \sigma_{k}\tilde{P}(x^{k})&lt;\epsilon σkP~(xk)<ϵ,则停止迭代, x k x^{k} xk 作为原问题的最优解;否则,令 σ k + 1 = c σ k \sigma_{k+1}=c\sigma_{k} σk+1=cσk k : = k + 1 k:=k+1 k:=k+1,转至步骤2。

    对于外罚函数的算法收敛性与外罚函数的病态性质这里不作讨论。 使用外罚函数法时,选取 σ 1 \sigma_{1} σ1过大,或者 σ k \sigma_{k} σk增长过快可以使算法快速收敛,但很难精确地求解相应的无约束极小问题;反之,可以使求得 P ( x , σ k + 1 ) P(x,\sigma_{k+1}) P(x,σk+1)的极小点变得容易,但收敛太慢。通常取 σ k = 0.1 × 2 k − 1 \sigma_{k}=0.1\times 2^{k-1} σk=0.1×2k1

    内罚函数法

    在外罚函数法中,近似最优解一般只能近似地满足约束条件,对于某些实际问题这样的近似最优解释不可接受的。内罚函数法是一类保持严格可行性的方法。其基本思想是:严格要求迭代点在可行域内移动,当迭代点接近可行域边界时,有无穷大的障碍,迫使迭代点返回可行域的内部。

    考虑不等式约束的优化问题,可行域内部记为: D 0 = { x ∈ R n ∣ c i ( x ) &lt; 0 , i = 1 , 2 , … , l } D^{0}=\{x\in\mathbb{R}^{n} | c_{i}(x)&lt;0, i=1,2,\dots,l\} D0={xRnci(x)<0,i=1,2,,l} B ( x ) = − ∑ i = 1 l ln ⁡ ( − c i ( x ) ) B(x)=-\sum_{i=1}^{l}\ln(-c_{i}(x)) B(x)=i=1lln(ci(x)) 定义如下形式的内罚函数:
    P ( x , r ) = f ( x ) + r B ( x ) = f ( x ) − r ∑ i = 1 l ln ⁡ ( − c i ( x ) ) \begin{aligned}P(x,r) &amp;=f(x)+rB(x)\\ &amp;=f(x)-r\sum_{i=1}^{l}\ln(-c_{i}(x))\end{aligned} P(x,r)=f(x)+rB(x)=f(x)ri=1lln(ci(x))其中 r &gt; 0 r&gt;0 r>0 是一参数。

    显然,当 x x x 在可行域内部, B ( x ) B(x) B(x)为一正数,当 r r r 趋近于 0 0 0 时, P ( x , r ) P(x,r) P(x,r) 的极小点就会趋近于优化问题的极小点。至少有一个 c i ( x ) c_{i}(x) ci(x) 趋于 0 0 0 时,会导致 B ( x ) B(x) B(x) 剧烈增大,迫使极小点落在可行域的内部。于是,原优化问题就转化为一下形式的优化问题:
    min ⁡ P ( x , r ) , x ∈ R n s. t.  c i ( x ) &lt; 0 , i = 1 , 2 , … , l \begin{aligned} &amp;\min P(x,r), x\in\mathbb{R}^{n}\\ \text{s. t. }&amp; c_{i}(x)&lt;0, i=1,2,\dots, l \end{aligned} s. t. minP(x,r),xRnci(x)<0,i=1,2,,l 注意使用内罚函数时,可行域由 D D D 变成 D 0 D^{0} D0 。内罚函数法简称内点法, B ( x ) B(x) B(x) 为对数障碍函数。(这里不介绍倒数障碍函数,因其用得不多性质也不佳)

    例 2:用内罚函数法求解约束问题 min ⁡ { f ( x ) = x 1 2 + 2 x 2 2 } s. t.  x 1 + x 2 − 1 ≥ 0 \begin{aligned} &amp;\min\{f(x)=x_{1}^{2}+2x_{2}^{2}\} \\ \text{s. t. }&amp; x_{1}+x_{2}-1\geq 0 \end{aligned} s. t. min{f(x)=x12+2x22}x1+x210 解:构造内罚函数
    P ( x ( r ) , r ) = x 1 2 + 2 x 2 2 − r ln ⁡ ( x 1 + x 2 − 1 ) P(x(r),r)=x_{1}^{2}+2x_{2}^{2}-r\ln(x_{1}+x_{2}-1) P(x(r),r)=x12+2x22rln(x1+x21)利用解析法:
    ∇ x P ( x ( r ) , r ) = ( 2 x 1 − r x 1 + x 2 − 1 , 4 x 2 − r x 1 + x 2 − 1 ) T = 0 \nabla_{x}P(x(r),r)=\left( 2x_{1}-\frac{r}{x_{1}+x_{2}-1}, 4x_{2}-\frac{r}{x_{1}+x_{2}-1} \right)^{T}=0 xP(x(r),r)=(2x1x1+x21r,4x2x1+x21r)T=0
    x ( r ) = ( 1 + 1 + 3 r 3 , 1 + 1 + 3 r 6 ) T x(r)=\left( \frac{1+\sqrt{1+3r}}{3}, \frac{1+\sqrt{1+3r}}{6} \right)^{T} x(r)=(31+1+3r ,61+1+3r )T r → 0 r\to 0 r0 ,则
    x ( r ) → x ∗ = ( 2 3 , 1 3 ) T , P ( x ( r ) , r ) → f ( x ∗ ) = 2 3 x(r)\to x^{*}=\left(\frac{2}{3}, \frac{1}{3}\right)^{T}, P(x(r),r)\to f(x^{*})=\frac{2}{3} x(r)x=(32,31)T,P(x(r),r)f(x)=32

    下面给出内罚函数法的算法,此处同样不讨论其收敛性和病态性质。

    1. 给定初始点 x 0 ∈ D 0 x^{0}\in D^{0} x0D0 ,设 ϵ &gt; 0 , 0 &lt; c &lt; 1 \epsilon&gt;0, 0&lt;c&lt;1 ϵ>0,0<c<1为给定实数,选择正值序列 { r k } \{r_{k}\} {rk} 使 r k → 0 r_{k}\to0 rk0,令 k = 1 k=1 k=1
    2. x k − 1 x^{k-1} xk1 为初始点,求解约束优化问题 min ⁡ { P ( x , r k ) = f ( x ) + r k B ( x ) } s. t.  x ∈ D 0 \begin{aligned} &amp;\min \{P(x,r_{k})=f(x)+r_{k}B(x)\} \\ \text{s. t. }&amp; x\in D^{0} \end{aligned} s. t. min{P(x,rk)=f(x)+rkB(x)}xD0得到最优解 x k x^{k} xk
    3. r k B ( x k ) &lt; ϵ r_{k}B(x^{k})&lt;\epsilon rkB(xk)<ϵ , 则停止迭代, x k x^{k} xk 作为原问题的最优解;否则,令 r k + 1 = c r k r_{k+1}=cr_{k} rk+1=crk , k : = k + 1 k:=k+1 k:=k+1,转至步骤2。

    注意由于可行域发生了变化, D 0 D^{0} D0不能为空,因此内罚函数法不能处理等式约束问题

    乘子法

    内外罚函数法的主要缺点是当罚函数中的 σ → + ∞ \sigma\to+\infty σ+ 或者 r → 0 r\to0 r0 时,其Hesse矩阵出现病态,给无约束问题的数值求解带来很大困难。为克服这一缺点,本节介绍乘子法。乘子法的原理与二阶充分条件与Lagrange函数的性质有关,时间问题这里不做详细推导,仅给出定理。

    等式约束问题的乘子法

    定理
    x ∗ x^{*} x, λ ∗ \lambda^{*} λ 满足约束问题
    min ⁡ f ( x ) , x ∈ R n s. t.  c i ( x ) = 0 , i = 1 , 2 , … , l \begin{aligned} &amp;\min f(x), x\in\mathbb{R}^{n} \\ \text{s. t. }&amp; c_{i}(x)=0, i=1,2,\dots,l \end{aligned} s. t. minf(x),xRnci(x)=0,i=1,2,,l的二阶充分条件,则存在 σ ∗ &gt; 0 \sigma^{*}&gt;0 σ>0,使当 σ ≥ σ ∗ \sigma\geq \sigma^{*} σσ 时, x ∗ x^{*} x 是无约束问题
    min ⁡ { ϕ ( x , λ ∗ , σ ) = f ( x ) + ∑ i = 1 l λ i ∗ c i ( x ) + σ 2 ∑ i = 1 l c i 2 ( x ) } \min\{\phi(x,\lambda^{*},\sigma) = f(x)+\sum_{i=1}^{l}\lambda_{i}^{*}c_{i}(x)+\frac{\sigma}{2}\sum_{i=1}^{l}c_{i}^{2}(x) \} min{ϕ(x,λ,σ)=f(x)+i=1lλici(x)+2σi=1lci2(x)}的严格局部解。反之,若 x k x^{k} xk ϕ ( x , λ ∗ , σ k ) \phi(x,\lambda^{*},\sigma_{k}) ϕ(x,λ,σk) 的极小点,并且 c ( x k ) = 0 c(x^{k})=0 c(xk)=0,则 x k x^{k} xk 是上述约束问题的最优解。

    ϕ ( ⋅ ) \phi(\cdot) ϕ() 被称为增广Lagrange函数乘子罚函数 λ ∗ \lambda^{*} λ 实际上是最优解 x ∗ x^{*} x 处的Lagrange乘子。我们可以通过取一个适当大的 σ \sigma σ ,然后调整 λ \lambda λ 使它逐渐趋近于 λ ∗ \lambda^{*} λ ,就能得到约束问题的最优解,这是乘子法的基本思想。

    下面给出具体迭代算法:

    1. 给定初始点 x 0 x^{0} x0 ,设初始乘子 λ 1 \lambda^{1} λ1 ,精度要求为 ϵ \epsilon ϵ ,放大系数为 c c c,选择序列 { σ k } \{\sigma_{k}\} {σk},使 σ k → + ∞ \sigma_{k}\to+\infty σk+,令 k = 1 k=1 k=1
    2. x k − 1 x^{k-1} xk1 为初始点,求解无约束优化问题 min ⁡ x ϕ ( x , λ k , σ k ) \min_{x}\phi(x,\lambda^{k},\sigma_{k}) xminϕ(x,λk,σk)得到最优解 x k x^{k} xk
    3. [ ∑ i = 1 l c i 2 ( x k ) ] 1 2 ≤ ϵ [\sum_{i=1}^{l}c_{i}^{2}(x_{k})]^{\frac{1}{2}}\leq \epsilon [i=1lci2(xk)]21ϵ,则停止迭代,得到近似解 x k x^{k} xk;否则,转到步骤4。
    4. λ i k + 1 = λ i k + σ k c i ( x k ) \lambda_{i}^{k+1}=\lambda_{i}^{k}+\sigma_{k}c_{i}(x^{k}) λik+1=λik+σkci(xk) k : = k + 1 k:=k+1 k:=k+1,转到步骤2。

    只有不等式约束时的乘子法

    现在我们考虑只有不等式约束的问题:
    min ⁡ f ( x ) , x ∈ R n s. t.  c i ( x ) ≤ 0 , i = 1 , 2 , … , l \begin{aligned} &amp;\min f(x), x\in\mathbb{R}^{n} \\ \text{s. t. }&amp; c_{i}(x)\leq 0, i=1,2,\dots,l \end{aligned} s. t. minf(x),xRnci(x)0,i=1,2,,l利用等式约束的结果,引入松弛变量 z i z_{i} zi,将上述问题转化为等式约束问题
    min ⁡ f ( x ) , x ∈ R n s. t.  c i ( x ) + z i 2 = 0 , i = 1 , 2 , … , l \begin{aligned} &amp;\min f(x), x\in\mathbb{R}^{n} \\ \text{s. t. }&amp; c_{i}(x)+z_{i}^{2}= 0, i=1,2,\dots,l \end{aligned} s. t. minf(x),xRnci(x)+zi2=0,i=1,2,,l由于变量增加了,因此问题的维度由 n + l n+l n+l 变成 n ˉ + 2 l \bar{n}+2l nˉ+2l 。这使得问题变得复杂。为了克服此问题,我们可以先关于 z z z 求极小 z ˉ \bar{z} zˉ,再将其代入原问题。此处同样不讨论具体细节。

    下面给出具体算法:

    1. 给定初始点 x 0 x^{0} x0 ,设初始乘子 λ 1 \lambda^{1} λ1 ,精度要求 ϵ \epsilon ϵ ,放大系数为 c c c ,选择序列 { σ k } \{\sigma_{k}\} {σk},使 σ k → + ∞ \sigma_{k}\to+\infty σk+,令 k = 1 k=1 k=1
    2. x k − 1 x^{k-1} xk1 为初始点,求解无约束规划问题: min ⁡ x ϕ ( x , λ k , σ k ) \min_{x}\phi(x,\lambda^{k},\sigma_{k}) xminϕ(x,λk,σk)得到最优解 x k x^{k} xk
    3. { ∑ i = 1 l [ max ⁡ ( c i ( x k ) , − λ i k σ k ) ] 2 } 1 2 ≤ ϵ \left\{\sum_{i=1}^{l}\left[\max\left(c_{i}(x^{k}), -\frac{\lambda_{i}^{k}}{\sigma_{k}}\right)\right]^{2}\right\}^{\frac{1}{2}}\leq \epsilon {i=1l[max(ci(xk),σkλik)]2}21ϵ,则停止迭代,得近似解 x k x^{k} xk ;否则,转至步骤4。
    4. λ i k + 1 = max ⁡ { 0 , λ i k + σ k c i ( x k ) } , k : = k + 1 \lambda_{i}^{k+1}=\max\{0, \lambda_{i}^{k}+\sigma_{k}c_{i}(x^{k})\}, k:=k+1 λik+1=max{0,λik+σkci(xk)},k:=k+1,转至步骤2。

    一般问题的乘子法求解

    对于一般约束优化问题:
    min ⁡ f ( x ) s. t.  c i ( x ) = 0 , i ∈ E = { 1 , 2 , … , l } c i ( x ) ≤ 0 , i ∈ I = { l + 1 , l + 2 , … , l + m } x ∈ R n \begin{aligned} &amp;\min f(x) \\ \text{s. t. } &amp;c_{i}(x) = 0, i\in E=\{1,2,\dots, l\}\\ &amp; c_{i}(x)\leq 0, i\in I = \{l+1, l+2,\dots,l+m\} \\ &amp; x\in \mathbb{R}^{n} \end{aligned} s. t. minf(x)ci(x)=0,iE={1,2,,l}ci(x)0,iI={l+1,l+2,,l+m}xRn 乘子罚函数为
    ϕ ( x , λ , σ ) = f ( x ) + ∑ i = 1 l λ i c i ( x ) + σ 2 ∑ i = 1 l c i 2 ( x ) + 1 2 σ ∑ i = l + 1 l + m { [ max ⁡ ( 0 , λ i + σ c i ( x ) ) ] 2 − λ i 2 } \phi(x,\lambda,\sigma)=f(x)+\sum_{i=1}^{l}\lambda_{i}c_{i}(x)+\frac{\sigma}{2}\sum_{i=1}^{l}c_{i}^{2}(x)+\frac{1}{2\sigma}\sum_{i=l+1}^{l+m}\{[\max(0, \lambda_{i}+\sigma c_{i}(x))]^{2}-\lambda_{i}^{2}\} ϕ(x,λ,σ)=f(x)+i=1lλici(x)+2σi=1lci2(x)+2σ1i=l+1l+m{[max(0,λi+σci(x))]2λi2}其乘子迭代公式为:
    λ i k + 1 = λ i k + σ k c i ( x k ) , i = 1 , 2 , … , l λ i k + 1 = max ⁡ { 0 , λ i k + σ k c i ( x k ) } , i = l + 1 , l + 2 , … , l + m \begin{aligned}&amp;\lambda_{i}^{k+1}=\lambda_{i}^{k}+\sigma_{k}c_{i}(x^{k}),\quad &amp;i=1,2,\dots,l\\&amp;\lambda_{i}^{k+1}=\max\{0,\lambda_{i}^{k}+\sigma_{k}c_{i}(x^{k})\},\quad &amp;i=l+1,l+2,\dots,l+m \end{aligned} λik+1=λik+σkci(xk),λik+1=max{0,λik+σkci(xk)},i=1,2,,li=l+1,l+2,,l+m终止准则为:
    { ∑ i = 1 l c i 2 ( x k ) + ∑ i = l + 1 l + m [ max ⁡ ( c i ( x k ) , − λ i k σ k ) ] 2 } 1 2 ≤ ϵ \left\{\sum_{i=1}^{l}c_{i}^{2}(x^{k})+\sum_{i=l+1}^{l+m}\left[\max\left(c_{i}(x^{k}), -\frac{\lambda_{i}^{k}}{\sigma_{k}}\right)\right]^{2}\right\}^{\frac{1}{2}}\leq\epsilon {i=1lci2(xk)+i=l+1l+m[max(ci(xk),σkλik)]2}21ϵ

    关于Lagrange乘子法更一般的介绍可参考此文

    展开全文
  • 这种方法的基本思想是通过许多易于处理的线性约束尽可能地近似非线性约束,这将导致问题复杂性和易处理性之间的良好平衡。进行案例研究以证明所提出的方法。结果表明,与不考虑需求相关性的情况相比,可以有效地降低...
  • 首先描述线性规划问题中约束条件增加时的递推求解问题,此问题在线性规划问题中具有广泛的实际背景;然后提出一个基于凸空间思想的快速求解此类问题的递推算法,该算法能快速判断其矛盾约束、冗余约束以及新问题的...
  • 边界约束的二次规划

    2013-08-02 11:52:24
    解一个边界约束凸二次规划问题。我们考虑严格(正定)凸二次规划和半『F定 凸二次规划两种情形。对于严格(『F定)凸二次规划本文结合已有的矩阵正则 分裂和向量投影的思想,提出了一个改进方法,并对正则分裂的参数选择...
  • 全覆盖路径规划思想(1)

    千次阅读 2019-10-14 19:32:01
    全覆盖路径规划思想(1)全覆盖路径规划输入条件全局规划思想判断下一点 全覆盖路径规划 主要用于目前比较火的全自动扫地机、洗地机。需要要求机器人遍历一个地图中所有空间。本文章仅描述其基本原理。 输入条件 ...

    全覆盖路径规划

    主要用于目前比较火的全自动扫地机、洗地机。需要要求机器人遍历一个地图中所有空间。本文章仅描述其基本原理。

    输入条件

    输入:

    • 一张地图
    • 清扫边界
        ox_outside = [0.0, 200.0, 200, 0.0, 0.0]     # 外边界,即清扫范围
        oy_outside = [0.0, 0.0,  60,  60.0, 0.0]
    
        ox_inside = [[50, 90, 75, 50],[100, 150, 130, 100],[160, 170, 130 , 160]]    # 内部障碍边界
        oy_inside = [[18, 48, 28, 18],[18 , 45,  28,  18] ,[20,  30,  10,   20]]
    

    输出:

    • 全覆盖路线

    全局规划思想

    1. 根据边界提取一张地图中所需覆盖范围,即清扫范围;
    2. 根据外边界,提取最长边界,用于覆盖时的遍历的方向,并记录一个顶点,用于原点;
        max_dist = 0.0
        vec = [0.0, 0.0]
        sweep_start_pos = [0.0, 0.0]
        for i in range(len(ox) - 1):
            dx = ox[i + 1] - ox[i]
            dy = oy[i + 1] - oy[i]
            d = np.sqrt(dx ** 2 + dy ** 2)
    
            if d > max_dist:
                max_dist = d
                vec = [dx, dy]                 #最长边向量,即斜率
                ori_pos = [ox[i], oy[i]]       #最长边起始顶点
    
    1. 根据最长边和一个顶点,将清扫边界和内部障碍物,进行坐标转换,即旋转和平移;将记录的一顶点,作为原点,将最长边作为X轴正方向,进行坐标转换。
    2. 经过以上步骤,则目前清扫范围在x轴方向最长,因此为最适合遍历方向;
    3. 构建栅格地图,将边界外以及障碍物内全部标记为1,而清扫区域标记为0;
    4. 栅格地图进行膨胀,主要考虑机器人大小问题;
    5. 栅格地图闭算法,主要是滤除掉
    6. 定义清扫的主要方向,从下到上,第一次从左到右。(可更改,本文仅以此种情况说明)
    7. 查找清扫起始点,方法是从栅格图最下一行从左到右进行遍历,查找第一个标记为0的栅格,则为起始坐标;
    8. 查找终点,方法与9一样;
    9. 从起点开始开始查找下一个点;
    10. 判断是否为终点或者不存在下一个点,否则执行11步骤;
    11. 记录每一个点坐标,根据原点和长边向量,还原坐标;
    12. 同时9~12步可执行多次,如此可进行分区覆盖;采用python仿真效果图如下:

    在这里插入图片描述

    判断下一点

    已知:

    1. 栅格标记为0.5,表明已经走过;
    2. 栅格标记为1,不能行走;
    3. 栅格标记为0,表明需要清扫未清扫区域;
    4. 初始位置为start_pos
    5. 初始扫描方向为Direction_x = 1
      流程图如下:
      在这里插入图片描述
      附python优化后的源码github
      参考AtsushiSakai/PythonRobotics源工程github
    展开全文
  • 约束的轨迹规划 在前面Minimum Snap即基础上加入避障; 算法思想: 用八叉树地图生成bouding box 搜索到经过bouding box 重叠区域的路径 用贝塞尔曲线进行优化 贝塞尔曲线有4个优点: 曲线的控制点必然经过路径...

    硬约束的轨迹规划

    在前面Minimum Snap即基础上加入避障;
    算法思想:

    • 用八叉树地图生成bouding box

    • 搜索到经过bouding box 重叠区域的路径

    • 用贝塞尔曲线进行优化

    • 贝塞尔曲线有4个优点:
      曲线的控制点必然经过路径起始点
      凸包包含所有控制点 曲线一定在凸包内
      求导后依然是贝塞尔曲线,并且控制点可以由原来的控制点表示
      时间0<t<1

    • 构建QM 要重新推导代价函数

    • 构建Abeq 没有了中间waypoint约束

    • 多了区域性的约束 即不等式约束

    • 贝塞尔曲线的系数和杨辉三角有关:如图3.我的理解是,在求导时B曲线不能像多项式一样直观的得到系数,但他的规律是求导时系数的一部分正好对应杨辉三角;

    • 不等式约束 Abieq 的构建还不是很清楚到底是怎么将不等式变成矩阵形式

    • Abeq的构建不清楚连续性约束的构建过程(留在以后有时间解决)

    • 大体上基于走廊的轨迹规划已经清楚 再细节上还需研究

    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 线性约束的非线性规划 许多可以被有效解决的大型非线性规划中所有或者几乎所有的约束,都是线性的。只是将目标函数扩展为非线性。相对来说容易解决。 下面四种规划是特殊的NLP问题 凸规划 若最优化问题的目标...
  • 线性规划约束满足问题的思考

    万次阅读 2016-09-18 11:19:41
    本文写给对线性规划约束满足问题的使用有困惑的朋友,如果你曾经在这方面存在一些疑问,这篇文章对你来说就再适合不过了,如果有对线性规划的解法感兴趣,那么也推荐你看一看我的思考~ *注:之前一直以为约束满足...
  • 对TWSVM做了修正,基于新的优化准则设计了一种特殊TWSVM(GTWSVM),在此基础上,提出了快速GTWSVM(FGTWSVM),其将GTWSVM转换为无约束规划问题求解。该算法在保证得到与TWSVM相当的分类性能以及较快的计算速度的...
  • 提出了一种针对目标函数、约束条件都是非线性的非线性规划问题的新算法。此算法主要是利用可分离函数和近似求解的思想来求解问题。数值计算结果显示,该方法是可行和有效的。
  • 然后,结合后者的线性约束条件,提出了一个缩减子超矩形算法,该算法的主要思想是对于违犯线性约束条件的变量,从箱约束条件中先行删除,再利用分枝算法求最优值点。本文证明了算法的全局收敛性。数值算例表明,对于大规模...
  • 基于改进遗传算法的双重路径约束下多AGV的路径规划作者:Zengliang Han, Dongqing Wang ,Feng Liu,Zhiyong Zhao,翻译:Wu Xian摘要:论文主要研究一种改进的遗传算法在多个自动导引车(AGV)路径规划中的应用。...
  • 根据广义乘子法的思想,将等式约束的凸二次规划转化为无约束问题,再利用正交校正共扼梯度法来求解,得到等式约束严格凸二次规划的新算法,不用求逆矩阵,这样可用来解大规模稀疏问题,数值结果表明:在微机486/33上就能解...
  • 非线性规划(二): Matlab 求解约束极值问题

    万次阅读 多人点赞 2019-04-24 11:10:34
    非线性规划(一):定义与数值优化...非线性规划(二): Matlab 求解约束极值问题 目录 约束极值问题 1 二次规划 2 罚函数法 3 Matlab 求约束极值问题 3.1 fminbnd 函数 3.2 fseminf 函数 3.3 fminimax 函数...
  • 约束规划 最速下降法 Newton法 Newton-最速下降混合算法 阻尼Newton法 拟Newton法 共轭梯度法 无约束问题与最优解 考虑如下最优化问题: minx∈Rnf(x)minx∈Rnf(x)\min_{x\in\mathbb{R}...
  • 利用Fletcher作用集方法的思想,将Murty等提出的正交校正共扼梯度法推广来求解具有上、下界约束的简单凸二次规划,证明了新算法具有有限步终止性,并且改进了Polyak的迭代法。数值结果表明,新算法比Polyak的迭代法求解...
  • 动态规划问题思想及算法

    千次阅读 2019-03-27 15:50:05
    基本思想 若要解一个给定问题,我们需要解其不同部分(即子问题),再合并子问题的解以得出原问题的解。 通常许多子问题非常相似,为此动态规划法试图仅仅解决每个子问题一次,从而减少计算量: 一旦某个给定子问题...
  • 约束二进制二次规划问题(UBQP)在于最大化二次0-1函数。 这是一个众所周知的NP难题,并且是用于各种组合优化问题的统一模型。 本文提出了一种离散的Hopfield神经网络(DHNN),并结合了UBQP的分布估计算法(EDA)...
  • 在大二运筹学的考试线性规划部分,有一题是写出支持向量机的表达式。因此尝试着用线性规划思想来解释和推导SVM,如有错误请不吝赐教。 运筹学线性规划三步法: 目标函数 决策变量 约束条件 ...
  • 更高次的则可以用“伴随矩阵”的方法(具体参考matlab中的roots函数方法,主要思想就是将多项式求根问题转换为求矩阵特征值问题)。 Bezier Curve Optimization 基于走廊的优化方法存在的问题是:施加全局的安全和动力...
  • 实验目录一、拉格朗日乘子法的介绍二、三、四、五、 ...其主要思想是将约束条件函数与原函数联立,从而求出使原函数取得极值的各个变量的解,可将所有约束的优化模型问题转化为无约束极值问题的求解...
  • 约束优化方法

    2021-05-27 16:18:01
    简述约束优化方法的基本思想和分类。
  • 而无约束线性规划可以用梯度法等实现求解,利用惩罚函数更方便我们制成计算机算法,在现代计算机算法中,凡涉及到求解最值,都会大量的运用惩罚函数或者借鉴惩罚函数思想。 惩罚函数可以分为外点法和内点法,其中...
  • 动态规划 核心思想 将问题分解为多个子问题,求解出多个子问题的解,然后将子问题的解存储起来,这些子问题的解相互是有关系的所以一般用迭代来解决,最后将子问题的解合并得到最终问题的解。 一般有以下性质: 最...
  • Mifflin,Sagastizabal和Oustry等提出的UV-分解理论,给出了非光滑凸函数f在不可微点的二阶性质的新方法.UV-分解理论的基本思想是将Rn分解为2个正交的子空间U和V的直和,使得原函数在U空间上的一阶逼近是线性的,...
  • 分治法: 基本思想: 将问题分解成多个子问题,并允许不断分解,使规模越来越小,最终可用已知的方法求解足够小的问题。  使用要求: (1) 问题能够按照某种...问题的最优子结构性质是该问题可用动态规划算法或贪心
  • 本文研究了Sugeno度量空间上的第二种不确定规划,即Sugeno度量空间上的机会约束规划。 首先,给出了α最优值和α悲观值作为排名度量的定义和特征。 其次,介绍了Sugeno机会受限编程(SCCP)。 最后,为了构建复杂...
  • 利用互补松弛约束条件将非线性整数规划模型转化为具有光滑特性的非线性规划模型,降低了决策求解复杂性;无需对配电网进行分层解耦,即可实现单一和多重故障区段的有效辨识。为有效求解互补松弛故障定位模型,基于...
  • 约束满足问题 CSP【转】

    千次阅读 2018-05-10 09:05:24
    比如新的学期教室的规划分配,飞机场跑道的占用情况,它们都涉及了约束条件。我们所熟知的经典的皇后问题、幻方问题都属于约束满足问题。约束满足问题可以分为二元约束满足问题和多元约束满足问题。其中,多元约束...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 21,819
精华内容 8,727
关键字:

约束规划思想