PERFECT DUALITY THEORY AND COMPLETE SOLUTIONS TO A

OptimizationVol.52,Nos.4–5,August–October2003,pp.467–493PERFECTDUALITYTHEORYANDCOMPLETESOLUTIONSTOACLASSOFGLOBALOPTIMIZATIONPROBLEMS*DAVIDYANGGAOyDepartmentofMathematics,VirginiaPolytechnicInstitute&StateUniversity,Blacksburg,VA24061,USA(Received13December2002;Infinalform23July2003)Thisarticlepresentsacompletesetofsolutionsforaclassofglobaloptimizationproblems.Theseproblemsaredirectlyrelatedtonumericalizationofalargeclassofsemilinearnonconvexpartialdifferentialequationsinnonconvexmechanicsincludingphasetransitions,chaoticdynamics,nonlinearfieldtheory,andsuper-conductivity.Themethodusedistheso-calledcanonicaldualtransformationdevelopedrecently.Itisshownthat,bythismethod,thesedifficultnonconvexconstrainedprimalproblemsinRncanbeconvertedintoaone-dimensionalcanonicaldualproblem,i.e.theperfectdualformulationwithzerodualitygapandwithoutanyperturbation.Thisdualcriticalityconditionleadstoanalgebraicequationwhichcanbesolvedcompletely.Therefore,acompletesetofsolutionstotheprimalproblemsisobtained.Theextremalityofthesesolutionsarecontrolledbythetrialitytheorydiscoveredrecently[D.Y.Gao(2000).DualityPrinciplesinNonconvexSystems:Theory,MethodsandApplications,Vol.xviii,p.454.KluwerAcademicPublishers,Dordrecht/Boston/London.].Severalexamplesareillustratedincludingthenonconvexconstrainedquadraticprogramming.ResultsshowthattheseproblemscanbesolvedcompletelytoobtainallKKTpointsandglobalminimizers.Keywords:Duality;Trialitytheory;Globaloptimization;Nonconvexvariations;Canonicaldualtransformation;Nonconvexmechanics;Criticalpointtheory;Semilinearequations;NP-hardproblems;QuadraticprogrammingMathematicsSubjectClassifications2000:49N15;49M37;90C26;90C201PROBLEMANDMOTIVATIONTheprimarygoalofthisarticleistosolvethefollowingglobaloptimizationproblem(inshort,theprimalproblemðPÞ):ðPÞ:minPðxÞ¼12hx,AxiþWðxÞ
hx,fijx2Xk
,ð1Þ*ThisarticleisdedicatedtoProfessorGilbertStrangontheoccasionofhis70thbirthday.ThemainresultsofthisarticlehasbeenpresentedattheInternationalConferenceonNonsmooth/NonconvexMechanics,AristotleUniversityofThessaloniki(A.U.Th.),July5–6,2002(keynotelecture),andtheSecondInternationalConferenceonOptimizationandControlwithApplications,August18–22,2002,YellowMountains,Anhui,China(plenarylecture).yE-mail:gao@vt.eduISSN0233-1934print:ISSN1029-4945online
2003Taylor&FrancisLtdDOI:10.1080/02331930310001611501wherethefeasiblespaceXkisaconvexsubsetofanormedspaceXsuchthatthealgebraicinteriorofXisnotempty;A:X!XisalinearoperatorwithA¼A,whichmapseachx2XintothedualspaceX;thebilinearformhx,xi:XX!RputsXandXinduality;W:X!Risagiven(notnecessarilyconvex)function;f2Xisagiveninput;P:Xk!Rrepresentsthetotalcostofthesystem.AlthoughtheglobalminimizationwithinequalityconstraintsarediscussedinSection6,thisarticleismainlyinterestedinfindingallcriticalpointsofthenonconvexfunctionP(x).Thus,inthecasethatthenonconvexfunctionW:Xk!RisGaˆteauxdifferentiable,thestationary(orcriticality)conditionDP(x)¼0leadstothegoverningequationAxþDWðxÞ¼f,ð2ÞwhereDW(x)representstheGaˆteauxderivativeofWatx,whichisamappingfromXintoitsdualspaceX.Theabstractform(2)oftheprimalproblemðPÞcoversmanysituations.Innon-convexmechanics(cf.[23,27]),whereXisaninfinitedimensionalfunctionspace,thestatevariablexisafieldfunction,usuallydenotedbyu(x),andA:X!Xisusuallyapartialdifferentialoperator.Inthiscase,thegoverningEq.(2)isaso-calledsemi-linearequation.Forexample,inLandau–Ginzburgtheoryofsuperconductivity,A¼

istheLaplacianoveragivenspacedomainRnandWðuÞ¼Z12
12u2
2distheLandaudoublewellpotential,inwhich
,0arematerialconstants.ThenthegoverningEq.(2)leadstothewell-knownLandau–Ginzburgequation
uþ
u12u2
¼f:Thissemilineardifferentialequationplaysanimportantroleinmaterialsscienceandphysicsincluding:ferroelectricity,ferromagnetism,ferroelasticity,andsuper-conductivity.DuetothefactthattheLandauenergyW(u)isnonconvexfunctional,theLandau–Ginzburgequationhasprovendifficulttosolve.Traditionaldirectanalysisandrelatednumericalmethodsforsolvingthisnonconvexvariationalproblemhaveprovenunsuccessfultodate.Indynamicalsystems,ifA¼
@,ttþ
isawaveoperatoroveragivenspace-timedomainRnR,andthenonconvexfunctionalissimplygivenasWðuÞ¼
Rcosud,then(2)isthewell-knownsine-Gordonequationu,tt

u¼sinðuÞ
f:Thisequationappearsinmanybranchesofphysics.Itprovidesoneofthesimplestmodelsoftheunifiedfieldtheory.Itcanalsobefoundinthetheoryofdislocationsinmetals,inthetheoryofJosephsonjunctions,aswellasininterpretingcertainbiologicalprocesseslikeDNAdynamics.Inthetimedomain½0,1Þ,ifwekeep468D.Y.GAOonlythefirsttwotermsoftheTaylor’sexpansionofsin(u),thenthesine-Gordonequationreducestothewell-knownDuffingequation,u,tt¼uð1
u2=6Þ
f.Eveninthisverysimpleone-dimensionalordinarydifferentialequation,ananalyticsolutionisstillverydifficulttoobtain.Itisknownthatthisequationisextremelysensitivetotheinitialconditionsandtheinput(drivingforce)f(t)(see[17,18]).Generallyspeaking,duetothenonconvexityofthefunctionW(u),verysmallperturbationsofthesystem’sinitialconditionsandparametersmayleadthesystemtodifferentoperatingpointswithsignificantly