Luận án tính ổn định của một số hệ ràng buộc và bài toán tối ưu

VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY INSTITUTE OF MATHEMATICS DUONG THI KIM HUYEN STABILITY OF SOME CONSTRAINT SYSTEMS AND OPTIMIZATION PROBLEMS DISSERTATION SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF DOCTOR OF PHILOSOPHY IN MATHEMATICS HANOI - 2019 VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY INSTITUTE OF MATHEMATICS DUONG THI KIM HUYEN STABILITY OF SOME CONSTRAINT SYSTEMS AND OPTIMIZATION PROBLEMS Speciality: Applied Mathematics Speciality code: 9 46 01 12 DISSERTATION FOR THE DEGREE OF DOCTOR OF PHILOSOPHY IN MATHEMATICS Supervisor: Prof. NGUYEN DONG YEN HANOI - 2019 Confirmation This dissertation was written on the basis of my research works carried out at the Institute of Mathematics, Vietnam Academy of Science and Technology, under the guidance of Prof. Nguyen Dong Yen. All results presented in this dissertation have never been published by others.

Hanoi, October 2, 2019 The author Duong Thi Kim Huyen i Acknowledgment I still remember very well the first time I have met Prof. Nguyen Dong Yen at Institute of Mathematics. On that day I attended a seminar of Prof. Hoang Tuy about Global Optimization.

At the end of the seminar, I came to talk with Prof. Nguyen Dong Yen. I said to him that I wanted to learn about Optimization Theory, and I asked him to let me be his student. He did say yes.

A few days later, he sent me an email and he informed me that my master thesis would be about “openness of set-valued maps and implicit multifunction theorems”. Three years later, I defensed successfully my master thesis under his guidance at Institute of Mathematics, Vietnam Academy of Science and Technology. I would say I am deeply indebted to him not only for his supervision, encouragement and support in my research, but also for his precious advices in life. The Institute of Mathematics is a wonderful place for studying and work- ing.

I would like to thank all the staff members of the Institute who have helped me to complete my master thesis and this work within the schedules. I also would like to express my special appreciation to Prof. Hoang Xuan Phu, Assoc. Ta Duy Phuong, Assoc.

Phan Thanh An, and other members of the weekly seminar at Department of Numerical Analysis and Scientific Computing, Institute of Mathematics, as well as all the mem- bers of Prof. Nguyen Dong Yen’s research group for their valuable comments and suggestions on my research results. I greatly appreciate Dr. Pham Duy Khanh and Dr.

Nguyen Thanh Qui, who have helped me in typing my master thesis when I was pregnant with my first baby, and encouraged me to pursue a PhD program. I would like to thank Prof. Le Dung Muu, Prof. Nguyen Xuan Tan, Assoc.

Truong Xuan Duc Ha, Assoc. Nguyen Nang Tam, Assoc. Nguyen Thi Thu Thuy, and Dr. Le Hai Yen, for their careful ii readings of the first version of this dissertation and valuable comments.

Financial supports from the Vietnam National Foundation for Science and Technology Development (NAFOSTED) are gratefully acknowledged. I am sincerely grateful to Prof. Jen-Chih Yao from Department of Applied Mathematics, National Sun Yat-sen University, Taiwan, and Prof. Ching- Feng Wen from Research Center for Nonlinear Analysis and Optimization, Kaohsiung Medical University, Taiwan, for granting several short-termed scholarships for my doctorate studies.

I would like to thank Prof. Xiao-qi Yang for his supervision during my stay at Department of Applied Math- ematics, Hong Kong Polytechnic University, Hong Kong, by the Research Student Attachment Program. I would like to show my appreciation to Prof. Boris Mordukhovich from Department of Mathematics, Wayne State University, USA, and Ass.

