二次规划优化算法_最优化方法马昌凤答案

二次规划优化算法_最优化方法马昌凤答案二次规划问题(QuadraticProgramming,QP)是一种非线性规划问题,它的目标函数为二次函数,约束条件和线性规划问题的约束条件一样,都是线性等式或线性不等式_二次规划问题求解

二次规划优化算法_最优化方法马昌凤答案

参考资料

  • 二次规划的若干算法研究
  • 关于凸二次规划若干算法的研究
  • 二次规划
  • 不等式约束的优化问题

由于在面试中有被问及QP的原理,所以重点来总结一波QP的原理。

1. 二次规划形式

二次规划问题(Quadratic Programming,QP)是一种非线性规划问题,它的目标函数为二次函数,约束条件和线性规划问题的约束条件一样,都是线性等式或线性不等式,即

min ⁡ 1 2 x ⊤ G x + h ⊤ x s . t . a i ⊤ x ⩽ b i , i ∈ I = { 1 ⋯ m } . a i ⊤ x = b i , i ∈ ϵ = { m + 1 , … m + l } .  (1) \tag{1} \begin{aligned} &\min \frac{1}{2} x^{\top} G x+h^{\top} x\\ s.t.\quad &a_{i}^{\top} x \leqslant b_{i}, \quad i\in \mathcal{I}=\{1 \cdots m\}.\\ &a_{i}^{\top} x=b_{i}, \quad i\in\mathcal{\epsilon}=\{m+1, \ldots m + l \}\text {. } \end{aligned} s.t.min21xGx+hxaixbi,iI={
1m}.
aix=bi,iϵ={
m+1,m+l}
(1)

一般二次规划问题可以分成以下几类:

  • 凸二次规划问题:G半正定,问题有全局解
  • 严格凸二次规划问题:G正定,问题有唯一全局解
  • 一般二次规划问题:G不定,问题有稳定点或局部解

二次规划应用广泛,常见的例如有:求最小二乘法,点到多面体的距离,模型预测控制的求解等。

下面我们分别介绍等式约束和不等式约束下的二次规划的求解。

2. 等式约束二次规划问题

等式约束的二次规划问题一般形式如下:

min ⁡ 1 2 x ⊤ G x + h ⊤ x s . t . A ⊤ x = b (2) \tag{2} \begin{aligned} \min &\frac{1}{2} x^{\top} G x+h^{\top} x\\ s.t.\quad &A^{\top}x=b \end{aligned} mins.t.21xGx+hxAx=b(2)

其中
b ∈ R m , A ∈ R n × m , rank ⁡ ( A ) = m , n > m b \in R^{m}, A \in R^{n \times m}, \operatorname{rank}(A)=m, n>m bRm,ARn×m,rank(A)=m,n>m

2.1 变量消去法

1. 示例

变量消去法思路很简单,就是初中时候学过的消元法(当然,抽象之后还是挺高级的)。例如举个小栗子,假设要求解下面这个二次规划问题:

min ⁡ x 1 2 + x 2 2 + x 1 + x 2  s.t.  x 1 + x 2 = 1 \begin{array}{ll} \min & \mathrm{x}_{1}^{2}+\mathrm{x}_{2}^{2}+\mathrm{x}_{1}+ \mathrm{x}_{2} \\ \text { s.t. } & \mathrm{x}_{1}+\mathrm{x}_{2}=1 \end{array} min s.t. x12+x22+x1+x2x1+x2=1
消除一个变量 x 2 x_2 x2,这样就可以很简单的求解出来:
min ⁡ x 1 2 + ( 1 − x 1 ) 2 + 1 − x 1 + x 1 \min \mathrm{x}_{1}^{2}+\left(1-\mathrm{x}_{1}\right)^{2}+1-\mathrm{x}_{1}+ \mathrm{x}_{1} minx12+(1x1)2+1x1+x1

当然我们还可以用拉格朗日法,推导出KKT条件(后面会讲):
min ⁡ x 1 2 + x 2 2 + x 1 + x 2 + λ ( x 1 + x 2 − 1 ) \min \mathrm{x}_{1}^{2}+\mathrm{x}_{2}^{2}+\mathrm{x}_{1}+\mathrm{x}_{2}+\lambda\left(\mathrm{x}_{1}+\mathrm{x}_{2}-1\right) minx12+x22+x1+x2+λ(x1+x21)

2. 具体过程

