起作用集法(Active Set Method)是一种用于求解约束优化问题的有效算法,特别适用于二次规划问题。以下是使用起作用集法解决二次规划问题的基本步骤和概念。1 q9 d% u0 H0 n# G; E) U G
. X8 q% G8 [8 j) X6 c### 二次规划问题的形式& T5 n) D6 E2 e) \' P9 R% W6 x
* j1 l/ V& u/ t% }! }5 ?# H
二次规划问题通常可以表示为:2 G) a, v+ i. B5 X+ R+ m2 l L1 o
9 x# p) {1 \% L* W/ T" p# M+ K$ R
\[ 5 E2 z% S/ `2 P! A- C) ` P\text{Minimize } f(x) = \frac{1}{2} x^T Q x + c^T x p1 N t& c( e7 ^" ~$ ^0 |, {
\]2 M4 C' a( i" \- E* V
; e" C1 z! a( a5 `- z/ e约束条件为: F, u6 s2 R( b0 b ! }( G2 g. Q& f& }3 X" A, V\[ # K1 h" ~* @1 E* KAx \leq b 5 N8 v( f! D! N/ k) I$ p6 M\] # N: b2 u+ o! S4 b; i2 J+ j3 ~ P2 o# C: E. _6 t
\[ 8 Z& W* N4 k' F$ `, {" m ?x \geq 0 / u8 Y, S& u: Y7 \+ K9 r\]) @+ W; |7 u- U. B8 H: O
- A) y) i4 t6 K! n其中,\(Q\) 是一个对称正定矩阵,\(c\) 是一个向量,\(A\) 是约束条件的系数矩阵,\(b\) 是约束条件的右侧向量。 ; @' L% `1 O1 S( u8 z ; O- U. d( i+ X b0 W8 h6 m### 起作用集法的步骤8 f0 c* [- ~! K2 M, ^3 V7 o" c; a
8 G" x m7 |, l' A7 @
1. **初始化**: 1 ?- S- \5 l- k9 |( ` - 选择一个初始可行解 \(x_0\)。 # l9 X- a. A, T - 确定初始的起作用集(即当前活动的约束条件)。- b: ^! ?9 D% U; ~
" \9 \+ T: D/ q; e
2. **构造拉格朗日函数**:( H7 g8 f$ K6 g9 D
- 对于当前的起作用集,构造拉格朗日函数:3 Y9 ^8 ?) O! @; m3 E6 D
0 @* S( M+ S" X4 U: e2 f \[ 9 y! N) q- L( h L(x, \lambda) = \frac{1}{2} x^T Q x + c^T x + \lambda^T (b - Ax)- B z' v7 N; w7 V% |6 Z
\]2 o; g$ S4 g) B+ o7 D; l
, l! `' e5 s3 |7 l7 J3 h3. **求解一阶条件**:& f. r7 b, L, s. z F
- 对 \(L\) 关于 \(x\) 和 \(\lambda\) 分别求偏导数,并令其等于零,得到一个方程组。 ) V4 P: ]2 L2 I 8 t% i0 k- g a, k, E4. **更新解**:" @$ K J6 ?& ?$ g; ~3 m0 r
- 通过求解上述方程组,得到新的解 \(x\)。 , V1 [* t- e: A# a& E& T - 检查新的解是否满足所有约束条件。- ^. c2 {# p- R- O8 N4 n
$ y* f& t; p: L
5. **更新起作用集**:4 |1 L0 W$ B" X9 o" b
- 如果新的解违反了某些约束条件,则将这些约束条件加入起作用集。" O) f& u" E9 k) U' ]4 \( P# I
- 如果新的解满足所有约束条件,则检查是否可以退出当前的起作用集。 9 f. S. O1 X# {$ d5 a# P1 F3 [* D5 U: g( p x
6. **迭代**:3 E3 E7 c$ G' B3 Z; p
- 重复步骤 2 到 5,直到满足收敛条件(例如,目标函数值的变化小于某个阈值)。3 D3 s' b z4 J$ N$ ?- e& \
2 u- Q( b$ q- t% S2 o: \. L7. **确定最优解**:. B: J7 i# Z) x
- 当达到收敛条件时,当前解即为最优解。( P( ]" y& E0 O% k+ t2 i
5 E$ I. x! o8 o% M" K. P8 J
### 示例/ s. q( y3 O# E1 r
3 |3 s% d2 ]9 S' @假设我们有一个简单的二次规划问题: $ J! W( C, ]' b c% G4 L9 [' Y z, j7 g7 V\[& t* G: Z- [4 w) y
\text{Minimize } f(x) = x_1^2 + x_2^2 0 F+ }+ d& `9 W% ], [\]; n7 b- y: A* V. k. }7 Y- k" {
) | Y1 F+ o: w s* s
约束条件为: " U9 a( r5 p5 J6 h" G/ ?, n! o' O, t t4 {- K' A
\[( [3 O `2 h' f2 Y3 e1 N$ Y
x_1 + x_2 \leq 1 . q/ y& Z7 Z8 o& P: F" m0 s/ k\] $ y' |& E2 t7 V/ X2 y, ^# s9 ^ ) Q. `. V8 N' b1 Z/ g) c% K\[ # q( B" Q. f5 c3 Rx_1, x_2 \geq 03 n. k7 M. \! A
\]: u% `! F d5 z g6 S& `8 f3 n
: G+ H. z. [( K3 l* K. @**步骤**: 6 ^* M! @1 p2 M/ C: T6 D 4 c5 C: k3 @/ e# ~* ~4 ~# L! h1. **初始化**:) Z) ?! l$ r% |) o/ b
- 选择初始解 \(x_0 = (0, 0)\),起作用集为空。8 n3 l- t; ~+ `7 {
8 L+ w5 L/ R% K
2. **构造拉格朗日函数**: . `1 o, I T/ e. ~/ O0 |4 { - 对于当前的起作用集,构造拉格朗日函数。 0 {3 o* Y+ E, z! p9 H9 m0 o, \. D/ h( {. O: B% l" n' }
3. **求解一阶条件**: 3 S: p+ v" w$ j* h; ~5 j# F. b( X& d - 计算偏导数并求解。 5 A( Z) e* U( |1 u3 |5 t; u9 N7 A
4. **更新解**:* b: P. K& Q1 D
- 得到新的解 \(x\),检查是否满足约束。 ! d: P% G" |# k7 l# }* }1 g# d L1 Z4 r" Q0 A
5. **更新起作用集**: . ` @2 } @/ ?% S9 A - 如果 \(x_1 + x_2 > 1\),则将约束 \(x_1 + x_2 \leq 1\) 加入起作用集。* D# d% b3 k; d$ J5 E* ^; e1 O
* n; C( x5 v3 }2 N7 ?; M- E8 W
6. **迭代**:/ |2 l( i( Z I
- 重复上述步骤,直到收敛。" K% e& ~& L8 V9 M: u0 q- }
6 D4 [5 F" a% R( q
7. **确定最优解**: & t) K' k1 l; q5 q0 e - 最终得到的解即为最优解。1 S5 q* x# C5 d2 U$ v2 g
" o4 a6 ^ r/ Z- Y2 {" Q' g' |### 总结' Q! A4 H4 v' f; f( X' y9 r o: `
) J. u; W$ ~( }
起作用集法是一种有效的求解二次规划问题的算法,通过动态调整活动约束集来逐步逼近最优解。它适用于处理具有线性约束的优化问题,尤其在约束条件较多的情况下表现良好。9 y: O1 o& k# Q9 V
, K U4 t; {# |/ ?* c$ Q A/ N
; O# i w k/ V; Y! O
) r. V( s f. J0 f. C