An interior-point algorithm for nonconvex nonlinear programming

ABSTRACT. The paper describes an interior--point algorithm for nonconvex nonlinear programming which is a direct extension of interior--point methods for linear and quadratic programming. Major modifications include a merit function and an altered search d

ANINTERIOR–POINTALGORITHMFORNONCONVEXNONLINEAR

PROGRAMMING

ROBERTJ.VANDERBEIANDDAVIDF.SHANNO

StatisticsandOperationsResearch

PrincetonUniversity

SOR-97-21

ABSTRACT.Thepaperdescribesaninterior–pointalgorithmfornonconvexnonlinear

programmingwhichisadirectextensionofinterior–pointmethodsforlinearandquadratic

programming.Majormodi cationsincludeameritfunctionandanalteredsearchdirection

toensurethatadescentdirectionforthemeritfunctionisobtained.Preliminarynumerical

testingindicatesthatthemethodisrobust.Further,numericalcomparisonswithMINOS

andLANCELOTshowthatthemethodisef cient,andhasthepromiseofgreatlyreducing

solutiontimesonatleastsomeclassesofmodels.

1.INTRODUCTION

Inthispaper,wedescribemodi cationsthatweusedtoconvertthequadraticprogram-ming(QP)solverLOQOintoageneralnonconvexnonlinearprogrammingsolver(ofthesamename).Asacodeforquadraticprogramming,LOQOimplementsaninterior-pointmethod.ThecompletedetailsoftheQPimplementationcanbefoundin[25].Inviewofthedramaticsuccessofmoderninterior-pointmethodsforlinearandquadraticprogram-ming,ourguidingphilosophywastomodifytheQPinterior-pointmethodinLOQOaslittleaspossibletomakearobustandef cientgeneralnonconvexnonlinearoptimizer.

Fornotationalsimplicity,webeginbyconsideringthefollowingnonlinearprogram-mingproblem:

(1)minimizef(x)

subjecttohi(x)≥0,i=1,...,m,

wherexisavectorofdimensionnandf(x)andthehi(x)areassumedtobetwicecon-tinuouslydifferentiable.Thisisasimpli cationofthegeneralnonlinearprogrammingproblem,whichcanincludeequalityconstraintsandboundsonthevariables.Infact,themethoddevelopedinthispaperanditsimplementationinLOQOhandlesallofthesecasesef ciently,andtheexactwayinwhichthisisaccomplishedisdiscussedindetaillater.For