应用变量消去法求解包括以下3个步骤:

  1. x x x分成基本变量 x B x_{B} xB 与非基本变量 x N x_{N} xN 两部分,利用等式约束将基本变量用非基本变量表示出来;
  2. 再将基本变量带入目标函数,从而消去基本变量,把问题化为一个关于非基本变量的无约束最优化问题;
  3. 最后求解无约束最优化问题的方法解之

具体来说:

A A A 分块,使其包含一个 m × m m \times m m×m 非奇异矩阵 A B , x , h A_{B} , x , h ABxh 做对应的分块
x = ( x B x N ) , A = ( A B A N ) , G = ( G B B G B N G N B G N N ) , h = ( h B h N ) (3) \tag{3} x=\left(\begin{array}{c} x_{B} \\ x_{N} \end{array}\right), A=\left(\begin{array}{c} A_{B} \\ A_{N} \end{array}\right), G=\left(\begin{array}{ll} G_{B B} & G_{B N} \\ G_{N B} & G_{N N} \end{array}\right), h=\left(\begin{array}{c} h_{B} \\ h_{N} \end{array}\right) x=(xBxN),A=(ABAN),G=(GBBGNBGBNGNN),h=(hBhN)(3)

所以等式约束 A ⊤ x = b A^{\top}x=b Ax=b就转化为:
( A B A N ) ⊤ ( x B x N ) = b (4) \tag{4} \left(\begin{array}{c} A_{B} \\ A_{N} \end{array}\right)^{\top} \left(\begin{array}{c} x_{B} \\ x_{N} \end{array}\right) =b (ABAN)(xBxN)=b(4)

将等式(4)写开得
A B x B + A N x N = b (5) \tag{5} \begin{gathered} A_{B}x_{B} +A_{N}x_{N}=\mathrm{b} \\ \end{gathered} ABxB+ANxN=b(5)
将基本变量用非基本变量表示出来
x B = A B − 1 b − A B − 1 A N x N (6) \tag{6} x_{B}=A_{B}^{-1}b-A_{B}^{-1}A_{N}x_{N} xB=AB1bAB1ANxN(6)

这样原变量就可以写成:
x = ( x B x N ) = ( A B − 1 b − A B − 1 A N x N x N ) = ( A B − 1 b 0 ) + ( − A B − 1 A N I ) x N = x 0 + Z x N (7) \tag{7} \begin{aligned} x=\left(\begin{array}{c} x_{B} \\ x_{N} \end{array}\right)= \left(\begin{array}{c} A_{B}^{-1}b-A_{B}^{-1}A_{N}x_{N} \\ x_{N} \end{array}\right) =\left(\begin{array}{c} A_{B}^{-1}b \\ 0 \end{array}\right)+ \left(\begin{array}{c} -A_{B}^{-1}A_{N} \\ I \end{array}\right)x_{N}=x_0+Zx_{N} \end{aligned} x=(xBxN)=(AB1bAB1ANxNxN)=(AB1b0)+(AB1ANI)xN=x0+ZxN(7)
即写成了一个类似于 x = x 0 + Z x N x=x_0+Zx_{N} x=x0+ZxN 的形式,这样我们将其代入目标函数,消去基本变量,把问题化为一个关于非基本变量的无约束最优化问题,最后求解无约束最优化问题的方法就能解出答案。

我们将 x = x 0 + Z x N x=x_0+Zx_{N} x=x0+ZxN 带入到目标函数中得:
min ⁡ f ( x ) = 1 2 x T G x + h T x = 1 2 ( x 0 + Z x N ) T G ( x 0 + Z x N ) + h T ( x 0 + Z x N ) (8) \tag{8} \begin{aligned} \min f(x)&=\frac{1}{2} x^{T} G x+h^{T} x\\ &=\frac{1}{2}\left(x_0+Zx_{N}\right)^TG\left(x_0+Zx_{N}\right)+h^T\left(x_0+Zx_{N}\right) \end{aligned} minf(x)=21xTGx+hTx=21(x0+ZxN)TG(x0+ZxN)+hT(x0+ZxN)(8)