Tran Thai An Nghia from Department of Mathematics and Statistics, Oak- land University, USA, for valuable comments and encouragement on my re- search works. My enormous gratitude goes to my husband and my son for their love, en- couragement, and especially for their patience during the time I was working intensively to complete my PhD studies. Finally, I would like to express my love and thanks to my parents, my parents in law, my ant in law, and all my sisters and brothers for their strong encouragement and support. iii Contents Table of Notation vi Introduction viii Chapter 1.1 Basic Concepts from Variational Analysis .2 Properties of Multifunctions and Implicit Multifunctions .3 An Overview on Implicit Function Theorems for Multifunctions 5 Chapter 2.

Linear Constraint Systems under Total Perturba- tions 8 2.1 An Introduction to Parametric Linear Constraint Systems .2 The Solution Maps of Parametric Linear Constraint Systems .3 Stability Properties of Generalized Linear Inequality Systems .4 The Solution Maps of Linear Complementarity Problems .5 The Solution Maps of Affine Variational Inequalities. Linear Constraint Systems under Linear Perturba- tions 35 3.1 Stability properties of Linear Constraint Systems under Linear Perturbations .2 Solution Stability of Linear Complementarity Problems under Linear Perturbations .3 Solution Stability of Affine Variational Inequalities under Lin- ear Perturbations. Sensitivity Analysis of a Stationary Point Set Map under Total Perturbations 59 4.3 Lipschitzian Stability of the Stationary Point Set Map .4 The Robinson Stability of the Stationary Point Set Map .5 Applications to Quadratic Programming .6 Results Obtained by Another Approach .7 Proof of Lemma 4.8 Proof of Lemma 4. 100 General Conclusions 101 List of Author’s Related Papers 102 References 103 Index 110 v Table of Notations R the set of real numbers R̄ the set of extended real numbers ∅ the empty set Rn the n-dimensional Euclidean vector space hx, yi the scalar product in an Euclidean space ||x|| the norm of a vector x B(x, ρ) the open ball centered x with radius ρ B̄(x, ρ) the closed ball centered x with radius ρ BX the open unit ball of X N (x̄) the family of the neighborhoods of x̄ Rn+ the nonnegative orthant in Rn Rn− the nonpositive orthant in Rn Rm×n the vector space of m × n real matrices detA the determinant of matrix A AT the transpose of matrix A ker A the kernel of matrix A (i., the null space of the operator corresponding to matrix A) E the unit matrix rank C the rank of matrix C C0 a negative semidefinite matrix X∗ the dual space of a Banach space X X ∗∗ the dual space of X ∗ A∗ : Y ∗ → X ∗ the adjoint operator of a bounded linear operator A : X → Y d(x, Ω) the distance from x to a set Ω Nb (x̄; Ω) or N bΩ (x̄) the Fréchet normal cone of Ω at x̄ N (x̄; Ω) or NΩ (x̄) the Mordukhovich normal cone of Ω at x̄ Ω x −→ x̄ x → x̄ and x ∈ Ω vi Limsup the Painlevé-Kuratowski upper limit ∇f (x̄) the Fréchet derivative of f : X → Y at x̄ ∇2 f (x̄) the Hessian matrix of f : X → R at x̄ ∇x ψ(x̄, ȳ) the partial derivative of ψ : X × Y → Z in x at (x̄, ȳ) epif the epigraph of a function f : X → R ∂f (x) the Mordukhovich subdifferential of f at x ∂ ∞ f (x) the singular subdifferential of f at x ∂ 2 f (x̄, ȳ) the second-order subdifferential of f at x̄ in direction ȳ ∈ ∂f (x̄) ∂x ψ(x̄, ȳ) the partial subdifferential of ψ : X × Y → R in x at (x̄, ȳ) g◦f the composite function of g and f F :X⇒Y a set-valued map between X and Y gph F the graph of F Db ∗ F (x̄, ȳ)(·) the Fréchet coderivative of F at (x̄, ȳ) D∗ F (x̄, ȳ)(·) the Mordukhovich coderivative of F at (x̄, ȳ) int D the topological interior of D L⊥ the orthogonal complement of a set L L∗ the polar cone of L cone D the cone generated by D resp.

