Luận án tiến sĩ: Tồn tại & ổn định nghiệm QHTP không lồi - Trần Văn Nghị, ĐHSPHN 2

MINISTRY OF EDUCATION AND TRAINING HANOI PEDAGOGICAL UNIVERSITY 2 TRAN VAN NGHI EXISTENCE AND STABILITY FOR QUADRATIC PROGRAMMING PROBLEMS WITH NON-CONVEX OBJECTIVE FUNCTION DOCTORAL DISSERTATION IN MATHEMATICS Hanoi, 2017 MINISTRY OF EDUCATION AND TRAINING HANOI PEDAGOGICAL UNIVERSITY 2 TRAN VAN NGHI EXISTENCE AND STABILITY FOR QUADRATIC PROGRAMMING PROBLEMS WITH NON-CONVEX OBJECTIVE FUNCTION Speciality: Analysis Speciality code: 62 46 01 02 DOCTORAL DISSERTATION IN MATHEMATICS Supervisor: Assoc. Nguyen Nang Tam Hanoi, 2017 Confirmation This dissertation has been written on the basis of my research works carried at Hanoi Pedagogical University 2, under the supervision of Assoc. Nguyen Nang Tam. The presented results have never been published by others.

The author Tran Van Nghi Acknowledgment I would like to express my deep gratitude to my supervisor, Assoc. Nguyen Nang Tam, for his careful and effective guidance. I would like to thank the board of directors of Hanoi Pedagogical University 2, for providing me with pleasant working conditions. I am grateful to the leaders of Department of Mathematics, and my colleagues, for granting me various financial supports and/or constant help during the four years of my PhD study.

Last but not least, I wish to express my endless gratitude to my grandparents, my parents and also to my brother for their unconditional and unlimited love and support. My special gratitude goes to my wife for her love and encouragement. I dedicate this work as a spiritual gift to my children. Contents Table of Notations iii Introduction 1 1 Existence of solutions 7 1.

A Frank-Wolfe type theorem. An Eaves type theorem. 20 2 Stability for global, local and stationary solution sets 21 2. Continuity of the global optimal solution map.

Assumptions and auxiliary results. Upper semicontinuity of the global optimal solu- tion map. Lower semicontinuity of the global optimal solu- tion map. Semicontinuity of the local optimal solution map.

Stability of stationary solutions. Upper semicontinuity of the stationary solution map 31 2. A result on stability of stationary solutions. 41 3 Continuity and directional differentiability of the optimal value function 42 3.

Continuity of the optimal value function. First-order directional differentiability. Second-order directional differentiability. 73 4 Stability for extended trust region subproblems 74 4.

Some stability results for parametric ETRS. Continuity of the stationary solution map. Continuity of the optimal value function. ETRS with a linear inequality constraint.

Lower semicontinuity of the stationary solution map 86 4. Coderivatives of the normal cone mapping. 121 General Conclusions 123 List of Author’s Papers 124 References 124 ii Table of Notations (P ) the optimization problem LP linear programming N LP nonlinear programming QP quadratic programming LCQP linearly constrained quadratic programming QCQP quadratically constrained quadratic programming T RS trust region subproblem ET RS extended trust region subproblem VI variational inequality AV I affine variational inequality EAV I extended affine variational inequality (QP (p)) the QCQP problem depending on the parameter p F(p) the feasible region of (QP (p)) L(p) the local optimal solution set of (QP (p)) IL(p) the isolated local optimal solution set of (QP (p)) G(p) the global optimal solution set of (QP (p)) S(p) the stationary solution set of (QP (p)) KKT Karush-Kuhn-Tucker L(x, p, λ) the Lagrange function of (QP (p)) Λ(x̄, p) the set of all Lagrange multipliers corresponding to x̄ (V I(F, S)) the VI depending on the function F and the S (V I(p)) the VI depending on the parametric p (ETm (w)) the extended trust region subproblem depending on the parametric w iii SCQ Slater Constraint Qualification M F CQ Mangasarian-Fromovitz Constraint Qualification (M F RC)p0 the Mangasarian-Fromovitz Regularity Condition un- der direction p0 LICQ Linear Independence Constraint Qualification I(x̄, p) the active constraint index set of (QP (p)) at x̄ R the real set Rn the n-dimensional Euclidean space Rn×n S the space of real symmetric (n × n)–matrices Rn×n S+ the set of positive semidefinite real symmetric (n×n)– matrices Rn+ {(x1 ,. , xn ) ∈ Rn : xi ≥ 0, i = 1,.

, n} xT y or hx, yi the scalar product of vectors x, y kxk the Euclidean norm of a vector x domF effective domain of F gphF graph of F Lim sup limit in the sence Painlevé-Kuratowski AT the transposed matrix of A Nb (x̄; Ω) Fréchet normal cone of Ω at x̄ N (x̄; Ω) Mordukhovich normal cone of Ω at x̄ b ∗ F (x̄, ȳ)(·) D Fréchet coderivative of F at (x̄, ȳ) D∗ F (x̄, ȳ)(·) Mordukhovich coderivative of F at (x̄, ȳ) C x −→ x̄ x → x̄ and x ∈ C α ↓ ᾱ α → ᾱ and α ≥ ᾱ α ↑ ᾱ α → ᾱ and α ≤ ᾱ 0+ C the recession cone of C ϕ0 (p, p0 ) first-order directional derivative at p in direction p0 N ull(Q) {x ∈ Rn : Qx = 0} pos{a, b} {θa + γb : θ ≥ 0, γ ≥ 0} S∗ {x ∈ Rn : y T x ≥ 0 ∀y ∈ S} iv Introduction Optimization concerns the analysis and the solution of problems in order to find the best elements in a given set. It is an important and very successful area of the applied mathematics. Applications of optimization are expanding and diverse. Among the most popular areas of applica- tion, we should mention as follows: engineering, statistics, economics, computer science, management sciences, and mathematics itself.

