Luận án Tiến sĩ: Phân tích biến phân và ổn định trong các bài toán tối ưu hóa

Wayne State University Wayne State University Dissertations 1-1-2016 Variational Analysis And Stability In Optimization M. Ebrahim Sarabi Wayne State University, Follow this and additional works at: http://digitalcommons.edu/oa_dissertations Part of the Mathematics Commons Recommended Citation Sarabi, M. Ebrahim, "Variational Analysis And Stability In Optimization" (2016). Wayne State University Dissertations.

This Open Access Dissertation is brought to you for free and open access by DigitalCommons@WayneState. It has been accepted for inclusion in Wayne State University Dissertations by an authorized administrator of DigitalCommons@WayneState. VARIATIONAL ANALYSIS AND STABILITY IN OPTIMIZATION by M. EBRAHIM SARABI DISSERTATION Submitted to the Graduate School of Wayne State University, Detroit, Michigan in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY 2016 MAJOR: (Applied) MATHEMATICS Approved By: ———————————————————– Advisor Date ———————————————————– ———————————————————– ———————————————————– ———————————————————– DEDICATION To my parents ii ACKNOWLEDGEMENTS It would be impossible to adequately express my gratitude and appreciation for my advisor, Professor Boris Mordukhovich.

His ceaseless devotion, support, and encouragement has been the driving force behind all my accomplishments during my doctoral studies. He is the inspiration for the kind of mathematician I aspire to be. It was my great honor to have him as my advisor during the years at Wayne State University. I am also indebted to my mentor Professor Dinh The Luc from whom I learned a lot about optimization and variational analysis.

I would like to thank the rest of my thesis committee: Professors Alper Murat, Peiyong Wang, George Yin, and Sheng Zhang for taking their time to serve on my dissertation committee. My sincere thanks also go to the entire Department of Mathematics at Wayne State University for their kind support in a number of ways. Specially, I wish to thank Christopher Leirstein and Christopher Nazelli for their invaluable feedbacks and help with my teaching. Most importantly, none of this would have been possible without the love and endless care of my family.

I would like to thank my parents for their love, encouragement, and support. iii TABLE OF CONTENTS Dedication. iii CHAPTER 1: INTRODUCTION. 1 CHAPTER 2: FULL STABILITY FOR UNCONSTRAINED PROBLEMS 5 2.1 Tools of Variational Analysis .3 Characterizations of Full Stability.

13 CHAPTER 3: STABILITY ANALYSIS OF UNCONSTRAINED PROB- LEMS .1 Full Stability of Constrained Optimization Problems .2 Relationships of Full Stability with Other Stability Notions. 34 CHAPTER 4: SECOND-ORDER ANALYSIS OF PIECEWISE LINEAR FUNCTIONS .1 Reducibility, Nondegeneracy and Second-Order Qualification .2 Full Stability in Composite Optimization .3 Full Stability in Constrained Minimax Problems .4 Strong Regularity and Strong Stability in Composite Models. 66 CHAPTER 5: CRITICAL MULTIPLIERS FOR COMPOSITE PROBLEMS 77 5.1 Critical Multipliers for Composite Optimization Problems .2 Full Stability and Critical Multipliers. 104 iv 1 CHAPTER 1 INTRODUCTION Lipschitzian stability of locally optimal solutions with respect to small parameter per- turbations is undoubtedly important in optimization theory allowing us to recognize robust solutions and support computational work from the viewpoints of justifying numerical al- gorithms, their convergence properties, stopping criteria, etc.

There are several versions of Lipschitzian stability in optimization; see, e., the books [1, 5, 10, 27, 53] and the references therein. The focus of this dissertation is on what is known as full stability of locally opti- mal solutions introduced by Levy, Poliquin and Rockafellar [20]. This notion emerged as a far-going extension of tilt stability of local minimizers in the sense of Poliquin and Rock- afellar [45]; see Chapter 2 for the precise definitions and more discussions. It seems that full stability is probably the most fundamental stability notion for locally optimal solutions, from both theoretical and practical points of view, particularly in connection with numerical methodology and applications [20, 45].

