Newton-kkt interior-point methods for indefinite q

ComputOptimApplic(2007)36:5–41DOI10.1007/s10589-006-8717-1Newton-KKTinterior-pointmethodsforindefinitequadraticprogramming∗P.-A.Absil·Andr´eL.TitsReceived:29September2004/Revised:5August2005/Publishedonline:14July2006CSpringerScience+BusinessMedia,LLC2006AbstractTwointerior-pointalgorithmsareproposedandanalyzed,forthe(local)solutionof(possibly)indefinitequadraticprogrammingproblems.TheyareoftheNewton-KKTvarietyinthat(muchlikeinthecaseofprimal-dualalgorithmsforlinearprogramming)searchdirectionsforthe“primal”variablesandtheKarush-Kuhn-Tucker(KKT)multiplierestimatesarecomponentsoftheNewton(orquasi-Newton)directionforthesolutionoftheequalitiesinthefirst-orderKKTconditionsofoptimalityoraperturbedversionoftheseconditions.Ouralgorithmsareadaptedfrompreviouslyproposedalgorithmsforconvexquadraticprogrammingandgeneralnonlinearprogramming.First,inspiredbyrecentworkbyP.Tsengbasedona“primal”affine-scalingalgorithm(`alaDikin)[J.ofGlobalOptimization,30(2004),no.2,285–300],weconsiderasimpleNewton-KKTaffine-scalingalgorithm.Then,a“barrier”versionofthesamealgorithmisconsidered,whichreducestotheaffine-scalingversionwhenthebarrierparameterissettozeroateveryiteration,ratherthantotheprescribedvalue.Globalandlocalquadraticconvergenceareprovedundernondegeneracyassumptionsforbothalgorithms.Numericalresultsonrandomlygeneratedproblemssuggestthattheproposedalgorithmsmaybeofgreatpracticalinterest.∗TheworkofthefirstauthorwassupportedinpartbytheSchoolofComputationalScienceofFloridaStateUniversitythroughapostdoctoralfellowship.PartofthisworkwasdonewhilethisauthorwasaResearchFe-llowwiththeBelgianNationalFundforScientificResearch(AspirantduF.N.R.S.)attheUniversityofLi`ege.TheworkofthesecondauthorwassupportedinpartbytheNationalScienceFoundationunderGrantsDMI-9813057andDMI-0422931andbytheUSDepartmentofEnergyunderGrantDEFG0204ER25655.Anyop-inions,findings,andconclusionsorrecommendationsexpressedinthispaperarethoseoftheauthorsanddonotnecessarilyreflecttheviewsoftheNationalScienceFoundationorthoseoftheUSDepartmentofEnergy.P.-A.AbsilD´epartementd’ing´enieriemath´ematique,Universit´ecatholiquedeLouvain,1348Louvain-la-Neuve,Belgiumhomepage:˜absilA.L.Tits()DepartmentofElectricalandComputerEngineeringandInstituteforSystemsResearch,UniversityofMaryland,CollegePark,MD20742,USAe-mail:[e-mail],A.L.TitsKeywordsInterior-pointalgorithms·Primal-dualalgorithms·Indefinitequadraticprogramming·Newton-KKT1.IntroductionConsiderthequadraticprogrammingproblem(P)minimize12x,Hx+c,xs.t.Ax≤b,x∈Rn,withA∈Rm×n,b∈Rm,c∈Rn,andwithH∈Rn×nsymmetric.Inthepasttwodecades,muchresearchactivityhasbeendevotedtodevelopingandanalyzinginterior-pointmethodsforsolvingsuchproblemsintheconvexcase,i.e.,whenHispositivesemidefinite.TheInteriorEllipsoidmethodofYeandTse[37]isaprimalaffine-scalingalgorithmforconvexquadraticprogramminginstandardequalityform.Theprimalaffinescalingideaconsistsinminimizingthecostoverasequenceofellipsoidswhoseshapedependsonthedistancefromthecurrentinteriorfeasiblepointtothefacesofthefeasiblepolyhedron.Dikin[9]developedthemethodforlinearproblemsandproveditsglobalconvergenceunderaprimalnondegeneracyassumption.Thismethodmayalternativelybeviewedasaninteriortrust-regionmethod[7]wheretheDikinellipsoidisusedasthetrustregion.YeandTse[37]showedthatifthesequencegeneratedbytheirInteriorEllipsoidalgorithmconverges,thenthelimitpointisanoptimalsolution.Inthestrictlyconvexcase,thealgorithmgeneratessequencesthatconvergetotheoptimalsolution[32,33].In[37],amodifiedversionisalsoproposed,derivedasanextensionofKarmarkar’slinearprogrammingalgorithm,andcomplexityboundsareobtained.MonteiroandTsuchiya[21]provedconvergenceofthealgorithmwithoutanynondegeneracyassumption.(Wereferto[21]forfurtherreferencesontheconvexquadraticprogrammingproblem.)MonteiroandAdler[19]proposedabarrier-basedpath-followingalgorithmandobtainedcomplexitybounds.Interior-pointmethodshavealsobeenproposedforthecomputationoflocalsolutionstogeneral,nonlinearprogrammingproblems(see,e.g.,[14,17,18,23,11,12,15,31,29,4,24,6,26,36,16],andtherecentsurvey[13]),andtheseofcoursecanbeusedfortackling(P).However,onlylimitedattentionhasbeendevotedtoexploitingthequadraticprogrammingstructureof(P)inthenonconvexcase.NotableexceptionsincludetheworkofYeandofTseng[33,34,25,27]onDikin’salgorithm[9],thatofBonnansandBouhtou[2],andthatofColemanandLiu[8],aswediscussnext.Interior-pointmethodsforthegeneral(indefinite)quadraticprogrammingproblemwerefirstconsideredin[33],wherenumericalexperimentswiththeInteriorEllipsoidmethodintheindefinitecasewerementioned.TheInteriorEllipsoidmethodwasformallyextendedtoindefinitequadraticprogrammingin[34].Inthatpaper,undersomenondegeneracyassump-tions,thesequencesproducedbythatalgorithmareshowntoconvergetoapointsatisfyingthefirstandsecondordernecessaryconditionsofoptimality.Thisalgorithmwasfurtheran-alyzedbyBonnansandBouhtou[2],whoproposedanextendedalgorithmallowinginexactsolutionofthetrust-regionsubproblemsandthepossibilityofalinesearchinthedirectionobtainedfromthesubproblem.Undernondeg