最优化 18 惩罚函数法

清华大学最优化课件

第13章

惩罚函数法

SUMT(Sequential unconstrained minimization technique)

序列无约束最小化技术 外点法：迭代点在可行域外部移动罚函数法 内点法：迭代点在可行域内部移动

清华大学最优化课件

外点法

min f ( x) ( A) s.t. g i ( x) 0 i 1,2, , m h ( x ) 0 j 1, 2, , l j 其中f ( x), g i ( x)(i 1,2, , m), h j ( x)( j 1,2, , l )在E上连续。 S {x| g i ( x) 0(i 1,2, , m), h j ( x) 0( j 1,2, , l )}n

清华大学最优化课件

引入罚项

p ( x) g i ( x) h j ( x)i 1 j 1

m

l

其中 ( y ), ( y )是连续函数，且满足 ( y ) 0 ( y ) 0当y 0当y 0

当y 0 ( y ) 0 当y 0 ( y ) 0函数 和 的典型取法： g i ( x) max 0, g i ( x)

h j ( x) h j ( x)

其中 1, 1均为给定常数，通常取 2。

清华大学最优化课件

min f ( x) s.t. g i ( x) 0 i 1,2, , m h j ( x) 0 j 1,2, , l min F ( x, ) f ( x ) p ( x )l m min F ( x, ) f ( x ) g i ( x ) h j ( x ) j 1 i 1

其中 是很大的正数。

清华大学最优化课件

min f ( x) ( x1 1) x s.t. g ( x) x2 1 0

2

2 2

解：定义罚函数 F ( x, ) ( x1 1) x max 0, ( x2 1) 2 2 2 2 2 ( x 1 ) x 1 2 2 2 2 ( x1 1) x2 ( x2 1) 2

x2 1 x2 1

清华大学最优化课件

F 2( x1 1) x1

x2 1 F 2 x2 x2 2 x2 2 ( x2 1) x2 1

F令 0 x1

F 0得 x2 1 ( ) 1

1 x1 x x2 1

清华大学最优化课件

min x1 x2 s.t. x1 x 0定义罚函数2 2 F ( x, ) x1 x2 ( x1 x2 ) 2 1 2 ( x1 x2 ) F ( x, ) 1 2 ( x x 2 )( 2 x ) 1 2 2 令 F ( x, ) 0,得

2 2

1 1 1 1 1 x , , 4 2 4 2

T

T

清华大学最优化课件

min f ( x) x1 x2 s.t. g1 ( x) x x2 0 g 2 ( x) x1 0解：定义罚函数 F ( x, ) x1 x2 max 0, x x22 1

2 1

max 0, x 2 1

2

F 2 1 2 2 max 0, x1 x2 x1 max 0, x1 ( 1) x1

F 1 2 max 0, x12 x2 ( 1) x2

清华大学最优化课件

令

F 0 x12 1

F 0得 x2

1 4 x1 ( x x2 ) 2 x1 0 2 1 2 ( x 1 x2 ) 0 1 1 1 x1 x2 2 2 2 (2 2 ) 2 x1 0 当 时，有 x 2 0

清华大学最优化课件

步骤

:

1.给定初始点x,初始罚因子 1 0( 1 1),放大( 0)

系数c 1,允许误差 0,置k 1。

2.以x

( k 1)

为初始点，求解无约束问题

min f ( x) k p ( x)设其极小点为x ( k )。3.若 k p ( x ( k ) ) ,则停止计算，得到点x ( k );否则，令 k 1 c k,置k: k 1,返回2。

清华大学最优化课件

例:用外点法求解

min ( x 1) s.t. x 2 0解：取x ( 0) 0, 1 1,令 p ( x) max 0, x 2 0 p ( x) 2 ( x 2)2

2

则

x 2 x 2

清华大学最优化课件

第一次迭代

求解无约束最优化问题： min F ( x, 1 ) ( x 1) 2 1 p ( x)2 ( x 1) 其中F ( x, 1 ) 2 2 ( x 1) 1 ( x 2) 3 (1)解得： x 2

x 2 x 2

1

令 2 10 1 10

1

x

(1)2

清华大学最优化课件

第二次迭代

求解无约束最优化问题： min F ( x, 2 ) ( x 1) 10 p ( x) ( x 1)其中F ( x, 2 ) 2 2 ( x 1) 10 ( x 2) 21 (2)解得： x 1112 2

x 2 x 2

令 3 10 2 100

1

x

(2)2

清华大学最优化课件

第三次迭代

求解无约束最优化问题： min F ( x, 3 ) ( x 1) 100 p ( x)2 x 2 ( x 1)其中F ( x, 3 ) 2 2 ( x 1) 100 ( x 2) x 2 201 (3)解得： x 101 2

以此类推，得序列： 3 21 201 2001,,,, 2 11 101 1001

x* 2

清华大学最优化课件

引理1对于由外点法所产生的序列 x ( k ),总有

(1) F ( x ( k 1), k 1 ) F ( x ( k ), k ) ( 2) p ( x( k 1)

) p( x )

(k )

(3) f ( x ( k 1) ) f ( x ( k ) )证明： (1)由F ( x, ) f ( x) p ( x)和 k 1 k知 F (x( k 1)

, k 1 ) f ( x f (x( k 1)

( k 1)

) k 1 p ( x( k 1)

( k 1)

)( k 1)

) k p( x

) F (x

, k )(k )

x是F ( x, k )的极小点, 对 x,有F ( x, k ) F ( x, k )(k )

F ( x ( k 1), k ) F ( x ( k ), k ) F ( x ( k 1), k 1 ) F ( x ( k ), k )

清华大学最优化课件

(2) x和x(k )

( k 1)

分别使F ( x, k ), F ( x, k 1 )取极小( k 1)

f (x

( k 1)

) k p( x

) f ( x ) k p ( x ) (*)

(k )

(k )

f ( x ( k ) ) k 1 p ( x ( k ) ) f ( x ( k 1) ) k 1 p( x ( k 1) )

k p ( x ( k 1) ) k 1 p ( x ( k ) ) k p ( x ( k ) ) k 1 p ( x ( k 1) ) k 1 k p( x ) k 1 k p( x(k ) ( k 1)

)

p( x ) p( x(3)由(*),得 f (x( k 1) (k )

(k )

( k 1)

)

(2) p( x ( k 1) ) p ( x ( k ) ) (3) f ( x ( k 1) ) f ( x ( k ) )

) f ( x ) k p( x ) p( x 0

(k )

( k 1)

)