In [20], the authors derived necessary and sufficient conditions for fully stable minimizers of parameterized optimization problems written in the unconstrained format with extended- real-valued and prox-regular cost functions. They expressed these conditions in terms of a partial modification of the second-order subdifferential (or generalized Hessian) in the sense of Mordukhovich [26], which was previously used in [45] for characterizations of tilt stabil- ity. As mentioned in [20], implementing this approach in particular classes of constrained optimization problems important for the theory and applications requires the developments of second-order subdifferential calculus for the constructions involved, which was challenging and not available at that time. Partly such a calculus has been developed in the recent paper by Mordukhovich and Rockafellar [38] with applications to tilt stability therein.

Quite recently, Mordukhovich and Nghia [31] have developed a new approach to both Lipschitzian and Hölderian (introduced therein) full stability in finite and infinite dimensions and applied it to deriving constructive characterization of full stability in NLPs, infinite- 2 dimensional problems with polyhedric constraints, and optimal control problems governed by semilinear elliptic equations without any nondegeneracy assumption. Moreover, they extended their results in [33] for constrained optimization problems under the nondegeneracy assumption using the uniform second-order growth condition. The main goal of this dissertation is to obtain complete characterizations of full stability for remarkable classes of constrained optimization problems expressing these characteriza- tions entirely in terms of the problem data. The classes under consideration include general models given in composite formats of optimization (particularly with fully amenable compo- sitions), and consequently for classical problems of nonlinear programming (NLP) with C 2 equality and inequality constraints.

The key machinery is based on exact (equality type) second-order calculus rules for the aforementioned constructions taken partly from [38] and also the new ones derived in this dissertation. The rest of the dissertation is organized as follows. In Chapter 2 we review the basic generalized differential tools of variational analysis used in formulations and proofs of the main results. We then presents definitions of full stability and related notions for optimiza- tion problems written in the unconstrained extended-real-valued format.

We discuss the second-order necessary and sufficient conditions for full stability of local minimizers in this setting [20] and establish relationships between full stability of local minimizers and the new notion of partial strong metric regularity (PSMR) of the corresponding subdifferential map- pings. Then these conditions are characterized via a certain uniform second-order growth condition (USOGC). Chapter 3 addresses a general class of constrained optimization problems covering those in conic programming, establishes new properties of fully stable minimizers, and provides new proofs of major second-order characterizations of fully stable minimizers under reducibil- ity and partial nondegeneracy conditions. In particular, the developed approach allows us to describe the framework of canonical perturbations, where full stability is equivalent to 3 tilt stability under an appropriate parametric reduction.

Then we investigate relationships between full stability of local minimizers for general constrained optimization problems with C 2 -smooth data and Lipschitzian single-valued localizations of solution maps to the corre- sponding KKT (Karush-Kuhn-Tucker) systems. The obtained results with self-contained proofs ensure, in particular, the equivalence between full stability of local minimizers and Robinson’s strong regularity [47] of the associated generalized equations as well as strong Lipschitz stability of stationary points with respect to C 2 -smooth perturbations. The major result of Chapter 4 is to establish a certain equivalence between qualification conditions used in [28, 38] for deriving by different approaches the exact second-order chain rule for fully amenable compositions involving convex piecewise linear (CPWL) functions. Being important for its own sake, the key ingredient of this result (together with the explicit calculation of the second-order subdifferential of CPWL functions) is the proof of the so- called C ∞ -reducibility of CPWL functions via linear transformations that are used then in the formulation of partial nondegeneracy.

As a by-product of the obtained equivalence, we completely clarify the essence of the powerful second-order chain rule that is largely employed in the subsequent material. Next we present the explicit composite SSOSC characterization of fully stable local minimizers in the partially nondegenerate composite framework of opti- mization involving CPWL functions. Then we effectively apply the general composite result to characterizing full stability of local optimal solutions of minimax problems with polyhedral constraints. Finally, we finish our study of composite optimization models with CPWL func- tions with characterizing strong regularity of the associated KKT systems and strong stability of the related stationary points under perturbations.

