齐次光滑算法及其应用
|
摘要
光滑算法已经成功地应用于求解各类优化问题.在其全局收敛性分析中,提出了各种涉及到所考虑问题的可行性与可解性的假设,这样的假设在文献中被称做正则性假设.然而,这些假设在很多情况下是很难验证的.众所周知:齐次自对偶内点算法能够求解一些优化问题且在不需要任何正则性假设的情况下可获得全局收敛性.一个自然的问题是光滑算法是否也具有这样好的收敛性?本博士论文将对这一问题做出探讨.具体如下:
首先,本文基于单调线性互补问题(LCP)新构造的扩充系统,提出了一个求解LCP的光滑算法,并且证明算法在不需要任何正则性假设的情况下是全局收敛的.特别地,若LCP可解,则算法给出LCP的一个极大互补解,或者给出一个指标表明LCP是可解的,对于后一种情况,用已有的光滑算法直接求解,不需添加任何假设,可以得到LCP的一个极大互补解;若LCP是不可行的,则算法给出一个指标表明LCP是不可行的.
其次,本文针对对称锥线性规划(SCLP),构造一个齐次自对偶模型,提出了一个光滑算法.在对SCLP不做任何正则性假设的情况下,可以得到算法的全局收敛性.此算法在每一次迭代过程中,只需要求解一个线性系统和执行一次线搜索.特别地,若SCLP可解,则通过使用算法求得的解可以得到SCLP的一个解;若SCLP是强不可行的,则算法给出一个指标表明SCLP是不可行的.本文对算法做了一些数值计算,实验表明:实际计算的结果与得到的理论结果是相符的.
最后,本文基于已提出的SCLP的齐次自对偶模型,结合非精确牛顿法的技术,提出了一个非精确光滑算法.该算法具备了前面光滑算法所有的性质,而且在每个迭代步中,用共轭梯度法近似地求解牛顿方程,因而它可以用于求解大规模问题.我们将其应用于目前信号处理领域的研究热点之一――压缩感知理论.作为压缩感知理论中信号恢复的重构算法,与其它流行的算法相比,它能更准确地恢复信号.
Smoothing algorithms have been proposed for solving various optimiza-tion problems successfully. In the analysis of their global convergence, variousassumptions have been presented in the literature, such as the existence ofstrictly feasible points or optimal solutions, which are called regularity as-sumptions. However, it is possible that it is very di?cult to check whetherthese assumptions hold or not. It is well known that the homogeneous andself-dual interior point methods have been proposed for solving some opti-mization problems and shown to be globally convergent without requiring anyregularity assumption. A natural question is whether a smoothing algorithmhas such a good property? This thesis gives some studies on this topic.
Firstly, we present a smoothing algorithm for solving an augmented sys-tem constructed by the standard monotone linear complementarity problem(LCP). The algorithm is showed to be globally convergent without requiringany regularity assumption. In particular, if the LCP has a solution, then thealgorithm either generates a maximal complementary solution of the LCP ordetects correctly solvability of the LCP, and in the latter case, an existingsmoothing algorithm can be directly applied to solve the LCP without anyadditional assumption and it generates a maximal complementary solution ofthe LCP; and if the LCP is infeasible, then the algorithm detects correctlyinfeasibility of the LCP.
Secondly, we propose a smoothing algorithm for solving the symmetriccone linear program (SCLP) by making use of an homogeneous and self-dualmodel constructed by the SCLP. This algorithm is proved to be globally con-vergent without requiring any regularity assumption. It only needs to solveone system of linear equations and to perform one line search at each itera-tion. In particular, if the SCLP has a solution, the algorithm will generate asolution of the SCLP; and if the problem is strongly infeasible, the algorithm will correctly detect infeasibility of the SCLP. We also reported some prelimi-nary numerical results of the algorithm. The numerical results show that ourtheoretical findings coincide with the practical results.
Finally, based on the proposed homogeneous and self-dual model of theSCLP and the technique from inexact Newton methods, we present an inexactsmoothing algorithm for the SCLP, which has all the properties that the formersmoothing algorithm has. Since we solve the Newton equation approximatelyby using the conjugate gradient method at each iteration, the proposed inexactsmoothing algorithm can solve large-scale problems. We apply the algorithmto recovery problems in compressive sensing theory, which is one of the populartopics in signal processing field. As one of the compressive sensing recoveryalgorithms, this algorithm could recover sparse signals more exactly than theother state-of-the-art algorithms.
首先,本文基于单调线性互补问题(LCP)新构造的扩充系统,提出了一个求解LCP的光滑算法,并且证明算法在不需要任何正则性假设的情况下是全局收敛的.特别地,若LCP可解,则算法给出LCP的一个极大互补解,或者给出一个指标表明LCP是可解的,对于后一种情况,用已有的光滑算法直接求解,不需添加任何假设,可以得到LCP的一个极大互补解;若LCP是不可行的,则算法给出一个指标表明LCP是不可行的.
其次,本文针对对称锥线性规划(SCLP),构造一个齐次自对偶模型,提出了一个光滑算法.在对SCLP不做任何正则性假设的情况下,可以得到算法的全局收敛性.此算法在每一次迭代过程中,只需要求解一个线性系统和执行一次线搜索.特别地,若SCLP可解,则通过使用算法求得的解可以得到SCLP的一个解;若SCLP是强不可行的,则算法给出一个指标表明SCLP是不可行的.本文对算法做了一些数值计算,实验表明:实际计算的结果与得到的理论结果是相符的.
最后,本文基于已提出的SCLP的齐次自对偶模型,结合非精确牛顿法的技术,提出了一个非精确光滑算法.该算法具备了前面光滑算法所有的性质,而且在每个迭代步中,用共轭梯度法近似地求解牛顿方程,因而它可以用于求解大规模问题.我们将其应用于目前信号处理领域的研究热点之一――压缩感知理论.作为压缩感知理论中信号恢复的重构算法,与其它流行的算法相比,它能更准确地恢复信号.
Smoothing algorithms have been proposed for solving various optimiza-tion problems successfully. In the analysis of their global convergence, variousassumptions have been presented in the literature, such as the existence ofstrictly feasible points or optimal solutions, which are called regularity as-sumptions. However, it is possible that it is very di?cult to check whetherthese assumptions hold or not. It is well known that the homogeneous andself-dual interior point methods have been proposed for solving some opti-mization problems and shown to be globally convergent without requiring anyregularity assumption. A natural question is whether a smoothing algorithmhas such a good property? This thesis gives some studies on this topic.
Firstly, we present a smoothing algorithm for solving an augmented sys-tem constructed by the standard monotone linear complementarity problem(LCP). The algorithm is showed to be globally convergent without requiringany regularity assumption. In particular, if the LCP has a solution, then thealgorithm either generates a maximal complementary solution of the LCP ordetects correctly solvability of the LCP, and in the latter case, an existingsmoothing algorithm can be directly applied to solve the LCP without anyadditional assumption and it generates a maximal complementary solution ofthe LCP; and if the LCP is infeasible, then the algorithm detects correctlyinfeasibility of the LCP.
Secondly, we propose a smoothing algorithm for solving the symmetriccone linear program (SCLP) by making use of an homogeneous and self-dualmodel constructed by the SCLP. This algorithm is proved to be globally con-vergent without requiring any regularity assumption. It only needs to solveone system of linear equations and to perform one line search at each itera-tion. In particular, if the SCLP has a solution, the algorithm will generate asolution of the SCLP; and if the problem is strongly infeasible, the algorithm will correctly detect infeasibility of the SCLP. We also reported some prelimi-nary numerical results of the algorithm. The numerical results show that ourtheoretical findings coincide with the practical results.
Finally, based on the proposed homogeneous and self-dual model of theSCLP and the technique from inexact Newton methods, we present an inexactsmoothing algorithm for the SCLP, which has all the properties that the formersmoothing algorithm has. Since we solve the Newton equation approximatelyby using the conjugate gradient method at each iteration, the proposed inexactsmoothing algorithm can solve large-scale problems. We apply the algorithmto recovery problems in compressive sensing theory, which is one of the populartopics in signal processing field. As one of the compressive sensing recoveryalgorithms, this algorithm could recover sparse signals more exactly than theother state-of-the-art algorithms.
引文
[1] Dantzig G B. Linear programming and extensions. Published by Prince-ton University Press, 1963
[2] Karmarkar N K. A new polynamial-time algorithm for linear program-ming. Combination 1984, 4:373～395
[3] Facchinei F, Pang J S. Finite-dimensional variational inequalities andcomplementarity problems. New York:Springer, 2003
[4] Cottle R W. Note on a fundamental theorem in quadratic programming.Journal of the Society of Industrial and Applied Mathematics, 1964,12:663～665
[5] Dantzig G B, Cottle R W. Positive (semi-) definite programming. In:Abadie J, ed. Nonlinear Programming. Amsterdam:North-Holland, 1967
[6] Harker P T, Pang J S. Finite-dimensional variational inequality andnonlinear complementarity problems: A survey of theory, algorithmsand applications. Mathematical Programming, 1990, 48:161～220
[7] Cottle R W, Pang J S, Stone R E. The Linear Complementarity Problem.Academic Press, Boston, 1992
[8]修乃华,高自友,互补问题算法的新进展,数学进展,1999,28(3):193～210
[9] Isac G. Topological methods in coplementarity theory. Boston:KluwerAcademic Publishers, 2000
[10]韩继业,修乃华,戚厚铎,非线性互补理论与算法,上海:上海科学技术出版社,2006
[11] Faraut J, Koranyi A. Analysis on Symmetric Cones. Oxford Mathemat-ical Monographs, Oxford University Press, New York, 1994
[12] Faybusovich L. Linear systems in Jordan algebras and primal-dualinterior-point algorithm. Journal of Computational and Applied Math-ematics, 1997, 86:149～175
[13] Faybusovich L. Euclidean Jordan algebras and interior-point algorithms.Positivity, 1997, 1:331～357
[14] Nesterov Y, Nemirovski A. Interior point polynomial methods in con-vex programming: theory and applications. Philadelphia: Society forIndustrial unapplied Mathematics(SIAM), 1994
[15] Schmieta S H, Alizadeh F. Extension of primal-dual interior point algo-rithms to symmetric cones. Mathematical Program, 2003, 96:409～438
[16] Schmieta S H, Alizadeh F. Associative and Jordan algebras, and poly-nomial time interior-point algorithms for symmetric cones. Mathematicsof Operations Research, 2001, 26:543～564
[17] Qi L, Sun D. Nonsmooth equations and smoothing methods. In: Eber-hard A, Glover B M, Hill R, Ralph D, eds, Progress in Optimization.Dordrecht: Kluwer Academic Publisher, 1998
[18] Qi L, Sun D. A survey of some nonsmooth equations and smoothingNewton methods. In: Eberhard A, Glover B M, Hill R, Ralph D, eds,Progress in Optimization. Dordrecht: Kluwer Academic Publisher, 1999,121
[19] Qi L, Sun D. Smoothing functions and smoothing Newton method forcomplementarity and variational inequality problems. Journal on Opti-mization Theory and Applications, 2002, 113:121～147
[20] Qi H D, Liao L Z. A smoothing Newton method for extended verticallinear complementarity problems. SIAM Journal on Matrix Analysis andApplications, 1999, 21:45～66
[21] Qi H D, Liao L Z. A smoothing Newton method for general nonlinearcomplementarity problems. Computational Optimization and Applica-tions, 2000, 17:231～253
[22] Huang Z H, Qi L, Sun D. Sub-quadratic convergence of a smoothingNewton algorithm for the P0 and monotone LCP. Mathematical Pro-gramming, 2004, 99:423～441
[23] Huang Z H, Han J Y, Chen Z. Predictor-corrector smoothing Newtonmethod, based on a new smoothing function, for sloving the nonlinearcomplementarity problem with a P0 function. Journal of OptimizationTheory and Applications, 2003, 117(1):39～68
[24] Huang Z H, Zhang L P, Han J Y. A hybrid smoothing-nonsmoothNewton-type algorithm yielding an exact solution of the P0-LCP. Journalof Computational Mathematics, 2004, 6:797～806
[25] Huang Z H, Sun D, Zhao G Y. A smoothing Newton-type algorithm ofstronger convergence for the quadratically constrained convex quadraticprogramming. Computational Optimization and Applications, 2006,35:199～237
[26] Huang Z H, Gu W Z. A smoothing-type algorithm for solving linearcomplementarity problems with strong convergence properties. AppliedMathematics and Optimization, 2008, 57:17～29
[27] Burke J, Xu S. The global linear convergence of a non-interior path-following algorithm for linear complementarity problems. Mathematicsof Operations Research, 1998, 23:719～734
[28] Burke J, Xu S. A non-interior predictor-corrector path following algo-rithm for the monotone linear complementarity problem. MathematicalProgramming, 2000, 87:113～130
[29] Chen B, Chen X. A global and local superlinear continuation-smoothingmethod for P0+R0 and monotone NCP. SIAM Journal on Optimization,1999, 9:624～645
[30] Chen B, Harker P T. A non-interior-point continuation method for lin-ear complementarity problem. SIAM Journal on Matrix Analysis andApplication, 1993, 14:1168～1190
[31] Chen C, Mangasarian O L. Smoothing method for convex inequali-ties and linear complementarity problems. Mathematical Programming,1995, 71:51～69
[32] Chen B, Xiu N. Superlinear noninterior one-step continuation methodfor monotone LCP in the absence of strict complementarity. Journal ofOptimization Theory and Application, 2001, 108:317～332
[33] Chen X, Ye Y. On homotopy-smoothing methods for variational inequal-ities. SIAM Journal on Control and Optimization, 1999, 37:589～616
[34] Chen X, Ye Y. On smoothing methods for the P0 matrix linear comple-mentarity problem. SIAM Journal on Optimization, 2000, 11:341～363
[35] Chen X, Tseng P. Non-interior continuation methods for solving semidef-inite complementarity problems. Mathematical Programming, 2003, 95:431～474
[36] Engelke S, Kanzow C. Predictor-corrector smoothing methods for thesolution of linear programming. Preprint. Department of Mathematics,University of Hamburg, 2000
[37] Hayashi S, Yamashita N, Fukushima M. A combined smoothing andregularization method for monotone second-order cone complementarityproblems. SIAM Journal on Optimization, 2005, 15:593～615
[38] Kanzow C. Some noninterior continuation methods for linear comple-mentarity problems. SIAM Journal on Matrix Analysis and Applications,1996, 17:851～868
[39] Qi H D. A regularization smoothing Newton method for box constrainedvariational inequality problems with P0-functions. SIAM Journal on Op-timization, 1999, 10:315～330
[40] Qi L, Sun D. Improving the convergence of non-interior point algorithmfor nonlinear complementarity problems. Mathematics of Computation,2000, 69:283～304
[41] Qi L, Sun D, Zhou G. A new look at smoothing Newton methods fornonlinear complementarity problems and box constrained variational in-equality problems. Mathematical Programming, 2000, 87:1～35
[42] Tseng P. Analysis of a non-interior continuation method based onChen-Mangasarian smoothing functions for complementarity problems.in Reformulation-Nonsmooth, Piecewise Smooth, Semismooth andSmoothing Methods, edited by Fukushima, M. and Qi, L., Kluwer Aca-demic Publishers, Boston, 1999, 381～404
[43] Hotta K, Yoshise A. Global convergence of a non-interior-point algo-rithms using Chen-Harker-Kanzow functions for nonlinear complemen-tarity problems. Mathematical Programming, 1999, 86:105～133
[44] Huang Z H. The global linear and local quadratic convergence of a non-interior continuation algorithm for the LCP. IMA Journal of NumericalAnalysis, 2005, 25:670～684
[45] Huang Z H. Su?cient conditions on nonemptiness and boundedness ofthe solution set of the P0 function nonlinear complementarity problem.Operations Research Letters, 2002, 30:202～210
[46] Facchinei F, Kanzow C. Beyond monotonicity in regularization methodsfor nonlinear complementarity problems. SIAM Journal on Control andOptimization, 1999, 37:1150～1161
[47] Huang Z H, Sun J. A non-interior continuation algorithm for the P0 orP? LCP with strong global and local convergence properties. AppliedMathematics and Optimization, 2005, 26:237～262
[48] Karamardian S. Complementarity problems over cones with monotoneand pseudomonotone maps. Journal of Optimization Theory and Appli-cation, 1976, 18:445～454
[49] Mclinden L. Stable monotone variational inequalities. MathematicalProgramming, 1990, 48:303～338
[50] Engelke S, Kanzow C. Improved smoothing-type methods for the solu-tion of linear programs. Numerical Mathematics, 2002, 90:487～507
[51] Huang Z H. Locating a maximally complementary solution of the mono-tone NCP by using non-interior-point smoothing algorithms. Mathemat-ical Methods of Operations Research, 2005, 61:41～55
[52] Sun J, Huang Z H. A smoothing Newton algorithm for the LCP with asu?cient matrix that terminates finitely at a maximally complementarysolution. Optimization Methods and Software, 2006, 21(4):597～615
[53] Huang Z H, Liu X H. Extension of smoothing Newton algorithms tosolve linear programming over symmetric cones. Technique Report, De-partment of Mathematics, School of Science, Tianjin University, P.R.China, 2007
[54] Liu X H, Huang Z H. A smoothing Newton algorithm based on a one-parametric class of smoothing functions for linear programming oversymmetric cones. Mathematical Methods of Operations Research, 2009,70:385～404
[55] Liu J Y, Zhang L W, Wang Y H. Some properties of a class of merit func-tions for symmetric cone complementarity problem. Asia-Pacific JournalOperational Research, 2006, 23:473～495
[56] Ye Y, Todd M J, Mizuno S. An O(√nL)-iteration homogeneous andself-dual linear programming algorithm. Mathematics of Operations Re-search, 1994, 19:52～67
[57] Xu X, Hung P F, Ye Y. A simplified homogeneous and self-dual linearprogramming algorithm and its implementation. Annals of OperationsResearch, 1996, 62:151～172
[58] Ye Y. On homogeneous and self-dual algorithms for LCP. MathematicalProgramming, 1996,76:211～221
[59] Andersen E, Ye Y. On a homogeneous algorithm for the monotone com-plementarity problems. Mathematical Programming, 1999, 84:375～400
[60] Andersen E, Ye Y. A Computational study of the homogeneous algo-rithm for large-scale convex optimization. Computational Optimizationand Applications, 1998, 10:243～269
[61] Lou Z Q, Sturm J F, Zhang S Z. Duality and self-duality for convexprogramming. Technical Report 9719/A, Econometric Institute, EramusUniversity Rotterdam, The Netherlands, 1997
[62] Lou Z Q, Sturm J F, Zhang S Z. Conic convex programming and self-dualembedding. Optimization Methods and Software, 2000, 14:169～218
[63] Zhang S Z. A new self-dual embedding method for convex programming.Journal of Global Optimization, 2004, 29:479～496
[64] Yoshise A. A homogeneous model for P0 and P? nonlinear complemen-tarity problems. Technique Report, Graduate School of Systems andInformation Engineering, University of Tsukuba, Japan, 2003
[65] Yoshise A. Interior point trajectories and a homogeneous model for non-linear complementarity problems over symmetric cones. SIAM Journalon Optimization, 2006, 17:1129～1153
[66] Yoshise A. Homeogeneous algorithms for monotone complementarityproblems over symmetric cones. Technique Report, Graduate School ofSystems and Information Engineering, University of Tsukuba, Japan,2008
[67] Huang Z H, Wang H. Smoothing-type algorithm for solving linear pro-grams by using an augmented complementarity problem. Applied Math-ematics and Computation, 2006, 177:330～345
[68] Kong L C, Xiu N H. On uniqueness of the Jordan frame in EuclideanJordan algebras.北京交通大学学报, 2007, 31:54～57
[69] Tao J, Gowda S. Some P-properties for nonlinear transformation onEuclidean Jordan algebras. Mathematics of Operations Research 2005,30:985～1004
[70] Kong L C, Tuncel L, Xiu N H. Fischer-Burmeister conplementarity func-tion on Euclidean Jordan algebras. Technique Report, Department ofCombinatorics and Optimization, Beijing Jiaotong University, 2007
[71] Ortega J M, Rheinboldt W C. Iterative Solution of nonlinear equationsin several variables. Academic Rress, New York and London, 1970
[72] Dembo R S, Eisenstat S C, Steihaug T. Inexact Newton methods. SIAMJournal on Numerical Analysis, 1982, 19:400～408
[73] Adler I, Gale D. On the solution of the positive semi-definite comple-mentarity problem. Technique Report ORC 75-12, Operations ResearchCenter, University of California, Berkely, 1975
[74] Gu¨ler O, Ye Y. Convergence behavior of interior-point algorithms, Math-ematical Programming, 1993, 60:215～228
[75] Nemirovski A. Lectures on modern convex optimization. School of In-dustrial and System Engineering, Georgia Institute of Technology, 2005
[76] Huang Z H, Hu S L, Han J Y. Global Convergence of a smoothing algo-rithm for symmetric cone complementarity problems with a nonmono-tone line search. Science in China, 2009, 39(4):833～848
[77] Gowda M S, Sznajder R, Tao J. Some P-properties for linear transforma-tions on Euclidean Jordan algebras. Linear Algebra and its Application,2004, 393:203～232
[78] Candés E, Michael W. An introduction to compressive sampling. IEEEsignal processing magazine, 2008, 25(2):21～30
[79] Romberg J. Imaging via compressive sampling. IEEE signal processingmagazine, 2008, 25(2):14～20
[80] Candés E, Romberg J, Tao T. Robust uncertainty principles: Exact sig-nal reconstruction form highly incomplete frequency information. IEEETransactions on Information Theory, 2006, 52(2):489～509
[81] Candés E, Tao T. Decoding by linear programming. IEEE Transactionson Information Theory, 2005, 51(12):4203～4215
[82] Candés E, Romberg J. Quantitative robust uncertainty principles andoptimally sparse decompositions. Foundations of Computational Math-ematics, 2006, 6(2):227～254
[83] Candés E, Romberg J, Tao T. Stable signal recovery from incompleteand inaccurate measurements. Communications on Pure and AppliedMathematics, 2006, 59:1207～1223
[84] Candés E, Tao T. Near-optimal signal recovery from random projec-tions and universal encoding strategies. IEEE Transactions on Informa-tion Theory, 2006, 52(12):5406～5425
[85] Candés E, Tao T. The dantzig selector: statistical estimation when pis much smaller than n. Annals of Statistics, 2007, 35(6):2313～2351
[86] Chen S B, Donoho D L, Saunders M A. Atomic decomposition by basispursuit. SIAM Journal on Scientific Computing, 1999, 20:33～61
[87] Lu Z. Gradient based method for cone programming with application tolarge-scale compressed sensing. Technique Report, Optimization-online,Department of Mathematics, Simon Fraser University, Burnaby, BCV5A 1S6, Canada, 2008
[88] Turlach B. On algorithms for solving least squares problems under anL1 penalty or an L1 constraint. In Proceeding of the American Statis-tical Association, Statistical Computing Section, Alexandria, VA, 2005,2572～2577
[89] Cai X C, Keyes D E. Nonlinearly preconditioned inexact Newton algo-rithms. SIAM Journal on Scientific Computing, 2002, 24:183～200
[90] Eisenstat S C, Walker H F. Choosing the forcing term in an inexactNewton method. SIAM Journal on Scientific Computing, 1996, 17:16～32
[91] Dembo R S, Steinaug T. Truncated Newton algorithm for large-scaleoptimization. Mathematical Programming, 1983, 26:190～212
[92] Brown P N, Saad Y. Hybrid Krylov methods for nonlinear systems ofequations. SAIM Journal on Scientific and Statistical Computing, 1990,11:450～481
[93] Flkkema D R, Sleijpen G L G, Van Der Vorst H A. Accelerated inexactNewton schemes for large systems of nonlinear equations. SAIM Journalon Scientific Computing, 1998, 19:657～674
[94] Lu?zanin Z, Herceg D, Krejic N. Parameter selection for inexact Newtonmethod. Nonlinear Analysis: Theory, Methods and Applications, 1997,30:17～24
[95] Shadid J N, Tuminaro R S, Walker H F. An inexact Newton methodfor fully coupled solution of the Navier-Stokes equations with heat andmass transport. Journal of Computational Physics, 1997, 137:155～185
[96] An H B. On convergence of the additive schwarz preconditional inexactNewton method. SIAM Journal Numerical Analysis, 2005, 43:1850～1871
[97] Donoho D L. Compressed sesing. IEEE Transections on InformationTheory, 2006, 52(4):1289～1306
[98] Candés E. Compressive sampling. In: Proceedings of InternationalCongress of Mathematicians. Zurich, Switzerland: European Mathemat-ical Society Publishing House, 2006, 1433～1452
[99] Baraniuk R. Compressive sensing. IEEE Signal Processing Magazine,2007, 24(4):118～121
[100] Donoho D L. For most large underdetermined systems of linear equa-tions, the minimal l1 norm solution is also the sparsest solution. Com-munications on Pure and Applied Mathematics, 2006, 59(6):797～829
[101] Donoho D L, Elad M. Stable recovery of sparse overcomplete representa-tions in the presence of noise. IEEE Transactions on Information Theory,2006, 52(1):6～18
[102] Tropp J, Gilbert A. Signal recovery from random measurements via or-thogonal matching pursuit. IEEE Transactions on Information Theory,2007, 53(12):4655～4666
[103] Tropp J. Greed is good: Algorithmic results for sparse approximation.IEEE Transactions on Information Theory, 2006, 50(10):2231～2342
[104] Kingsbury N G. Complex wavelets for shift invariant analysis and filter-ing of signals. Journal of Applied and Computational Harmonic Analysis,2001, 10(3):234～253
[105] Herrity K K, Gilbert A C, Tropp J A. Sparse approximation via intera-tive thresholding. In: Proceedings of the IEEE International Conferenceon Acoustics, Speech and Signal Processing. Washington D.C., USA:IEEE, 2006, 624～627
[106] Hestenes M R, Stiefel E. Methods of conjugate gradients fo solving linearsystems. Journal of Research of the National Bureau of Standards, 1952,49:409～436
[107] Demmel J. Applied numerical linear algebra. Cambridge, U.K.: Cam-birdge University Press, 1997
[108] Nocedal J, Wright S. Numerical optimization. Springer Series in Opera-tions Research, 1999
[109] Kim S J, Lustig M, Boyd S. An interior-point method for large-scalel1-regularized least squares. IEEE Journal of Selected Topics in SignalProcessing, 2007, 4:606～617
[110] Mohimani G H, Zadeh M B, Jutten C. A fast approach for overcompletesparse decomposition based on smoothed l0 norm. IEEE Transection onSignal Processing, 2009, 57:289～301
[2] Karmarkar N K. A new polynamial-time algorithm for linear program-ming. Combination 1984, 4:373～395
[3] Facchinei F, Pang J S. Finite-dimensional variational inequalities andcomplementarity problems. New York:Springer, 2003
[4] Cottle R W. Note on a fundamental theorem in quadratic programming.Journal of the Society of Industrial and Applied Mathematics, 1964,12:663～665
[5] Dantzig G B, Cottle R W. Positive (semi-) definite programming. In:Abadie J, ed. Nonlinear Programming. Amsterdam:North-Holland, 1967
[6] Harker P T, Pang J S. Finite-dimensional variational inequality andnonlinear complementarity problems: A survey of theory, algorithmsand applications. Mathematical Programming, 1990, 48:161～220
[7] Cottle R W, Pang J S, Stone R E. The Linear Complementarity Problem.Academic Press, Boston, 1992
[8]修乃华,高自友,互补问题算法的新进展,数学进展,1999,28(3):193～210
[9] Isac G. Topological methods in coplementarity theory. Boston:KluwerAcademic Publishers, 2000
[10]韩继业,修乃华,戚厚铎,非线性互补理论与算法,上海:上海科学技术出版社,2006
[11] Faraut J, Koranyi A. Analysis on Symmetric Cones. Oxford Mathemat-ical Monographs, Oxford University Press, New York, 1994
[12] Faybusovich L. Linear systems in Jordan algebras and primal-dualinterior-point algorithm. Journal of Computational and Applied Math-ematics, 1997, 86:149～175
[13] Faybusovich L. Euclidean Jordan algebras and interior-point algorithms.Positivity, 1997, 1:331～357
[14] Nesterov Y, Nemirovski A. Interior point polynomial methods in con-vex programming: theory and applications. Philadelphia: Society forIndustrial unapplied Mathematics(SIAM), 1994
[15] Schmieta S H, Alizadeh F. Extension of primal-dual interior point algo-rithms to symmetric cones. Mathematical Program, 2003, 96:409～438
[16] Schmieta S H, Alizadeh F. Associative and Jordan algebras, and poly-nomial time interior-point algorithms for symmetric cones. Mathematicsof Operations Research, 2001, 26:543～564
[17] Qi L, Sun D. Nonsmooth equations and smoothing methods. In: Eber-hard A, Glover B M, Hill R, Ralph D, eds, Progress in Optimization.Dordrecht: Kluwer Academic Publisher, 1998
[18] Qi L, Sun D. A survey of some nonsmooth equations and smoothingNewton methods. In: Eberhard A, Glover B M, Hill R, Ralph D, eds,Progress in Optimization. Dordrecht: Kluwer Academic Publisher, 1999,121
[19] Qi L, Sun D. Smoothing functions and smoothing Newton method forcomplementarity and variational inequality problems. Journal on Opti-mization Theory and Applications, 2002, 113:121～147
[20] Qi H D, Liao L Z. A smoothing Newton method for extended verticallinear complementarity problems. SIAM Journal on Matrix Analysis andApplications, 1999, 21:45～66
[21] Qi H D, Liao L Z. A smoothing Newton method for general nonlinearcomplementarity problems. Computational Optimization and Applica-tions, 2000, 17:231～253
[22] Huang Z H, Qi L, Sun D. Sub-quadratic convergence of a smoothingNewton algorithm for the P0 and monotone LCP. Mathematical Pro-gramming, 2004, 99:423～441
[23] Huang Z H, Han J Y, Chen Z. Predictor-corrector smoothing Newtonmethod, based on a new smoothing function, for sloving the nonlinearcomplementarity problem with a P0 function. Journal of OptimizationTheory and Applications, 2003, 117(1):39～68
[24] Huang Z H, Zhang L P, Han J Y. A hybrid smoothing-nonsmoothNewton-type algorithm yielding an exact solution of the P0-LCP. Journalof Computational Mathematics, 2004, 6:797～806
[25] Huang Z H, Sun D, Zhao G Y. A smoothing Newton-type algorithm ofstronger convergence for the quadratically constrained convex quadraticprogramming. Computational Optimization and Applications, 2006,35:199～237
[26] Huang Z H, Gu W Z. A smoothing-type algorithm for solving linearcomplementarity problems with strong convergence properties. AppliedMathematics and Optimization, 2008, 57:17～29
[27] Burke J, Xu S. The global linear convergence of a non-interior path-following algorithm for linear complementarity problems. Mathematicsof Operations Research, 1998, 23:719～734
[28] Burke J, Xu S. A non-interior predictor-corrector path following algo-rithm for the monotone linear complementarity problem. MathematicalProgramming, 2000, 87:113～130
[29] Chen B, Chen X. A global and local superlinear continuation-smoothingmethod for P0+R0 and monotone NCP. SIAM Journal on Optimization,1999, 9:624～645
[30] Chen B, Harker P T. A non-interior-point continuation method for lin-ear complementarity problem. SIAM Journal on Matrix Analysis andApplication, 1993, 14:1168～1190
[31] Chen C, Mangasarian O L. Smoothing method for convex inequali-ties and linear complementarity problems. Mathematical Programming,1995, 71:51～69
[32] Chen B, Xiu N. Superlinear noninterior one-step continuation methodfor monotone LCP in the absence of strict complementarity. Journal ofOptimization Theory and Application, 2001, 108:317～332
[33] Chen X, Ye Y. On homotopy-smoothing methods for variational inequal-ities. SIAM Journal on Control and Optimization, 1999, 37:589～616
[34] Chen X, Ye Y. On smoothing methods for the P0 matrix linear comple-mentarity problem. SIAM Journal on Optimization, 2000, 11:341～363
[35] Chen X, Tseng P. Non-interior continuation methods for solving semidef-inite complementarity problems. Mathematical Programming, 2003, 95:431～474
[36] Engelke S, Kanzow C. Predictor-corrector smoothing methods for thesolution of linear programming. Preprint. Department of Mathematics,University of Hamburg, 2000
[37] Hayashi S, Yamashita N, Fukushima M. A combined smoothing andregularization method for monotone second-order cone complementarityproblems. SIAM Journal on Optimization, 2005, 15:593～615
[38] Kanzow C. Some noninterior continuation methods for linear comple-mentarity problems. SIAM Journal on Matrix Analysis and Applications,1996, 17:851～868
[39] Qi H D. A regularization smoothing Newton method for box constrainedvariational inequality problems with P0-functions. SIAM Journal on Op-timization, 1999, 10:315～330
[40] Qi L, Sun D. Improving the convergence of non-interior point algorithmfor nonlinear complementarity problems. Mathematics of Computation,2000, 69:283～304
[41] Qi L, Sun D, Zhou G. A new look at smoothing Newton methods fornonlinear complementarity problems and box constrained variational in-equality problems. Mathematical Programming, 2000, 87:1～35
[42] Tseng P. Analysis of a non-interior continuation method based onChen-Mangasarian smoothing functions for complementarity problems.in Reformulation-Nonsmooth, Piecewise Smooth, Semismooth andSmoothing Methods, edited by Fukushima, M. and Qi, L., Kluwer Aca-demic Publishers, Boston, 1999, 381～404
[43] Hotta K, Yoshise A. Global convergence of a non-interior-point algo-rithms using Chen-Harker-Kanzow functions for nonlinear complemen-tarity problems. Mathematical Programming, 1999, 86:105～133
[44] Huang Z H. The global linear and local quadratic convergence of a non-interior continuation algorithm for the LCP. IMA Journal of NumericalAnalysis, 2005, 25:670～684
[45] Huang Z H. Su?cient conditions on nonemptiness and boundedness ofthe solution set of the P0 function nonlinear complementarity problem.Operations Research Letters, 2002, 30:202～210
[46] Facchinei F, Kanzow C. Beyond monotonicity in regularization methodsfor nonlinear complementarity problems. SIAM Journal on Control andOptimization, 1999, 37:1150～1161
[47] Huang Z H, Sun J. A non-interior continuation algorithm for the P0 orP? LCP with strong global and local convergence properties. AppliedMathematics and Optimization, 2005, 26:237～262
[48] Karamardian S. Complementarity problems over cones with monotoneand pseudomonotone maps. Journal of Optimization Theory and Appli-cation, 1976, 18:445～454
[49] Mclinden L. Stable monotone variational inequalities. MathematicalProgramming, 1990, 48:303～338
[50] Engelke S, Kanzow C. Improved smoothing-type methods for the solu-tion of linear programs. Numerical Mathematics, 2002, 90:487～507
[51] Huang Z H. Locating a maximally complementary solution of the mono-tone NCP by using non-interior-point smoothing algorithms. Mathemat-ical Methods of Operations Research, 2005, 61:41～55
[52] Sun J, Huang Z H. A smoothing Newton algorithm for the LCP with asu?cient matrix that terminates finitely at a maximally complementarysolution. Optimization Methods and Software, 2006, 21(4):597～615
[53] Huang Z H, Liu X H. Extension of smoothing Newton algorithms tosolve linear programming over symmetric cones. Technique Report, De-partment of Mathematics, School of Science, Tianjin University, P.R.China, 2007
[54] Liu X H, Huang Z H. A smoothing Newton algorithm based on a one-parametric class of smoothing functions for linear programming oversymmetric cones. Mathematical Methods of Operations Research, 2009,70:385～404
[55] Liu J Y, Zhang L W, Wang Y H. Some properties of a class of merit func-tions for symmetric cone complementarity problem. Asia-Pacific JournalOperational Research, 2006, 23:473～495
[56] Ye Y, Todd M J, Mizuno S. An O(√nL)-iteration homogeneous andself-dual linear programming algorithm. Mathematics of Operations Re-search, 1994, 19:52～67
[57] Xu X, Hung P F, Ye Y. A simplified homogeneous and self-dual linearprogramming algorithm and its implementation. Annals of OperationsResearch, 1996, 62:151～172
[58] Ye Y. On homogeneous and self-dual algorithms for LCP. MathematicalProgramming, 1996,76:211～221
[59] Andersen E, Ye Y. On a homogeneous algorithm for the monotone com-plementarity problems. Mathematical Programming, 1999, 84:375～400
[60] Andersen E, Ye Y. A Computational study of the homogeneous algo-rithm for large-scale convex optimization. Computational Optimizationand Applications, 1998, 10:243～269
[61] Lou Z Q, Sturm J F, Zhang S Z. Duality and self-duality for convexprogramming. Technical Report 9719/A, Econometric Institute, EramusUniversity Rotterdam, The Netherlands, 1997
[62] Lou Z Q, Sturm J F, Zhang S Z. Conic convex programming and self-dualembedding. Optimization Methods and Software, 2000, 14:169～218
[63] Zhang S Z. A new self-dual embedding method for convex programming.Journal of Global Optimization, 2004, 29:479～496
[64] Yoshise A. A homogeneous model for P0 and P? nonlinear complemen-tarity problems. Technique Report, Graduate School of Systems andInformation Engineering, University of Tsukuba, Japan, 2003
[65] Yoshise A. Interior point trajectories and a homogeneous model for non-linear complementarity problems over symmetric cones. SIAM Journalon Optimization, 2006, 17:1129～1153
[66] Yoshise A. Homeogeneous algorithms for monotone complementarityproblems over symmetric cones. Technique Report, Graduate School ofSystems and Information Engineering, University of Tsukuba, Japan,2008
[67] Huang Z H, Wang H. Smoothing-type algorithm for solving linear pro-grams by using an augmented complementarity problem. Applied Math-ematics and Computation, 2006, 177:330～345
[68] Kong L C, Xiu N H. On uniqueness of the Jordan frame in EuclideanJordan algebras.北京交通大学学报, 2007, 31:54～57
[69] Tao J, Gowda S. Some P-properties for nonlinear transformation onEuclidean Jordan algebras. Mathematics of Operations Research 2005,30:985～1004
[70] Kong L C, Tuncel L, Xiu N H. Fischer-Burmeister conplementarity func-tion on Euclidean Jordan algebras. Technique Report, Department ofCombinatorics and Optimization, Beijing Jiaotong University, 2007
[71] Ortega J M, Rheinboldt W C. Iterative Solution of nonlinear equationsin several variables. Academic Rress, New York and London, 1970
[72] Dembo R S, Eisenstat S C, Steihaug T. Inexact Newton methods. SIAMJournal on Numerical Analysis, 1982, 19:400～408
[73] Adler I, Gale D. On the solution of the positive semi-definite comple-mentarity problem. Technique Report ORC 75-12, Operations ResearchCenter, University of California, Berkely, 1975
[74] Gu¨ler O, Ye Y. Convergence behavior of interior-point algorithms, Math-ematical Programming, 1993, 60:215～228
[75] Nemirovski A. Lectures on modern convex optimization. School of In-dustrial and System Engineering, Georgia Institute of Technology, 2005
[76] Huang Z H, Hu S L, Han J Y. Global Convergence of a smoothing algo-rithm for symmetric cone complementarity problems with a nonmono-tone line search. Science in China, 2009, 39(4):833～848
[77] Gowda M S, Sznajder R, Tao J. Some P-properties for linear transforma-tions on Euclidean Jordan algebras. Linear Algebra and its Application,2004, 393:203～232
[78] Candés E, Michael W. An introduction to compressive sampling. IEEEsignal processing magazine, 2008, 25(2):21～30
[79] Romberg J. Imaging via compressive sampling. IEEE signal processingmagazine, 2008, 25(2):14～20
[80] Candés E, Romberg J, Tao T. Robust uncertainty principles: Exact sig-nal reconstruction form highly incomplete frequency information. IEEETransactions on Information Theory, 2006, 52(2):489～509
[81] Candés E, Tao T. Decoding by linear programming. IEEE Transactionson Information Theory, 2005, 51(12):4203～4215
[82] Candés E, Romberg J. Quantitative robust uncertainty principles andoptimally sparse decompositions. Foundations of Computational Math-ematics, 2006, 6(2):227～254
[83] Candés E, Romberg J, Tao T. Stable signal recovery from incompleteand inaccurate measurements. Communications on Pure and AppliedMathematics, 2006, 59:1207～1223
[84] Candés E, Tao T. Near-optimal signal recovery from random projec-tions and universal encoding strategies. IEEE Transactions on Informa-tion Theory, 2006, 52(12):5406～5425
[85] Candés E, Tao T. The dantzig selector: statistical estimation when pis much smaller than n. Annals of Statistics, 2007, 35(6):2313～2351
[86] Chen S B, Donoho D L, Saunders M A. Atomic decomposition by basispursuit. SIAM Journal on Scientific Computing, 1999, 20:33～61
[87] Lu Z. Gradient based method for cone programming with application tolarge-scale compressed sensing. Technique Report, Optimization-online,Department of Mathematics, Simon Fraser University, Burnaby, BCV5A 1S6, Canada, 2008
[88] Turlach B. On algorithms for solving least squares problems under anL1 penalty or an L1 constraint. In Proceeding of the American Statis-tical Association, Statistical Computing Section, Alexandria, VA, 2005,2572～2577
[89] Cai X C, Keyes D E. Nonlinearly preconditioned inexact Newton algo-rithms. SIAM Journal on Scientific Computing, 2002, 24:183～200
[90] Eisenstat S C, Walker H F. Choosing the forcing term in an inexactNewton method. SIAM Journal on Scientific Computing, 1996, 17:16～32
[91] Dembo R S, Steinaug T. Truncated Newton algorithm for large-scaleoptimization. Mathematical Programming, 1983, 26:190～212
[92] Brown P N, Saad Y. Hybrid Krylov methods for nonlinear systems ofequations. SAIM Journal on Scientific and Statistical Computing, 1990,11:450～481
[93] Flkkema D R, Sleijpen G L G, Van Der Vorst H A. Accelerated inexactNewton schemes for large systems of nonlinear equations. SAIM Journalon Scientific Computing, 1998, 19:657～674
[94] Lu?zanin Z, Herceg D, Krejic N. Parameter selection for inexact Newtonmethod. Nonlinear Analysis: Theory, Methods and Applications, 1997,30:17～24
[95] Shadid J N, Tuminaro R S, Walker H F. An inexact Newton methodfor fully coupled solution of the Navier-Stokes equations with heat andmass transport. Journal of Computational Physics, 1997, 137:155～185
[96] An H B. On convergence of the additive schwarz preconditional inexactNewton method. SIAM Journal Numerical Analysis, 2005, 43:1850～1871
[97] Donoho D L. Compressed sesing. IEEE Transections on InformationTheory, 2006, 52(4):1289～1306
[98] Candés E. Compressive sampling. In: Proceedings of InternationalCongress of Mathematicians. Zurich, Switzerland: European Mathemat-ical Society Publishing House, 2006, 1433～1452
[99] Baraniuk R. Compressive sensing. IEEE Signal Processing Magazine,2007, 24(4):118～121
[100] Donoho D L. For most large underdetermined systems of linear equa-tions, the minimal l1 norm solution is also the sparsest solution. Com-munications on Pure and Applied Mathematics, 2006, 59(6):797～829
[101] Donoho D L, Elad M. Stable recovery of sparse overcomplete representa-tions in the presence of noise. IEEE Transactions on Information Theory,2006, 52(1):6～18
[102] Tropp J, Gilbert A. Signal recovery from random measurements via or-thogonal matching pursuit. IEEE Transactions on Information Theory,2007, 53(12):4655～4666
[103] Tropp J. Greed is good: Algorithmic results for sparse approximation.IEEE Transactions on Information Theory, 2006, 50(10):2231～2342
[104] Kingsbury N G. Complex wavelets for shift invariant analysis and filter-ing of signals. Journal of Applied and Computational Harmonic Analysis,2001, 10(3):234～253
[105] Herrity K K, Gilbert A C, Tropp J A. Sparse approximation via intera-tive thresholding. In: Proceedings of the IEEE International Conferenceon Acoustics, Speech and Signal Processing. Washington D.C., USA:IEEE, 2006, 624～627
[106] Hestenes M R, Stiefel E. Methods of conjugate gradients fo solving linearsystems. Journal of Research of the National Bureau of Standards, 1952,49:409～436
[107] Demmel J. Applied numerical linear algebra. Cambridge, U.K.: Cam-birdge University Press, 1997
[108] Nocedal J, Wright S. Numerical optimization. Springer Series in Opera-tions Research, 1999
[109] Kim S J, Lustig M, Boyd S. An interior-point method for large-scalel1-regularized least squares. IEEE Journal of Selected Topics in SignalProcessing, 2007, 4:606～617
[110] Mohimani G H, Zadeh M B, Jutten C. A fast approach for overcompletesparse decomposition based on smoothed l0 norm. IEEE Transection onSignal Processing, 2009, 57:289～301