Q> Canadian Mathematical Society Societe mathematique du Canada Editors-in-Chief Redacteurs-en-chef J. Borwein K.Dilcher Advisory Board Comite consultatif P. Borwein R. Kane S. Shen CMS Books in Mathematics Ouvrages ofe mathematiques de la SMC 1 HERMAN/KUCERA/SIMSA Equations and Inequalities 2 ARNOLD Abelian Groups and Representations of Finite Partially Ordered Sets 3 BORWEIN/LEWIS Convex Analysis and Nonlinear Optimization, 2nd Ed. 4 LEVIN/LUBINSKY Orthogonal Polynomials for Exponential Weights 5 KANE Reflection Groups and Invariant Theory 6 PHILLIPS TWO Millennia of Mathematics 7 DEUTSCH Best Approximation in Inner Product Spaces 8 FABIAN ET AL. Functional Analysis and Infinite-Dimensional Geometry 9 KRI^EK/LUCA/SOMER 17 Lectures on Fermat Numbers 10 BORWEIN Computational Excursions in Analysis and Number Theory 11 REED/SALES (Editors) Recent Advances in Algorithms and Combinatorics 12 HERMAN/KUCERA/SIMSA Counting and Configurations 13 NAZARETH Differentiable Optimization and Equation Solving 14 PHILLIPS Interpolation and Approximation by Polynomials 15 BEN-ISRAEL/GREVILLE Generalized Inverses, 2nd Ed. 16 ZHAO Dynamical Systems in Population Biology 17 GoPFERT ET AL . Variational Methods in Partially Ordered Spaces 18 AKIVIS/GOLDBERG Differential Geometry of Varieties with Degenerate Gauss Maps 19 MIKHALEV/SHPILRAIN/YU Combinatorial Methods 20 BORWEIN/ZHU Techniquesof Variational Analysis 21 VAN BRUMMELEN/KINYON Mathematics and the Historian's Craft 22 LuccHETTi Convexity and Well-Posed Problems 23 NICULESCU/PERSSON Convex Functions and Their Applications 24 SINGER Duality for Nonconvex Approximation and Optimization 25 HIGGINSON/PIMM/SINCLAIR Mathematics and the Aesthetic Ivan Singer Duality for Nonconvex Approximation and Optimization With 17 Figures ^ Sprim ger Ivan Singer Simion Stoilow Institute of Mathematics 014700 Bucharest Romania Editors-in-Chief Redacteurs-en-chef Jonathan Borwein Karl Dilcher Department of Mathematics and Statistics Dalhousie University Halifax, Nova Scotia B3H 3J5 Canada cbs-editors @ cms.math.ca Mathematics Subject Classification: 46N10,49N15,90C26,90C48 Library of Congress Cataloging-in-PubHcation Data Singer, Ivan. DuaHty for nonconvex approximation and optimization / Ivan Singer. p. cm. — (CMS books in mathematics; 24) ISBN-13: 978-0-387-28394-4 (alk. paper) ISBN-10: 0-387-28394-3 (alk. paper) ISBN-10: 0-387-28395-1 (e-book) 1. Convex functions. 2. Convex sets. 3. Duality theory (Mathematics) 4. Approximation theory. 5. Convex domains. 6. Convexity spaces. I. Title. II. Series. QA640.S56 2005 515'.8-dc22 2005051742 Printed on acid-free paper. © 2006 Springer Science+Business Media, Inc. All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer Science+Business Media, Inc., 233 Spring Street, New York, NY 10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed is forbidden. The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights. Printed in the United States of America. 9 8 7 6 5 4 3 21 springeronline.com To the memory of my wonderful wife, Crina Contents List of Figures xi Preface xiii 1 Preliminaries 1 1.1 Some preliminaries from convex analysis 1 1.2 Some preliminaries from abstract convex analysis 27 1.3 Duality for best approximation by elements of convex sets 39 1.4 Duality for convex and quasi-convex infimization 46 1.4.1 Unperturbational theory 47 1.4.2 Perturbational theory 71 2 Worst Approximation 85 2.1 The deviation of a set from an element 86 2.2 Characterizations and existence of farthest points 93 3 Duality for Quasi-convex Supremization 101 3.1 Some hyperplane theorems of surrogate duality 103 3.2 Unconstrained surrogate dual problems for quasi-convex supremization 108 3.3 Constrained surrogate dual problems for quasi-convex supremization 121 3.4 Lagrangian duality for convex supremization 127 3.4.1 Unperturbational theory 127 3.4.2 Perturbational theory 129 viii Contents 3.5 Duality for quasi-convex supremization over structured primal constraint sets 131 4 Optimal Solutions for Quasi-convex Maximization 137 4.1 Maximum points of quasi-convex functions 137 4.2 Maximum points of continuous convex functions 144 4.3 Some basic subdifferential characterizations of maximum points 149 5 Reverse Convex Best Approximation 153 5.1 The distance to the complement of a convex set 154 5.2 Characterizations and existence of elements of best approximation in complements of convex sets 161 6 Unperturbational Duality for Reverse Convex Infimization 169 6.1 Some hyperplane theorems of surrogate duality 171 6.2 Unconstrained surrogate dual problems for reverse convex infimization 175 6.3 Constrained surrogate dual problems for reverse convex infimization 184 6.4 Unperturbational Lagrangian duality for reverse convex infimization 189 6.5 Duality for infimization over structured primal reverse convex .constraint sets 190 6.5.1 Systems 190 6.5.2 Inequality constraints 198 7 Optimal Solutions for Reverse Convex Infimization 203 7.1 Minimum points of functions on reverse convex subsets of locally convex spaces 203 7.2 Subdifferential characterizations of minimum points of functions on reverse convex sets 209 8 Duality for D.C. Optimization Problems 213 8.1 Unperturbational duality for unconstrained d.c. infimization 213 8.2 Minimum points of d.c. functions 221 8.3 Duality for d.c. infimization with a d.c. inequality constraint 225 8.4 Duality for d.c. infimization with finitely many d.c. inequality constraints 232 8.5 Perturbational theory 244 8.6 Duality for optimization problems involving maximum operators 247 8.6.1 Duality via conjugations of type Lau 248 8.6.2 Duality via Fenchel conjugations 252 9 Duality for Optimization in the Framework of Abstract Convexity ... 259 9.1 Additional preliminaries from abstract convex analysis 259 9.2 Surrogate duality for abstract quasi-convex supremization, using polarities AG : 2^ ^ 2^ and AG : 2^ ^ 2^^^ 267 Contents ix 9.3 Constrained surrogate duality for abstract quasi-convex supremization, using families of subsets of X 270 9.4 Surrogate duality for abstract reverse convex infimization, using polarities AG : 2^ ^ 2^ and Ac: 2^ -> 2^^^ 271 9.5 Constrained surrogate duality for abstract reverse convex infimization, using families of subsets of X 273 9.6 Duality for unconstrained abstract d.c. infimization 275 10 Notes and Remarks 279 References 329 Index 347 List of Figures 1.1 3 1.2 12 1.3 40 1.4 44 1.5 49 2.1 86 2.2 88 2.3 90 2.4 91 2.5 92 2.6 95 2.7 96 5.1 153 5.2 156 5.3 157 5.4 159 5.5 163