没有合适的资源?快使用搜索试试~ 我知道了~
求解带线性等式约束的界约束优化问题的有效集算法
需积分: 1 1 下载量 178 浏览量
2019-12-29
01:34:22
上传
评论
收藏 304KB PDF 举报
温馨提示
试读
11页
求解带线性等式约束的界约束优化问题的有效集算法,闫秀娟,王永丽,许多实际应用问题可以被表述为带界约束和单一线性等式约束的优化问题。本文介绍了一种新的求解此问题的方法。该方法利用零空间法
资源推荐
资源详情
资源评论
http://www.paper.edu.cn
- 1 -
中国科技论文在线
求解带线性等式约束的界约束优化问题的
有效集算法
#
闫秀娟,王永丽,贺国平
**
基金项目:国家自然科学基金(10971122);山东省自然科学基金(Y2008A01);高校博士点专项科研基
金(20093718110005);山东省博士基金项目(2010BSE06047)
作者简介:闫秀娟,(1986-),女,硕士研究生,主要研究方向:控制理论及其应用。
通信联系人:王永丽,(1977-),女,副教授,主要研究方向:最优化理论及其应用。E-mail:
wangyongli@sdkd.net.cn
(山东科技大学信息科学与工程学院,山东 青岛 266590) 5
摘要:许多实际应用问题可以被表述为带界约束和单一线性等式约束的优化问题。本文介绍
了一种新的求解此问题的方法。该方法利用零空间法,将原始问题转化为与之等价的只带线
性不等式约束的优化问题,再用部分谱投影梯度法求解转换后的问题,从而求得原问题的解。
该方法将原问题中的等式约束去掉,使问题变为只含有线性不等式约束的优化问题,简化了
问题的约束形式,并降低了问题的维度。算法具有全局收敛性。 10
关键词:运筹学与控制论;界约束;线性约束;零空间法;谱投影梯度
中图分类号:O224
An Active Set Method for Box Constrained Optimization
with Linear Equality Constraint
15
YAN Xiujuan, WANG Yongli, HE Guoping
(College of Information Science and Engineering, Shandong University of Science and
Technology, ShanDong QingDao 266590)
Abstract: Many practical problems can be formulated as optimization problems with bound
constraints and a single linearly equality constraint. In this paper, a method for this kind of 20
problem is introduced. Using the null-space methods, this framework transforms the original
problem into a linearly inequalities constrained optimization problem, and then, utilizes partial
spectral projected gradient method to solve the new equivalent problem so as to solve the original
problem. The framework removes the equality constraints of the problem, making the problem as
an optimization problem with linear inequality constraints, simplifying the form of constraints and 25
reducing the dimension of the problem. Convergence proofs are given.
Keywords:
Operational research and control theory; box constrained optimization; linear
constrains; null-space methods; spectral projected gradient
0 引言 30
考虑如下问题
min ( )
.. ,
.
T
fx
s
tAx b
lxu
=
≤
≤
(1)
其中, ():
n
fx R R→ 为实值函数, ,,, ,
Tmn n m
AR xluRbR
×
∈∈∈,lu≤ 。许多
实际应用问题,如最优控制问题,交通平衡问题,证券组合投资问题,多物资网络流问题
[1,2,3,4]
等都可以表示成问题(1)的形式。此外,最大团问题
[5]
也可以表示为(1)形式的不定二次规划35
问题。V. N. Vapnik 及其团队开发的支持向量机
[6]
也可以转化为求解如下形式的二次规划问
题:
http://www.paper.edu.cn
- 2 -
中国科技论文在线
0
1
min
2
.. 0,
0.
m
TT
R
T
He
st y
Ce
α
α
αα
α
α
∈
−
=
≤≤
(2)
其中, (1,...,1)
T
e = 为 m 维向量,
0
0C > 是惩罚参数。目前,支持向量机(SVM)已被
广泛应用到文本分类、图像识别、手写数字识别和生物信息技术等领域。 40
对问题(1)以及(2)的求解方法包括有效集法
[7]
、原始对偶算法
[8]
、谱梯度法
[9]
等。其中,
戴彧虹等
[10]
针对(2)形式的二次规划问题提出了一个基于割线近似的算法,数值试验表明该
算法在实际应用中表现良好,但是该算法没有给出收敛性证明。此外,R. Tavakoli 在文献[11]
中提出用 W. Hager 等人提出的求解界约束优化问题的有效集法
[12]
求解问题(1)。该方法用投
影梯度法识别有效约束,然后固定有效约束对应的变量分量。对非有效变量,采用零空间法45
去除等式约束,将原问题变为等价的线性不等式约束问题进行求解。但是,此迭代得到的新
的迭代点违反了原问题的线性等式约束。因此,该方法是不可行的。另一方面,目前已有的
求解标准支持向量机的工作集算法或分解算法都是基于 KKT最大违背对的思想,如 J. Platt
[13]
提出的 SMO 算法,以及 T. Joachims
[14]
、P. Tseng
[15]
等人提出的分解算法等。与一般约束优
化问题的有效集算法不同,其每步迭代仍需求解带有不等式约束的子问题,并且由于每步迭50
代的子问题约束个数通常较少,故虽然子问题的规模降低了,但势必会导致迭代次数的增加,
特别是处理海量数据的分类问题时,这一矛盾就会变得尤为突出。
基于上述问题,本文对 R. Tavakoli 的算法进行了修正,通过采用零空间法,将问题(1)
转换成与之等价的只含线性不等式约束的问题。然后,利用 Marina Andretta 等人
[16]
提出的
部分谱投影梯度法求解转换后的问题,从而求得原问题的解。在适当假设下,证明了算法的55
收敛性。最后,将此方法运用到标准支持向量机的求解中,得到一个简化形式的有效集算法。
1 处理线性等式约束的零空间法
本节主要介绍处理问题(1)的线性等式约束的零空间法。给定满秩矩阵
Tmn
AR
×
∈ ,则
可以将
T
A 的零空间 ()
T
NA 表示为:
(){ : 0},
TnT
NA p R Ap=∈ = (3) 60
即
()
T
NA 是与
T
A 的行向量正交的向量的集合,且其维数是 nm
−
。显然, ()
T
NA 中
的任意两个向量的线性组合也属于
()
T
NA 。假设 ()
T
NA 的基为
12
,,,
nm
pp p
−
L ,记
12
(),
nm
Zpp p
−
= L
则
Z
是
T
A 的零空间矩阵,且 0
T
AZ
=
。若将
Z
的值域表示为 (){ | }
nm
RZ Zv v R
−
=∈,
则 65
() ( ).
T
RZ NA=
假设
0
n
x
R∈ 是
T
Ax b= 的一个特解,则
T
Ax b
=
的任意解
n
x
R∈ 可以表示为:
0
.
x
xZv=+ (4)
考虑问题(1),利用(4)式,可以将
n
R 上的优化问题(1)转化为既约空间
nm
R
−
上的线性
http://www.paper.edu.cn
- 3 -
中国科技论文在线
不等式约束优化问题: 70
0
0
min ( )
.. .
nm
vR
fx Zv
s
tlx Zvu
−
∈
+
≤
+≤
(5)
显然,对
T
Ax b
=
的任意特解
0
n
x
R∈ ,问题(1)与(5)等价。由链式法则,可计算得出
在试探点
0
v 处关于既约向量 v 的梯度和 Hessian 阵,即
00 00
() (),
T
vx
fx Zv Z fx Zv∇+=∇+
22
00 00
() ().
T
vx
fx Zv Z fx ZvZ∇+=∇+ 75
通常,用 QR 分解
[17]
计算满秩矩阵的正交零空间。假设
Tmn
AR
×
∈
是一满秩矩阵,则可
以将
A 的 QR 分解描述为
)
(
1
12
.
0
nm
R
AQRQQ
×
⎛⎞
==
⎜⎟
⎝⎠
其中,Q 是正交矩阵,
()
12 1
,,
nm n nm mm
QR QR RR
×
×− ×
∈∈ ∈。因为Q 是正交矩阵,所
以 80
(
)
1
0.
TTT
AQ R R==
即
11 2
,0
TTT
AQ R AQ==。因此,
2
Z
Q
=
。
可以通过 Householder 变换来计算矩阵
A 的 QR 分解。将正交矩阵Q 表示为变换矩阵 H
的乘积:
12
.
m
QHH H= L 85
其中
nn
i
HR
×
∈ 是正交矩阵,且具有如下一般形式
.
T
HI uu
τ
=−
其中 I 是单位矩阵, ,
n
Ru R
τ
∈∈。
另外,满秩矩阵
Tmn
AR
×
∈ 的零空间的另一种取法是正交投影矩阵
nn
PR
×
∈ ,
1
().
TT
PIAAAA
−
=− 90
显然,
0
T
AP= 。此零空间矩阵与前者的主要区别在于正交投影矩阵 P 不是满秩矩阵。
因此,利用矩阵
P 可以将优化问题(1)转化为全空间
n
R 上的线性不等式约束问题。
2 求解线性不等式约束问题的有效集算法
在利用第一节的零空间法将原问题(1)转换成等价问题(5)后,本节利用 Marina Andretta
等
[16]
提出的结合有效集策略的部分谱投影梯度法求解转换后的问题(5)。 95
考虑问题(5),记
00
','llxuux=− = − ,则可以将问题(5)改写为
min ( )
.. ' '.
nm
vR
fv
s
tl Zvu
−
∈
≤≤
(6)
其中,
12
12
(,,,), (,,, ),
nT i i i i T i nm
nm
Z
zz z z zz z z R
−
−
== ∈LL。记
剩余10页未读,继续阅读
资源评论
weixin_38713039
- 粉丝: 6
- 资源: 948
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功