A CONVEXIFICATION METHOD FOR A CLASS OF GLOBAL OPT

AConvexificationMethodforaClassofGlobalOptimizationProblemswithApplicationstoReliabilityOptimizationXiaolingSun,KenMcKinnon,DuanLiOctober2000MS00-17WorkdoneduringXiaolingSun’svisittoEdinburghNov1999-Nov2000.PartiallysupportedbyResearchGrantsCouncilofHongKong,grantCUHK4056/98E,andtheNationalScienceFoundationofChina,grant79970107.XiaolingSun:DepartmentofMathematicsShanghaiUniversity,Baoshan,Shanghai200436,P.R.China.E-Mail:[e-mail]:DepartmentofMathematicsandStatisticsUniversityofEdinburgh,TheKing’sBuildings,EdinburghEH93JZTel.(33)1316505042E-Mail:[e-mail]:DepartmentofSystemsEngineeringandEngineeringManagementTheChineseUniversityofHongKong,Shatin,N.T.,HongKongE-mail:[e-mail]FORACLASSOFGLOBALOPTIMIZATIONPROBLEMSWITHAPPLICATIONSTORELIABILITYOPTIMIZATIONXIAOLINGSUNDepartmentofMathematics,ShanghaiUniversity,Baoshan,Shanghai200436,P.R.ChinaKENMCKINNONDepartmentofMathematicsandStatisticsUniversityofEdinburgh,EdinburghEH93JZ,UKDUANLI†DepartmentofSystemEngineeringandEngineeringManagement,TheChineseUniversityofHongKong,Shatin,N.T.,HongKong([e-mail])October,2000AbstractAconvexificationmethodisproposedforsolvingaclassofglobaloptimizationproblemswithcertainmonotoneproperties.Itisshownthatthisclassofproblemscanbetransformedintoequivalentconcaveminimizationproblemsusingtheproposedconvexificationschemes.Anouterapproximationmethodcanthenbeusedtofindtheglobalsolutionofthetransformedproblem.Applicationstomixed-integernonlinearprogrammingproblemsarisinginreliabilityoptimizationofcomplexsystemsarediscussedandsatisfactorynumericalresultsarepresented.KeyWords:Globaloptimization,monotoneoptimization,concaveminimization,reliabilityopti-mization.ThisresearchwaspartiallysupportedbytheResearchGrantsCouncilofHongKong,grantno.CUHK4056/98E,andtheNationalScienceFoundationofChinaunderGrant79970107.†Correspondingauthor.11IntroductionWeconsiderglobaloptimizationproblemsoftheform:maxf(x)(1.1)s:t:gj(x)cj;j=1;2;:::;m;x2X;wheref:Rn!Randgj:Rn!R,j=1;:::;m,arecontinuousfunctionssatisfyingthefollowingmonotoneproperties:(a)f(x)andgj(x),j=1;:::;m,areincreasingfunctionsofeachxi,or(b)f(x)andgj(x),j=1;:::;m,aredecreasingfunctionsofeachxi.WeassumethatXisanonemptyclosedset.Theproblem(1.1)canbeviewedasthecontinuousversionofthemultidimensionalnonlinearknapsackproblem.Duetothemonotonicityoffandthegj’s,theoptimalsolutionof(1.1)alwaysliesontheboundaryofthefeasibleregion.Theproblem(1.1),however,mayhavemultiplelocaloptimalsolutionssincef(x)isnotnecessarilyconcaveandgjarenotnecessarilyconvex.Therefore,problem(1.1)isessentiallyaglobaloptimizationproblem.Theliteratureonthesolutionmethodsforglobaloptimizationcanbeclassifiedintotwocate-gories.Themethodsinthefirstcategoryaredevisedtocopewithgeneralglobaloptimizationprob-lemswithnospecialstructuralpropertyassumed.Thiscategoryincludesdeterministicmethods(see,e.g.,[1][4][6][7][8]andthereferencestherein)andstochasticmethods(see.e.g.,[3][14][15]andthereferencestherein).Thesecondcategoryofmethodsconfinesitsapplicabilitytocertainstructuredglobaloptimizationproblems,inparticular,concaveminimization,D.C.programmingandreverseconvexprogramming([2][5][6][13]).Forconcaveminimization,theglobalminimumoveracompactconvexsetisalwaysachievedatanextremepointoftheconvexset.Thisprominentfeatureleadstovariousimplementablealgorithmsthatguaranteeaconvergencetoaglobaloptimalsolutionoftheproblem.Themainpurposeofthispaperistopresentanovelconvexificationtransformationmethodtoconvertproblem(1.1)intoaconcaveminimizationproblem.Themonotonepropertyof(1.1)andtheresultingconvexfeasibleregionallowustoadoptanouterapproximationprocedureforsolvingtheresultingconcaveminimizationproblem.Thisconvexificationmethodisapplicabletoalargeclassofreal-worldoptimizationproblemsarisinginreliabilitynetworksystemswheremonotonicityisaninherentproperty.Convexificationsolutionschemeshavebeenrecentlyadoptedsuccessfullyinsomeothersubjectsofoptimization,suchasinconvexifyingtheperturbationfunctionandLagrangian2functioninthedualsearchmethodsfornonlinearprogramming([9][11])andinconvexifyingthenoninferiorfrontierinmultiobjectiveoptimization([10]).Insection2weestablishageneraltheoremontherelationshipbetweenmonotonicityandconvexityofarealfunction.Twospecificformsofconvexificationtransformationarethenproposed.Insection3theconvexificationtransformationisappliedtothefunctionsinproblem(1.1).Theresultingequivalentproblemisaconcaveminimizationproblemtowhichouterapproximationmethodcanbeusedtosearchforaglobaloptimalsolution.Insection4weshowhowtheproposedconvexificationmethodscanbeadoptedtotacklemixed-integernonlinearprogrammingproblemsinreliabilitynetworksystembycombiningtheouterapproximationmethodwithabranch-and-boundstrategy.2ConvexificationtransformationsofmonotonefunctionsAfunctionh:X!Riscalledstrictlyincreasing(decreasing)onXifh(x)isastrictlyincreasing(decreasing)functionofeachxi.Considerthefollowingtransformationoffunctionh(x):hp(y)=Tph1pt(y);(2.1)wherep0isaparameter,T:R1!R1isarealfunctionandt:Rn!Rnisaseparable1-1mapp