min-max-min规划的凝聚同伦方法及其在数据挖掘中的应用
|
摘要
min-max-min规划是一类重要的非光滑非凸优化问题,在工程优化设计、电子线路设计、数据挖掘等领域有着重要应用.本文的工作在已有的凝聚同伦算法的基础上进行.
第一章主要介绍min-max-min规划模型及其应用背景,并回顾一些相关理论与算法.
第二章提出了数值跟踪凝聚同伦的一个基于截断策略的高效率算法.在算法的每步迭代,只用到max-min函数的组成函数中的一小部分的凝聚函数,这一部分组成函数对应的下标集合在每步迭代过程中随着截断精度控制准则自适应调整.以尽可能地减少函数的梯度及海赛阵的计算量.我们给出保持校正算法的二次收敛性和预估步的有效性的截断凝聚精度控制准则,该精度控制准则不涉及梯度和海赛阵的计算.只与max-min函数的组成函数的函数值有关.基于该精度控制准则,我们证明了截断凝聚同伦算法的收敛性及每步校正的局部二次收敛性.
第三章基于二次凝聚函数,对min-max-min规划构造了一种动约束函数,使得原问题的可行集可以由一个凸球约束连续形变过去,进而给出了一类新的凝聚形变同伦方法.新算法不要求可行集满足弱法锥条件,并且不要求初始点是内点.
第四章基于离散化相容逼近的策略,将半无限min-max-min问题转化为有限min-max-min规划问题,再用截断凝聚同伦方法求解.可以证明:当离散点充分稠密时.离散化子问题的稳定点是原问题的6-次稳定点.
第五章将半无限min-max-min问题写成一个双层规划问题.在底层问题严格凸的假设下,建立了原问题的一阶最优性条件,并构造凝聚同伦方法求解该问题.在一定条件下.可以证明通向原问题的广义KKT点的光滑同伦路径的存在性和收敛性.
第六章考虑了截断凝聚同伦算法在数据挖掘的支持向量机模型求解中的一些应用.首先考虑了半监督分类问题.将已有的求解半监督分类问题的一个支持向量机模型加以变形,得到一个由max型以及max-min型的非光滑函数组合得到的无约束非光滑非凸优化问题,并构造了截断凝聚同伦算法求解该模型.其次考虑了多示例分类问题.该问题是线性min-max-min规划问题,即组成函数均为线性函数.我们证明该问题满足弱法锥条件,因此可以用截断凝聚同伦方法求解该问题.
文中所有的算法,都用Matlab编程实现,并通过数值实验与已有的一些算法相比较,结果表明本文给出的算法是有效的.
Min-max-min programming is a kind of important nonsmooth problem that appears in various fields such as engineering optimization design, circuit design and data mining. The thesis is based on the existing aggregate homotopy method, it consists of the following sections:
In Chapter 1. min-max-min programming problem with its application ground is formulated, and some results on related theory and algorithms are recalled.
In Chapter 2, by giving a truncated aggregate strategy, an efficient truncate aggregate method for numerically tracing aggregate homotopy path is introduced. At every iteration, only a part of component functions are used to make aggregate smoothing approximation, whose index set is updated adaptively with a truncated aggregate criterion. The criterion concerns only with computation of component functions value, not their gradients or Hessian. Based on the criterion, the convergence of the truncated aggregate homotopy method and locally quadratic convergence of the corrector iterations at every step are discussed.
In Chapter 3, using twice aggregate function, a new aggregate deformation homotopy method is established to solve min-max-min programming. Compared to aggregate homotopy method, the new method doesn't require the weak normal cone condition and doesn't require an interior initial point.
In Chapter 4. based on the well known discretized consistent approximate strategy, a semi-infinite min-max-min programming is approximated by finite min-max-min problems. It's proven that anε-substationary point can be obtained by solving some dense enough min-max-min programming with truncated aggregate homotopy method.
In Chapter 5, a semi-infinite min-max-min problem is reformulated into a special bi-level problem. Under an assumption that the lower level problem is a strictly convex problem, a first-order Optimality condition of the original problem is given. An aggregate homotopy is established for solving the problem. It's proven that the homotopy determines a smooth path, which approaching to a solution of a generalized KKT point of the original problem.
In the last section, some applications of the aggregate homotopy method arc discussed. Firstly, a reformulation of the semi-supervised support vector machines is given. An uncon- strained nonsmooth problem with max type and max-min type is obtained. Utilizing the truncated aggregate technique, an implementation procedure is presented. Secondly, some considerations on the weak normal cone condition are given. It's proven that multiple-instance support vector machines satisfies the condition. As a result, truncated aggregate homotopy method is feasible for it.
All methods in the thesis are implemented by Matlab software. Some numerical comparisons are given to show the efficiency of the methods.
第一章主要介绍min-max-min规划模型及其应用背景,并回顾一些相关理论与算法.
第二章提出了数值跟踪凝聚同伦的一个基于截断策略的高效率算法.在算法的每步迭代,只用到max-min函数的组成函数中的一小部分的凝聚函数,这一部分组成函数对应的下标集合在每步迭代过程中随着截断精度控制准则自适应调整.以尽可能地减少函数的梯度及海赛阵的计算量.我们给出保持校正算法的二次收敛性和预估步的有效性的截断凝聚精度控制准则,该精度控制准则不涉及梯度和海赛阵的计算.只与max-min函数的组成函数的函数值有关.基于该精度控制准则,我们证明了截断凝聚同伦算法的收敛性及每步校正的局部二次收敛性.
第三章基于二次凝聚函数,对min-max-min规划构造了一种动约束函数,使得原问题的可行集可以由一个凸球约束连续形变过去,进而给出了一类新的凝聚形变同伦方法.新算法不要求可行集满足弱法锥条件,并且不要求初始点是内点.
第四章基于离散化相容逼近的策略,将半无限min-max-min问题转化为有限min-max-min规划问题,再用截断凝聚同伦方法求解.可以证明:当离散点充分稠密时.离散化子问题的稳定点是原问题的6-次稳定点.
第五章将半无限min-max-min问题写成一个双层规划问题.在底层问题严格凸的假设下,建立了原问题的一阶最优性条件,并构造凝聚同伦方法求解该问题.在一定条件下.可以证明通向原问题的广义KKT点的光滑同伦路径的存在性和收敛性.
第六章考虑了截断凝聚同伦算法在数据挖掘的支持向量机模型求解中的一些应用.首先考虑了半监督分类问题.将已有的求解半监督分类问题的一个支持向量机模型加以变形,得到一个由max型以及max-min型的非光滑函数组合得到的无约束非光滑非凸优化问题,并构造了截断凝聚同伦算法求解该模型.其次考虑了多示例分类问题.该问题是线性min-max-min规划问题,即组成函数均为线性函数.我们证明该问题满足弱法锥条件,因此可以用截断凝聚同伦方法求解该问题.
文中所有的算法,都用Matlab编程实现,并通过数值实验与已有的一些算法相比较,结果表明本文给出的算法是有效的.
Min-max-min programming is a kind of important nonsmooth problem that appears in various fields such as engineering optimization design, circuit design and data mining. The thesis is based on the existing aggregate homotopy method, it consists of the following sections:
In Chapter 1. min-max-min programming problem with its application ground is formulated, and some results on related theory and algorithms are recalled.
In Chapter 2, by giving a truncated aggregate strategy, an efficient truncate aggregate method for numerically tracing aggregate homotopy path is introduced. At every iteration, only a part of component functions are used to make aggregate smoothing approximation, whose index set is updated adaptively with a truncated aggregate criterion. The criterion concerns only with computation of component functions value, not their gradients or Hessian. Based on the criterion, the convergence of the truncated aggregate homotopy method and locally quadratic convergence of the corrector iterations at every step are discussed.
In Chapter 3, using twice aggregate function, a new aggregate deformation homotopy method is established to solve min-max-min programming. Compared to aggregate homotopy method, the new method doesn't require the weak normal cone condition and doesn't require an interior initial point.
In Chapter 4. based on the well known discretized consistent approximate strategy, a semi-infinite min-max-min programming is approximated by finite min-max-min problems. It's proven that anε-substationary point can be obtained by solving some dense enough min-max-min programming with truncated aggregate homotopy method.
In Chapter 5, a semi-infinite min-max-min problem is reformulated into a special bi-level problem. Under an assumption that the lower level problem is a strictly convex problem, a first-order Optimality condition of the original problem is given. An aggregate homotopy is established for solving the problem. It's proven that the homotopy determines a smooth path, which approaching to a solution of a generalized KKT point of the original problem.
In the last section, some applications of the aggregate homotopy method arc discussed. Firstly, a reformulation of the semi-supervised support vector machines is given. An uncon- strained nonsmooth problem with max type and max-min type is obtained. Utilizing the truncated aggregate technique, an implementation procedure is presented. Secondly, some considerations on the weak normal cone condition are given. It's proven that multiple-instance support vector machines satisfies the condition. As a result, truncated aggregate homotopy method is feasible for it.
All methods in the thesis are implemented by Matlab software. Some numerical comparisons are given to show the efficiency of the methods.
引文
[1]He,L.and Polak,E.,Effective diagonalization strategies for the solution of a class of optimal design problems[J].IEEE Trans.Auto.Contr.,1990,35:258-267.
[2]Bandler,J.W..Liu,P.C.and Tromp,H.,A nonlinear programming approach to optimal design centering:tolerancing,and tuning[J].IEEE Trans.Circuits Systems,1976,CAS-23:155-165.
[3]Polak,E.and Sangiovauni-Vincentelli,A.,Theoretical and computational aspects of the optimal design centering,tolerancing,and tuning problem[J].IEEE Trans.Circ.and Sys.,1979,26:795-813.
[4]Gilbert,E.G.and Johnson,D.W.,Distaace functions and their application to robot path planning in the presence of obstacles[J].IEEE J.Robotics Automat.,1985,RA-1:21-30.
[5]Grossman,I.E.and Sargent,R.W.,Optimal design of chemical plants with uncertain para-meters[J].AICHE J.,1978,24:1-7.
[6]Halemane,K.P.and Grossman,I.E.,Optimal process design under uncertainty[J].AICHE J.,1983,29:425-433.
[7]Ostrivsky,G.M.,Volin,Y.M.,Barit,E.I.and Senyavin,M.M.,Flexibility.analysis and optimization of chemical plants with uncertain parameters[J].Comput.Chem.Engrg.,1994,18:755-767.
[8]Cheng,C.K.,Deng,X.,Liao,Y.Z.and Yao,S.Z.,Symbolic layout compaction under conditional design rules[J].IEEE Trans.Comput.Aided Design,1992,11:475-486.
[9]Hochbaum,D.,Complexity and algorithms for logical constraints with applications to VLSI layout,compaction and clocking,Studies in Locational Analysis[C].ISOLD Ⅵ Proceedings,159-164,1993.
[10]罗长童,低维单形进化算法及其应用[D],长春:吉林大学博士论文,2007.
[11]Mangasarian,O.L.and Edward,W.W.,Multiple instance classification via.successive linear programming[J].JOTA,2008.137:555-568.
[12]Zhu,X.J.,Semi-supervised learning literature survey[R].Tech.report 1530 Computer Science,University of Wisconsin-Madison,2005.
[13]Polak,E.and Royset,J.O.,Algorithms for finite and semi-infinite min-max-min problems using adaptive smoothing techniques[J].JOTA.,2003,119:421-457.
[14]Royset,J.O.,Kiureghian,A.D.and Polak,E.,Reliability-based optimal structural design by the decoupling approach[J].Reliab.Eng.Sys.Saf.,2001,73:213-221.
[15]Royset,J.O.,Polak,E.and Kiureghian,A.D.,Adaptive approximations and exact penalization for the solution of generalized semi-infinite min-max problems[J].SIAM J.Optim.,2003,14:1-34.
[16]Kirjner-Neto,C.and Polak,E.,On the conversion of optimization problems with max-min constraints to standard optimization problems[J].,SIAM J.Optim.,1998,8:887-915.
[17]Dietterich,T.G.,Lathrop,R.H.and Lozano,P.T.,Solving the multiple-instance problem with axisparrallel rectangles[J].Artificial Intelligence,1997.89:31-71.
[18]Zhong,Z.H.,Multi-instance Learning:A Survey[R].Technical Report(2004),http://cs.nju.edu.cn/zhouzh/zhouzh.files/publication/techrep04.pdf.
[19]Andrews,S.,Tsochantaridis I.and Hofmann,T.,Support vector machines for multipleinstancc learning[C].Adv.Neural Inform.Proc.Sys.,2003,561-568.
[20]Rockafellar,R.T.,Convex Analysis[M].Princeton University Press,Princeton,New Jersey,1970.
[21]Dcmyanov,V.F.and Vasilcv,L.V.,Nondifferentiablc Optimization[M](in Russian),Nanka,Moscow,1981.(English edition,translated by Sasagawa,T.Springer-Optimization Software,New York,1986.)
[22]Clarkc,F.H.,Optimization and Nonsmooth Analysis[M].New York,Wiley-Interscience.Inc.,1983.
[23]Shor,N.Z.,Minimization Methods for Non-differentiablc Functions[M].(translated from the Russian by Kiwiel K.C.and Ruszczynski,A.),Springer-Verlag,Berlin,New York,1985.
[24]Mordukhovich,B.S.,Maximum principle in the problem of time optimal response with nonsmooth constraints[J].J.Appl.Math.Mech.1976,40:960-969.
[25]Mordukhovich,B.S.,Metric approximations and necessary optimality conditions for general classeds of nonsmooth extremum problems[J].Soviet Math.Doklady,1980,22:526-530.
[26]Rockafellar,R.T.and Wets,R.J.B.,Variational Analysis[M].Springer Verlag,1997.
[27]Mordukhovich,B.S.,Variational Analysis and Generalized Differentiation,(I:Basic theory and Ⅱ:Applications)[M].Springer Verlag,Berlin,2006.
[28]M(a|¨)kel(a|¨),M.M.and Neittaanm(a|¨)ki,P.,Nonsmooth Optimization:Analysis and Algorithms with Applications to Optimal Control[M].World Scientific Publishing Co.Pte.Ltd.,1992.
[29]Polak,E.,Optimization,Algorithms and Consistent Approximations[M].Springer-Verlag,New York,1997.
[30]Hiriart-Urruty,J.B.and Lemarechal,C.,Convex Analysis and Minimization Algorithms Ⅰ[M].Springer-Verlag,Berlin,1993.
[31]Demyanov,V.F.and Rubinov,A.M.,Constructive Nonsmooth Analysis[M].Frankfurt am Main Berlin Bern,Wien,1995.
[32]Clarke,F.H.,Ledyaev,Yu.S..Stern,R.J.and Wolenski,P.R.,Nonsmooth Analysis and Control Theory[M].New York,Springer-Verlag,1998.
[33]Bonnans,J.F.and Shapiro,A.,Perturbation Analysis of Optimization Problems[M],New York,Springer-verlag,2000.
[34]Bertsckas.D.P.,Nedic,A.and Ozdaglar.A.E.,Convex Analysis and Optimization[M].北京:清华大学出版社,2006.
[35]Dutta,J.,Generalized derivatives and nonsmooth optimization.a finite dimensional tour[J].TOP,2005,13:185-314.
[36]Scholtes,S..Nonconvex structures in nonlinear programming[J].Oper.Res.,2004,52:368-383.
[37]Li.S.J.,Yang,X.Q.and Teo,K.L.,On the conversion of optimization problems with max-min constraints to standard optimization problems[J].JOTA,2001,109:691-698.
[38]Kellogg R.B.,Li,T.Y.and Yorke J.A.,A constructive proof of the Brower fixed-point theorem and computational results[J].SIAM J.Numer.Anal.,1976,13:473-483.
[39]Smale,S.,A convergent process of price adjustment and global Newton method,J.Math.Econ.,3(1976),1-14.
[40]Chow,S.N.,Mallet-Paret,J.and Yorke,J.Z.,Finding zeros of maps:Homotopy methods that are constructive with probability one[J].Math.Comput.,1978,32:887-899.
[41]Garcia,C.B.and Zangwill,W.I.,Pathways to Solutions,Fixed Points and Equilibria[M].New Jersey,Prentice-Hall,1981.
[42]Allgower,E.L.and Georg,K.,Numerical Continuation Methods:An Introduction[M].Berlin.New York,Springer-verlag,1990.
[43]王则柯、高堂安,同伦方法引论[M].重庆:重庆出版社,1989.
[44]Gill,P.E.,Murray,W.,Saunders,M.A.,Tomlin,J.A.and Wright,M.H.,On the projected Newton barrier methods for linear programming and an equivalence to Karmarkar's projective method[J].Math.Prog.,1986,36:183-209.
[45]Megiddo,N.,Pathways to the optimal set in linear programming[C].Progress in Mathematical Programming,Interior Point and Related Methods,Megiddo,N.(eds).Springer,New York.131-158.1988.
[46]Kojima,M.,Mizuno,S.and Yoshise:A.,A primal-dual interior point algorithm for linear pro-grammming[C].In Progress in Mathematical Programming,Interior Point and Related Methods (N.Megiddo,ed.),N.Y.,Springer-Verlag,29-47,1988.
[47]Wright,S.J.and Nocedal J.,Numerical Optimization(second edition)[M].Springer-Verlag,New York,Berlin,2000.
[48]袁亚湘、孙文瑜,最优化理论与方法[M].北京:科学出版社:1997.
[49]Karmarkar,N.,A new polynomial-time algorithm for linear programming[J].Combinatorica,1984,14:373-395.
[50]Wright,S.J.,Primal-Dual Interior Point Methods[M].SIAM,Philadelphia,1997.
[51]Mehrotra,S.,On the implementation of a primal-dual interior point method[J].SIAM J.Optim.,1992,2:575-601.
[52]Mizuno,S.,Todd,M.J.and Ye,Y.,On adaptive primal-dual interior-point algorithms for linear programming[J].Math.Oper.Res.;1993,18:964-981.
[53]Shanno,D.F.and Vanderbei,R.J.,Interior-point methods for nonconvex nonlinear programming:orderings and higher-order methods[J].Math.Prog.,2000,87:303-316.
[54]刘国新,求解序列极大极小问题、互补问题和变分不等式的凝聚同伦方法[D].长春:吉林大学博士学位论文,2003.
[55]Alizadeh,F.,Haeberly,J.P.A.and Overton M.L.,Primal-dual interior-point methods for semidefininte programming:convergence rates,stability and numerical results[J].SIAM J.Optim.,1998,8:746-768.
[56]Feng,G.C.and Yu,B.,Combined homotopy interior point method for nonlinear programming problems[J].Lecture Notes in Numer.Anal.,1995,14:9-16.
[57]Feng,G.C.,Lin,Z.H.and Yu,.B..Existence of an interior pathway to a Karush-Kuhn-Tucker point of a nonconvex programming problem[J].Nonlinear Anal.,1998,32:761-768.
[58]Lin,Z.H.,Li.Y.and Yu,B.,A combined homotopy interior point method for general nonlinear programming problems[J].Appl.Math.Comput.,1996.80:209-224.
[59]Lin Z.H.,Yu.B.and Feng,G.C.;A combined homotopy interior point method for convex programming problem[J[.Appl.Math.Comput.,1997,84:193-211.
[60]Yu,B.,Feng,G.C.and Zhang,S.L.,The aggregate constraint homotopy method for nonconvex nonlinear programming[J[.Nonl.Anal.,2001,45:839-847.
[61]Liu,Q.H.,Yu,B.and Feng,G.C.,An interior point path-following method for nonconvex programming with quasi normal eone condition[J].数学进展,2000,29:281-282.
[62]Yu,B.,Liu Q.H.and Feng,G.C.,A combined homotopy interior point method for nonconvex programming with pseudo cone condition[J].J.Northeast.Math.,2000,16:383-386.
[63]Yu,B.,Xu,Q.and Feng,G.C.,On the complexity of a combined homotopy interior point method for convex programming[J].J.Comput.Appl.Math.,2007,200:32-46.
[64]徐庆,解非线性规划和变分不等式的内点同伦方法[D].长春:吉林大学博士学位论文,2002.
[65]徐庆、林正华,组合同伦方法在无界域上的收敛性[J].应用数学学报,2004.4:624-631.
[66]Xu,Q.and Yu,B.,Solving the Karush-Kuhn-Tucker system of a nonconvex programming problem on an unbounded set[J].Nonl.Anal.,2009,2:757-763.
[67]Jongen,H.Th.,Jonker,P.and Twilt,F.,On deformation in optimization[J].Meth.Oper.Res.,1980,37:171-184.
[68]Kojima,M.,Strongly stable stationary solutions in nonlinear programs[C],in:Analysis and computation of fixed points,Robinson S.M,(eds) Academic Press,New York,93-138,1980.
[69]Kojima,M.and Hirabayashi.R.,Continuous deformations of nonlinear programs[J].Math.Prog.study,1984,21:150-198.
[70]Jongen,H.Th.,Jonker,P.and Twilt,F.,Critical sets in parametric optimization[J].Math.Prog.,1986,34:333-353.
[71]Bofill,W.G.,Properties of an interior embedding for solving nonlinear optimization problems [J].Math.Prog.,1999.86:649-659.
[72]Guddat,J.,Vazquez,F.G.,Nowack,D.and R(u|¨)ckmann,Jan-J.,A modified standard embedding with jumps in nonlinear oPtimization[J].Eur.J.Oper.Res.,2006,169:1185-1205.
[73]Guddat,J.,Vazquez,F.G.and Nowack,D.,On the role of the Mangasarian-Fromovitz constraint qualification for penalty,exact penalty and Lagrange multiplier methods[C].Mathematical Programming with Data Perturbation,A.V.Fiacco,Marccl Dekker(eds.),New York,159-183,1997.
[74]Watson,L.T.,Theory of globally convergent probability-one homotopies for nonlinear programming [J]SIAM J.Optim.,2000,11:761-780.
[75]Billups S.C.and Watson,L.T.,A probability-one homotopy algorithm for nonsmooth equations and mixed complementarity problems[J].SIAM J.Optim.,2002,12:606-626.
[76]商玉凤、于波,解非凸规划问题的动边界组合同伦方法[J].数学研究与评论.2006,26:201-204.
[77]商玉凤、于波,凸规划问题的动边界组合同伦方法及其收敛性[J].吉林大学学报(理学版),2006,44:357-361.
[78]商玉凤,求解非线性规划、均衡规划和变分不等式问题的动边界组合同伦方法[D].长春:吉林大学博士学位论文,2006.
[79]高慧,解凸规划问题的一种半内点法[D].大连:大连理工大学硕士毕业论文,2006.
[80]Yu,B.and Lin Z.,Homotopy method for a class of nonconvex Brouwer fixed point problems[J].Appl.Math.Comput.,1996,74:65-77.
[81]Lin,Z.H.,Yu.B.and Zhu,D.L.,A continuation method for solving fixed points of selfmappings in general nonconvex sets[J].Nonl.Anal.,2003,52:905-915.
[82]Su,M.L.and Liu,Z.X.,Modified homotopy methods to solve fixed points of self-mapping in a broader class of nonconvex sets[J].Appl.Numer.Math,2008,58:236-248.
[83]Lin,Z.H.,Zhu,D.L.and Sheng,Z.P.,Finding a minimal efficient solution of a convex multi-objective programming[J].JOTA,2003,118:587-600.
[84]刘庆怀、林正华,求解多目标规划最小弱有效解的同伦内点方法[J].应用数学学报,2000,2:188-195.
[85]Song,W.,Yao,G.M.,Homotopy method for a general multiobjective programming problem [J].JOTA.2008,138:139-153.
[86]Zhu,D.L.,Xu,Q.and Lin,Z.H.,A homotopy method for solving bilevel programming problem[J].Nonl.Anal.,2004,57:917-928.
[87]Xu,Q.,Yu,B.and Feng,G.C.,Homotopy methods for solving variational inequalities in unbounded sets[J].J.Glob.Optim.,2005,31:121-131.
[88]Fan,X.N.and Yu,B.,Homotopy method for solving variational inequalities with bounded box constraints[J].Nonl.Anal.,2008,68:2357-2361.
[89]Xu,Q.and Dang,C.Y.,A new homotopy method for solving non-linear complementarity problems[J].Optim.,2008,57:681-689.
[90]李佳民,求解带平衡约束数学规划问题的组合同伦内点方法[D].长春:吉林大学博士论文,2007.
[91]Liu,G.X.,A homotopy interior point method for semi-infinite programming problems[J].J.Glob.Optim.,2007,37:631-646.
[92]Sun,W.J.,Liu,Q.H.and Wang,C.L.,A homotopy method for getting a local minimum of constrained nonconvex programming[J].Nonl.Anal.,doi:10.1016/j.na.2009.03.039,2009.
[93]Chen,C.and Mangasarian,O.L.,A class of smoothing functions for nonlinear and mixed complementarity problems[J].Comput.Optim.Appl.,1996,5:97-138.
[94]Smale,S.,Algorithms for solving equations[C].Proceedings of the International Congress of Mathematicians,Berkeley,California,172-195.1986.
[95]Zang,I.,A smoothing-out technique for min-max optimization[J].Math.Prog..1980.19:61-71.
[96]Chen,B.and Harker,P.T.,A non-interior-point continuation method for linear complemen-tarity problems[J].SIAM J.Matrix Anal.Appl.,1993,14:1168-1190.
[97]Chen,X.and Qi,L.,A parameterized Newton method and a Broyden-like method for solving nonsmooth equations[J].Comput.Optim.Appl.,1994,3:157-179.
[98]Kanzow,C.,Some noninterior continuation methods for linear complementarity,problems[J].SIAM J.Matrix Anal.Appl.,1996,17:851-868.
[99]Teo,K.L.,Rehbock,V.and Jennings,L.S.,A new computational algorithm for functional inequality constrained optimization problems[J].Automatica,1993,29:789-792.
[100]Li,X.S.,An aggregate function method for nonlinear programming[J].Science In China(A),1991,3:1467-1473.
[101]李兴斯,一类不可微优化问题的有效解法[J].中国科学(A),1994,24:371-377.
[102]Kort,B.W.and Bertsekas,D.P.,A new penalty function algorithm for constrained minimization [C].Proceedings of the 1972 IEEE Conference on Decision and Control,New Orleans,Louisiana,1972.
[103]Li,X.S.and Fang,S.C.,On the entropic regularization method for solving min-max problems with applications[J].Math.Meth.Oper.Res.,1997,46:119-130.
[104]Xu,S.,Smoothing method for min-max problem[J].Comput.Optim.Appl.,2001,20:267-279.
[105]Wang,X.and Qin,X.,A maximum entropy mcthod for multiobjectivc programming[J].Math.Numer.Sinica.,1996,3:305-308.
[106]Wang,X.and Huang,Z.,Two properties of a smoothing function[J].Mathematica Applicata,2001,14:61-65.
[107]Yu.B.,Qi,L.and Liu,G.X.,A modified aggregate homotopy method for convex minimax problems[C].Proceedings of.the 5~(th) international conference on Optimization,eds.Li,D.,Hong Kong,32-38,2001.
[108]苏孟龙、赵立芹、吕显瑞,组合极大熵同伦方法求解一类非凸非线性规划问题[J].吉林大学学报(理学版),2006,44:710-714.
[109]Fan,X.N.and Yu,B.,A smoothing homotopy method for solving variational inequalities[J].Nonl.Anal.,2009,70:211-219.
[110]Polak,E.,Royset,J.O.and Womersley,R.S.,Algorithms with adaptive smoothing for finite minimax problems[J].JOTA,2003,119:459-486.
[111]Polak,E.,Womersley,R.S.and Yin,H.X.,An algorithm based on active sets and smoothing for discretized semi-infintie minimax problems[J].JOTA,2008,138:311-328.
[112]Xiao,Y.,Xiong,H.J.and Yu,B.,A truncated aggregate homotopy method for nonlinear programming problems[J],to submit.
[113]Xiao,Y.and Yu,B.,A truncated aggregate smoothing Newton method for minimax problems [J],to submit.
[114]Yu,B.and Liu,G.X.,The aggregate homotopy method for constrained sequential max-min problems[J],to submit.
[115]陈美蓉、蒋娟、曹德欣,一类min-max-min问题的区间算法[J].应用数学与计算数学学报,2006,20:55-63.
[116]Bagirov,A.M.and Rubinov,A.M.,On minimization of max-min functions[C].Applied Optimization:Optimization and Control with Applications,L.Q.Qi,K.L.Teo and X.Q.Yang(eds),3-33.2006.
[117]Bagirov,A.M.and Ugon,J.,Supervised data classification via max-min separability[C].Continuous Optimization:Currect Trends and Modern Applications(Part Ⅰ),Jeyakumar,Ⅴ.and Rubinov,A.M.(eds),175-207,2006.
[118]Watson,L.T.,Billups,S.C.and Morgan,A.P.,Algorithm 652 Hompack:A suitc of Codes for Globally Convergent Homotopy Algorithms[J]ACM Trans.Math.Softw.,1987,13:281-310.
[119]Xiong H.J.and Yu B.,An aggregate deformation homotopy method for min-max-min prob-lems with max-min constraints[J].Comput.Optim.Appl.doi:10.1007/s10589-008-9229-y,2009.
[120]Bates,S.M.,Toward a precise smoothness hypothesis in Sard's theorem[C].Proceedings of the AMS.,1993,117:279-283.
[121]Golub G.H.and Van Loan C.F.,Matix Computation(Third Edition,中文版,袁亚湘等译)[M].北京:科学出版社,2001.
[122]Polak,E.and Royset,J.O.,On the use of augmented Lagrangians in the solution of generalized semi-infinite min-max problems[J].Comput.Optim.Appl.,2005,31:173-192.
[123]Still,G.,Lectures on parametric optimzation:An introduction[R].Middle East Technical University.of Ankara,http://wwwhome.math.utwente.nl/ stillgj/lectures/list.html,2006.
[124]Hettich,R.and Kortanek,K.O.,Semi-infinite programming:theory,methods and applica-tions[J].SIAM Rev.,1993,35:380-429.
[125]Still,G.,Generalized semi-infinite programming:theory and methods[J].Eur.J.Oper.Res.,1999,119:301-313.
[126]Stein,O.and Tezel,A.,The semismooth approach for semi-infinite programming under the reduction ansatz[J].J.Glob.Optim.,2008,41:245-266.
[127]Stein,O.and Still,G.,Solving semi-infinite optimization problems with interior point techniques [J].SIAM J.Control Optim.,2003,42:769-788.
[128]Stein,O.and Still,G.,On generalized semi-infinite optimization and bilevel optimization[J].Eur.J.Oper.Res.,2002,142:444-462.
[129]Qi,L.,Wu,S.Y.and Zhou,G.L..Semismooth Newton methods for solving semi-infinite programming problems[J].J.Glob.Optim..2003,27:215-232.
[130]Pang,L.P.,Wang,M.Z.and Xia,Z.Q.,First-order optimality conditions for two classes of generalized nonsmooth semi-infinite optimization[J].Comput.Math.Appl.,doi:10.1016/j.camwa.2008.02.037.2008.
[131]Jongen,H.Th.,R(u|¨)ckmann,J.-J.and Stein,O.,Generalized semi-infinite optimization:A first order optimality condition and examples[J].Math.Prog.,1998,83:145-158.
[132]Jongen,H.Th.and Stein,O.,On generic one-parametric semi-infinite optimization[J].SIAM J.Optim.,1997,7:1103-1137.
[133]Ye,J.J.and Wu,S.Y.,First order optimality conditions for generalized semi-infinite programming problems[J].JOTA.,2008,137:419-434.
[134]Zheng,X.Y.and Yang,X.Q.,Lagrange multipliers in nonsmooth semi-infinite optimization problems[J].Math.Oper.Res.,2007,32:168-181.
[135]Polak,E.and He,L.,Rate-preserving discretization strategies for semi-infinite programming and optimal constrol[J].SIAM J.Control Optim.,1992,30:548-572.
[136]Still,G.,Discretization in semi-infinite programming:the rate of convergence[J].Math.Prog.(Ser A.),2001,91:53-69.
[137]Li,D.H..Qi,L.,Tam,J.and Wu,S.Y.,A smoothing Newton method for semi-infinite programming[J].J.Glob.Optim.,2004,30:169-194.
[138]Hettich,R.,A comparison of some numerical methods for semi-infinite programming[R].Lecture Notes in Control and Information Science.Spingre Berlin/Heidelberg,15,112-125,1979.
[139]Canovas,M.J.,Lopez,M.A.and Parra J.,Stability in the discretization of a parametric semi-infinite inequality system[J].Math.Oper.Res.,2002,27:755-774.
[140]Hettich,R.,An implementation of a discretization method for semi-infinite programming[J].Math.Prog..1986,34:354-361.
[141]Reemtsen,R.,Discretization methods for the solution of semi-infinite programming problem [J].JOTA,1991,71:85-103.
[142]Goberna,A.and Lopez,M.A.,Linear Semi-Infinite Optimization[M].John Wiley & Sons.Chichester,UK,1998.
[143]Tits,A.L.,Absil,P.A.and Woessner,W.P.,Constraint reduction for linear programs with many inequality constraints]J].SIAM J.Optim.,2006,17:119-146.
[144]Han,J.and Kamber,M.,Data Mining:Concepts and Techniques[M].San Francisco:Morgan Kaufmann,2001.
[145]Vapnik,V.,统计学习理论的本质[M].张学工(译),北京:清华大学出版社,2000.
[146]邓乃杨、田英杰,数据挖掘中的新方法-支持向量机[M].北京:科学出版社,2004.
[147]Christopher J.C.Burges,A tutorial on support vector machines for pattern recognition[J].Data Mining and Knowledge Discovery,1998,2:121-167.
[148]Sch(o|¨)lkopf,B.and Smola,A.J.,Learning with Kernels[M].MIT press,Cambridge,MA,2002.
[149]Vapnik,V.and Sterin,A.,On structural risk minimization or overall risk in a problem of pattern recognition[J].Automation and Remote Control,1977,10:1495-1593.
[150]Bennett,K.P.and Demiriz,A.,Semi-supervised support vector machines[C].Advances in Neural Information Processing Systems,M.S.Kearns.S.A.Solla,and D.A.Cohn eds.,Cambridge,MA,MIT press,12.368-374,1998.
[151]Chapelle,O.,Training a support vector machine in the primal[J].Neural Comput.,2007,19:1155-1178.
[152]Kimeldorf,G.and Wahba,G.,Some results on tchebycheffian spline functions[J].J.Math.Anal.Appl.,1971,33:82-95.
[153]Chapcllc,O..Chi,M.M.and Zien,A.,A continuation mcthod for semi-supervised SVMs[C].ACM International Conference Proceeding Series,Proceedings of the 23rd International Conference on Machine Learning,148,185-192,2006.
[154]Chapelle,O.,Sindhwani,V.and Keerthi,S.S.,Branch and Bound for semi-supervised support vector machines[C].Advances in Neural Information Processing Systems 19:Proceedings of the 2006 Conference,MIT press.Cambridge,Mass,USA,09,217-224,2007.
[155]Chapelle,O.,Sindhwani,V.and Keerthi,S.S.,Optimization Techniques for semi-supervised support vector machines[J].J.Machine Learning Res.,2008,9:203-233.
[156]Chapelle,O.and Zien,A.,Semi-supervised classification by low density separation[C].Proceedings of the tenth international workshop on artificial intelligence and statistics,57-64,2005.
[157]Astorino,A.and Fuduli,A.,Nonsmooth optimization techniques for semi-supervised classification [J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2007,29:2135-2142.
[158]Fung,G.and Mangasarian,O.L.,Semi-supervised support vector machines for unlabeled data classification[J].Optim.Meth.Soft.,2001,15:29-44.
[159]陈俐羽,一类约束序列极大极小问题的凝聚同伦方法[D].大连:大连理工大学硕士论文,2007.
[160]熊慧娟、陈俐羽、于波:一类满足弱法锥条件的约束min-max-min问题的凝聚同伦方法[J].待投.
[161]Zhang,Q.and Goldman,S.A.,EM-DD:an improved multiple-instance learning technique [C].Neural Information Processing Systems 2001,Cambridgc,MA,MIT Press,1073-1080,2002.
[2]Bandler,J.W..Liu,P.C.and Tromp,H.,A nonlinear programming approach to optimal design centering:tolerancing,and tuning[J].IEEE Trans.Circuits Systems,1976,CAS-23:155-165.
[3]Polak,E.and Sangiovauni-Vincentelli,A.,Theoretical and computational aspects of the optimal design centering,tolerancing,and tuning problem[J].IEEE Trans.Circ.and Sys.,1979,26:795-813.
[4]Gilbert,E.G.and Johnson,D.W.,Distaace functions and their application to robot path planning in the presence of obstacles[J].IEEE J.Robotics Automat.,1985,RA-1:21-30.
[5]Grossman,I.E.and Sargent,R.W.,Optimal design of chemical plants with uncertain para-meters[J].AICHE J.,1978,24:1-7.
[6]Halemane,K.P.and Grossman,I.E.,Optimal process design under uncertainty[J].AICHE J.,1983,29:425-433.
[7]Ostrivsky,G.M.,Volin,Y.M.,Barit,E.I.and Senyavin,M.M.,Flexibility.analysis and optimization of chemical plants with uncertain parameters[J].Comput.Chem.Engrg.,1994,18:755-767.
[8]Cheng,C.K.,Deng,X.,Liao,Y.Z.and Yao,S.Z.,Symbolic layout compaction under conditional design rules[J].IEEE Trans.Comput.Aided Design,1992,11:475-486.
[9]Hochbaum,D.,Complexity and algorithms for logical constraints with applications to VLSI layout,compaction and clocking,Studies in Locational Analysis[C].ISOLD Ⅵ Proceedings,159-164,1993.
[10]罗长童,低维单形进化算法及其应用[D],长春:吉林大学博士论文,2007.
[11]Mangasarian,O.L.and Edward,W.W.,Multiple instance classification via.successive linear programming[J].JOTA,2008.137:555-568.
[12]Zhu,X.J.,Semi-supervised learning literature survey[R].Tech.report 1530 Computer Science,University of Wisconsin-Madison,2005.
[13]Polak,E.and Royset,J.O.,Algorithms for finite and semi-infinite min-max-min problems using adaptive smoothing techniques[J].JOTA.,2003,119:421-457.
[14]Royset,J.O.,Kiureghian,A.D.and Polak,E.,Reliability-based optimal structural design by the decoupling approach[J].Reliab.Eng.Sys.Saf.,2001,73:213-221.
[15]Royset,J.O.,Polak,E.and Kiureghian,A.D.,Adaptive approximations and exact penalization for the solution of generalized semi-infinite min-max problems[J].SIAM J.Optim.,2003,14:1-34.
[16]Kirjner-Neto,C.and Polak,E.,On the conversion of optimization problems with max-min constraints to standard optimization problems[J].,SIAM J.Optim.,1998,8:887-915.
[17]Dietterich,T.G.,Lathrop,R.H.and Lozano,P.T.,Solving the multiple-instance problem with axisparrallel rectangles[J].Artificial Intelligence,1997.89:31-71.
[18]Zhong,Z.H.,Multi-instance Learning:A Survey[R].Technical Report(2004),http://cs.nju.edu.cn/zhouzh/zhouzh.files/publication/techrep04.pdf.
[19]Andrews,S.,Tsochantaridis I.and Hofmann,T.,Support vector machines for multipleinstancc learning[C].Adv.Neural Inform.Proc.Sys.,2003,561-568.
[20]Rockafellar,R.T.,Convex Analysis[M].Princeton University Press,Princeton,New Jersey,1970.
[21]Dcmyanov,V.F.and Vasilcv,L.V.,Nondifferentiablc Optimization[M](in Russian),Nanka,Moscow,1981.(English edition,translated by Sasagawa,T.Springer-Optimization Software,New York,1986.)
[22]Clarkc,F.H.,Optimization and Nonsmooth Analysis[M].New York,Wiley-Interscience.Inc.,1983.
[23]Shor,N.Z.,Minimization Methods for Non-differentiablc Functions[M].(translated from the Russian by Kiwiel K.C.and Ruszczynski,A.),Springer-Verlag,Berlin,New York,1985.
[24]Mordukhovich,B.S.,Maximum principle in the problem of time optimal response with nonsmooth constraints[J].J.Appl.Math.Mech.1976,40:960-969.
[25]Mordukhovich,B.S.,Metric approximations and necessary optimality conditions for general classeds of nonsmooth extremum problems[J].Soviet Math.Doklady,1980,22:526-530.
[26]Rockafellar,R.T.and Wets,R.J.B.,Variational Analysis[M].Springer Verlag,1997.
[27]Mordukhovich,B.S.,Variational Analysis and Generalized Differentiation,(I:Basic theory and Ⅱ:Applications)[M].Springer Verlag,Berlin,2006.
[28]M(a|¨)kel(a|¨),M.M.and Neittaanm(a|¨)ki,P.,Nonsmooth Optimization:Analysis and Algorithms with Applications to Optimal Control[M].World Scientific Publishing Co.Pte.Ltd.,1992.
[29]Polak,E.,Optimization,Algorithms and Consistent Approximations[M].Springer-Verlag,New York,1997.
[30]Hiriart-Urruty,J.B.and Lemarechal,C.,Convex Analysis and Minimization Algorithms Ⅰ[M].Springer-Verlag,Berlin,1993.
[31]Demyanov,V.F.and Rubinov,A.M.,Constructive Nonsmooth Analysis[M].Frankfurt am Main Berlin Bern,Wien,1995.
[32]Clarke,F.H.,Ledyaev,Yu.S..Stern,R.J.and Wolenski,P.R.,Nonsmooth Analysis and Control Theory[M].New York,Springer-Verlag,1998.
[33]Bonnans,J.F.and Shapiro,A.,Perturbation Analysis of Optimization Problems[M],New York,Springer-verlag,2000.
[34]Bertsckas.D.P.,Nedic,A.and Ozdaglar.A.E.,Convex Analysis and Optimization[M].北京:清华大学出版社,2006.
[35]Dutta,J.,Generalized derivatives and nonsmooth optimization.a finite dimensional tour[J].TOP,2005,13:185-314.
[36]Scholtes,S..Nonconvex structures in nonlinear programming[J].Oper.Res.,2004,52:368-383.
[37]Li.S.J.,Yang,X.Q.and Teo,K.L.,On the conversion of optimization problems with max-min constraints to standard optimization problems[J].JOTA,2001,109:691-698.
[38]Kellogg R.B.,Li,T.Y.and Yorke J.A.,A constructive proof of the Brower fixed-point theorem and computational results[J].SIAM J.Numer.Anal.,1976,13:473-483.
[39]Smale,S.,A convergent process of price adjustment and global Newton method,J.Math.Econ.,3(1976),1-14.
[40]Chow,S.N.,Mallet-Paret,J.and Yorke,J.Z.,Finding zeros of maps:Homotopy methods that are constructive with probability one[J].Math.Comput.,1978,32:887-899.
[41]Garcia,C.B.and Zangwill,W.I.,Pathways to Solutions,Fixed Points and Equilibria[M].New Jersey,Prentice-Hall,1981.
[42]Allgower,E.L.and Georg,K.,Numerical Continuation Methods:An Introduction[M].Berlin.New York,Springer-verlag,1990.
[43]王则柯、高堂安,同伦方法引论[M].重庆:重庆出版社,1989.
[44]Gill,P.E.,Murray,W.,Saunders,M.A.,Tomlin,J.A.and Wright,M.H.,On the projected Newton barrier methods for linear programming and an equivalence to Karmarkar's projective method[J].Math.Prog.,1986,36:183-209.
[45]Megiddo,N.,Pathways to the optimal set in linear programming[C].Progress in Mathematical Programming,Interior Point and Related Methods,Megiddo,N.(eds).Springer,New York.131-158.1988.
[46]Kojima,M.,Mizuno,S.and Yoshise:A.,A primal-dual interior point algorithm for linear pro-grammming[C].In Progress in Mathematical Programming,Interior Point and Related Methods (N.Megiddo,ed.),N.Y.,Springer-Verlag,29-47,1988.
[47]Wright,S.J.and Nocedal J.,Numerical Optimization(second edition)[M].Springer-Verlag,New York,Berlin,2000.
[48]袁亚湘、孙文瑜,最优化理论与方法[M].北京:科学出版社:1997.
[49]Karmarkar,N.,A new polynomial-time algorithm for linear programming[J].Combinatorica,1984,14:373-395.
[50]Wright,S.J.,Primal-Dual Interior Point Methods[M].SIAM,Philadelphia,1997.
[51]Mehrotra,S.,On the implementation of a primal-dual interior point method[J].SIAM J.Optim.,1992,2:575-601.
[52]Mizuno,S.,Todd,M.J.and Ye,Y.,On adaptive primal-dual interior-point algorithms for linear programming[J].Math.Oper.Res.;1993,18:964-981.
[53]Shanno,D.F.and Vanderbei,R.J.,Interior-point methods for nonconvex nonlinear programming:orderings and higher-order methods[J].Math.Prog.,2000,87:303-316.
[54]刘国新,求解序列极大极小问题、互补问题和变分不等式的凝聚同伦方法[D].长春:吉林大学博士学位论文,2003.
[55]Alizadeh,F.,Haeberly,J.P.A.and Overton M.L.,Primal-dual interior-point methods for semidefininte programming:convergence rates,stability and numerical results[J].SIAM J.Optim.,1998,8:746-768.
[56]Feng,G.C.and Yu,B.,Combined homotopy interior point method for nonlinear programming problems[J].Lecture Notes in Numer.Anal.,1995,14:9-16.
[57]Feng,G.C.,Lin,Z.H.and Yu,.B..Existence of an interior pathway to a Karush-Kuhn-Tucker point of a nonconvex programming problem[J].Nonlinear Anal.,1998,32:761-768.
[58]Lin,Z.H.,Li.Y.and Yu,B.,A combined homotopy interior point method for general nonlinear programming problems[J].Appl.Math.Comput.,1996.80:209-224.
[59]Lin Z.H.,Yu.B.and Feng,G.C.;A combined homotopy interior point method for convex programming problem[J[.Appl.Math.Comput.,1997,84:193-211.
[60]Yu,B.,Feng,G.C.and Zhang,S.L.,The aggregate constraint homotopy method for nonconvex nonlinear programming[J[.Nonl.Anal.,2001,45:839-847.
[61]Liu,Q.H.,Yu,B.and Feng,G.C.,An interior point path-following method for nonconvex programming with quasi normal eone condition[J].数学进展,2000,29:281-282.
[62]Yu,B.,Liu Q.H.and Feng,G.C.,A combined homotopy interior point method for nonconvex programming with pseudo cone condition[J].J.Northeast.Math.,2000,16:383-386.
[63]Yu,B.,Xu,Q.and Feng,G.C.,On the complexity of a combined homotopy interior point method for convex programming[J].J.Comput.Appl.Math.,2007,200:32-46.
[64]徐庆,解非线性规划和变分不等式的内点同伦方法[D].长春:吉林大学博士学位论文,2002.
[65]徐庆、林正华,组合同伦方法在无界域上的收敛性[J].应用数学学报,2004.4:624-631.
[66]Xu,Q.and Yu,B.,Solving the Karush-Kuhn-Tucker system of a nonconvex programming problem on an unbounded set[J].Nonl.Anal.,2009,2:757-763.
[67]Jongen,H.Th.,Jonker,P.and Twilt,F.,On deformation in optimization[J].Meth.Oper.Res.,1980,37:171-184.
[68]Kojima,M.,Strongly stable stationary solutions in nonlinear programs[C],in:Analysis and computation of fixed points,Robinson S.M,(eds) Academic Press,New York,93-138,1980.
[69]Kojima,M.and Hirabayashi.R.,Continuous deformations of nonlinear programs[J].Math.Prog.study,1984,21:150-198.
[70]Jongen,H.Th.,Jonker,P.and Twilt,F.,Critical sets in parametric optimization[J].Math.Prog.,1986,34:333-353.
[71]Bofill,W.G.,Properties of an interior embedding for solving nonlinear optimization problems [J].Math.Prog.,1999.86:649-659.
[72]Guddat,J.,Vazquez,F.G.,Nowack,D.and R(u|¨)ckmann,Jan-J.,A modified standard embedding with jumps in nonlinear oPtimization[J].Eur.J.Oper.Res.,2006,169:1185-1205.
[73]Guddat,J.,Vazquez,F.G.and Nowack,D.,On the role of the Mangasarian-Fromovitz constraint qualification for penalty,exact penalty and Lagrange multiplier methods[C].Mathematical Programming with Data Perturbation,A.V.Fiacco,Marccl Dekker(eds.),New York,159-183,1997.
[74]Watson,L.T.,Theory of globally convergent probability-one homotopies for nonlinear programming [J]SIAM J.Optim.,2000,11:761-780.
[75]Billups S.C.and Watson,L.T.,A probability-one homotopy algorithm for nonsmooth equations and mixed complementarity problems[J].SIAM J.Optim.,2002,12:606-626.
[76]商玉凤、于波,解非凸规划问题的动边界组合同伦方法[J].数学研究与评论.2006,26:201-204.
[77]商玉凤、于波,凸规划问题的动边界组合同伦方法及其收敛性[J].吉林大学学报(理学版),2006,44:357-361.
[78]商玉凤,求解非线性规划、均衡规划和变分不等式问题的动边界组合同伦方法[D].长春:吉林大学博士学位论文,2006.
[79]高慧,解凸规划问题的一种半内点法[D].大连:大连理工大学硕士毕业论文,2006.
[80]Yu,B.and Lin Z.,Homotopy method for a class of nonconvex Brouwer fixed point problems[J].Appl.Math.Comput.,1996,74:65-77.
[81]Lin,Z.H.,Yu.B.and Zhu,D.L.,A continuation method for solving fixed points of selfmappings in general nonconvex sets[J].Nonl.Anal.,2003,52:905-915.
[82]Su,M.L.and Liu,Z.X.,Modified homotopy methods to solve fixed points of self-mapping in a broader class of nonconvex sets[J].Appl.Numer.Math,2008,58:236-248.
[83]Lin,Z.H.,Zhu,D.L.and Sheng,Z.P.,Finding a minimal efficient solution of a convex multi-objective programming[J].JOTA,2003,118:587-600.
[84]刘庆怀、林正华,求解多目标规划最小弱有效解的同伦内点方法[J].应用数学学报,2000,2:188-195.
[85]Song,W.,Yao,G.M.,Homotopy method for a general multiobjective programming problem [J].JOTA.2008,138:139-153.
[86]Zhu,D.L.,Xu,Q.and Lin,Z.H.,A homotopy method for solving bilevel programming problem[J].Nonl.Anal.,2004,57:917-928.
[87]Xu,Q.,Yu,B.and Feng,G.C.,Homotopy methods for solving variational inequalities in unbounded sets[J].J.Glob.Optim.,2005,31:121-131.
[88]Fan,X.N.and Yu,B.,Homotopy method for solving variational inequalities with bounded box constraints[J].Nonl.Anal.,2008,68:2357-2361.
[89]Xu,Q.and Dang,C.Y.,A new homotopy method for solving non-linear complementarity problems[J].Optim.,2008,57:681-689.
[90]李佳民,求解带平衡约束数学规划问题的组合同伦内点方法[D].长春:吉林大学博士论文,2007.
[91]Liu,G.X.,A homotopy interior point method for semi-infinite programming problems[J].J.Glob.Optim.,2007,37:631-646.
[92]Sun,W.J.,Liu,Q.H.and Wang,C.L.,A homotopy method for getting a local minimum of constrained nonconvex programming[J].Nonl.Anal.,doi:10.1016/j.na.2009.03.039,2009.
[93]Chen,C.and Mangasarian,O.L.,A class of smoothing functions for nonlinear and mixed complementarity problems[J].Comput.Optim.Appl.,1996,5:97-138.
[94]Smale,S.,Algorithms for solving equations[C].Proceedings of the International Congress of Mathematicians,Berkeley,California,172-195.1986.
[95]Zang,I.,A smoothing-out technique for min-max optimization[J].Math.Prog..1980.19:61-71.
[96]Chen,B.and Harker,P.T.,A non-interior-point continuation method for linear complemen-tarity problems[J].SIAM J.Matrix Anal.Appl.,1993,14:1168-1190.
[97]Chen,X.and Qi,L.,A parameterized Newton method and a Broyden-like method for solving nonsmooth equations[J].Comput.Optim.Appl.,1994,3:157-179.
[98]Kanzow,C.,Some noninterior continuation methods for linear complementarity,problems[J].SIAM J.Matrix Anal.Appl.,1996,17:851-868.
[99]Teo,K.L.,Rehbock,V.and Jennings,L.S.,A new computational algorithm for functional inequality constrained optimization problems[J].Automatica,1993,29:789-792.
[100]Li,X.S.,An aggregate function method for nonlinear programming[J].Science In China(A),1991,3:1467-1473.
[101]李兴斯,一类不可微优化问题的有效解法[J].中国科学(A),1994,24:371-377.
[102]Kort,B.W.and Bertsekas,D.P.,A new penalty function algorithm for constrained minimization [C].Proceedings of the 1972 IEEE Conference on Decision and Control,New Orleans,Louisiana,1972.
[103]Li,X.S.and Fang,S.C.,On the entropic regularization method for solving min-max problems with applications[J].Math.Meth.Oper.Res.,1997,46:119-130.
[104]Xu,S.,Smoothing method for min-max problem[J].Comput.Optim.Appl.,2001,20:267-279.
[105]Wang,X.and Qin,X.,A maximum entropy mcthod for multiobjectivc programming[J].Math.Numer.Sinica.,1996,3:305-308.
[106]Wang,X.and Huang,Z.,Two properties of a smoothing function[J].Mathematica Applicata,2001,14:61-65.
[107]Yu.B.,Qi,L.and Liu,G.X.,A modified aggregate homotopy method for convex minimax problems[C].Proceedings of.the 5~(th) international conference on Optimization,eds.Li,D.,Hong Kong,32-38,2001.
[108]苏孟龙、赵立芹、吕显瑞,组合极大熵同伦方法求解一类非凸非线性规划问题[J].吉林大学学报(理学版),2006,44:710-714.
[109]Fan,X.N.and Yu,B.,A smoothing homotopy method for solving variational inequalities[J].Nonl.Anal.,2009,70:211-219.
[110]Polak,E.,Royset,J.O.and Womersley,R.S.,Algorithms with adaptive smoothing for finite minimax problems[J].JOTA,2003,119:459-486.
[111]Polak,E.,Womersley,R.S.and Yin,H.X.,An algorithm based on active sets and smoothing for discretized semi-infintie minimax problems[J].JOTA,2008,138:311-328.
[112]Xiao,Y.,Xiong,H.J.and Yu,B.,A truncated aggregate homotopy method for nonlinear programming problems[J],to submit.
[113]Xiao,Y.and Yu,B.,A truncated aggregate smoothing Newton method for minimax problems [J],to submit.
[114]Yu,B.and Liu,G.X.,The aggregate homotopy method for constrained sequential max-min problems[J],to submit.
[115]陈美蓉、蒋娟、曹德欣,一类min-max-min问题的区间算法[J].应用数学与计算数学学报,2006,20:55-63.
[116]Bagirov,A.M.and Rubinov,A.M.,On minimization of max-min functions[C].Applied Optimization:Optimization and Control with Applications,L.Q.Qi,K.L.Teo and X.Q.Yang(eds),3-33.2006.
[117]Bagirov,A.M.and Ugon,J.,Supervised data classification via max-min separability[C].Continuous Optimization:Currect Trends and Modern Applications(Part Ⅰ),Jeyakumar,Ⅴ.and Rubinov,A.M.(eds),175-207,2006.
[118]Watson,L.T.,Billups,S.C.and Morgan,A.P.,Algorithm 652 Hompack:A suitc of Codes for Globally Convergent Homotopy Algorithms[J]ACM Trans.Math.Softw.,1987,13:281-310.
[119]Xiong H.J.and Yu B.,An aggregate deformation homotopy method for min-max-min prob-lems with max-min constraints[J].Comput.Optim.Appl.doi:10.1007/s10589-008-9229-y,2009.
[120]Bates,S.M.,Toward a precise smoothness hypothesis in Sard's theorem[C].Proceedings of the AMS.,1993,117:279-283.
[121]Golub G.H.and Van Loan C.F.,Matix Computation(Third Edition,中文版,袁亚湘等译)[M].北京:科学出版社,2001.
[122]Polak,E.and Royset,J.O.,On the use of augmented Lagrangians in the solution of generalized semi-infinite min-max problems[J].Comput.Optim.Appl.,2005,31:173-192.
[123]Still,G.,Lectures on parametric optimzation:An introduction[R].Middle East Technical University.of Ankara,http://wwwhome.math.utwente.nl/ stillgj/lectures/list.html,2006.
[124]Hettich,R.and Kortanek,K.O.,Semi-infinite programming:theory,methods and applica-tions[J].SIAM Rev.,1993,35:380-429.
[125]Still,G.,Generalized semi-infinite programming:theory and methods[J].Eur.J.Oper.Res.,1999,119:301-313.
[126]Stein,O.and Tezel,A.,The semismooth approach for semi-infinite programming under the reduction ansatz[J].J.Glob.Optim.,2008,41:245-266.
[127]Stein,O.and Still,G.,Solving semi-infinite optimization problems with interior point techniques [J].SIAM J.Control Optim.,2003,42:769-788.
[128]Stein,O.and Still,G.,On generalized semi-infinite optimization and bilevel optimization[J].Eur.J.Oper.Res.,2002,142:444-462.
[129]Qi,L.,Wu,S.Y.and Zhou,G.L..Semismooth Newton methods for solving semi-infinite programming problems[J].J.Glob.Optim..2003,27:215-232.
[130]Pang,L.P.,Wang,M.Z.and Xia,Z.Q.,First-order optimality conditions for two classes of generalized nonsmooth semi-infinite optimization[J].Comput.Math.Appl.,doi:10.1016/j.camwa.2008.02.037.2008.
[131]Jongen,H.Th.,R(u|¨)ckmann,J.-J.and Stein,O.,Generalized semi-infinite optimization:A first order optimality condition and examples[J].Math.Prog.,1998,83:145-158.
[132]Jongen,H.Th.and Stein,O.,On generic one-parametric semi-infinite optimization[J].SIAM J.Optim.,1997,7:1103-1137.
[133]Ye,J.J.and Wu,S.Y.,First order optimality conditions for generalized semi-infinite programming problems[J].JOTA.,2008,137:419-434.
[134]Zheng,X.Y.and Yang,X.Q.,Lagrange multipliers in nonsmooth semi-infinite optimization problems[J].Math.Oper.Res.,2007,32:168-181.
[135]Polak,E.and He,L.,Rate-preserving discretization strategies for semi-infinite programming and optimal constrol[J].SIAM J.Control Optim.,1992,30:548-572.
[136]Still,G.,Discretization in semi-infinite programming:the rate of convergence[J].Math.Prog.(Ser A.),2001,91:53-69.
[137]Li,D.H..Qi,L.,Tam,J.and Wu,S.Y.,A smoothing Newton method for semi-infinite programming[J].J.Glob.Optim.,2004,30:169-194.
[138]Hettich,R.,A comparison of some numerical methods for semi-infinite programming[R].Lecture Notes in Control and Information Science.Spingre Berlin/Heidelberg,15,112-125,1979.
[139]Canovas,M.J.,Lopez,M.A.and Parra J.,Stability in the discretization of a parametric semi-infinite inequality system[J].Math.Oper.Res.,2002,27:755-774.
[140]Hettich,R.,An implementation of a discretization method for semi-infinite programming[J].Math.Prog..1986,34:354-361.
[141]Reemtsen,R.,Discretization methods for the solution of semi-infinite programming problem [J].JOTA,1991,71:85-103.
[142]Goberna,A.and Lopez,M.A.,Linear Semi-Infinite Optimization[M].John Wiley & Sons.Chichester,UK,1998.
[143]Tits,A.L.,Absil,P.A.and Woessner,W.P.,Constraint reduction for linear programs with many inequality constraints]J].SIAM J.Optim.,2006,17:119-146.
[144]Han,J.and Kamber,M.,Data Mining:Concepts and Techniques[M].San Francisco:Morgan Kaufmann,2001.
[145]Vapnik,V.,统计学习理论的本质[M].张学工(译),北京:清华大学出版社,2000.
[146]邓乃杨、田英杰,数据挖掘中的新方法-支持向量机[M].北京:科学出版社,2004.
[147]Christopher J.C.Burges,A tutorial on support vector machines for pattern recognition[J].Data Mining and Knowledge Discovery,1998,2:121-167.
[148]Sch(o|¨)lkopf,B.and Smola,A.J.,Learning with Kernels[M].MIT press,Cambridge,MA,2002.
[149]Vapnik,V.and Sterin,A.,On structural risk minimization or overall risk in a problem of pattern recognition[J].Automation and Remote Control,1977,10:1495-1593.
[150]Bennett,K.P.and Demiriz,A.,Semi-supervised support vector machines[C].Advances in Neural Information Processing Systems,M.S.Kearns.S.A.Solla,and D.A.Cohn eds.,Cambridge,MA,MIT press,12.368-374,1998.
[151]Chapelle,O.,Training a support vector machine in the primal[J].Neural Comput.,2007,19:1155-1178.
[152]Kimeldorf,G.and Wahba,G.,Some results on tchebycheffian spline functions[J].J.Math.Anal.Appl.,1971,33:82-95.
[153]Chapcllc,O..Chi,M.M.and Zien,A.,A continuation mcthod for semi-supervised SVMs[C].ACM International Conference Proceeding Series,Proceedings of the 23rd International Conference on Machine Learning,148,185-192,2006.
[154]Chapelle,O.,Sindhwani,V.and Keerthi,S.S.,Branch and Bound for semi-supervised support vector machines[C].Advances in Neural Information Processing Systems 19:Proceedings of the 2006 Conference,MIT press.Cambridge,Mass,USA,09,217-224,2007.
[155]Chapelle,O.,Sindhwani,V.and Keerthi,S.S.,Optimization Techniques for semi-supervised support vector machines[J].J.Machine Learning Res.,2008,9:203-233.
[156]Chapelle,O.and Zien,A.,Semi-supervised classification by low density separation[C].Proceedings of the tenth international workshop on artificial intelligence and statistics,57-64,2005.
[157]Astorino,A.and Fuduli,A.,Nonsmooth optimization techniques for semi-supervised classification [J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2007,29:2135-2142.
[158]Fung,G.and Mangasarian,O.L.,Semi-supervised support vector machines for unlabeled data classification[J].Optim.Meth.Soft.,2001,15:29-44.
[159]陈俐羽,一类约束序列极大极小问题的凝聚同伦方法[D].大连:大连理工大学硕士论文,2007.
[160]熊慧娟、陈俐羽、于波:一类满足弱法锥条件的约束min-max-min问题的凝聚同伦方法[J].待投.
[161]Zhang,Q.and Goldman,S.A.,EM-DD:an improved multiple-instance learning technique [C].Neural Information Processing Systems 2001,Cambridgc,MA,MIT Press,1073-1080,2002.