Sensitivity analysis and lipschitzian properties in linear optimization

Resumen

The objective of the present thesis is studying the stability of linear optimization problems through Lipschitzian constants. In other words, we intend to quantify the rate of variation, around a given solution, of the optimal value and the feasible set with respect to the variation of the parameters of the model. Therefore, our research may be situated in the fields of Optimization, Linear Programming and Variational Analysis. Specifically, Chapter 1 deals with the computation of formulae which provide measures of rates of variation (decrease and increase) of the optimal value associated with a finite linear problem under canonical perturbations of the data. It is worth mentioning that canonical perturbations are those that affect the vector of coefficients of the objective function and the independent terms (the right-hand-side) of the constraints. Formally, we want to compute (or estimate) the so-called calmness modulus as well as the calmness from below and above moduli. Chapter 2 focuses on the computation of the Lipschitz modulus of the same optimal value function in the previous parametric setting, i.e., finite linear optimization problems under canonical perturbations. These two first chapters can be included in the paradigmatic topic of Sensitivity Analysis as they are concerned with quantifying the stability of the optimal value of optimization problems. Chapter 3 aims to study the Lipschitz lower semicontinuity (Lipschitz-lsc, in brief) of the feasible set mapping. Roughly speaking, this property measures the rate of local contraction (in a neighborhood of a nominal solution fixed in advance) of the feasible set under perturbations of the data's problem. In this chapter there is a notable jump with respect to the previous ones in terms of the parametric context: we now work with linear optimization problems where there is not necessarily a finite number of constraints but the index set is arbitrary; in particular, it may be finite or infinite. In this last case, we deal with the Linear Semi-Infinite Programming. About the type of perturbations, besides perturbations of right-hand-side of the constraints, we also analyze the feasible set mapping under left-hand-side perturbations. Additionally, the study of Lipschitz-lsc has led to study, at the same time, other Lipschitzian property of lower semicontinuity which we have called Lipschitz lower semicontinuity-star (Lipschitz-lsc*, in brief). In addition to these three mentioned chapters, the manuscript contains an unnumbered section, Introduction (and its Spanish version), as a preamble, where we present the work and expose the objectives that we want to cover in this research as well as we comment how these are integrated in the literature. Then, we have included the preliminary Chapter 0 in order to detail the parametric framework, the notation, the used tools and the previous results needed on to achieve the proposed objectives. To end the work, we have created another unnumbered section, Conclusions and future work (and its Spanish version), where we summarize and remark the main contributions of our research and give some brief comments on future research lines.