Marginal Analysis of Convex Optimization Problems with Set-Valued Inclusion Constraints
Amos Uderzo 1,∗ · 2024
Read Marginal Analysis of Convex Optimization Problems with Set-Valued Inclusion Constraints by Amos Uderzo 1,∗ (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-04155.txt.
Introduction
Amos Uderzo studies a class of optimization problems in a 2024 mathematics paper. Each problem asks for the best choice under constraints stated as set-valued inclusions, where the allowed set itself can shift. Such setups arise when cone constraints must hold robustly despite uncertain data.
Uderzo looks at how the best value of the problem changes as the inputs change. Under convexity assumptions and one global condition, he shows the value changes in a smooth, Lipschitz way. He then gives exact formulas for the subgradients of the value function. The paper also draws out what this stability means for calmness of the problem and for penalty methods.
Catalog record
| CREATOR | Amos Uderzo 1,∗ |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 60 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-04155
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Marginal Analysis of Convex Optimization Problems with Set-Valued Inclusion Constraints Amos Uderzo 1,∗ Abstract 1 Department of Mathematics and Applications, University of Milano-Bicocca, Milano (Italy) Abstract. In this paper, stability and sensitivity properties of a class of parametric constrained optimization problem, whose feasible region is defined by a set-valued inclusion, are investigated through the associated optimal value function. Set-valued inclusions are a kind of constraint system, which naturally emerges in contexts requiring the robust fulfilment of traditional cone constraints, where data are affected by uncertain elements having a non stochastic nature, or in (MPEC) as a vector equilibrium constraint, where feasible solutions are intended as equilibrium point in a strong sense. Under proper convexity assumptions on the objective function and the constraining set-valued term, combined with a global qualification condition, a class of parametric optimization problems is singled out, which displays a global Lipschitz behaviour. By employing recent results of variational analysis, elements for a sensitivity analysis of this class of problems are provided via exact subgradient formulae for the optimal value function. Further consequences of the stability behaviour are explored in terms of problem calmness and viability of penalization techniques. Keywords. Set-valued inclusions; C -concave multi-valued mappings; metric C -increase; parametric optimization; optimal value function; problem calmness; penalty function. 2020 Mathematics Subject Classification. 90C30, 90C31, 90C48. † † footnotetext: ∗ Corresponding author. E-mail address: [email protected] (A. Uderzo). 1. Introduction The present paper aims at bringing new insights into the study of the stability and sensitivity properties of parametric optimization problems with set-valued inclusion constraints. Stability and sensitivity issues for constrained optimization problems subject to parameter perturbations lie at the core of a well-recognized and very active area of variational analysis, often indicated as perturbation analysis of optimization problems (see [ 3 , 7 , 10 , 15 , 17 ] ). According to a deep-rooted approach to this topic, the two main objects of study are the optimal value (a.k.a. marginal or performance ) function associated with a class of parametric optimization problems and the (generally) multi-valued mapping collecting the optimal solutions (if any) of these problems, when the value of the parameter varies. Various qualitative and quantitative information describing how problems are conditioned by and react to changes in the parameter (e.g. solvability near reference values, closeness to known values, rate of changes and so on) can be grasped by analyzing these two objects. The investigations reported in the present paper focus on the analysis of the optimal value function, whereas the analysis of the solution mapping will be left for a future, specifically devoted, project of research. According to [ 17 , Chapter 4.6] it would not be an exaggeration to say that marginal functions manifest the essence of modern techniques in variational analysis involving perturbation and approximation procedures with the subsequent passing to the limit. The distinguishing feature of the optimization problems considered in the present paper consists in the fact that their constraints are expressed by parameterized set-valued inclusions. These lead to a constraint system format different from the generalized equation format typically occurring in the variational analysis literature, with its own geometry needing specifically devised tools to be adequately handled. Historically, to the best of the author’s knowledge, the appearance of such a constraint format can be traced back to [ 19 ] , where in order to address inexact linear programming problems feasible regions were considered, which are defined via ”set-containment”, so constraints are called there ”set-inclusive”. Subsequently, set-valued inclusions revealed to be a natural language to formalize the fulfilment of traditional cone constraints in the context of robust optimization, as it was introduced by A. Ben-Tal and A. Nemirovsky (see [ 5 , 6 ] ). Besides, they found further contexts of relevant application in vector optimization, in expressing ideal efficiency (see [ 23 ] ), and, more in general, in vector equilibrium theory, in formalizing the concept of strong solution to vector Ky-Fan inequalities (see [ 22 ] ). Let us consider the following class of parametric constrained optimization problems ({\sf P}_{p})\hskip 51.21504pt\begin{array}[]{cl}\displaystyle\min_{x\in\mathbb{X}}&\varphi(p,x)\\ \hbox{ sub }&F(p,x)\subseteq C,\end{array} where \varphi:\mathbb{P}\times\mathbb{X}\longrightarrow\mathbb{R} represents the objective function, \{\mathbf{0}\}\subsetneqq C\subsetneqq\mathbb{Y} is a (nontrivial) closed, convex cone, and F:\mathbb{P}\times\mathbb{X}\rightrightarrows\mathbb{Y} is a multi-valued mapping defining the set-valued inclusion problem, which formalizes the constraint system of the optimization problems. Throughout the paper, (\mathbb{P},\|\cdot\|) , (\mathbb{X},\|\cdot\|) , and (\mathbb{Y},\|\cdot\|) denote Banach spaces over the real field \mathbb{R} , with null vector \mathbf{0} . As should be clear, the variable p\in\mathbb{P} indicates the parameter subject to perturbation, while the variable x\in\mathbb{X} stands for the problem unknown. In the above setting, the (generally) multi-valued mapping {\sf R}:\mathbb{P}\rightrightarrows\mathbb{X} that describes the changes of the feasible region of ({\sf P}_{p}) , when the parameter p varies, is given by {\sf R}(p)=F^{+1}(p,\cdot)(C)=\{x\in X\ |\ F(p,x)\subseteq C\}, (1.1) where the notation F^{+1} (borrowed from [ 2 ] ) indicates one of the two possible manners to define the inverse image through the set-valued mapping F of a given subset of the range space, namely the core through F of that subset. The optimal value function {\sf val}:\mathbb{P}\longrightarrow\mathbb{R}\cup\{\pm\infty\} associated with the class of parametric constrained optimization problems ({\sf P}_{p}) takes the form {\sf val}(p)=\inf_{x\in{\sf R}(p)}\varphi(p,x), (1.2) while the problem solution set-valued mapping {\sf Argmin}:\mathbb{P}\rightrightarrows\mathbb{X} is given by {\sf Argmin}(p)=\{x\in{\sf R}(p)\ |\ \varphi(p,x)={\sf val}(p)\}. The investigations exposed in the present paper carry on the value analysis started in [ 20 ] , where several calmness properties of the marginal function {\sf val} have been established by employing various sufficient conditions for the local Lipschitz semicontinuity behaviour of {\sf R} . Although conducted within the same framework, the present analysis aims nonetheless at enlightening a different aspect of this topic. The idea triggering the investigations here contained relies on the expectation that much stronger global properties of {\sf val} can be obtained under suitable convexity assumptions on the problem data, which in [ 20 ] are completely disregarded. As one expects, convexity alone is not able to ensure those properties of {\sf val} , so its effects are studied in synergy with qualification conditions for set-valued inclusions, which are expressed in terms of C -increase behaviour of the set-valued term F . More precisely, it can be shown that convexity and Lipschitz continuity of {\sf val} can be achieved by applying a recently established result about the existence of continuous selection of {\sf R} . This leads to single out a class of problems ({\sf P}_{p}) , that will be called ”qualified convex optimization problems with set-valued inclusion constraints”, for which either {\sf val}\equiv-\infty or {\sf val} is convex and locally Lipschitz. The reader should notice that, in a finite-dimensional setting, this means that {\sf val} turns out to be smooth on \mathbb{P} , up to a (Lebesgue) residual subset. Furthermore, elements for the sensitivity analysis of ({\sf P}_{p}) are proposed by providing sharp estimates of the subgradient of {\sf val} , which are established by means of calculus rules for the Moreau-Rockafellar subdifferential and coderivative calculus for multifunctions with convex graph. The contents of the paper are arranged according to the following scheme. Section 2 collects all the technical tools, mainly coming from convex analysis and from the theory of set-valued inclusions, needed in the subsequent analysis. Section