IMPROVING CONSTRAINED NONLINEAR SEARCH ALGORITHMS

cCopyrightbyHonghaiZhang2001IMPROVINGCONSTRAINEDNONLINEARSEARCHALGORITHMSTHROUGHCONSTRAINTRELAXATIONBYHONGHAIZHANGB.S.,UniversityofScienceandTechnologyofChina,1998THESISSubmittedinpartialfulllmentoftherequirementsforthedegreeofMasterofScienceinComputerScienceintheGraduateCollegeoftheUniversityofIllinoisatUrbana-Champaign,2001Urbana,IllinoisAbstractInthisthesiswestudyconstraintrelaxationsofvariousnonlinearprogramming(NLP)al-gorithmsinordertoimprovetheirperformance.Forbothstochasticanddeterministicalgorithms,westudytherelationshipbetweentheexpectedtimetondafeasiblesolutionandtheconstraintrelaxationlevel,buildanexponentialmodelbasedonthisrelationship,anddevelopaconstraintrelaxationscheduleinsuchawaythatthetotaltimespenttondafeasiblesolutionforalltherelaxationlevelsisofthesameorderofmagnitudeasthetimespentforndingasolutionofsimilarqualityusingthelastrelaxationlevelalone.Whentheobjectiveandconstraintfunctionsarestochastic,wedenenewcriteriaofconstraintsatisfactionandsimilarconstraintrelaxationschedules.Similartothecasewhenfunctionsaredeterministic,webuildanexponentialmodelbetweentheexpectedtimetondafeasiblesolutionandtheassociatedconstraintrelaxationlevel.Wedevelopananytimeconstraintrelaxationscheduleinsuchawaythatthetotaltimespenttosolveaproblemforallconstraintrelaxationlevelsisofthesameorderofmagnitudeasthetimespentforndingafeasiblesolutionusingthelastrelaxationlevelalone.Finally,westudytheasymptoticbehaviorofournewalgorithmsandprovetheirasymptoticconvergence,basedonthetheoryofasymptoticconvergenceinsimulatedannealingandconstrainedsimulatedannealing.iiiTomywifeandmyparents.ivAcknowledgmentsFirst,Iwouldliketothankmyresearchadvisor,ProfessorBenjaminWah,forhisguidance,encouragementandvaluableideasinthiswork.Heintroducedmetothisareaandinspiredmeallthetime.Iwouldliketothankallthememberinmyresearchgroupfortheirideasandcommentsinthiswork.SpecialthanksgotoDr.TaoWangforhisresearchonconstrainedsimu-latedannealing(CSA),Dr.ZheWuforhisresearchonLagrangemultipliersfordiscreteconstrainedoptimization,andMr.YixinChenforhisresearchonanytimeCSA.Finallyandmostspecially,Iliketothankmywifeforherlovingme,supportingme,andkeepingmylifecolorful.ThisresearchwassupportedbyNationalAeronauticsandSpaceAdministrationGrantNAG2-1230.vTableofContentsChapter1Introduction:::::::::::::::::::::::::::::::::::::11.1DenitionofNLPProblems...........................11.1.1Optimizationwithdeterministicfunctions...............11.1.2Optimizationwithstochasticfunctions.................21.2BasicDenitionsandConcepts.........................41.2.1Conceptsincontinuousspace......................51.2.2Conceptsindiscretespace........................61.2.3Conceptsinmixed-integerspace.....................71.3ConstraintRelaxation..............................81.3.1ConstraintrelaxationforNLPswithdeterministicfunctions.....81.3.2ConstraintrelaxationforNLPswithstochasticfunctions.......111.4OutlineoftheThesis...............................132PreviousWork::::::::::::::::::::::::::::::::::::152.1MethodsforDiscreteOptimization.......................152.1.1DirectmethodsforsolvingdiscreteconstrainedNLPs.........162.1.2Transformationsintoconstrained0-1NLPs...............162.1.3Lagrangianrelaxation..........................172.1.4Penaltyformulationsandmethods...................172.2MethodsforContinuousConstrainedNLPs...................212.2.1DirectsolutionsforsolvingcontinuousconstrainedNLPs.......21vi2.2.2Penaltyformulations...........................252.2.3Lagrangianformulations.........................262.3MethodsforMixed-IntegerNLPs........................272.3.1DirectsolutionsforMINLPs.......................272.3.2Penaltyformulations...........................272.3.3Lagrangianformulations.........................292.4MethodsforConstrainedNLPswithUncertainty...............302.5ExistingConstrainedNLPSolvers........................322.6Summary.....................................323ConstraintRelaxationsinCSA:::::::::::::::::::::::::353.1AGeneralFrameworktoLookforSPdnanditsImplementation.......353.1.1Generalframework............................363.1.2Constrainedsimulatedannealing(CSA)................373.1.3CSAwithiterativedeepening......................383.2ConstraintRelaxationsDuringAnnealinginCSA...............403.2.1Relaxationofequalityconstraints...................403.2.2Theoryofgeneralizedsimulatedannealing...............423.2.3AsymptoticconvergenceofRCSA....................443.2.4Experimentalresults...........................463.3ConstraintRelaxationAcrossMultipleCSARuns...............473.3.1Problemformulation...........................473.3.2Constraintrelaxation...........................493.3.3PerformancemodelingofCSAsforndingfeasiblesolutions.....503.3.4Anytimeschedulewithiterativedeepening...............533.3.5Experimentalresults...........................553.4Summary.....................................614ConstraintRelaxationinLineSearch:::::::::::::::::::::624.1LineSearchforContinuousUnconstrainedProblems..............62vii4.2ConstrainedLineSearchAlgorithm