摘要
设计有效的算法是数值最优化中的重要研究课题.本硕士论文考察无约束优化问题、互补问题、多项式规划问题、张量规划问题等优化领域内的重点问题和近年来的热点问题,主要是从算法的设计、收敛性分析、数值计算效果、实际应用等方面进行研究.所设计的算法分别使用CUTEr、MCPLIB等标准的测试题库以及天津市第一中心医院的核磁共振影像数据来进行测试,并分别与SOSTOOLS、OptimizationTools(MatLab)等成熟的优化软件包进行了数值比较,实际计算效果是令人满意的.具体地,论文讨论的主要内容分成如下三个方面：
本文的第二章主要考虑无约束优化问题,首先提出了一个新的非单调线搜索算法,在适当的条件下证明它的全局收敛性和局部R-线性收敛性.对于所提出的算法,用测试题库CUTEr中的问题进行了测试,并与两个流行的非单调线搜索框架进行了比较.数值实验表明新提出的算法是有效的.其次,将一个非单调线搜索算法推广到了求解一类约束优化问题上,并且证明：如果所考虑的目标函数是拟凸的,而且相应的约束集合所定义的流形具有非负的截面曲率,那么所设计的算法是全局收敛的,并且收敛到问题的全局最优解.
第三章主要考虑互补问题.互补函数在互补问题的重构理论中起到了关键性的作用.本章首先提出了一族新的互补函数,该互补函数包含了众多流行的互补函数作为特例,并讨论了其若干性质,包括连续可微、Lipschitz连续、(强)半光滑、LC1、SC1等.利用这族互补函数,讨论了一个无导数的算法,使用测试题库MCPLIB来进行数值实验,实验结果表明新提出的函数是有价值的.其次,讨论了绝对值方程组与线性互补问题之间的关系：无需任何条件证明了Rn上的绝对值方程组等价于标准的线性互补问题,并给出了绝对值方程组的解集的一些性质；同时也提出了二阶锥上的绝对值方程组模型,设计了一个求解它的广义Newton算法,证明了算法的收敛性,一些数值计算表明该算法是有效的.作为一个应用,该算法为求解二阶锥上的互补问题提供了一个全新的方法.再次,对于互补问题的光滑Newton算法,现存的都是基于单调线搜索进行分析的,而实际计算中都用了非单调线搜索,缺乏相应的理论分析.本章第三部分引入了Kanzow-Kleinmichel光滑函数并证明了其Jacobian相容性,设计了一个求解非线性互补问题的具有新的非单调线搜索的光滑Newton算法并证明了其全局收敛性与局部二次收敛性,使用测试题库MCPLIB进行了数值实验,实验结果表明新设计的算法是有效的.最后,考虑对称锥互补问题,它为很多类互补问题提供了一个统一的框架,是近十几年优化领域研究的热点之一.本章第四部分给出了一个具有非单调线搜索的光滑Newton算法,在目前最弱的假设条件下证明了算法的全局收敛性.
第四章主要是考虑多项式规划问题.首先,对于双二次规划问题,在不同于传统多项式时间算法的思路下给出了双二次规划的一个目前最好的近似率,而且对于所给的松弛问题,提出了一个交互方向法,证明了算法的全局收敛性,数值计算表明：该方法可以为双二次规划问题提供一个很好的近似解,在与已知方法的数值比较中占有绝对优势.同时,通过提出和分析一种张量特征值的方法,也得到了一些双二次规划的结论.其次,将带秩约束的二次规划的近似率从目标函数矩阵为半正定推广到了一般情况.再次,对于多项式系统,给出了两个新的矩阵分解定理,并且在此基础上给出了一些新的多项式系统的择一定理.特别地,在一定条件下,将S-引理推广到了高次多项式系统.作为一个应用,给出了Z-特征值极值问题的(充分必要)最优性条件.最后,提出了一个用序列SDP方法逼近空间张量锥规划的的数值算法,并对随机构造的问题进行了数值计算,数值结果与SOSTOOLS得到的计算结果作了比较,结果显示：提出的方法是有效的.基于空间张量锥规划,提出了一个更广的张量锥规划并给出了对偶理论,把序列SDP方法推广到张量锥规划上,称这个方法为TCOSS.对于核磁共振医学影像中的弥散陡度张量模型,用锥规划的方法作了正定性分析,提出了一个新的锥规划算法,用此算法与传统的OptimizationTools (MatLab)中的最小二乘方法对模拟数据与实际数据作了数值比较,结果是令人满意的.
The design of an efficient algorithm is one of the most important research ar-eas in numerical optimization community. This thesis considers several important and hot optimization problems in recent years,such as unconstrained optimiza-tion,complementarity problems,polynomial programming,tensor conic program-ming,and mainly concentrates on the design,convergence analysis,numerical implementation and practical applications of algorithms.These algorithms are tested by using standard testing libraries CUTEr and MCPLIB,as well as real data from MRI center in Tianjin First Center Hospital,respectively. The corre-sponding numerical results are compared with some well known algorithms and sophisticated software,such as SOSTOOLS and OptimizationTools(MatLab),re-spectively. The results are encouraging.Concretely, there are three main chapters in this thesis:
The main issue of Chapter 2 is to consider unconstrained optimization.We first propose a new nonmonotone line search algorithm,and prove its global con-vergence and local R-linear convergence.The numerical results based on testing library CUTEr for this newly proposed algorithm are compared with two famous nonmonotone schemes, which indicate that the newly proposed algorithm is ef-fective.Then,a nonmonotone line search algorithm is extended to a class of constrained optimization problems. Under the assumption that the considered manifold defined by the constrained set has nonnegative sectional curvature and the involved function is quasi-convex,the iteration sequence of the algorithm globally converges to a global optimum.
Chapter 3 deals with complementarity problems(CPs).NCP-functions play a key role in reformulation methods for CPs.Firstly, a new family of NCP-functions is proposed,and its various favorable properties are investigated,in-cluding continuous differentiability, Lipschitz continuity,(strong)semismoothness, LC1,SC1 and so on.A derivative free algorithm based on the newly proposed NCP-functions is analyzed.Some numerical results for testing library MCPLIB show the value of this family of NCP-functions.Secondly, we consider the re-lationships between linear complementarity problems(LCPs)and absolute value equations(AVEs):without any assumption, we prove that LCP and AVE are equivalent to each other, and give some properties of the solution set for AVE; we also extend the AVE to the framework of second order cone(SOCAVE),and ana-lyze a generalized Newton algorithm for solving SOCAVE.The properties related to convergence of this algorithm are developed,some preliminarily numerical re-sults show its efficiency. As an application,we hence develop a new method towards LCP on second order cone.Thirdly, since the existing smoothing New-ton algorithms for complementarity problems are based on monotone line search, while their numerical implementations are based on nonmonotone line search, there lack theoretical analysis.After introducing Kanzow-Kleinmichel smooth-ing function and proving its Jacobian consistency, a smoothing Newton algorithm with a newly designed nonmonotone line search is proposed.The global linear and local quadratic convergence are proved.The numerical results based on MCPLIB indicate that this algorithm is efficient. Lastly, we consider CPs in the framework of symmetric cone which gives a unify framework for most CPs.We propose a smoothing Newton algorithm with a nonmonotone line search,and prove its global convergence under the weakest assumption.
We consider polynomial programming in Chapter 4.Firstly, we propose a favorable approximation ratio for bi-quadratic programming(Bi-QP) in an aspect which is different from that in the literature.An alternating direction method (ADM)is designed for a relaxation problem of Bi-QP, the global convergence is proved and the numerical results indicate:the ADM here could provide a favorable approximation solution for Bi-QP;and the ADM here is superior to the methods in the literature.Some results for Bi-QP are archived through an eigenvalue method of tensors as well.Secondly, we extend the approximation ratio for quadratic programming with rank constraints from positive semidefinite objective to the arbitrary case.Thirdly, based on two new decomposition results of matrices, serval alternative theorems are given.Especially, we generalize S-Lemma to the higher degree polynomial case under some suitable conditions.As an application, we give the (sufficient and necessary)optimality conditions for the extreme Z-eigenvalue problems of tensor.Lastly, a sequential SDP method for space tensor conic linear programming (STLP) is proposed.Some numerical results based on randomly generated examples are compared with those by SOSTOOLS,which show that the newly proposed method is promising. STLP is extended to tensor conic linear program(TCLP),and some duality results are proved.The former sequential SDP method is extended as well,which is called TCOSS in this thesis. Using the ideas above,we analyze the positive definiteness of diffusion kurtosis tensor imaging,and a newly conic linear programming(CLP)model is proposed. Numerical results for CLP and methods in OptimizationTools(MatLab)based on both synthetic and real data are compared,and the result is encouraging.
引文
[1]Nocedal,J.,Updating quasi-Newton matrices with limited storage. Math. Comput.1980,35:773-782.
[2]Ortega, J.M.,and Rheinboldt,W.,Iterative Solution of Nonlinear Equa-tions in Several Variables.SIAM.Philadelphia.2000.
[3]Yuan,Y.X.,and Sun,W.Y.,Optimization Theories and Methods.Beijing, Science Press,1997.
[4]Nocedal,J.,and Wright,S.J.,Numerical Optimization.Springer Press, 1999.
[5]Dai,Y.H.,On the nonmonotone line search.J.Optim.Theory Appl.2002, 112:315-330.
[6]Dai,Y.H.,A nonmonotone conjugate gradient algorithm for unconstrained optimization.J.Syst.Sci.Complex.2002,15:139-145.
[7]Grippo, L.,Lampariello,F.,and Lucidi,S.,A truncated Newton method with nonmonotone line search for unconstrained optimization.J.Optim. Theory Appl.1989,60:401-419.
[8]Grippo, L.,Lampariello, F.,and Lucidi,S.,A class of nonmonotone sta-bilization method in unconstrained optimization.Numer.Math.1991,59: 779-805.
[9]Panier,E.R.,and Tits,A.L.,Avoiding the maratas effect by means of a nonmonotone line search.SIAM.J.Numer.Anal.1991,28:1183-1195.
[10]Zhang, H.C.,and Hager,W.W.,A nonmonotone line search technique and its application to unconstrained optimization.SIAM.J.Optim.2004,14: 1043-1056.
[11]Burke,J.,and Xu,S.,The global linear convergence of a non-interior path-following algorithm for linear complementarity problems.Math.Oper.Res. 1998,23:719-734.
[12]Chen,B.,and Harker,P.T.,A non-interior-point continuation method for linear complementarity problem.SIAM J.Matrix Anal.Appl.1993,14: 1168-1190.
[13]Chen,B.,and Xiu,N.,A global linear and local quadratic non-interior con-tinuation method for nonlinear complementarity problems based on Chen-Mangasarian smoothing functions.SIAM J.Optim.1999,9:605-623.
[14]Chen,B.,and Xiu,N.,Superlinear noninterior one-step continuation method for monotone LCP in the absence of strict complementarity. J. Optim.Theory Appl.2001,108:317-332.
[15]Chen,C.,and Mangasarian,O.L.,A class of smoothing functions for non-linear and mixed complementarity problems.Comput.Optim.Appl.1999, 5:97-138.
[16]Chen,X.,and Ye,Y.,On homotopy-smoothing methods for variational inequalities.SIAM J.Control Optim.1999,37:589-616.
[17]Chen,X.,and Tseng,P.,Non-interior continuous methods for solving semidefinite complementarity problems.Math.Program.2003,95:431-474.
[18]Engelke,S.,and Kanzow,C.,Improved smoothing-type methods for the solution of linear programs.Numer.Math.2002,90:487-507.
[19]Facchinei,F.,Jiang, H.,and Qi,L.,A smoothing method for mathematical programming with equilibrium constraints.Math.Program.1999,85:107-134.
[20]Han,J.,Xiu,N.H.,and Qi,H.D.,Nonlinear Complementarity Problem Theory and Algorithms,Shanghai,China,Shanghai Scientific and Techni-cal Publishers.2006.(in chinese)
[21]Huang, Z.H.,The global linear and local quadratic convergence of a non-interior continuation algorithm for the LCP. IMA J.Numer.Anal.2005, 25:670-684.
[22]Huang, Z.H.,Han,J.,and Chen,Z.,A predictor-corrector smoothing New-ton algorithm,based on a new smoothing function,for solving the nonlinear complementarity problem with a PO function.J.Optim.Theory Appl.2003, 117:39-68.
[23]Huang, Z.H.,Qi,L.,and Sun,D.,Sub-quadratic convergence of a smoothing Newton algorithm for the PO-and monotone LCP. Math.Program.2004, 99:423-441.
[24]Huang, Z.H.,and Wang, H.,Smoothing-type algorithm for solving linear programs by using an augmented complementarity problem.Appl.Math. Comput.2006,177:330-345.
[25]Huang, Z.H.,and Xu,S.W.,Convergence properties of a non-interior-point smoothing algorithm for the P* NCP. J.Indus. Manag.Optim.2007,3: 569-584.
[26]Huang, Z.H.,and Ni,T.,Smoothing algorithms for complementarity prob-lems over symmetric cones.Comput.Optim.Appl.2009,online.
[27]Hayashi,S.,Yamashita,N.,and Fukushima,M.,A combined smoothing and regularization method for monotone second-order cone complementar-ity problems.SIAM J.Optim.2005,15:593-615.
[28]Kanzow,C.,and Kleinmichel,H.,A new class of semismooth Newton method for nonlinear complementarity problems.Comput.Optim.Appl. 1998,11:227-251.
[29]Liu,Y.J.,Zhang, Z.W.,and Wang,Y.H.,Analysis of smoothing method for symmetric conic lineae programming. J.Appl.Math.Computing.2006, 22:133-148.
[30]Qi,H.D.,A regularization smoothing Newton method for box constrained variational inequality problems with PO-functions.SIAM J.Optim.1999, 10:315-330.
[31]Qi,L.,Sun,D.,and Zhou,C.,A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequality problems.Math.Program.2000,87:1-35.
[32]Zhou,C.,Sun,D.,and Qi,L.,Numerical experiments for a class of squared smoothing Newton Methods for box constrained variational inequality prob-lems.In:M.Fukushima, L.Qi(Eds),Reformulation-Nonsmooth,Piecewise Smooth,Semismooth and Smoothing Methods.Kluwer Academic Publish-ers,Boston,1999,421-441.
[33]Faybusovich,L.,Euclidean Jordan algebra and interior-point algorithm. Positivity.1997,1:331-357.
[34]Faybusovich,L.,Linear systems in Jordan algebras and primal-dual interior-point algorithm.J.Comput.Appl.Math.1997,86:149-175.
[35]Pan,S.-H.,and Chen,J.-S.,A one-parametric class of merit functions for the symmetric cone complementarity problem.J.Math.Ana.Appl.2009, 355:195-215.
[36]Gowda,M.S.,and Sznajder,R.,Automorphism invariance of P and GUS properties of linear transformations in Euclidean Jordan algebras.Math. Oper.Res.2006,31:109-123.
[37]Gowda, M.S.,Sznajder,R.,and Tao,J.,Some P-properties for linear trans-formations on Euclidean Jordan algebras.Linear Algebra Appl.2004,393: 203-232.
[38]Kong, L.C.,Sun, J.,and Xiu,N.H.,A regularized smoothing Newton method for symmetric cone complementarity problems.SIAM J.Optim. 2008,19:1028-1047.
[39]Kong, L.C.,Tuncel,L.,and Xiu,N.H.,Vector-valued implicit Lagrangian for symmetric con complementarity problems.Asia-Pacific J.Oper.Res. 2009,26:199-233.
[40]Kong, L.C.,and Xiu,N.H.,New smooth C-functions for symmetric cone complementarity problems.Optim.Letters.2007,1(4):391-400.
[41]Liu,Y.J.,Zhang, L.W.,and Wang, Y.H.,Some properties of a class of merit functions for symmetric cone complementarity problems.Asia-Pacific J.Oper.Res.2006,23:473-495.
[42]Lu,Y.,and Yuan,Y.X.,An interior-point trust region algorithm for general cone progrmming.SIAM J.Optim.2007,18:65-86.
[43]Schmieta, V.,and Alizadeh,F.,Associative and Jordan algebras,and poly-nonial time interior-point algorithms for symmetrc cones.Math.Oper.Res. 2001,26:543-564.
[44]Schmieta, S.,and Alizadeh,F.,Extension of primal-dual interior-point al-gorithms to symmetric cones.Math.Program.2003,96:409-438.
[45]Sun,D.,and Sun,J.,Lowner's operator and spectral functions in Euclidean Joedan algebras.Math.Oper.Res.2008,33:421-445.
[46]Yoshise, A.,Interior point trajectories and a homogeneous model for non-linear complementarity problems over symmetric cones.SIAM J.Optim. 2006,17:1129-1153.
[47]Liu,D.C.,and Nocedal,J.,On the limited memory BFGS method for large scale optimization.Math.Program.1989,45:503-528.
[48]Andrei,N.,Scaled conjugate gradient algorithms for unconstrained opti-mization.Comput.Optim.Appl.2007,38:401-416.
[49]Grippo, L.,Lampariello,F.,and Lucidi,S., A nonmonotone line search technique for Newton's method.SIAM.J.Numer.Anal.1986,23:707-716.
[50]Pytlak,R.,and Tarnawski,T.,On the method of shortest residuals for unconstrained optimization.J.Optim.Theory. Appl.2007,133:99-110.
[51]Gould,N.I.M.,Orban,D.,and Toint,P.L.,CUTEr and SifDec:A con-strained and unconstrained environment,revisited.ACM Trans.Math. Software.2003,29:373-394.
[52]Burachik,R.S.,Grana Drummond,L.M.,Iusem,et.al.,Full convergence of the steepest descent method with inexact line searches.Optimization.1995, 32:137-146.
[53]Cruz Neto, J.X.,Lima,L.L.,and Oliveira,P.R.,Geodesic algorithms in Riemannian geometry. Balkan J.Geom.Appl.1998,3(2):89-100.
[54]Nemeth,S.,Five kinds of monotone vector fields.Pure Math.Appl.1999, 9(3-4):417-428.
[55]Quiroz,E.A.P.,Quispe,E.M.,and Oliveira, P.R.,Steepest descent method with a generalized Armijo search for quasiconvex functions on Riemannian manifolds.J.Math.Ana. Appl.2008,341:467-477.
[56]Billups,S.C.,Dirkse,S.P.,and Soares,M.C.,A comarison of algorithms for large scale mixed complementarity problems.Comput.Optim.Appl.1977, 7:3-25.
[57]Huang, Z.H.,Locating a maximally complementary solution of the mono-tone NCP by using non-interior-point smoothing algorithms.Math. Meth-ods Oper.Res.2005,61:41-55.
[58]Zhao,Y.B.,and Li D.,A globally and locally superlinearly convergent non-interior-point algorithm for PO LCPs.SIAM J.Optim.2003,13:1196-1221.
[59]Chen,B.,Chen,X.,and Kanzow, C.,A penalized Fischer-Burmeister NCP-function.Math.Program.2000,88:211-216.
[60]Chen,J.S.,The semismooth-related properties of a merit function and a de-scent method for the nonlinear complementarity problem.J.Global Optim. 2006,36:565-580.
[61]Chen,J.S.,On some NCP-function based on the generalized Fischer-Burmeister function.Asia-Pac.J.Oper.Res.2007,24:401-420.
[62]Chen,J.S.,and Pan,S.H.,A family of NCP functions and a desent method for the nonlinear complementarity problem.Comput.Optim.Appl.2008, 40:389-404.
[63]Chen,J.S.,and Pan,S.H.,A regularization semismooth Newton method based on the generalized Fischer-Burmeister function for PO-NCPs.J.Com-put.Appl.Math.2008,220:464-479.
[64]Facchinei,F.,and Pang,J.S.,Finite-Dimensional Variational Inequalities and Complementarity Problems.Springer Verlag,New York,2003.
[65]Pan,S.H.and Chen,J.S.A semismooth Newton method for the SOCCP based on one-parametric class of SOC complementarity functions.To ap-pear in Comput.Optim.Appl.
Sun,D.,and Qi,L.,On NCP-functions.Comput.Optim.Appl.1999,13: 201-220.
[67]Tseng P.,Growth behaviour of a class of merit functions for the nonlinear complementarity problem.J.Optim.Theory Appl.1996,89:17-37.
[68]Mangasarian,O.L.,and Meyer,R.R.,Absolute value equations.Linear Al-gebra Appl.2006,419:359-367.
[69]Mangasarian,O.L.,Absolute value programming.Comput.Optim.Appl. 2007,36:43-53.
[70]Mangasarian,O.L.,A generalized Newton method for absolute value equa-tions.Optim.Lett.2009,3:101-108.
[71]Prokopyev,O.A.,On equivalent reformulations for absolute value equa-tions.Comput.Optim.Appl.in press.
[72]Briet,J.,Filho, F.,and Vallentin,F.,The positive semidefinite grothendieck problem with rank constraint.Manuscript,2009.
[73]Jeyakumar,V.,Lee,G.M.,and Li,G.Y.,Alternative theorems for quadratic inequality systems and global quadratic optimization.SIAM J.Optim. 2009,20:983-1001.
[74]Ling, C.,Nie,J.W.,Qi,L.,et.al.,Bi-quadratic optimization over unit spheres and semidefinite programming relaxations.SIAM J.Optim.2009, 20:1286-1310.
[75]Cardoso, J.F.,High-order contrasts for independent component analysis. Neural Comput.1999,11:157-192.
[76]Comon,P.,Independent component analysis,a new concept?Signal Pro-cess.1994,36:287-314.
[77]Grigorascu,V.S.,and Regalia, P.A.,Tensor displacement structures and polyspectral matching.In:Fast Reliable Algorithms for Structured Matri-ces.Kailath,T.,and Sayed,A.H.,eds.SIAM,Philadelphia,1999.
[78]Han, D.,Dai,H.H.,and Qi,L.,Conditions for strong ellipticity of anisotropic elastic materials.J.Elasticity.2009,97:1-13.
[79]Kofidis,E.,and Regalia,P.A.,On the best rank-1 approximation of higher-order supersymmetric tensors.SIAM J. Matrix Anal.Appl.2002,23:863-884.
[80]Shor,N.Z.,Nondifferentiable Optimization and Polynomial Problems. Kluwer Academic Publishers,Dordrecht,The Netherlands,1998.
[81]Thomson,W.,Elements of a mathematical theory of elasticity. Philos. Trans.R. Soc..1856,166:481.
[82]Thomson, W.,Elasticity. Encyclopedia Briannica Vol.7,nineth ed.,Adam and Charles Black,London,Edingburgh.1878,796-825.
[83]Zhang, T.,and Golub,G.H.,Rank-one approximation of higher-order ten-sors.SIAM J.Matrix Anal.Appl.2001,23:534-550.
[84]Bomze,I.M.,Ling, C.,Qi,L.,et.al.,Standard bi-quadratic optimization problems and unconstrained polynomial reformulations.Manuscript,2009.
[85]Hu,S.L.,Huang, Z.H.,and Qi,L.,Eigenvalues and Decomposition of Even-Order Tensors with Applications to Bi-Quadratic Programming. Manuscript,2009.
[86]He,S.,Li,Z.,and Zhang,S.,Approximation Algorithms for Homogeneous Polynomial Optimization with Quadratic Constraints.Manuscript,2009.
[87]Luo,Z.-Q.,and Zhang,S.,A semidefinite relaxation scheme for multivariate quartic polynomial optimization with quadratic constraints.Manuscript, 2008.
[88]Zhang, X.,Ling, C.,and Qi,L.,Semidefinite relaxation bounds for bi-quadratic optimization problems with quadratic constraints.Manuscript, 2009.
[89]Gabay, D.,and Mercier,B.,A dual algorithm for the solution of nonlin-ear variational problems via finite element approximations.Compu.Math. Appl.1976,2:17-40.
[90]Chen,C., and Teboulle,M.,A proximal-based decomposition method for convex mini-mization problems.Math.Program.1994,64:81-101.
[91]Eckstein,J.,and Bertsekas,D.P.,On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone opera-tors.Math.Program.1992,55:93-318.
[92]He,B.S.,Liao,L.Z.,Han,D.R.,et.al.,A new inexact Alternating directions method for monotone variational inequalities.Math.Program.2002,92: 103-118
[93]Kontogiorgis,S.,and Meyer,R.R.,A variable-penalty Alternating direc-tions method for convex optimization.Math. Program.1998,83:29-53.
[94]Sun,J.,and Zhang,S.,A Modified alternating Direction Method for Convex Quadratically Constrained Quadratic Semidefinite Programs.Manuscript, 2009.
[95]Yu,Z.S.,Solving semidefinite programming problems via Alternating di-rection methods.J.Compu.Appl.Math.2006,193:437-445.
[96]Yuan,X.M.,and Yang,J.F.,Sparse and low-rank matrix decomposition via alternative direction methods.Manuscript,2009.
[97]Ben-Tal,A.,and Nemirovski,A.,On tractable approximations of uncertain linear matrix inequalities affected by interval uncertainty. SIAM J.Optim. 2002,12:811-833.
[98]Gibbons,L.E.,Hearn,D.W.,and Pardalos,P.M.,A continuous based heuristic for maximum clique problem.DIMACS Ser.Discrete Math.Theor. Comp.Sci.1996,26:103-124.
[99]Goemans,M.X.,and Williamson,D.P.,Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite program-ming.J.ACM.1995,42:1115-1145.
[100]Ye,Y.,Approximating quadratic programing with bound and quadratic constraints.Math.Program.84:219-226,1999.
[101]Nesterov,Y.E.,Semidefinite relaxation and nonconvex quadratic optimiza-tion.Optim.Method.Softw.1998,9:141-160.
[102]Chesi,G.,Garulli,A.,Tesi,A.,et.al.,Homogeneous Polynomial Forms for Robustness Analysis of Uncertain Systems Series:Lecture Notes in Control and Information Sciences.Vol.390,2009.
[103]Chen,X.,and Yuan,Y.X.,A note on quadratic forms.Math.Program. 1999,86:187-197.
[104]Hu,S.L.,Huang, Z.H.,Ni,H.Y.,et.al.,Positive definiteness of Diffusion Kurtosis Imaging.Manuscript,Tianjin University,2009.
[105]Polik,I.,and Terlaky, T.,A survey of the S-lemma. SIAM Rev.2007,49: 371-418.
[106]Qi, L.,and Teo, K.L.,Multivariate polynomial minimization and its appli-cation in signal processing.J.Global.Optim.2003,26:419-433.
[107]Qi,L.,Wang,F.,and Wang,Y.J.,Z-eigenvalue methods for a global poly-nomial optimization problem.Math.Program.2009,118:301-316.
[108]Qi,L.,and Ye,Y.,Space tensor conic programming.Department of Applied Mathematics,The Hong Kong Polytechnic University,2009.
[109]Qi,L.,Yu,G.,and Wu,E.X.,Higher order positive semi-definite diffu-sion tensor imaging. Department of Applied Mathematics,The Hong Kong Polytechnic University, April 2009.
[110]Yakubovich,V.A.,S-procedure in nonlinear control theory. Vestnik Leningrad.Univ.1971,1:62-77(in Russian).
[111]Yuan,Y.X.,On a subproblem of trust region algorithms for constrained optimization.Math.Program.1990,47:53-63.
[112]Ye,Y.,and Zhang, S.,New results on quadratic minimization.SIAM J. Optim.2003,14:245-267.
[113]Ai,W.,Huang, Y.W.,and Zhang,S.,New results on Hermitian matrix rank-one decomposition.Math.Program.2009, online.
[114]Ai,W.,Huang,Y.W.,and Zhang,S.,On the low rank solutions for linear matrix inequalities.Math.Oper.Res.2008,33:965-975.
[115]Beck,A.,On the convexity of a class of quadratic mappings and its applica-tion to the problem of finding the smallest ball enclosing a given intersection of ball.J.Global Optim.2007,39:113-126.
[116]Huang, Z.H.,Sun,D.,and Zhao,G.,A smoothing Newton-type algorithm of stronger convergence for the quadratically constrained convex quadratic pro-gramming. Comput.Optim.Appl.2006,35:199-237.
[117]Huang, Y.W.,and Zhang, S.,Complex matrix decomposition and quadratic programming.Math.Oper.Res.2007,32:758-768.
[118]Sturm,J.F.,and Zhang, S.,On cones of nonnegative quadratic functions. Math.Oper.Res.2003,28:246-267.
[119]So, A.,Ye,Y.,and Zhang,J.,A unified theorem on SDP rank reduction. Math.Oper.Res.2008,33:910-920.
[120]Dines,L.L.,On the mapping of quadratic forms.Bull.Amer.Math.Soc. 1941,47:494-498.
[121]Polyak,B.T.,Convexity of quadratic transformation and its use in control and optimization.J.Optim.Theory Appl.1998,99:563-583.
[122]Jeyakumar,V.,Farkas Lemma:Generalizations.In:Encylopedia of Opti-mization.Kluwer,Boston,2000,2:87-91.
[123]Martinez-Legaz,J.E.,and Seeger,A.,Yuan's alternative theorem and the maximization of the minimum eigenvalue function.J.Optim.Theory Appl. 1994,82:159-67.
[124]Qi,L.,Eigenvalues of a real supersymmetric tensor.J.Symb.Comput. 2005,40:1302-1324.
[125]Bloy, L.,and Verma, R.,On computing the underlying fiber directions from the diffusion orientation distribution function.In:Medical Image Com-puting and Computer-Assisted Intervention-MICCAI 2008,Metaxas,D., Axel,L.,Fichtinger,G.,et.al.,eds.,Springer-Verlag, Berlin,2008,1-8.
[126]Chefd'Hotel,C.,Tschumperle,D.,Deriche,R.,et.al.,Regularizing flows for constrained matrix-valued images.J.Math.Imaging Vis.2004,20:147-162.
[127]Descoteaux, M.,Angelino, E.,Fitzgibbons,S.,et.al.,Apparent diffusion co-efficients from high angular diffusion imaging:Estimation and applications. Magne.Reson.Med.2006,56:395-410.
[128]Ozarslan,E.,and Mareci,T.H.,Generalized diffision tensor imaging and analytical relationships between diffision tensor imaging and high angular resolution diffision imaging.Magne.Reson.Med.2003,50:955-965.
[129]Wang, Z.,Vemuri,B.C.,Chen,Y.,et.al.,A constrained variational prin-ciple for direct estimation and smoothing of the diffusion tensor field from complex DWI.IEEE Trans.Med.Imaging.2004,23:930-939.
[130]Descoteaux, M.,Angelino,E.,Fitzgibbons,S.,et.al.,Regularized,fast,and anaytical q-ball imaging. Magne.Reson.Med.2007,58:497-510.
[131]Basser,P.J.,and Jones,D.K.,Diffusion-tensor MRI:theory, experimental design and data analysis-a technical review.NMR Biomed.2002,15:456-467.
[132]Basser,P.J.,Mattiello,J.,and LeBihan,D.,MR diffusion tensor spec-troscopy and imaging. Biophysica.1994,66:259-267.
[133]Tuch,D.S.,Q-ball imaging.Magne.Reson.Med.2004,52:1358-1372.
[134]Lu,H.,Jensen,H.J.,Ramani,A.,Helpern,J.A.,Three-dimensional char-acterization of non-Gaussian water diffusion in humans using diffusion kur-tosis imaging. NMR in Biomedicine,2006,19:236-247.
[135]Dolan,E.D.,and More,J.J.,Benchmarking optimization software with performance profiles.Math.Program.2002,91:201-213.
[136]Huang, Z.H.,and Sun,J.,A smoothing Newton algorithm for mathemati-cal programs with complementarity constraints.J.Indus.Manag. Optimi. 2005,1:153-170.
[137]Huang, Z.H.,Zhang, Y.,and Wu, W.,A smoothing-type algorithm for solving system of inequalities.J.Comput.Appl.Math.2008,220:355-363.
[138]Ferris,M.C.,and Pang, J.S.,Engineering and economic applications of complementarity problems.SIAM J.Rev.1997,39:669-713.
[139]Harker,P.T.,and Pang, J.S.,Finite dimensional variational inequality and nonlinear complementarity problem:a survey of theory, algorithms and applications.Math.Program.1990,48:161-220.
[140]Pang, J.S.,Complementarity problems.In:Horst,R.,Pardalos,P.,eds. Handbook of Global Optimization.Kluwer Academic Publishers.Boston. Massachusetts.1994,271-338.
[141]Huang, Z.H.,Sufficient conditions on nonemptiness and boundedness of the solution set of the Po function nonlinear complementarity problem.Oper. Res.Letters.2002,30:202-210.
[142]Huang, Z.H.,and Gu,W.Z.,A smoothing-type algorithm for solving linear complementarity problems with strong convergence properties.Appl.Math. Optim.2008,57:17-29.
[143]Jiang,H.Y.,Fukushima,M.,Qi,L.et.al.,A trust region method for solving generalized complementarity problems.SIAM.J.Optim.1998,8:140-157.
[144]Kanzow,C.,Yamashita, N.,and Fukushima,M.,New NCP-functions and their properties.J.Optim.Theory Appl.1997,94:115-135.
[145]Yamashita, N.,and Fukushima,M.,On stationary points of the implicit La-grangian for nonlinear complementarity problems.J.Optim.Theory Appl. 1995,84:653-663.
[146]Yamashita, N.and Fukushima,M.,Modified Newton methods for solving a semismooth reformulation of monotone complementarity problems.Math. Program.1997,76:469-491.
[147]Faraut,J.,and Koranyi,A.,Analysis on Symmetric Cones.New York, Oxford Mathematical Monographs,Oxford University Press,1994.
[148]Clarke F.H.,Optimization and Nonsmooth Analysis,Wiley, New York, 1983.
[149]Mifflin,R.,Semismooth and semiconvex functions in constrained optimiza-tion.SIAM J.Control Optim.1997,15:957-972.
[150]Qi,L.,and Sun,J.,A nonsmooth version of Newton's method.Math.Pro-gram.1993,58:353-367.
[151]Chen,J.S.,and Tseng, P.,An unconstrained smooth minimization reformu-lation of the second-order cone complementarity problem.Math.Program. 2005,104:293-372.
[152]Fischer,A.,Solution of monotone complementarity problems with Lips-chitzian functions.Math.Program.1997,76:513-532.
[153]Hu,S.L.,Huang, Z.H.,and Lu,N.,Smoothness of a Generalized Merit Function for the Second-Order Cone Complementarity Problem.To appear in Pacific J.Optim.2010.
[154]Wang, Y.,Hu,S.L.,and Ni,H.Y.,A Smoothing Reformulation of D-Eigenvalues for Diffusion Kurtosis Tensor Based on A New Class of NCP-Functions.2009,Manuscript,submitted.
[155]Pan,S.H.,Kum,S.,Lim,Y.,et.al.,A generalized Fisher-Burmeister merit funvtion for the second-order cone complementarity problem.Manuscript, 2008.
[156]Prokopyev,O.A.,Butenko, S.,and Trapp,A.,Checking solvability of sys-tems of interval linear equations and inequalities via mixed integer pro-gramming.European J.Oper.Res.2009,199:117-121.
[157]Rohn,J.,A theorem of the alternatives for the equation Ax+B|x|=b. Linear and Multilinear Algebra.2004,52:421-426.
[158]Rohn,J.,Solvability of systems of interval linear equations and inequalities. In:Linear Optimization Problems with Inexact Data. Edited by Fiedler, M.,Nedoma, J.,Ramik,J.,et.al.,Springer.2006,35-78
[159]Cottle,R.W.,Pang,J.-S.,and Stone,R.E.,The Linear Complementarity Problem.Academic Press,New York,1992.
[160]Murty, K.G.,Yu,F.-T.,Linear Complementarity, Linear and Nonlinear Programming. Internet Edition,Dept.of Industrial and Operations Engi-neering The University of Michigan,Ann Arbor.1997.
[161]Pardalos,P.M.,The linear complementarity problem.In:Advances in Op-timization and Numerical Analysis Edited by Gomez,S.,and Hennart,J.P., Kluwer Academic Publishers,1994,39-49.
[162]Hu,S.L.,Huang, Z.H.,and Zhang, Q.,A Generalized Newton Method for Absolute Value Equations Associated with Second Order Cones.2009, Manuscript,submitted.
[163]Alizadeh,F.,and Goldfarb,D.,Second-order cone programming. Math. Program.2003,95:3-51.
[164]Kojima,M.,Megiddo,N.,Noma,T.,et.al.,A unified approach to in-trior point algorithm for linear complementarity problems.Lecture Notes in Computer Science,Springer-Verlag,Berlin,Germany, Vol.538,1991.
[165]Chen,X.,Qi,L.,and Sun,D.F.,Global and superlinear convergence of the smoothing Newton method and its application to general box constrained variational inequalities.Math.Comput.1998,67:519-540.
[166]Kanzow,C.,and Pieper,H.,Jacobian smoothing methods for nonlinear complementarity problems.SIAM.J.Optim.1999,9:342-373.
[167]Ravindran,G.,and Gowda, M.S.,Regularization of Po-functions in box variational inequality problems.SIAM J.Optim.2001,11:748-760.
[168]Gowda,M.S.,and Sznajder,J.J.,Weak univalence and connectedness of inverse images of continuous functions.Math. Oper.Res.1999,24:255-261.
[169]Sturm,J.,Using SeDuMi 1.02,a Matlab toolbox for optimization over symmetric cones.Optim.Methods Softw.1999,11-12:625-653.
[170]Hu,S.L.,and Huang, Z.H.,A Note on Approximating Quadratic Program-ming with Rank Constraint.2009, Manuscript,submitted.
[171]Schoenberg, I.J.,Positive definite functions on spheres.Duke Math.J.1942, 9:96-108.
[172]Rockafellar,R.T.,Convex Analysis.Princeton Publisher,Princeton,1970.
[173]Finsler,P.,Uber das Vorkommen definiter und semidefiniter Formen in Scharen quadratischer Formen.Comm.Math.Helvetia.1937,9:188-192.
[174]Baccari,A.,and Trad,A.,On the classical necessary second-order optimal-ity conditions in the presence of equality and inequality constraints.SIAM J.Optim.2005,15:394-408.
[175]Nestrov,Y.E.,and Nemirovski,A.,Interior Point Polynomial Time Meth-ods in Convex Programming. SIAM,Philadelphia,1994.
[176]Lasserre,J.,Global optimization with polynomials and the problem of mo-ments.SIAM J.Optim.2001,11:796-817.
[177]Putinar,M.,Positive polynomials on compact semi-algebraic sets.Ind. Univ.Math.J.1993,42:969-984.
[178]Schmuedgen,K.,The K-moment problem for compact semi-algebraic sets. Mathematische Annalen.1991,289:203-206.
[179]Chesi,G.,Tesi,A.,Vicino,A.,et.al.,A convex approach to a class of mini-mum norm problems.In:Garulli,A.,Tesi,A.,Vicino, A.,eds.Robustness in Identification and Control.Springer,London,1999,359-372.
[180]Chesi,G.,Tesi,A.,Vicino,A.,et.al.,On convexification of some mini-mum distance problems.In:5th European Control Conference,Karlsruhe, Germany,1999.
[181]Parrilo,P.A.,Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization.PhD thesis,CIT,2000.
[182]Parrilo,P.A.,Semidefinite programming relaxations for semialgebraic prob-lems.Math.Progrm.2003,96:293-320.
[183]Prajna, S.,Papachristodoulou,A.,Seiler,P.,et.al.,SOSTOOLS,User's guide,Version 2.00.2004.
[184]Hu,S.L.,Huang,Z.H.,and Qi,L.,Finding the Extreme Z-Eigenvalues of Tensor via Sequential SDPs:TCOSS.2009,Numerical Report.
[185]Stejskal, E.O.,Tanner,J.E.,Spin diffusion measurements:spin echoes in the presence of a time-dependent field gradient.J.Chem.Phy.1965,42: 288-292.
[186]Cox, D.,Little,J.,Oshea,D.,Using Algebraic Geometry, Springer-Verlag, New York,1998.
