牛顿内点法求解h 正则化的最小二乘问题
王侦倪，邱欢
(西安石油大学电子工程学院，陕西西安，710065 )
摘要：本文主要描述了一种用于求解大规模A 正则LSP 的专用内点方法，该方法使用预条件共轭梯度算法来计算搜索方向，内点方法可以在短时间内解决大量稀疏问题，其中包含一百万个变量和观察值并且可以通过利用这些变换的快速算法来有效 地解决大量密集问题，并用实验证明了该算法。关键词：内点法；共轭梯度法；稀疏
Newton interior point method for solving regularized least squares problem
Wang  Zhenni , Qiu  Huan
(School  of  electronic  engineering , Xi*an  Petroleum  University , X if  an  Shaanxi , 710065)
Abstract : This paper mainly describes a special interior point method for solving large-scale regular LSPs. This method uses the preconditioned conjugate gradient algorithm to calculate the search direction. The
interior point method can solve a large number of sparse problems in a short time, including one hundred Thousands of variables and observations and can effectively solve a large number of intensive problems by using these transformations of fast algorithm, and experimentally proved the algorithm.Keywords ： Interior point m e t h o d ； Conjugate gradient m e t h o d ； Sparse
1公式介绍
一个线性模型如下所示：
y  = Ax  + v
其中，jce J T 是未知向量，是观测向量，v e /T 是噪
声，d e  iT "”是字典矩阵。
2
細U 化最小二乘
防止过度拟合的标准技术或Tikhonov 正则化[1]公式为：
—
(1)
当正则化参数;1>〇时，Tikhonov 正则化问题或/2规则化 最小二乘问题(LSP )可转化为下式求解：
正则化是最小化策略的实现={AT A  + XiylAT y
(2)
Tikhonov 正则化的一些基本属性有：
(1) 直线性。它的解在线性函数里面不是线性的。(2)
限制性。随着;1 — 0,x '2聚集在摩尔-彭罗斯解决方案
里面，极限点满足L 2范数最小化的所有点，即j  (也->〇 = 0。
3々规则化最小二乘
在4规则化最小二乘(LS )中，本文用Tikhonov 正则化中使 用的平方和的绝对值之和来代替，使得：
+ 乂 K
(3)
其中，；公〇是正则项，式(3)为调整最小二乘
(LSP )。
4正则化的一些基本属性：(1) 非线性。/1最小二乘产生一个向量，它在线性函数里面
不是线性的。
(2) 限制性。随着；1 — 0乂正则化显示不同的限制性，在&正
S IM M
则化中，限制点在所有满足4最小范数，即，(▲ - >〇 = 〇。
(3)
随着；I  — 〇〇，有限收敛为零。在4正则化中，A 的有限值
决定趋向，即：
^>^=||2^||_
(4)
其中 |“|L =maxi |w ,.|。
(4) 正则化路径。Tikhonov 正则化问题的解变化平稳, 相反，A 范数求解是分段线性解路径特性[2]。
A 正则化(LS )通常会产生一个稀疏向量x ，即具有相对较少
的非零系数。
随着A 逐渐减少，x 有可能更倾向于稀疏a 4]。相反，对于
Tikhonov 正则化问题的解;^通常具有所有的非零系数。
最近，正规化的思想在信号处理和统计方面引起了学者很大 的兴趣。在信号处理中，正则化的思想主要体现在几个方面，包括
基础追踪去噪和不完全测量的信号恢复方法[6]。在统计学中，正
则化的思想被用在众所周知的Lasso 算法中用于特征选择及其
扩展，比如弹性网。
4数值实验
本文用截断牛顿内点法的方法用来恢复稀疏信号。算法参数 如下：
a  = Qm,P  = 0.5,S m t a  = 0.5,= 2,^ = 0.01,
= 200
考虑信号；的稀疏信号恢复问题，其由10个幅度为
±1的峰值组成，如图1(a )所示。假设：
y  = Ax  + ve  Rm
其中，A x 给出m =128个频率的x 的离散余弦变换，从索引1
上的布中选择1... 1024。
本文方法封不低于1%次优的点，相对容差为0.01。将正则化
(下转第43页）
49 |
FFOO 转化为二进制为1111111100000000，将D 250十进制值
0 V  0 = 0。D 20十进制值20转化为二进制10100。D 30十 15400转化为二进制为11110000101000。经过字与运算后D 250 进制值30转化为二进制11110，经过高低8位交换后为
低8位数存放在D 20中，而高8位存放在D 30中。
图2仿真结果2 (合并值)
字或逻辑运算：1V 1 = 1;1V 0=1;0V 1 = 1 (上接第49页）
测量的数量远远少于未知的数量，但是基于A 正则化的方法能够 确切地到了原始信号中非零点的位置。最小能量重构方法根本 不能识别非零位置。我们应用了广泛的Tikhonov 正则化参数的 范围来估计信号，可以实现信号重构。
参考文献
[1]    A.Neumaier,'Solving ill-conditioned and singular
linear systems:A tutorial on regularization* SIAM  R E V ,vol.40,n o.3, p p.636-666.[2] B .E fro n , T .H astie, I  J ohnstone, a nd R .Tibshirani,’ Least angle
regression,'' Ann.Statist,vol.32,no.2,pp.407-499,2004.[3] T.Hastie ，R.Tibshirani,and J.Firedman,The Elements
of Statistical Learning.New York:Springer- Verlag,2011 .Springer Series in  Statistics.
[4] R.Tibshirani, ’ Regression shrinkage and
selection via the lasso/ J. Roy.Statist.Soc.ser. B ,vol.58,n o. 1,pp.267-288,1996.
[5] S .C h en ,D .D on oho,an d M .Saunders/ Atom ic decom position
by basis pursuit,’ SIAM Rev.,vol.43,no. 1, pp.129-159,2011.
[6]    E.Candes/ Compressive sampling/ Proc.Int.Conger.
M athem atics,2006
甲 g J I i i l
参数取为乂 = O .OUnax ，其中Anax 的值使用⑷中给出的公式计算，与
其他方法相比，截断的牛顿内点方'法对于这个中等问题是最有效的。
mil l
1000
1900
20C Q
3900
(a )原始信号(b )最低能量重构
(c ) BPDN  重构图1稀疏信号重构
5实纖论
图1(c )所示的是通过求解BPDN 问题获得;C n 的信号，虽然
__________________________________
1)250 0|Q|1|1|1|1|0|0|0|0|1|0|1|0|0|0FF 0|Q|0|Q|0|Q|0|Q|1|1|1|1|1|1|1|1|
FF00
1|1|1|1|1|1|1|1|Q|Q|Q|Q|0|Q|Q|Q|
D20 Q |〇 Q|Q Q|Q Q|Q Q|Q 1|Q 1|Q|Q|Q|
D30
0|0|1|1|1|1|0|Q|0|Q|0|0|0|0|0|0|
卞•与运算
图3字与运算过程
1111000000000。字或运算得到的结果为1111000010100，转化为 十进制为7700。而十进制值7700按上述字与运算，然后将D 30 髙低8位交换，又能还原成D 20=20、D 30 = 30的结果，这与仿真 得到的结果是一致的。
__________M m ___________________________
D20 |0|0|0|0|0|0|0|0|0|0|0|1|0|1|0|0|D30 |0|Q|Q|1|1|1|1|Q|Q|Q|Q|0|Q|0|0|Q|D250 |0|Q|Q|1|1|1|1|Q|Q|Q|Q|1|Q|1|Q|Q|
字或运算
图4字或运算过程
5结论
解决这个问题运用了字与和字或运算，其实还可以利用移位 的方法得到，不过那样涉及的命令比较多，程序相对比较复杂。字 与和字或运算虽然是一种简单命令，平时很少用到，但它与其他命 令结合一起使用，可以十分巧妙地处理数据，本例就是其中之一。
参考文献
[1] 宋伯生.P L C 编程理论•算法及技巧[M ].北京：机械工业出
版社.2005.2.
[2] 史国生.电气控制与可编程控制器技术[M ].北京：化学工业
出版社
.2003.12.

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。