On Differential Stability of a Class of Convex Optimization Problems

Nguyen Dong Yen, Duong Thi Viet An, Vu Thi Huong, Nguyen Ngoc Luan · 2024

Read On Differential Stability of a Class of Convex Optimization Problems by Nguyen Dong Yen, Duong Thi Viet An, Vu Thi Huong, Nguyen Ngoc Luan (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-11996.txt.

Introduction

Nguyen Dong Yen and co-authors sharpened results in 2024 on differential stability in convex optimisation. Their setting is parametric problems described by generalised polyhedral functions and set-valued maps. Prior work gave upper and lower estimates for two kinds of subdifferential of the best-value function.

The authors clarify how those upper and lower estimates relate. An example shows a lower estimate can be strict, falling short of the true value. Surprisingly, each upper estimate turns out to be an equality, giving exact formulas. When either the goal function or the constraint map is polyhedral, upper and lower estimates coincide as well.

Catalog record

CREATORNguyen Dong Yen, Duong Thi Viet An, Vu Thi Huong, Nguyen Ngoc Luan
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE41 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-11996

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On Differential Stability of a Class of Convex Optimization Problems Nguyen Dong Yen, Duong Thi Viet An, Vu Thi Huong, Nguyen Ngoc Luan Abstract The recent results of An, Luan, and Yen [Differential stability in convex optimization via generalized polyhedrality. Vietnam J. Math. https://-doi.org/10.1007/s10013-024-00721-y] on differential stability of parametric optimization problems described by proper generalized polyhedral convex functions and generalized polyhedral convex set-valued maps are analyzed, developed, and sharpened in this paper. Namely, keeping the Hausdorff locally convex topological vector spaces setting, we clarify the relationships between the upper estimates and lower estimates for the subdifferential and the singular subdifferential of the optimal value function. As shown by an example, the lower estimates can be strict. But, surprisingly, each upper estimate is an equality. Thus, exact formulas for the subdifferential and the singular subdifferential under consideration are obtained. In addition, it is proved that each subdifferential upper estimate coincides with the corresponding lower estimate if either the objective function or the constraint set-valued map is polyhedral convex. ∎ MSC 49J27 49K40 90C25 90C30 90C31 1 Introduction Differential stability of convex optimization problems has been studied by many authors. Among the first results, we would like to refer to Theorem 29.1 from the classical book of Rockafellar R_1970 , where the subdifferential of the perturbation function of a convex program associated with a convex bifunction between two Euclidean spaces was computed via the set of the Kuhn-Tucker vectors. Since convex bifunctions can be considered as generalizations of set-valued maps (see ( R_1970 , p. 292) ), where instead of the indicator function of each value of the map one may have an extended-real-valued function, this theorem yields a formula for the subdifferential of the optimal value function of certain convex programs under inclusion constraints. Note that differential stability of convex optimization problems under inclusion constraints has received much attention from researchers. A formula for computing the subdifferential of the optimal value function of an optimization problem in Hilbert spaces, where the perturbations are canonical and the objective function is unperturbed, was obtained by Aubin ( Aubin_1998 , Problem 35 - Subdifferentials of Marginal Functions, p. 335) under a regularity condition. An analysis and extensions of the result were given by An and Yen AnYen2015 for optimization problems in Hausdorff locally convex topological vector spaces. More comprehensive results in this direction have been established by Mordukhovich et al. ( bmnrt2017 , Proposition 7.1 and Theorem 7.2) (see also Theorem 4.56 and the commentaries on p. 309 in the book by Mordukhovich and Nam bmn2022 ). Various results on differential stability of convex optimization problems under inclusion constraints and their applications to optimal control of discrete or continuous dynamical systems can be found in the books by Mordukhovich and Nam ( bmn , pp. 106–108) and ( bmn2022 , pp. 286–288) , and the papers An_Huong_Xu_2022 ; An_Jourani ; An_Toan_2018 ; An_Yao_2016 ; AnYaoYen2020 ; AnYen2018 ; Mahmudov_2018 ; bmnrt2017 ; Toan_Thuy_2021 ; Thuy_Toan_2016 . Interesting differential stability results for convex optimization problems via \varepsilon -subdifferential and infimal convolution of convex functions, are available in An_Gutierrez_2021 ; An_Kobis_Tuyen_2020 ; An_Yao_2019 ; Toan_2022 . In LuanKimYen_2022 , some results of AnYen2015 have been effectively used in the study of differential stability of parametric conic linear programming problems. Recently, the problem of computing or estimating the subdifferential of the optimal value function of a parametric optimization problem described by a proper generalized polyhedral convex function and a generalized polyhedral convex set-valued map has been considered by An et al. AnLuanYen_2023 . Using the Hausdorff locally convex topological vector spaces setting, the authors have obtained upper estimates and lower estimates for the subdifferential and the singular subdifferential of the optimal value function at a given parameter. The interested reader is referred to the paper by Luan and Yao LuanYao_2019 for a systematic investigation on the solution existence, optimality conditions, and duality theorems for generalized polyhedral convex optimization problems. Our purpose in the present paper is to solve Question 3 in AnLuanYen_2023 , which asks for examples justifying that each subdifferential estimate given there can be strict. First, we will have a closer look at the subdifferential upper and lower estimates provided in that paper. Then, we will construct a nontrivial example (see the proof of Theorem 3.2 below) to show that the lower estimates can be strict. Next, we will prove that each upper estimate given in AnLuanYen_2023 is an equality. By doing so, we get exact formulas for the subdifferential and the singular subdifferential of the optimal value function at a given parameter. Finally, for the case where either the objective function or the constraint set-valued mapping is polyhedral convex, it will be shown that each upper estimate coincides with the corresponding lower estimate. The organization of this paper is as follows. Basic definitions and some preliminaries are collected in Section 2 . Sections 3 and 4 address the above-mentioned open question from AnLuanYen_2023 . Section 5 considers differential stability under a polyhedral convexity assumption, and Section 6 gives some concluding remarks. 2 Basic Definitions and Preliminaries Let X and Y be real Hausdorff locally convex topological vector spaces. Denote the dual spaces of X and Y , respectively, by X^{*} and Y^{*} . For x^{*}\in X^{*} and x\in X , the value x^{*} at x is abbreviated to \langle x^{*},x\rangle . Let X^{*} and Y^{*} be equipped with the weak ∗ topology. Details about the latter concept can be found in ( bmn2022 , Definition 1.107 and Subsection 1.2.2) and ( Rudin_1991 , pp. 67–68) . For a subset C\subset X , by \overline{C} we denote the closure of C in the topology of X . Similarly, given a subset D\subset X^{*} , we let \overline{D} stand for the closure of D in the weak ∗ topology of X^{*} . The cone generated by C is defined by \mbox{\rm cone}\,C=\{tx\mid t\geq 0,x\in C\} . The extended real line is the set \overline{\mathbb{R}}:=\mathbb{R}\cup\{\pm\infty\} . One says that a set C in X is convex if (1-t)x+tu\in C for all x,u\in C and t\in[0,1] . The normal cone to a convex set C at \bar{x}\in C is defined by N(\bar{x};C)=\big\{x^{*}\in X^{*}\;\big|\;\langle x^{*},x-\bar{x}\rangle\leq 0\ \;\mbox{\rm for all }\;x\in C\big\}. For any \bar{x}\notin C , we put N(\bar{x};C)=\emptyset . The indicator function \delta(.;C) of a subset C\subset X is given by \delta(x;C)=0 for x\in C and \delta(x;C)=+\infty for x\in X\setminus C . Given a function f\colon X\to\overline{\mathbb{R}} , we define the epigraph and the effective domain of f respectively by \displaystyle\mbox{\rm epi}\,f=\big\{(x,\lambda)\in X\times\mathbb{R}\;\big|\;f(x)\leq\lambda\big\}\ \;\mbox{\rm and }\;\mbox{\rm dom}\,f=\big\{x\in X\;\big|\;f(x)<+\infty\big\}. If \mbox{\rm epi}\,f is a convex set in X\times\mathbb{R} , one says that f is a convex function . If \mbox{\rm dom}\,f\neq\emptyset and f(x)\neq-\infty for all x\in X , then f is called a proper function . Let f:X\rightarrow\overline{\mathbb{R}} be a convex function and \bar{x}\in X be such that f(\bar{x})\in\mathbb{R} . The subdifferential of f at \bar{x} is defined by \displaystyle\partial f(\bar{x})=\big\{x^{*}\in X^{*}\mid\langle x^{*},x-\bar{x}\rangle\leq f(x)-f(\bar{x}),\ \forall x\in X\big\}. The singular subdifferential of f at \bar{x} is the set \displaystyle\partial^{\infty}f(\bar{x}):=\big\{x^{*}\in X^{*}\mid(x^{*},0)\in N((\bar{x},f(\bar{x}));{\rm{epi}}\,f)\big\}. We put \partial f(\bar{x})=\emptyset and \partial^{\infty}f(\bar{x})=\emptyset if either \bar{x}\notin{\rm dom}\,f or f(\bar{x})=-\infty . Proposition 1 (See ( AnYen2015 , Proposition 4.2) ) If f:X\rightarrow\overline{\mathbb{R}} is a convex function, then

Read the complete text