论文部分内容阅读
对于求解带约束的最小二乘问题（简称LSQI问题） min‖Ax-b‖2，A∈Rm×n，m≥n s.t‖Bx-d‖2≤α,B∈Rp×n （0.1） 本文把所述的问题看作是一个最优化问题，提出了借助最优化方法求解带约束的最小二乘问题的两种新的解法。本文提出了运用并行单纯形法和可行下降方向法分别求解此问题。本文首先借助于割平面法将问题（0.1）的非线性约束化成线性约束，然后将线性约束转化为无约束问题来求解。从而获得一个比较满意的初值估计。然后从初始解出发依次迭代分别运用并行单纯形法和可行下降方向法求解问题（0.1）。并行单纯形法是一种直接方法，它具有不用计算导数，并行性好但对初值有依赖性，精度不高的特点。对于大规模的LSQI问题，可行下降方向法具有精度高的特点（可参见数值试验三，四，六，七，八）（与割平面法和并行单纯形法以及广义奇异值分解法相比）。可行下降方向法利用割平面法求得的一个初值，然后通过求解一系列的线性规划求得可行下降方向，依次迭代求得最小二乘解。由于割平面法具有收敛快，计算量小（可参见数值试验一）的特点，所以作为初值估计是比较实用的。经过大量的数值实验证明，可行下降方向法是求解带非线性约束的最小二乘问题的有效解法，它克服了割平面法精度差的缺点，对于求解大规模的带约束的最小二乘问题，从精度这方面来说大大优于广义奇异值分解。（可参见数值试验七，八）对于并行单纯形法，若是小规模的最小二乘问题，在精度方面，并行单纯形法比广义奇异值分解的效果差，在速度方面，若考虑到并行度，并行单纯形法比广义奇异值分解的速度快。但是对于大规模的最小二乘问题，并行单纯形法在精度上优于广义奇异值分解，在收敛速度方面上劣于广义奇异值分解。（可参见数值试验三，四） 总之，对于小规模的带约束的最小二乘问题，广义奇异值分解法是一种比较好的方法。（可参见数值试验一，二，九）但是若ATA为人规模矩阵或大型稀疏矩阵时，厂‘义奇汁值分解i去注往由于毛1算量太大而不能进行1、‘去’川丁参见文献}21第671臾)l（TJ且会破坏稀疏川‘阵的稀疏队。而本算法则不会破坏稀疏矩阵的稀疏性，保持了稀疏知阵原有的稀疏J性。经过大量的数值实验证明，对f大规模的矩阵或大型稀疏矩阵，可行下降方向法是一种有效的算法。（可参见数值实验卜，十一）它克服了割平面法的缺点，对于求解大规模的带约束的最小一乘问题要优于广‘义奇异值分解法和并行单纯形法。 对于带约束的最小二乘问题二乞n{}Ax一b}}25.艺j}Bx一dj，2三a其中A任Rm‘“，B任招‘“，b任Rm，d任尸，x任R”.它可转化为戚nllAx一bII孟s川Bx一aIl呈三矿（0 .2）、、口产9目 .﹃.上Zr.、。讯f（x）=xT了厂Ax一ZbTA二十犷b。.t武x）二xTBTBx一ZdTBx十dTd一护三。