约束优化问题的极值条件

等式约束优化问题的极值条件

求解等式约束优化问题 m i n f (x ) s . t . h k (x )=0(k =1, 2, ⋅⋅⋅, m ) 需要导出极值存在的条件，对这一问题有两种处理方法：消元法和拉格朗日乘子法（升维法） 一、消元法（降维法）

1. 对于二元函数 min f (x 1, x 2) s . t . h (x 1, x 2)=0，

根据等式约束条件，将一个变量x 1表示成另一个变量x 2的函数关系x 1=ϕ(x 2)，然后将这一函数关系代入到目标函数f (x 1, x 2)中消去x 1变成一元函数F (x 2) 2. 对于n 维情况 min f (x 1, x 2, ⋅⋅⋅, x n )s . t . h k (x 1, x 2, ⋅⋅⋅, x n )=0(k =1, 2, ⋅⋅⋅, l ) 由l 个约束方程将n 个变量中的前l 个变量用其余的n -l 个变量表示：

x 1=ϕ1(x l +1, x l +2, ⋅⋅⋅, x n ) x 2=ϕ2(x l +1, x l +2, ⋅⋅⋅, x n ) ...

x l =ϕl (x l +1, x l +2, ⋅⋅⋅, x n )

将这些函数关系代入到目标函数中，得到F (x l +1, x l +2, ⋅⋅⋅, x n ) 二、拉格朗日乘子法（升维法）

设x =(x 1, x 2, ⋅⋅⋅, x n ) T ，目标函数是f (x )，约束条件h k (x )=0(k =1, 2, ⋅⋅⋅, l ) 的l 个等式约束方程。为了求出f (x )的可能极值点x *=(x 1*, x 2*, ⋅⋅⋅, x n *) T ，引入拉格朗日乘子λk (k =1, 2, ⋅⋅⋅, l ) ，并构成一个新的目标函数

F (x , λ) =f (x )+∑λk h k (x )

k =1l

把F (x , λ)作为新的无约束条件的目标函数来求解它的极值点，满足约束条件

h k (x )=0(k =1, 2, ⋅⋅⋅, l ) 的原目标函数f (x )的极值点。 F (x , λ)具有极值的必要条件

∂F ∂F

=0(i =1, 2, ⋅⋅⋅, n ) ，=0(k =1, 2, ⋅⋅⋅, l ) 可得l +n ∂x i ∂λk

个方程，从而解得x =(x 1, x 2, ⋅⋅⋅, x n ) T 和λk (k =1, 2, ⋅⋅⋅, l ) 共有l +n 个未知变量的值。 即x *=(x 1*, x 2*, ⋅⋅⋅, x n *) T 是函数f (x )的极值点的坐标值。

不等式约束优化问题的极值条件

一、一元函数在给定区间上的极值条件

对于一元函数min f (x ) s . t . g 1(x )=a -x ≤0g 2(x )=x -b ≤0

dg 1dg 2⎧df

+μ+μ=012⎪dx dx dx ⎪

极值条件可以表示成：⎨μ1g 1=0, μ2g 2=0

⎪μ1≥0, μ2≥0⎪⎩

引入作用下标集合J (x )=j g j (x )=0, j =1, 2则可将上式改写成：

{}

dg j ⎧df

=0⎪+∑μj

dx dx j ∈J ⎪

⎨g j (x )=0, j ∈J 即只考虑起作用的约束及其对应的拉格朗日乘子。 ⎪μ≥0, j ∈J

j

⎪⎩

二、库恩塔克条件

1、对于多元函数min f (x ) s . t . g j (x )≤0(j =1, 2, ⋅⋅⋅, m )

通过引入m 个松弛变量，是不等式约束变成等式约束，组成相应的拉格朗日函数

2F x , x , μ=f (x ) +∑μj g j (x )+x n +j

j =1

()

m

()

对应一元函数的极值条件可以推导出多元函数的极值条件为：

m ⎧∂f x *∂g j x *

+∑μj =0, i =1, 2,..., n ⎪∂x ∂x j =1i i ⎪⎪*

μj g j x =0, j =1, 2,..., m ⎨

⎪μj ≥0, j =1, 2,..., m ⎪⎪⎩

()

()

()

引入起作用的约束的下标集合可改写成：

⎧∂f x *∂g j x *

+∑μj =0, i =1, 2,..., n ⎪∂x ∂x j ∈J i i ⎪⎪*

g j x =0, j ∈J ⎨

⎪μj ≥0, j ∈J ⎪⎪⎩

()

()

()

将上式偏微分形式表示为梯度形式得：

-∇f x *=∑μj ∇g j x *

j ∈J

*

几何意义：在约束极小值点x 处，函数f (x ) 的负梯度一定能表示成所有起作用

()()

的约束在该点梯度的非负线性组合。 2、同时具有等式和不等式约束的优化问题

min f (x ) s . t . g j (x )≤0(j =1, 2, ⋅⋅⋅, m ) ，h k (x )=0(k =1, 2,..., l ) 极值条件可表示为：

l ∂g j ⎧∂f ∂h k

+μ+λ=0, i =1, 2,..., n ∑∑j k ⎪∂x ∂x ∂x k =1i i ⎪i j ∈J

g j (x )=0, j ∈J ⎨

⎪μj ≥0, j ∈J ⎪⎩