除了 x N x_N xN,其他都是已知的常数项 ,由于常数项不影响优化结果,所以优化过程中省略常数项。另外,找出所有 x N T P x N x_N^TPx_N xNTPxN Q x N Qx_N QxN的形式的项,可得如下形式:
min ⁡ f ( x ) = 1 2 x N T P x N + Q x N P = Z T G Z Q = x 0 T G Z + h T Z (9) \tag{9} \begin{aligned} \min f(x)&=\frac{1}{2}x_N^TPx_N+Qx_N\\ P&=Z^TGZ\\ Q&=x_0^TGZ+h^TZ \end{aligned} minf(x)PQ=21xNTPxN+QxN=ZTGZ=x0TGZ+hTZ(9)

注意:从式(8)到式(9)的化简形式不太严谨,这里大体是想表示通过化简是可以将式(8)化成 x N T P x N + Q x N x_N^TPx_N+Qx_N xNTPxN+QxN形式的项(这里为了偷懒,式(8)的 G G G h h h都没有写成分块矩阵的形式)

对式(9)求导等于零:
( Z T G Z ) x N + Q = 0 (10) \tag{10} \left(Z^TGZ\right)x_N+Q=0 (ZTGZ)xN+Q=0(10)
如果想要其有唯一最优解,也就必须要满足 Z T G Z Z^TGZ ZTGZ 为正定。

2.2 Lagrange法

等式约束二次规划的Lagrange函数为
L ( x , λ ) = 1 2 x T G x + h T x + λ ( A T x − b ) (11) \tag{11} L(x, \lambda)=\frac{1}{2} x^{T} G x+h^{T} x+\lambda\left(A^{T} x-b\right) L(x,λ)=21xTGx+hTx+λ(ATxb)(11)
其中 λ \lambda λ称为Lagrange乘数,正负皆有可能。Lagrange乘数法将原本的约束优化问题转换成等价的无约束优化问题
min ⁡ x , λ L ( x , λ ) (12) \tag{12} \min _{x, \lambda} L(x, \lambda) x,λminL(x,λ)(12)
计算 L L L x x x λ \lambda λ 的偏导数并设为零,可得最优解的必要条件:

{ ∂ L ∂ x = G x + h + λ A = 0 ——定常方程式 ∂ L ∂ λ = A T x − b = 0 ——约束条件 (13) \tag{13} \left\{\begin{array}{l} \frac{\partial L}{\partial x}=G x+h+\lambda A=0 \quad\text{——定常方程式}\\ \\ \frac{\partial L}{\partial \lambda}=A^{T} x-b=0 \quad\text{——约束条件} \end{array}\right.

xL=Gx+h+λA=0——定常方程式λL=ATxb=0——约束条件
(13)

表示为方程组:
[ G A A T 0 ] [ x λ ] = [ − h b ] (14) \tag{14} \left[\begin{array}{cc} G & A \\ A^{T} & 0 \end{array}\right]\left[\begin{array}{l} x \\ \lambda \end{array}\right]=\left[\begin{array}{r} -h \\ b \end{array}\right] [GATA0][xλ]=[hb](14)

这样将这个方程组求解之后就可以求得最优解。

2.3 变量消去 vs Lagrange法

根据等式(10)和(14)的维度关系,变量消去法其实是转化成了一个 n − m n-m nm维的问题,也就是说求解 n − m n-m nm个方程组就能解决这个问题。而 Lagrange法是将其转化成一个 n + m n+m n+m维的问题,即 n n n个变量, m m m个乘子。

如果建模建出来的问题就只需要求解一次等式二次规划问题,那么哪一个其实都可以求解,如果维数太大,建议用变量消去法。

变量消去法很直观,使用非基变量表示基变量,但是由于需要计算 A B A_B AB的逆,当 A B A_B AB接近奇异时会导致误差很大.

3. 不等式约束二次规划问题

本节主要来自参考资料4.

3.1 Lagrange乘数法与KKT条件

1. 只有不等式约束的一般形式

先考虑只有不等式约束的一般形式:
min ⁡ f ( x )  s.t.  g ( x ) ≤ 0. \begin{array}{ll} \min & f(\mathbf{x}) \\ \text { s.t. } & g(\mathbf{x}) \leq 0 . \end{array} min s.t. f(x)g(x)0.
约束不等式 g ( x ) ≤ 0 g(\mathbf{x}) \leq 0 g(x)0 称为原始可行性(primal feasibility),据此我们定义可行域(feasible region)

K = { x ∈ R n ∣ g ( x ) ≤ 0 } K=\{\mathbf{x} \in \mathbb{R}^{n} \mid g(\mathbf{x}) \leq 0\} K={
x
Rng(x)0}

假设 x ⋆ \mathbf{x}^{\star} x 为满足约束条件的最佳解,分开两种情况讨论:

  • g ( x ⋆ ) < 0 g\left(\mathbf{x}^{\star}\right)<0 g(x)<0 ,最佳解位于 K K K 的内部,称为内部解(interior solution),这时约束条件是无效的 (inactive);
  • g ( x ⋆ ) = 0 g\left(\mathbf{x}^{\star}\right)=0 g(x)=0 ,最佳解落在 K K K 的边界,称为边界解(boundary solution),此时约束条件是有 效的(active)。

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

  • 内部解: 在约束条件无效的情形下, g ( x ) g(\mathbf{x}) g(x) 不起作用,约束优化问题退化为无约束优化问题, 因此驻点 x ⋆ \mathbf{x}^{\star} x 满足 ∇ f = 0 \nabla f=\mathbf{0} f=0 λ = 0 \lambda=0 λ=0
  • 边界解:在约束条件有效的情形下,约束不等式变成等式 g ( x ) = 0 g(\mathbf{x})=0 g(x)=0 ,这与前述Lagrange乘数法的情况相同。 我们可以证明驻点 x ⋆ \mathbf{x}^{\star} x 发生于 ∇ f ∈ span ⁡ ∇ g \nabla f \in \operatorname{span}\nabla g fspang (span是生成子空间),换句话说,存在 λ \lambda λ 使得 ∇ f = − λ ∇ g \nabla f=-\lambda \nabla g f=λg ,但这里 λ \lambda λ 的正负号是有其意义的。因为我们希望最小化 f f f ,梯度 ∇ f \nabla f f (函数 f f f 在点 x \mathbf{x} x 的最陡上升方向)应该指向可行域 K K K 的内部(因为你的最优解最小值是在边界取得的),但 ∇ g \nabla g g 指向 K K K 的外部(即 g ( x ) > 0 g(\mathbf{x})>0 g(x)>0 的区域,因为你的约束是小于等于 0 ),因此 λ ≥ 0 \lambda \geq 0 λ0,称为对偶可行性(dual feasibility)

因此,不论是内部解或边界解, λ g ( x ) = 0 \lambda g(\mathbf{x})=0 λg(x)=0 恒成立,称为互补松弛性(complementary slackness)。整合上述两种情况,最佳解的必要条件包括Lagrangian函数 L ( x , λ ) L(\mathbf{x}, \lambda) L(x,λ)定常方程式、原始可行性、对偶可行性,以及互补松弛性
{ ∇ x L = ∇ f + λ ∇ g = 0 g ( x ) ≤ 0 λ ≥ 0 λ g ( x ) = 0. \left\{\begin{array}{l} \begin{aligned} \nabla_{\mathbf{x}} L &=\nabla f+\lambda \nabla g=\mathbf{0} \\ g(\mathbf{x}) & \leq 0 \\ \lambda & \geq 0 \\ \lambda g(\mathbf{x}) &=0 . \end{aligned} \end{array}\right.

xLg(x)λλg(x)=f+λg=000=0.

这些条件合称为Karush-Kuhn-Tucker (KKT)条件。如果我们要最大化 f ( x ) f(\mathbf{x}) f(x) 且受限于 g ( x ) ≤ 0 g(\mathbf{x}) \leq 0 g(x)0 ,那么对偶可行性要改成 λ ≤ 0 \lambda \leq 0 λ0

2. 标准约束优化

考虑标准约束优化问题(或称非线性规划):
min ⁡ f ( x )  s.t.  g j ( x ) = 0 , j = 1 , … , m , h k ( x ) ≤ 0 , k = 1 , … , p . \begin{array}{ll} \min & f(\mathbf{x}) \\ \text { s.t. } & g_{j}(\mathbf{x})=0, \quad j=1, \ldots, m, \\ & h_{k}(\mathbf{x}) \leq 0, \quad k=1, \ldots, p . \end{array} min s.t. f(x)gj(x)=0,j=1,,m,hk(x)0,k=1,,p.
定义Lagrangian 函数
L ( x , { λ j } , { μ k } ) = f ( x ) + ∑ j = 1 m λ j g j ( x ) + ∑ k = 1 p μ k h k ( x ) L\left(\mathbf{x},\left\{\lambda_{j}\right\},\left\{\mu_{k}\right\}\right)=f(\mathbf{x})+\sum_{j=1}^{m} \lambda_{j} g_{j}(\mathbf{x})+\sum_{k=1}^{p} \mu_{k} h_{k}(\mathbf{x}) L(x,{
λj}
,{
μk}
)
=
f(x)+j=1mλjgj(x)+k=1pμkhk(x)

其中 λ j \lambda_{j} λj 是对应 g j ( x ) = 0 g_{j}(\mathbf{x})=0 gj(x)=0 的Lagrange乘数, μ k \mu_{k} μk 是对应 h k ( x ) ≤ 0 h_{k}(\mathbf{x}) \leq 0 hk(x)0 的Lagrange乘数(或称 KKT乘数)。KKT条件包括定常方程式、原始可行性、对偶可行性,以及互补松弛性,如下所示:
{ ∇ x L = 0 g j ( x ) = 0 , j = 1 , … , m , h k ( x ) ≤ 0 , μ k ≥ 0 , μ k h k ( x ) = 0 , k = 1 , … , p . \left\{\begin{array}{l} \begin{aligned} \nabla_{\mathbf{x}} L &=\mathbf{0} \\ g_{j}(\mathbf{x}) &=0, \quad j=1, \ldots, m, \\ h_{k}(\mathbf{x}) & \leq 0, \\ \mu_{k} & \geq 0, \\ \mu_{k} h_{k}(\mathbf{x}) &=0, \quad k=1, \ldots, p . \end{aligned} \end{array}\right.

xLgj(x)hk(x)μkμkhk(x)=0=0,j=1,,m,0,0,=0,k=1,,p.

3. 示例

  1. 考虑这个问题
    { min ⁡ x 1 2 + x 2 2  s.t.  x 1 + x 2 = 1 x 2 ≤ α \left\{\begin{array}{ll} \min & x_{1}^{2}+x_{2}^{2} \\ \text { s.t. } & x_{1}+x_{2}=1 \\ & x_{2} \leq \alpha \end{array}\right.

    min s.t. x12+x22x1+x2=1x2α

    其中 ( x 1 , x 2 ) ∈ R 2 , α \left(x_{1}, x_{2}\right) \in \mathbb{R}^{2}, \alpha (x1,x2)R2,α 为实数。写出Lagrangigan函数
    L ( x 1 , x 2 , λ , μ ) = x 1 2 + x 2 2 + λ ( 1 − x 1 − x 2 ) + μ ( x 2 − α ) L\left(x_{1}, x_{2}, \lambda, \mu\right)=x_{1}^{2}+x_{2}^{2}+\lambda\left(1-x_{1}-x_{2}\right)+\mu\left(x_{2}-\alpha\right) L(x1,x2,λ,μ)=x12+x22+λ(1x1x2)+μ(x2α)
    KKT 方程组如下:
    { ∂ L ∂ x i = 0 , i = 1 , 2 x 1 + x 2 = 1 x 2 − α ≤ 0 μ ≥ 0 μ ( x 2 − α ) = 0 \left\{\begin{array}{l} \begin{aligned} \frac{\partial L}{\partial x_{i}} &=0, \quad i=1,2 \\ x_{1}+x_{2} &=1 \\ x_{2}-\alpha & \leq 0 \\ \mu & \geq 0 \\ \mu\left(x_{2}-\alpha\right) &=0 \end{aligned} \end{array}\right.

    xiLx1+x2x2αμμ(x2α)=0,i=1,2=100=0

    求偏导可得
    { ∂ L ∂ x 1 = 2 x 1 − λ = 0 ∂ L ∂ x 2 = 2 x 2 − λ + μ = 0 \left\{\begin{array}{l} \begin{aligned} \frac{\partial L}{\partial x_{1}}&=2 x_{1}-\lambda=0\\ \frac{\partial L}{\partial x_{2}}&=2 x_{2}-\lambda+\mu=0 \end{aligned} \end{array}\right.

    x1Lx2L=2x1λ=0=2x2λ+μ=0

    分别解出
    { x 1 = λ 2 x 2 = λ 2 − μ 2 \left\{\begin{array}{l} \begin{aligned} x_{1}&=\frac{\lambda}{2}\\ x_{2}&=\frac{\lambda}{2}-\frac{\mu}{2} \end{aligned} \end{array}\right.

    x1x2=2λ=2λ2μ

    代入约束等式
    x 1 + x 2 = λ − μ 2 = 1 x_{1}+x_{2}=\lambda-\frac{\mu}{2}=1 x1+x2=λ2μ=1

    合并上面结果,
    { x 1 = μ 4 + 1 2 x 2 = − μ 4 + 1 2 \left\{\begin{array}{l} \begin{aligned} x_{1}&=\frac{\mu}{4}+\frac{1}{2}\\ x_{2}&=-\frac{\mu}{4}+\frac{1}{2} \end{aligned} \end{array}\right.

    x1x2=4μ+21=4μ+21

    最后再加入约束不等式

    − μ 4 + 1 2 ≤ α -\frac{\mu}{4}+\frac{1}{2} \leq \alpha 4μ+21α
    μ ≥ 2 − 4 α \mu \geq 2-4 \alpha μ24α

    底下分开三种情况讨论。

    1. α > 1 2 \alpha>\frac{1}{2} α>21 : 不难验证 μ = 0 > 2 − 4 α \mu=0>2-4 \alpha μ=0>24α 满足所有的KKT条件,约束不等式是无效的, x 1 ⋆ = x 2 ⋆ = 1 2 x_{1}^{\star}=x_{2}^{\star}=\frac{1}{2} x1=x2=21 是内部解,目标函数的极小值是 1 2 \frac{1}{2} 21
    2. α = 1 2 \alpha=\frac{1}{2} α=21 : 如同 1 , μ = 0 = 2 − 4 α \mu=0=2-4 \alpha μ=0=24α 满足所有的KKT条件, x 1 ⋆ = x 2 ⋆ = 1 2 x_{1}^{\star}=x_{2}^{\star}=\frac{1}{2} x1=x2=21 是边界解,因为 x 2 ⋆ = α x_{2}^{\star}=\alpha x2=α
    3. α < 1 2 \alpha<\frac{1}{2} α<21 : 这时约束不等式是有效的, μ = 2 − 4 α > 0 \mu=2-4 \alpha>0 μ=24α>0 ,则 x 1 ⋆ = 1 − α x_{1}^{\star}=1-\alpha x1=1α x 2 ⋆ = α x_{2}^{\star}=\alpha x2=α ,目 标函数的极小值是 ( 1 − α ) 2 + α 2 (1-\alpha)^{2}+\alpha^{2} (1α)2+α2
  2. 考虑优化问题
    min ⁡ f ( x ) = − 2 x 1 2 − x 1 2  s.t.  x 1 2 + x 2 2 − 2 = 0 − x 1 + x 2 ≥ 0 x 1 ≥ 0 , x 2 ≥ 0 (1) \tag{1} \begin{aligned} &\operatorname{min }f(\mathrm{x})=-2 \mathrm{x}_1^2-\mathrm{x}_1^2 \\ &\text { s.t. } \quad \mathrm{x}_1^2+\mathrm{x}_2^2-2=0 \\ &\quad-\mathrm{x}_1+\mathrm{x}_2 \geq 0 \\ &\quad \mathrm{x}_1 \geq 0, \mathrm{x}_2 \geq 0 \end{aligned} minf(x)=2x12x12 s.t. x12+x222=0x1+x20x10,x20(1)
    试验证 x ∗ = ( 1 , 1 ) T x^*=(1,1)^{\mathrm{T}} x=(1,1)T K K T \mathrm{KKT} KKT 点,并求出问题的 K K T \mathrm{KKT} KKT 对。
    【解】记
    f ( x ) = − 2 x 1 2 − x 1 2   g ( x ) = x 1 2 + x 2 2 − 2   h 1 ( x ) = x 1 − x 2   h 2 ( x ) = − x 1   h 3 ( x ) = − x 2 (2) \tag{2} \begin{aligned} \mathrm{f}(\mathrm{x}) &=-2 \mathrm{x}_1^2-\mathrm{x}_1^2 \\ \mathrm{~g}(\mathrm{x}) &=\mathrm{x}_1^2+\mathrm{x}_2^2-2 \\ \mathrm{~h}_1(\mathrm{x}) &=\mathrm{x}_1-\mathrm{x}_2 \\ \mathrm{~h}_2(\mathrm{x}) &=-\mathrm{x}_1 \\ \mathrm{~h}_3(\mathrm{x}) &=-\mathrm{x}_2 \end{aligned} f(x) g(x) h1(x) h2(x) h3(x)=2x12x12=x12+x222=x1x2=x1=x2(2)

    求梯度(都使用向量的形式写法,更紧凑),得到
    ∇ f ( x ) = [ − 4 x 1 − 2 x 2 ] , ∇ g ( x ) = [ 2 x 1 2 x 2 ] ∇ h 1 ( x ) = [ 1 − 1 ] , ∇ h 2 ( x ) = [ − 1 0 ] , ∇ h 3 ( x ) = [ 0 − 1 ] (3) \tag{3} \begin{aligned} \nabla \mathrm{f}(\mathrm{x})=\left[\begin{array}{c} -4 \mathrm{x}_1 \\ -2 \mathrm{x}_2 \end{array}\right], \quad \nabla \mathrm{g}(\mathrm{x})=\left[\begin{array}{l} 2 \mathrm{x}_1 \\ 2 \mathrm{x}_2 \end{array}\right] \\ \nabla \mathrm{h}_1(\mathrm{x})=\left[\begin{array}{c} 1 \\ -1 \end{array}\right], \quad \nabla \mathrm{h}_2(\mathrm{x})=\left[\begin{array}{l} -1 \\ 0 \end{array}\right], \quad \nabla \mathrm{h}_3(\mathrm{x})=\left[\begin{array}{l} 0 \\ -1 \end{array}\right] \end{aligned} f(x)=[4x12x2],g(x)=[2x12x2]h1(x)=[11],h2(x)=[10],h3(x)=[01](3)
    x ∗ = ( 1 , 1 ) T x^*=(1,1)^{\mathrm{T}} x=(1,1)T 代入上面5个式子,由 K K T \mathrm{KKT} KKT 条件有,

    { − 4 + 2 λ + μ 1 − μ 2 = 0 − 2 + 2 λ − μ 1 + μ 3 = 0 (4) \tag{4} \left\{\begin{array}{l} -4+2 \lambda+\mu_1-\mu_2=0 \\ -2+2 \lambda-\mu_1+\mu_3=0 \end{array}\right. {
    4+2λ+μ1μ2=02+2λμ1+μ3=0
    (4)

    因为
    { μ 2 h 2 ( x ) = 0 μ 3 h 3 ( x ) = 0 ⇒ { μ 2 ∗ = 0 μ 3 ∗ = 0 (5) \tag{5} \left\{\begin{array} { l } { \mu _ { 2 } \mathrm { h } _ { 2 } ( { \mathrm { x } } ) = 0 } \\ { \mu _ { 3 } \mathrm { h } _ { 3 } ( { \mathrm { x } } ) = 0 } \end{array} \Rightarrow \left\{\begin{array}{l} \mu_2^*=0 \\ \mu_3^*=0 \end{array}\right.\right. {
    μ2h2(x)=0μ3h3(x)=0{
    μ2=0μ3=0
    (5)

    所以(4)变为
    { − 4 + 2 λ + μ 1 = 0 − 2 + 2 λ − μ 1 = 0 (6) \tag{6} \left\{\begin{array}{l} -4+2 \lambda+\mu_1=0 \\ -2+2 \lambda-\mu_1=0 \end{array}\right. {
    4+2λ+μ1=02+2λμ1=0
    (6)

    求解 ( 6 ) (6) (6) 式,得到
    { λ ∗ = 1.5 μ 1 ∗ = 1 (7) \tag{7} \left\{\begin{array}{l} \lambda^*=1.5 \\ \mu_1^*=1 \end{array}\right. {
    λ=1.5μ1=1
    (7)

    这表明 x ∗ \mathrm{x}^* x K K T \mathrm{KKT} KKT 点, ( x ∗ , ( λ ∗ , μ ∗ ) ) \left(\mathrm{x}^*,\left(\lambda^*, \mu^*\right)\right) (x,(λ,μ)) K K T \mathrm{KKT} KKT 对,其中, λ ∗ = 1.5 , μ ∗ = ( 1 , 0 , 0 ) T \lambda^*=1.5 , \mu^*=(1,0,0)^{\mathrm{T}} λ=1.5μ=(1,0,0)T


分割线,下面待更新


3.2 内点法

内点法引入障碍函数将约束条件转化为目标函数,生成等价于原模型的优化问题。

3.3 积极集法

今天的文章二次规划优化算法_最优化方法马昌凤答案分享到此就结束了,感谢您的阅读。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/83476.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注