[3]-F.H.-Clarke--Optimization-and-Nonsmooth-Analys

LINEARPROGRAMSANDIMPLICITFUNCTIONSKatrinHaukandFlorianJarreReferences[1]N.AmentaandG.Ziegler,Shadowsandslicesofpolytopes,inProceedingsoftheTwelfthAnnualSymposiumonComputationalGeometry,ACMPress,Philadelphia,P.A,1996,pp.10–19.[2]D.P.Bertsekas,NonlinearProgramming(2ndedition),AthenaScientific,Nashua,N.H,1999.[3]F.H.Clarke,OptimizationandNonsmoothAnalysis(2ndedition),ClassicsinAppliedMathematics5,SIAM,Philadelphia,P.A,1990.[4]A.R.Conn,N.I.M.Gould,A.SartenaerandP.L.Toint,Convergencepropertiesofanaugmentedlagrangianalgorithmforoptimizationwithacombinationofgeneralequalityandnonlinearconstraints,SIAMJ.Optim.6(1996)674–703.[5]A.R.Conn,N.I.M.GouldandP.L.Toint,AgloballyconvergentaugmentedLagrangianalgorithmforoptimizationwithgeneralconstraintsandsimplebounds,SIAMJ.Nu-mericalAnal.28(1991)545–572.[6]M.C.Ferris,T.S.MunsonandD.Ralph,Ahomotopymethodformixedcomplemen-tarityproblemsbasedonthePATHsolver,inNumericalAnalysis1999,ResearchNotesinMathematics,D.F.GriffithsandG.A.Watson(eds.),ChapmanandHall,London,2000,pp.143–167.[7]M.P.FriedlanderandM.A.Saunders,AgloballyconvergentlinearlyconstrainedLa-grangianmethodfornonlinearoptimization,SIAMJ.Optim.(2006)toappear.[8]G.H.GolubandC.F.VanLoan,MatrixComputations,2ndEdn.,TheJohnHopkinsUniversityPress,Baltimore,M.D,1989.[9]M.R.Hestenes,Multiplierandgradientmethods,J.Optim.TheoryAppl.4(1969)303–320.[10]J.B.Hiriart-UrrutyandC.Lemarechal,ConvexAnalysisandMinimizationAlgorithms,Volume1,Springer,Berlin,1996.[11]F.JarreandJ.Stoer,MathematischeOptimierung,Springer,Berlin,2004.[12]N.Karmarkar,Anewpolynomial-timealgorithmforlinearprogramming,Combinator-ica4(1984)373–395.[13]L.G.Khachiyan,Apolynomialalgorithminlinearprogramming,SovietMathematicsDoklady20(1979)191–194.[14]M.Kojima,N.MegiddoandS.Mizuno,Theoreticalconvergenceoflarge-stepprimald-ualinteriorpointalgorithmsforlinearprogramming,Math.Program.59(1992)1–21.[15]N.Megiddo,Linearprogramminginlineartimewhenthedimensionisfixed,J.ACM31(1984)114–127.[16]R.MonteiroandT.Tsuchiya,AvariantoftheVavasis-Yelayered-stepinterior-pointalgorithmforlinearprogramming,SIAMJ.Optim.13(4)(2003)1054–1079.[17]T.Pietrzykowski,Thepotentialmethodforconditionalmaximainthelocallycompactmetricspaces,Numer.Math.14(4)(1970)325–329.[18]M.J.D.Powell,Amethodfornonlinearconstraints,inminimizationproblems,R.Fletcher(ed),Optimization,AcademicPress,NewYork,1969,pp.283–298.[19]F.Rendl,SolvingSemidefiniteProgramsusingBundleMethodsandtheAugmentedLagrangianApproach,PlenarytalkatVeszpremOptimizationConference:AdvancedAlgorithms(VOCAL),Veszprem,Hungary,December13-15,2004.[20]R.T.Rockafellar,ConvexAnalysis,Princetonmathematicalseries28,PrincetonUni-versityPress,Princeton,N.J,1970.[21]E.Tardos,Astronglypolynomialalgorithmtosolvecombinatoriallinearprograms,Oper.Res.34(2)(1986)250–256.[22]S.VavasisandY.Ye,AprimaldualacceleratedinteriorpointmethodwhoserunningtimedependsonlyonA,Math.Program.74(1996)79–120.[23]Y.Ye,M.J.ToddandS.Mizuno,AnO(#nL)-iterationhomogeneousandself-duallinearprogrammingalgorithm,Math.Oper.Res.19(1994)53–67.Manuscriptreceived21December2005revised13September2006acceptedforpublication26September2006KatrinHaukInstitutf¨urMathematik,Universit¨atD¨usseldorf,Universit¨atsstr.1,D–40225D¨usseldorf,FederalRepublicofGermanyE-mailaddress:[e-mail]¨urMathematik,Universit¨atD¨usseldorf,Universit¨atsstr.1,D–40225D¨usseldorf,FederalRepublicofGermanyE-mailaddress:[e-mail]°2007YokohamaPublishers