We prove that these differently defined notions are equivalent to full stability of the corresponding local minimizers under partial nondegeneracy being therefore completely characterized by the aforementioned SSOSC. The last chapter discusses a very recent concept of critical multipliers for composite optimization problems. We first formulate the later concept in this framework and then 4 characterize it via second-order subdifferentials. Then we show that full stability of local minimizers can rule out critical multipliers for problems of composite optimization.

5 CHAPTER 2 FULL STABILITY FOR UNCON- STRAINED PROBLEMS 2.1 Tools of Variational Analysis In this chapter we briefly overview some basic constructions of generalized differentiation in variational analysis, which are widely used in what follows. Then we discuss the concept of full stability in the general framework of unconstrained optimization problems. Finally, we provide some characterizations of this concept, which open the door to proceed in the subsequent chapters. We start with recalling the corresponding first-order subdifferentials as well as associated objects of variational geometry.

Given ϕ : Rn → R finite at x̄, its regular subdifferential (known also as the presubdifferential and as the Fréchet or viscosity subdifferential) at x̄ is n ϕ(x) − ϕ(x̄) − hv, x − x̄i o ∂ϕ(x̄) b := v ∈ Rn lim inf ≥0 .1) x→x̄ kx − x̄k While ∂ϕ(x̄) b reduces to a singleton {∇ϕ(x̄)} if ϕ is Fréchet differentiable at x̄ and to the classical subdifferential of convex analysis if ϕ is convex, the set (2.1) may often be empty for nonconvex and nonsmooth functions as, e. Another serious disadvantage of (2.1) is the failure of standard calculus rules inevitably required in the theory and applications of variational analysis including those to optimization and equilibria. The picture dramatically changes when we perform a limiting procedure over the mapping ϕ x 7→ ∂ϕ(x) b as x → x̄ that leads us to the (basic first-order) subdifferential of ϕ at x̄ defined by ∂ϕ(x̄) := Lim sup ∂ϕ(x) b (2.2) ϕ x→x̄ and known also as the general, or limiting, or Mordukhovich subdifferential; it was first introduced in [24] in an equivalent way. In contrast to (2.1), the subgradient set (2.2) is often nonconvex (e., ∂ϕ(0) = {−1, 1} for ϕ(x) = −|x|) while enjoying a full calculus based 6 on variational/extremal principles, which replace separation arguments in the absence of convexity.

We need also another first-order subdifferential construction for ϕ : Rn → R finite at x̄, which is complemented to (2.2) in the case of non-Lipschitzian functions. The singu- lar/horizon subdifferential of ϕ at x̄ is defined by ∂ ∞ ϕ(x̄) := Lim sup λ∂ϕ(x).3) ϕ x→x̄ λ↓0 We know that ∂ ∞ ϕ(x̄) = {0} if and only if ϕ is locally Lipschitzian around x̄, provided that it is lower semicontinuous (l.) around this point. Recall further some constructions of variational geometry needed in what follows and 6 Ω ⊂ Rn , consider its associated with the subdifferential ones defined above. Given a set ∅ = indicator function δ(x; Ω) equal to 0 for x ∈ Ω and to ∞ otherwise.

For any fixed x̄ ∈ Ω, the regular normal cone to Ω at x̄ is n hv, x − x̄i o N b (x̄; Ω) := ∂δ(x̄; b Ω) = v ∈ Rn lim sup ≤0 (2.4) Ω x→x̄ kx − x̄k and the (basic, limiting) normal cone to Ω at x̄ is N (x̄; Ω) := ∂δ(x̄; Ω). It follows from (2.4) that the normal cone N (x̄; Ω) admits the limiting representation N (x̄; Ω) = Lim sup N b (x; Ω) (2.5) Ω x→x̄ via the Painlevé-Kuratowski outer limit. Observe also the duality/polarity correspondence n o b (x̄; Ω) = T (x̄; Ω)∗ := v ∈ Rn hv, wi ≤ 0 for all w ∈ T (x̄; Ω) N (2.6) between the regular normal cone (2.