LOQO User’s Manual - Version 4.05

LOQOUser’sManual–Version4.05RobertJ.VanderbeiOperationsResearchandFinancialEngineeringTechnicalReportNo.ORFE-99-??October12,2000PrincetonUniversitySchoolofEngineeringandAppliedScienceDepartmentofOperationsResearchandFinancialEngineeringPrinceton,NewJersey08544LOQOUSER’SMANUAL–VERSION4.05ROBERTJ.VANDERBEIABSTRACT.LOQOisasystemforsolvingsmoothconstrainedoptimizationproblems.Theproblemscanbelinearornon-linear,convexornonconvex,constrainedorunconstrained.Theonlyrealrestrictionisthatthefunctionsdefiningtheproblembesmooth(atthepointsevaluatedbythealgorithm).Iftheproblemisconvex,LOQOfindsagloballyoptimalsolution.Otherwise,itfindsalocallyoptimalsolutionneartoagivenstartingpoint.Thismanualdescribes(1)howtoinstallLOQOonyourhardware,(2)howtouseAMPLtogetherwithLOQOtosolvegeneralconvexoptimizationproblems,(3)howtousethesubroutinelibrarytoformulateandsolveconvexoptimizationproblems,and(4)howtoformulateandsolvelinearandquadraticprogramsinMPSformat.1.INTRODUCTIONLOQOisasystemforsolvingsmoothconstrainedoptimizationproblemsinthefollowingform:minimizef(x)subjecttoa≤h(x)≤bl≤x≤u.Here,thevariablextakesvaluesinRn,landuaregivenn-vectors,fisareal-valuedfunctiondefinedon{x:l≤x≤u},hisamapfromthissetintoRm,andaandbaregivenm-vectors.Someorallcomponentsofaandlcanbe−∞,whereassomeorallcomponentsofbanducanbe∞.ThefunctionsfandhmustbetwicedifferentiableatthepointsatwhichtheyareevaluatedbyLOQO.Theproblemisconvexiffisconvex,eachcomponentfunctionhiisconvex,andai=−∞wheneverhiisnotlinear.Iftheproblemisconvex,thenLOQOfindsagloballyoptimalsolution.Otherwise,itfindsalocallyoptimalsolutionneartoagivenstartingpoint.LOQOisbasedonaninfeasible,primal-dual,interior-pointmethodappliedtoasequenceofquadraticapproxima-tionstothegivenproblem.See[6],[7],and[5]foradetaileddiscussionofthealgorithmimplementedinLOQO.TherearethreewaystoconveyproblemstoLOQO.(1)Forgeneraloptimizationproblems,theprefereduserinterfaceisviatheAMPL[2]modelinglanguage.(2)ForthosewithoutaccesstoAMPL,thereisasubroutinelibrarythatonecanlinktotheirownprograms.ThisisapainfulwaytouseLOQO,butforsomeitmaybetheonlyoption.(3)Iftheproblemisalinearprogram,onecanuseindustrystandardMPSfilesasinput.Iftheproblemisalinearlyconstrainedquadraticprogram,onecanuseasimpleextensionoftheMPSformat.MPSfilescanbecreatedeitherwithaspecificallycreatedgeneratorprogramorviaanyofthepopularoptimizationmodelinglanguagessuchasAMPLorGAMS[1].Thismanualdescribes(1)howtoinstallLOQOonyourhardware,(2)howtouseAMPLtogetherwithLOQOtosolvegeneralconvexoptimizationproblems,(3)howtousethesubroutinelibrarytoformulateandsolveconvexoptimizationproblems,and(4)howtoformulateandsolvelinearandquadraticprogramsinMPSformat.ResearchsupportedbyONRthroughgrantN00014-98-1-0036andbyNSFthroughgrantCCR-9403789.12ROBERTJ.VANDERBEI2.INSTALLATIONThenormalmechanismfordistributionisbydownloadingfromtheauthor’shomepage:˜rvdb/UndertheheadingLOQOInfoonecanclickonDownloadandfollowtheinstructionsonthedownloadwebpage.Afterdownloadingandunzipping,youwillfindseveralfiles:loqo.exeAnexecutablecode,whichcanreadproblemsformulatedbytheAMPLmodelinglan-guage.Forlinearprogrammingproblems,itcanalsoreadindustry-standardMPSform(seeafiro.mpsforanexample)andforquadraticprogrammingproblemsitcanreadanextensionofMPSform.loqo.libAnarchivefilecontainingtheLOQOfunctionlibrary.loqo.cAfilecontainingthemainprogramforloqo.ItisincludedasanexampleonhowtousetheLOQOfunctionlibrary.hs046.cAmodificationofloqo.cillustratinghowtousethefunctionlibrarytosolveproblem46intheHockandSchittkowski[3]testsuite.loqo.hAheaderfilecontainingthefunctionprototypesforeachfunctionintheLOQOfunctionlibrary.Thisfilemustbe#include’dinanyprogramfileinwhichcallstotheLOQOfunctionlibraryaremade(loqo.candhs046.careexamplesofthis).myalloc.hAheaderfilecontainingmacrostomakedynamicmemoryallocationlessofachore.3.USINGLOQOWITHAMPLItiseasytouseLOQOwithAMPL.InanAMPLmodelonesimplyputsoptionsolverloqo;beforethesolvecommand.Ifonewishestoadjustsomeuser-settableparameters,theycanbesetwithintheAMPLmodelaswell.Forexample,toincreasetheamountofoutputproducedbythesolverandtorequestareportofthesolutiontime,oneputsthefollowingstatementintheAMPLmodelaheadofthecalltothesolver:optionloqo_optionsverbose=2timing=1;Parameters,theirmeaningsandtheirdefaults,aredescribedinalatersection.HundredsofsampleAMPLmodelscanbedownloadedfromtheauthor’shomepage˜rvdb/.Oneexampleisdiscussedinthefollowingsubsection.Belowwedescribeonespecificreal-worldmodelandshowhowtosolveitwithAMPL/LOQO.3.1.TheMarkowitzModel.Markowitzreceivedthe1990NobelPrizeinEconomicsforhisportfoliooptimizationmodelinwhichthetradeoffbetweenriskandrewardisexplicitlytreated.Weshallbrieflydescribethismodelinitssimplestform.Givenacollectionofpotentialinvestments(indexed,say,from1ton),letRjdenotethereturninthenexttimeperiodoninvestmentj,j=1,...,n.Ingeneral,Rjisarandomvariable,althoughsomeinvestmentsmaybeessentiallydeterministic.Aportfolioisdeterminedbyspecifyingwhatfractionofone’sassetstoputintoeachinvestment.Thatis,aportfolioisacollectionofnonnegativenumbersxj,j=1,..