运用改进的线性规划算法求解分片线性方程组
清华大学学报(自然科学版) 2009年第49卷第10期
CN 1122223 N . 49, N o . 10J T singhua U niv (Sci &Tech ) , 2009, V o l w 5
. net . cn h ttp : qhxbw . ch inaj ournal
运用改进的线性规划算法求解分片线性方程组
李 颖, 黄晓霖, 王书宁
(清华大学自动化系, 北京100084)
摘 要:为了提高求解分片线性方程组的线性规划算法的计算效率, 提出基于线性规划算法的改进算法。首先找出若干线性区域组成的超立方体, 使得方程组函数在此超立方体上表现为凸函数或凹函数, 然后在超立方体上求解一次特定的线性规划问题并判断此超立方体是否含有方程组的解。该文给出的数例中改进线性规划算法需要求解的线性规划问题数目仅为线性规划算法的1 4。改进线性规划算法无需在全部线性区域上求解线性规划, 因此相对线性规划算法提高了计算效率, 提高程度取决于方程组函数的性质。关键词:电路求解; 分片线性方程组; 线性规划中图分类号:TM 133
文章编号:100020054(2009) 1020017204
文献标识码:A
分片线性方程组在特定区域内表现为线性方程组的
性质通常可以简化大规模非线性方程组的求解
。
一种求解分片线性方程组的思路是尽可能多地在较短时间内排除不含方程组解的线性区域, 然后在不能排除的区域上求解线性方程组从而得到方程组的全部解。文[6-12]提出了若干种基于上述思想的算法。文[7-8]:通过判断[9-12]介绍了一种基于:通过在各分片线性区域上求解指域。线性规划算法能够更有效地判断出不含方程组解的线性区域, 从而减少需要求解的线性方程组的数目, 提高了计算效率, 但是需要在所有线性区域上求解线性规划问题。为了避免在所有线性区域上求解线性规划问题, 本文指出当方程组函数在若干线性区域组成的超立方体上表现为凸函数或凹函数时, 只需求解一次特定的线性规划问题就可能判断出此超立方体不含方程组的解, 减少需要求解的线性规划数目, 从而提高算法的计算效率。
[1-12]
F i nd i ng a ll of ise -l i near equa tion s usi li programm i ng
L I Ying , HUANG Xia o lin , W ANG S huning
(D epart men t of Automation , Tsi nghua Un iversity ,
Be ij i ng 100084, Ch i na )
Abstract :A linear p rogramm ing (L P ) algo rithm w as developed to mo re efficiently find all so luti ons of p iecew ise 2linear equati ons than the traditi onal L P algo rithm.
T his algo rithm first finds the
hypercube consisting of the vari ous linear regi ons w ith the equati ons being o ther convex o r concave in this hypercube . T hen, specific L P p roblem s are so lved in the hypercube to deter m ine w hether the so luti on exists . Fo r the examp le given in th is paper, the algo rithm uses only 25%as m any linear p rogram s as the conventi onal L P algo rithm.
T hus
th is algo rithm
is mo re efficient
than
the
conventi onal L P algo rithm since it reduces the num ber of linear p rogram s that need to be so lved .
The i m p roved perfo r m ance
compared to the conventi onal L P algo rithm depends on the equati on p roperties . Key words :circuit
so lving;
p iecew ise 2linear
equati ons;
linear
p rogramm ing
1 问题描述
部分实际电路可以用式(1) 表示[11]:
(1) f (x ) =P g (x ) +Q x -r =0.
T n n
其中f (x ) =[f 1(x ) , f 2(x ) , …, f n (x ) ]:R →R ; x
T n
=(x 1, x 2, …, x n ) ∈R 表示电路中各电阻上的电压
或电流; P 、Q 为n ×n 常矩阵; r =(r 1, r 2, …, r n ) ∈n
R 为常向量; g (x ) =[g 1(x 1) , g 2(x 2) , …,
收稿日期:2008209215
基金项目:国家自然科学基金资助项目(60674025, 60534060) ;
国家“九七三”重点基础研究项目(2002CB 312200)
作者简介:李颖(1984—) , 男(汉) , 湖南, 硕士研究生。
通讯联系人:王书宁, 教授, E 2. tsinghua . edu . cn m ail :s w ang @m ail
T
求解非线性方程组的一个有效的思路是将非线性方程组近似为分片线性方程组来求出原非线性方
程组的近似解; 此外在电路仿真中, 有一部分非线性元器件可以用特定模型近似为分片线性元器件。
18
T
n
n
清华大学学报(自然科学版) 2009, 49(10)
g n (x n ) ]:R →R 为连续分片线性方程组, g i (x i ) :
11n
R →R (i =1, 2, …, n ) 。对于函数f j (x ) (x ∈R , j =
n
称Α。j , k 为凸变形点
i
假设在Αj , k (k =1, 2, …, m i +1) 中有q 个变形点,
i i 记其下标为Σj (1) , Σj (2) , …, Σj (q ) 并令Αj , Σ(1)
j j i
i
i i i i i
1, 2, …, n ) , 如果f j (x ) =
∑f
i =1
i
j (x i ) , 其中f (x i ) 为i j
i i i i
11
R →R 的函数, 则称f j (x ) 具有可分性。容易发现, 式(1) 中f j (x ) (j =1, 2, …, n ) 具有可分性, f j (x ) =n
上述q +1个变形点将其分割成了q 个区间I j , t =
i i [Αj , Σ(t ) , Αj , Σ(t +1) ],1≤t ≤q 。对每一个区间I j , t , 若j j i
Αj , Σ(t ) 为凹变形点, 则Υj (x i ) 在I j , t 上为凹函数; 若j
^i
i i
^i
∑f
i =1
i
j (x i ) (i =1, 2, …, n ) , 其中f i j (x i ) :R 1→R 1为
i
i
i i
^i
定义在[l , u ]上的一维函数。
i 。例如在Αj , Σ(t ) 为凸变形点, 则Υj (x i ) 在I j , t 上为凸函数j
i i
^i
2 具有特殊性质的超立方体
若在方程组定义域D 内某一区域上分片线性方
程组f (x ) 为线性方程组, 则称这一区域为线性区
1122
域。设方程组定义域为D =[l , u ]×[l , u ]×…×n n
[l , u ],首先将方程组的定义域划分成若干线性区
i
域。f j (x i ) 在x i 方向上取m i +1个分隔点:
i i i i i Αj , k (k =1, …, m i +1, Αj , 1=l , Αj , m +1=u ) . i
图1中, Α。Α1为凹变形点, Α3为凸变形点1、Α3以及
(x ) 为凹Α7将[Α1, Α7]划分为2个子区间, [Α1, Α3]上Υ(x ) 为凸函数。函数, 在[Α3, Α7]上Υ
为了简单起见, 令Αm i +1, k =Α2, k =…=Αn , k (Π1≤k ≤
i
1) 。这样f j (x i ) (j =1, 2, …, n ) 在x i 方向就被划分为
m i 段分片线性函数并且可以得到f j (x i ) 在各段上的
i i
线性逼近函数Κj , k (x i ) (k =1, …, m i ) , j k
i
i i i
(x i ) =A i
j , k
x i +B
i j , k
i i
(k =1, , i k j , k ) i
j
i (Αj , k ) (k =1, 2, …, m i , 可以表示为:
O ={x =(x 1, x 2, …, x n ) a i ≤x i ≤b i ,
T
图1 凹、凸变形点图示
找到变形点并根据变形点将[l , u ]划分为I j , t
i i =[Αj , Σ(t ) , Αj , Σ(t +1) ],1≤t ≤q 之后, 若Υj (x i ) 在I j , t 上j j
i i
^i
i i i
^i
i =1, 2, …, n }.
i i i
将定义域进行划分之后, 得到f j (x i ) 在[l , u ]上
为凸函数, 则[13]
Υj (x i ) =m ax Κj , k (x i ) , Πx i ∈I j , t , i
i
i
k ∈S
j
^i
的分片线性逼近函数为Υ(x i ) =Κ(x i ) (x i ∈[Α,
i Αj , k +1],k =1, 2, …, m i ) , 根据可分性, f j (x ) 在定义
n
i
j i j , k i j , k
其中
S j ={k Σj (t ) ≤k
i i i
同理若Υj (x i ) 在I j , t 上为凹函数, 则Υj (x i ) =
i
i
i
域内的分片线性逼近函数为Υj (x ) =
i
∑Υ(x ) (i =
i
j
i
i =1
i j , k
^
1, 2, …, n ) 。对于Υj (x i ) 在各段的斜率A …, m i ) , 若
A A A
i i j , k i j , k i j , k
(k =1, 2,
m in Κj , k (x i ) , Πx i ∈I j , t , 其中S j ={k Σj (t ) ≤k
i
i
i
i
k ∈S
j
^i
>A >A
i
j , k +1i
j , k +1i
j , k -1
且A ,
i
j , k -1
A
i j , k
, ,
1
k =1; k =m . i
+1) }。
且A
i
j , k -1i
j , k -2
3 改进的线性规划算法
(2)
称Α。若j , k 为凹变形点
A A i
j , k i j , k i j , k
线性规划算法在任意一个线性区域上需要求解线性规划问题式(4) (5) 来判断方程组在此线性区域上是否有解。
m in Υw (x ) ,
s . t .
A
i
j , k +1i
j , k +1i
j , k -1
且A ,
i
j , k -1
>A
i j , k
, ,
1
k =1; k =m . i
且A
i
j , k -1i
j , k -2
Υj (x ) =0,
a j ≤x j ≤b j ,
j =1, 2, …, w -j =1, 2, …, n .
1;
(4)
(3)
李 颖, 等: 运用改进的线性规划算法求解分片线性方程组19
n
m ax Υw (x ) ,
s . t .
Υj (x ) =0,
a j ≤x j ≤b j ,
j =1, 2, …, w -j =1, 2, …, n .
1;
m ax
(5)
s . t .
z i ≤Κw , k (x i ) ;
i
∑z ,
i
i =1
当式(1) 中P 为单位矩阵时, 设O 为定义域内一
个包含若干个线性区域的超立方体, O ={x =(x 1,
T i
x 2…, x n ) a i ≤x i ≤b i , i =1, 2, …, n }且Υw (x i ) 在[a i ,
Υj (x ) =0,
a j ≤x j ≤b j , k ∈S w .
i
j =1, 2, …, w -j =1, 2, …, n ;
1;
(8)
b i ]上为凸函数(Πi =1, 2, …, n ) , 那么Υw (x ) 在O 内
i 为凸函数。已知在划分分片线性区域时Υw (x i ) 在x i
方向上取的分隔点为Αj , k (k =1, …, m i +1) , 设Αj , y =i
a i , Α
i
j , y ′
i
i i
因此, 当Υw (x ) 在O 上各个方向均为凸函数时, 只需求解式(7) 就可以得到O 上的m in Υw (x ) , 如果
同理, 当Υm in ΥO 内没有方程组的解。w (x ) >0, 说明w (x ) 在O 上各个方向均为凹函数时, 求解式(8) 就可
得到m ax Υw (x ) , 如果m ax Υw (x )
=b i , 在O 内Υ(x i ) =m ax Κ(x i ) , Πx i ∈i
i
w
i w , k
k ∈S
w
[a i , b i ],其中S w ={k y i ≤k
i n
n
w , i
程组的解。设O 在x i 方向上由m i (m i ≥1) 段分片线性
区间组成, 则O 内共有M =m 1×m 2×…×m n 个线性
(x i ) ,
Υw (x ) =
∑Υ
i =1
(x i ) =
∑m ax Κ
i =1
k ∈S
i
w
i w , k
式(4) 可以写成:
n
m in
∑m ax Κ
i =1
i w , k (x i ) ,
1;
(6)
Υj (x ) =0, s . t .
a j ≤x j ≤b j , k ∈S w .
i
j =1, 2, …, w -j =1, 2, …, n ;
区域。相对线性规划算法需要在M 个线性区域上求
解线性规划问题式(4) 和式(5) , 现在只需求解一次线性规划就可能排除M 个线性区域。
:将方程组定义, 。对某个超, 按线性; 对函数在其上表现为凸函数的超立方体, 求解式(7) 所示的线性规划问题, 若对任意w 有解大于0或不存在, 则此超立方体上不含方程组的解; 同理对函数在其上表现为凹函数的超立方体, 求解式(8) 所示线性规划问题, 若对任意w 有解小于0或不存在, 则此超立方体上不含方程组的解。如果对w =1, 2, …, n 均不能排除此超立方体, 则将其拆成线性区域按线性规划算法求解。
:
n
z i ≥Κ(x i ) ;
i w , k
z ,
i
i =1
s . t .
Υj (x ) =0,
a j ≤x j ≤b j , k ∈S w .
i
j =1, 2, …, w -j =1, 2, …, n ;
1;
(7)
33333
理由如下:设x =(x 1, …, x n , z 1, …, z n ) 是式
(7) 的最优解, 则有z i =m ax Κ(x i ) , Π1≤i ≤n , 因
i
i w , k
k ∈S
w
3
4 数 例
考虑下述非线性方程组:
f 1(x ) =x 1-f 2(x ) =x 2-3
3
此x =(x , …, x n ) 为式(6) 的可行解。又设z =(x 1, …, x n , z 1, …, z n ) , 其中z i =m ax Κ(x i ) 为式(6) 的i
i
w , k
k ∈S
w
3
31
3
^^
4x 1+2x 1+x 2=0,
2
2
^^^^
4x 2+3x 2+x 1+1=0.
任一可行解。可以看出z 亦是式(7) 的可行解, 因此在O 上求解式(7) 等价于求解式(6) 。
i
同理, 若Υw (x i ) 在[a i , b i ]上为凹函数(Πi =1, 2, i i
…, n ) , 则Υ设Α=b i , O 为凹函数。w (x ) 在j , y =a i , Αj , y ′
i i
^
定义域为[0, 4]×[0, 4],取x i ={0,0. 5, 1, …,
3. 5, 4},i =1, 2为各坐标轴上分片线性区间起点。对f 1(x ) 进行符号判断之后, 得到可能含有方程组解的矩形区域[0. 5, 1]×[0, 4],[1, 1. 5]×[0, 4],[1. 5, 2]×[0, 4],[2, 2. 5]×[0, 4],[2. 5, 3]×[0, 4],[3, 3. 5]×[0, 4]。
原有的线性规划算法需要将这6个矩形区域各自在x 2方向上以x 2∈{0,0. 5, 1, …, 3. 5, 4}为起点划分为8个更小的线性矩形区域。而按照改进的线性规划算法, 这6个区域只需各自划分为2个更小的区域。例如矩形区域[1. 5, 2]×[0, 4]原本需要划分
在O 内Υw , i (x i ) =m in Κw , k (x i ) , Πx i ∈[a i , b i ],其中i
i
k ∈S
w
n
S ={k y i ≤k
i w n
∑Υ
i =1
w , i
(x i ) =
∑m in Κ
i =1
i k ∈S
w
i w , k (x i ) , 求解式(5) 等价于求解:
20
清华大学学报(自然科学版)
[4]U sh ida A , N akam ura T.
C ircuits,
System s,
2009, 49(10)
Interval analysis of nonlinear
Comm unicati on.
Japan:T he
为[1. 5, 2]×[0, 0. 5],…, [1. 5, 2]×[3. 5, 4]等8个矩形区域(如图2a 所示) , 而改进的线性规划算法则只需将[1. 5, 2]×[0, 4]划分为[1. 5, 2]×[0, 1]、[1. 5, 2]×[1, 4]这2个矩形区域(如图2b 所示) , 其中f 2(x ) 的分片线性逼近函数Υ. 5, 2]×[0, 2(x ) 在[11]上为凹函数, 在[1. 5, 2]×[1, 4]上为凸函数。在[1. 5, 2]×[1, 4]上使用改进的线性规划算法可直接计算得出Υ2(x ) 满足式(11) 的约束条件下的最小值
resistive circuits [C] P roceedings of Jo int T ech Conf
Computers,
IE I CE P ress, 1989:499-505.
[5]V andenberghe L , D e M oo r B L , V andew alle J.
generalized linear comp lem entarity p roblem app lied to the comp lete analysis of resistive p iecew ise 2linear circuits [J].
IE E E T rans C ircu its S y ste m s , 1989, 36:1382-
1391.
[6]Yam am ura K, O ch iai M. A n efficient algo rithm fo r finding all so luti ons of p iecew ise 2linear resistive circuits [J]. IE E E
T rans C ircu its S y ste m s I , 1992, 39:213-
大于0, 说明在[1. 5, 2]×[1, 4]中不含方程组的解。相比原有算法需要求解6次线性规划来判断[1. 5, 2]×[1, 4]是否含有方程组的解, 改进的线性规划算法只需求解1次。同理在[1. 5, 2]×[0, 1]上只需求解1次线性规划算法就可判断出不含方程组的解。因此在[1. 5, 2]×[0, 4]上, 改进的线性规划算法总共需要求解2次线性规划问题, 数目仅为原线性规划算法的1 4
。
221.
IE E E T rans
[7]Yam am ura K. F inding all so luti ons of p iecew ise 2linear
551.
circuits
[J].
resistive circuits using si m p le sign tests [J].
C ircu its S y ste m s I , 1993, 40:546-
[8]Yam am ura K, M ish ina M. A n algo rithm fo r finding all so luti ons
of
p iecew ise 2linear
resistive
In ternational J ou rnal of C ircu it T heory and A p p lica tions ,
1996, 24:223-231. [9]
Yam am ura K,
O hsh i m a T.
F inding all so luti ons of
p iecew ise 2linear resistive circuits using linear p rogramm ing [J]. IE E E T rans C ircu its S y ste m s I , 1998, 45:434-445. [10]Yam am ura K, T anaka S . Perfo r m ance evaluati on of the L P
test algo rithm fo r finding luti ons of p iecew ise 2linear [J]. am tiona l J ou rna l of
C ircu it
T A , (5) :501-
506.
K . F inding all so luti ons of
1120.
so luti ons of
resistive circuits using an L P test [J]. IE E E
T rans C ircu its S y ste m s I , 2000, 47:1115-
[12]Yam am ura K, Kancko R. F inding all
p iecew ise 2linear resistive circuits using the si m p lex m ethod [J]. IE E E T rans C ircu its S y ste m s I , 2003, 50:160-165. [13]ZHAN G H ao, W AN G Shuning .
p iecew ise 2linear 212-217.
app roxi m ati on
Global op ti m izati on of [J].
J ou rnal
of
separable objective functi ons on convex po lyhedra via
图2 两种算法的区域划分
C o m p u ta tiona l and A p p lied M a the m a tics , 2006, 197(1) :
5 结 论
本文提出的改进线性规划算法利用函数在某些超立方体上表现为凸函数或凹函数时具有的特殊性质改进了线性规划算法, 使得通过求解一个线性规划问题而排除多个线性区域成为可能。根据数例中非线性方程组的求解过程来看, 改进的线性规划算法的运算量相对线性规划算法有所减少。
参考文献 (References )
[1]
Chua L O ,
Ying R L
P.
F inding all so luti ons of
229.
p iecew ise 2linear circuits [J]. In terna tiona l J ou rnal of C ircu it
T heory and A p p lica tions , 1982, 10:201-
[2]H uang Q , L iu R. A si m p le algo rithm fo r finding all so luti ons of p iecew ise 2linear netwo rk s [J].
S y te m s , 1989, 36:600-IE E E T rans C ircu its
[3]N ish i T.
660.
A n efficient m ethod to find all so luti ons of
p iecew ise 2linear resistive circuits [C] P roceedings of IEEE Internati onal Sympo sium on C ircuits and System s . Po rtland:IEEE P ress, 1989:2052-2055.