Op- timization problem arises in approximation theory, probability theory, structure design, chemical process control, routing in telecommunica- tion networks, image reconstruction, experiment design, radiation ther- apy, asset valuation, portfolio management, supply chain management, facility location, and others. Generally, an optimization problem (P ) can be stated very simply as follows. We have a given set C and a real-valued function f on C. The problem is to find a point x̄ ∈ C such that f (x̄) ≤ f (x) for all x ∈ C.

Then, C is called the feasible set or the constraint region, and the function f is called the objective function. Normally, C is defined by a system of equations and inequalities, which we call constraints. If C = Rn then we call the problem (P ) to be the unconstrained optimization problem. We say that (P ) is the constrained problem if C is a strict subset of the space Rn (i., C ⊂ Rn and C 6= Rn ).

A feasible vector x̄ ∈ C is called a global solution of (P ) if f (x̄) 6= +∞ and f (x̄) ≤ f (x) for all x ∈ C. We say that x̄ is a local solution of (P ) if f (x̄) 6= +∞ and there exists a neighborhood U of x̄ such that f (x̄) ≤ f (x) for all x ∈ C ∩ U. The set 1 of all the global solutions (resp., the local solutions) of (P ) is denoted by (G(P )) (resp. The optimization theory includes various fields such as integer, stochastic, linear, nonlinear, convex, nonconvex, smooth, nonsmooth op- timization, optimal control, semi-infinite programming, ect,.

T here have been several main directions of research including: existence of solutions, optimality conditions, sensitivity analysis, duality theory and numerical methods. The most popular constrained optimization problem is the linear programming (LP) problems, in which the objective function is a linear function and the constraint set is defined by finitely many linear equa- tions and inequalities. If the objective function or some of the equations or inequalities defining the feasible set are nonlinear, the optimization problem is called the nonlinear programming (NLP) problem. In this case, the specific techniques and theoretical results of LP cannot be di- rectly applied, and a more general approach is needed.

Quadratic programming (QP) problems constitute a special class of NLP problems. Numerous problems in real world applications, including problems in planning and scheduling, economies of scale, engineering de- sign, and control are naturally expressed as QP problems. One also uses QP problems in order to approximate NLP problems. The importance of QP was presented by Floudas and Visweswaran [33].

Many important research results for linearly constrained quadratic programming (LCQP) problems can be found in Lee et al. [56] and the references cited therein. Since the finite dimensional LCQP problems have been rather comprehensively investigated, several authors are now interested in studying quadratically constrained non-convex quadratic programming (QCQP) problems. The study of QCQP problems originated in 1951 by Kuhn and Tucker [55], if not earlier.

These problems have been of great inter- 2 ests to the researchers in theory and practice. Besides the theoretical importance, QCQP problems are of wide applications. In numerical op- timization, at each iteration of the trust region method, a QP problem with one elliptic constraint is solved as a subproblem in order to find a moving direction. This subproblem is a special case of QCQP and is known as the trust region subproblem (TRS).

In binary integer program- ming problems, the integer requirements can be formulated as quadratic constraints. In statistics, the linear regression model minimizes an un- constrained quadratic function which is a special case of QCQP. On qualitative properties of QCQP problems, one often concerns solution existence, optimal conditions, sensitivity analysis and stability. The solution existence of QP problems is one of the most impor- tant issues.

In 1956, Frank and Wolfe [34] extended the fundamental existence of linear programming by proving that an arbitrary quadratic function f attains its minimum over a nonempty convex polyhedral set C provided that f is bounded from below over C (called Frank-Wolfe Theorem). From then to now, there have been some other proofs for this theorem and its extended versions. Belousov [12, Chapter II, Section 4, Theorem 13] and Terlaky [105] proved the following result: A QP problem has a solution if its objective function is convex and bounded below over a nonempty constraint set defined by convex quadratic func- tions. Detailed proofs of this result can be found in [13,66].

In 1999, Luo and Zhang [66, Theorem 2] proved that a QP problem has a solution if its objective function is bounded below over a nonempty constraint set defined by a convex quadratic function and linear constraint functions. They also showed [66, Example 2, p. 94] that there exists a nonconvex QP problem in R4 with two convex quadratic constraints whose objective function is bounded from below over a nonempty constraint set, which has no solutions. Belousov and Klatte [13, p.

45] observed that the effect of nonconvexity of the objective function can be seen in R3. Bertsekas 3 and Tseng [14] proved the solution existence of a QP problem when all the asymptotic directions of constraint set are retractive local hori- zon directions and the objective function is bounded below constraint set. Tuy and Tuan [106] established some important results on the solu- tion existence for nonconvex QP problems. Given a quadratic function and a convex quadratic constraint set, verifying whether the function is bounded from below on the set is a rather difficult task.

Eaves [31] dis- cussed another fundamental existence theorem (called Eaves Theorem) for LCQP problems which gives us a tool for dealing with the task. Eaves Theorem presented verifiable necessary and sufficient conditions for the solution existence of LCQP problems. By using the concept of recession cone in convex analysis, Lee et al. [61] established an Eaves type Theo- rem for convex QCQP problems.

Up to now, many researchers have been studying sufficient conditions for the solution existence of a nonconvex QP problem whose constraint set is defined by finitely many quadratic inequalities. Stability for parametric QCQP problems plays an important role because they can be used for analyzing algorithms for solving this prob- lem. For convex QP problems, Best et al.