respectively diag[Mαα , Mββ , Mγγ ] a block diagonal matrix LCP linear complementarity problem AVI affine variational inequality TRS the trust-region subproblem MFCQ The Mangasarian-Fromovitz Constraint Qualification vii Introduction Many real problems lead to formulating equations and solving them. These equations may contain parameters like initial data or control variables. The solution set of a parametric equation can be considered as a multifunction (that is, a point-to-set function) of the parameters involved. The latter can be called an implicit multifunction.

A natural question is that “What properties can the implicit multifunction possess?”. Under suitable differentiability assumptions, classical implicit function the- orems have addressed thoroughly the above question from finite-dimensional settings to infinite-dimensional settings. Nowadays, the models of interest (for instance, constrained optimization problems) outrun equations. Thus, Variational Analysis (see, e., [50, 80]) has appeared to meet the need of this increasingly strong development.

Zhu, and other authors, have studied implicit multifunctions and qualitative aspects of optimiza- tion and equilibrium problems by different approaches. In particular, with the two-volume book “Variational Analysis and Generalized Differentiation” (see [50, 51]) and a series of research papers, Mordukhovich has given basic tools (coderivatives, subdiffentials, normal cones, and calculus rules), funda- mental results, and advanced techniques for qualitative studies of optimiza- tion and equilibrium problems. Especially, the fourth chapter of the book is entirely devoted to such important properties of the solution set of paramet- ric problems as the Lipschitz stability and metric regularity. These properties indicate good behaviors of the multifunction in question.

The two models considered in that chapter of Mordukhovich’s book bear the names paramet- ric constraint system and parametric variational system. More discussions and references on implicit multifunction theorems can be found in the books viii by Borwein and Zhu [10], Dontchev and Rockafellar [19], and Klatte and Kummer [35]. Let us briefly review some contents of the book “Implicit Functions and Solution Mappings” [19] of Dontchev and Rockafellar. The first chapter of this book is devoted to functions defined implicitly by equations and the authors begin with classical inverse function theorem and classical implicit function theorem.

The book presents a very deep view from Variational Analysis on solution maps. The authors have investigated many properties of solution maps such as calmness, Lipschitz continuity, outer Lipschitz con- tinuity, Aubin property, metric regularity, linear openness, strong regularity and their applications to Numerical Analysis. The main tools that have been used in the book are graphical differentiation and coderivetive. Within this dissertation we use coderivative to study three properties of solution maps in finite-dimensional settings, which include Aubin property (Lipschitz-like property), metric regularity, and the Robinson stability of so- lution maps of constraint and variational systems.

Results on these stability properties are applied to studying the solution stability of linear comple- mentarity problem, affine variational inequalities, and a typical parametric optimization problem. Introduced by Aubin [5, p. 98] under the name pseudo-Lipschitz prop- erty, the Lipschitz-like property of multifunctions is a fundamental concept in stability and sensitivity analysis of optimization and equilibrium prob- lems. The Lipschitz-like property guarantees the local convergence of some variants of Newton’s method for generalized equations [12, 17, 19].

In partic- ular, from [19, Theorem 6C. 328] it follows that, if a mild approximation condition is satisfied and the solution map under right-hand-side perturba- tions is Lipschitz-like around a point in question, then there exists an iter- ative sequence Q-linearly converging to the solution. Moreover, as shown by Dontchev [17, Theorem 1], the Newton method applied to a generalized equation in a Banach space is locally convergent uniformly in the canonical parameter if and only if the solution map of this equation is Lipschitz-like around the reference point. In addition, if the derivative of the base map is locally Lipschitz, then the Lipschitz-likeness implies the existence of a Q- quadratically convergent Newton sequence (see [17, Theorem 2]).

Metric regularity (in the classical sense) is another fundamental property ix of set-valued mappings. We refer to the survey of A. Ioffe [32, 33] on this property and its applications.