Duality in Global Optimization: Optimality Conditions and Algorithmical Aspects Dissertation zur Erlangung des akademischen Grades einer Doktorin der Naturwissenschaften Dem Fachbereich IV der Universit(cid:127)at Trier vorgelegt von Mirjam Du(cid:127)r Berichte aus der Mathematik Mirjam Dür Duality in Global Optimization: Optimality Conditions and Algorithmical Aspects . Shaker Verlag Aachen 1999 Die Deutsche Bibliothek - CIP-Einheitsaufnahme Dür, Mirjam: Duality in Global Optimization: Optimality Conditions and AlgorithmicalAspects/ Mirjam Dür. - Als Ms. gedr. - Aachen : Shaker, 1999 (Berichte aus der Mathematik) Zugl.: Trier, Univ., Diss., 1999 ISBN 3-8265-6115-5 . Copyright Shaker Verlag 1999 Alle Rechte, auch das des auszugsweisen Nachdruckes, der auszugsweisen oder vollständigen Wiedergabe, der Speicherung in Datenverarbeitungs- anlagen und der Übersetzung, vorbehalten. Als Manuskript gedruckt. Printed in Germany. ISBN 3-8265-6115-5 ISSN 0945-0882 Shaker Verlag GmbH • Postfach 1290 • 52013 Aachen Telefon: 02407 / 95 96 - 0 • Telefax: 02407 / 95 96 - 9 Internet: www.shaker.de • eMail: [email protected] To M. Acknowledgements TheworkonthisthesiswascarriedoutunderthesupervisionofR.Horst,Universityof Trier,Germany,whomIthankforgivingmetheopportunityofstudyingattheUniver- sityofTrierfortwoyears. Iamalso grateful toJ.{B. Hiriart{Urruty, Universit(cid:19)e Paul Sabatier, Toulouse, France, for his readiness to act as a referee of this thesis and for giving many hints for future research. I highly bene(cid:12)ted fromthe collaboration with the membersof the global optimization groupinTrier: N.V.Thoai,U.RaberandM.Locatelli. W.Oettli,UniversityofMannheim,Germany,gavevaluable commentsonChapter2of thisthesis. MythankalsogoestoI.M.Bomze,UniversityofVienna,Austria,forcontinualencour- agementandstimulatingdiscussions. Myworkwould nothave been possible without the(cid:12)nancial supportofthe\Deutsche Forschungsgemeinschaft"duringmytimeinthe\GraduiertenkollegMathematischeOp- timierung"inTrierfromApril1996toMay1998. Themembersofthe\Graduiertenkolleg MathematischeOptimierung",inparticularits speakerE.Sachs,providedapleasantatmosphereforworking. Finally, Iwouldlike tothankthemembersoftheDepartmentofStatistics atVienna’s University ofEconomics and Business Administration, which Iam a(cid:14)liated with since June1998,fortheirsupportandencouragement. Erster Berichterstatter: Prof.Dr.R.Horst,Universit(cid:127)atTrier Zweiter Berichterstatter: Prof.Dr.J.{B.Hiriart{Urruty,Universit(cid:19)ePaul Sabatier,Toulouse Tag dermu(cid:127)ndlichen Pru(cid:127)fung: 12.April1999 Contents I Optimality Conditions 1 1 Introductionto PartI 3 2 Global OptimalityConditionsforMinimizing Di(cid:11)erencesofFunctions 5 2.1 IntroducingtheProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2 Preliminaries fromConvexAnalysis . . . . . . . . . . . . . . . . . . . . . 6 2.3 OptimalityConditionsforD.C.Problems . . . . . . . . . . . . . . . . . . 8 2.4 OptimalityConditionsforaMoreGeneralClassofFunctions. . . . . . . 10 3 Global Optimality Conditions for Convex Maximization 17 3.1 FromD.C.ProgrammingtoConvexMaximization . . . . . . . . . . . . . 18 3.2 InterconnectionofGlobalOptimalityCriteria . . . . . . . . . . . . . . . 22 3.3 FurtherOptimalityConditions. . . . . . . . . . . . . . . . . . . . . . . . 26 3.3.1 Reformulationof(HU)intheDi(cid:11)erentiable Case . . . . . . . . . 26 3.3.2 MaximizationofStrictlyConvexQuadraticFunctionsoverConvex Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 3.3.3 Equivalences betweenNonconvexOptimizationProblems . . . . . 29 4 ConnectionsbetweenLocal andGlobal Optimality Conditions 31 4.1 NecessaryConditionsforLocalOptimality . . . . . . . . . . . . . . . . . 31 4.2 ThePiecewise A(cid:14)neCase . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.3 Su(cid:14)cientConditionsforLocalOptimality . . . . . . . . . . . . . . . . . 36 4.4 AGeneralization ofStrekalovsky’sOptimalityConditiontoD.C.Problems 37 i ii Contents 5 Remarks on D.C. Decompositions 39 5.1 ExistenceofD.C.Decompositions . . . . . . . . . . . . . . . . . . . . . . 39 5.2 D.C.DecompositionsforPolynomials . . . . . . . . . . . . . . . . . . . . 40 II Algorithmical Aspects 45 6 Introductionto PartII 47 7 The Branch{and{BoundAlgorithm 49 7.1 TheBasicBranch{and{BoundScheme . . . . . . . . . . . . . . . . . . . 49 7.2 BranchingandBoundingProcedures . . . . . . . . . . . . . . . . . . . . 51 7.3 ConvergenceConditions . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 8 Lagrange Duality and Partitioning Techniques 55 8.1 ConvexEnvelopesandDuality . . . . . . . . . . . . . . . . . . . . . . . . 55 8.1.1 ConvexEnvelopes. . . . . . . . . . . . . . . . . . . . . . . . . . . 55 8.1.2 DualityGap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 8.2 Branch{and{BoundMethodswithDualBounds . . . . . . . . . . . . . . 59 8.2.1 LimitBehaviouronNestedSequences. . . . . . . . . . . . . . . . 59 8.2.2 PartitioningMethodswithDualBounds . . . . . . . . . . . . . . 62 8.2.3 PartlyConvexOptimizationProblems . . . . . . . . . . . . . . . 64 8.3 SomeApplications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 8.3.1 LinearlyConstrainedProblemsandConvexi(cid:12)cation . . . . . . . . 66 8.3.2 GeneralizedBilinear Constraints. . . . . . . . . . . . . . . . . . . 66 8.3.3 MaximizingtheSumofA(cid:14)neRatios . . . . . . . . . . . . . . . . 67 8.3.4 ConcaveMinimizationunderReverseConvexConstraints. . . . . 68 9 Global Optimization of Sums of Ratios and the Corresponding Multiple{Criteria Decision Problem 69 9.1 Applications andBackground . . . . . . . . . . . . . . . . . . . . . . . . 69 Contents iii 9.2 Application of the Basic Branch{and{Bound Scheme to the Sum{of{ RatiosProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 9.3 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 9.4 UpperBoundsforSumsofA(cid:14)neRatios . . . . . . . . . . . . . . . . . . 76 9.5 LowerBoundsforSumsofA(cid:14)neRatios . . . . . . . . . . . . . . . . . . 80 9.5.1 TheCorrespondingMultiple{Objective Problem . . . . . . . . . . 80 9.5.2 AGeneralizedParametricApproach . . . . . . . . . . . . . . . . 81 9.5.3 AFiniteProcedureforCalculating E(cid:14)cientPoints . . . . . . . . 86 9.6 NumericalResults. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88 10SecondBranch{and{BoundApproachfortheSum{of{RatiosProblem 91 10.1 ReformulatingtheProblem . . . . . . . . . . . . . . . . . . . . . . . . . 92 10.2 TheAlgorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 10.2.1 UpperBounds. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 10.2.2 ComputationofFeasiblePoints . . . . . . . . . . . . . . . . . . . 96 10.3 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 10.4 NumericalResults. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 Bibliography 101 Index 107 Part I Optimality Conditions 1