Abstract
The present paper is devoted to the computation of the Lipschitz modulus of the optimal value function restricted to its domain in linear programming under different types of perturbations. In the first stage, we study separately perturbations of the right-hand side of the constraints and perturbations of the coefficients of the objective function. Secondly, we deal with canonical perturbations, i.e., right-hand side perturbations together with linear perturbations of the objective. We advance that an exact formula for the Lipschitz modulus in the context of right-hand side perturbations is provided, and lower and upper estimates for the corresponding moduli are also established in the other two perturbation frameworks. In both cases, the corresponding upper estimates are shown to provide the exact moduli when the nominal (original) optimal set is bounded. A key strategy here consists in taking advantage of the background on calmness in linear programming and providing the aimed Lipschitz modulus through the computation of a uniform calmness constant.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Saaty, T., Gass, S.: Parametric objective function (part 1). J. Oper. Res. Soc. Am. 2, 316–319 (1954)
Gass, S., Saaty, T.: Parametric objective function (part 2)-generalization. J. Oper. Res. Soc. Am. 3, 395–401 (1955)
Nožička, F., Guddat, J., Hollatz, H., Bank, B.: Theorie der Linearen Parametrischen Optimierung. Akademie-Verlag, Berlin (1974)
Bank, B., Guddat, J., Klatte, D., Kummer, B., Tammer, K.: Non-Linear Parametric Optimization. Akademie-Verlag, Berlin (1982). and Birkhäuser, Basel (1983)
Klatte, D.: Lineare Optimierungsprobleme mit Parametern in der Koeffizientenmatrix der Restriktionen. In: Lommatzsch, K. (ed.) Anwendungen der Linearen Parametrischen Optimierung, pp. 23–53. Akademie-Verlag, Berlin (1979)
Wets, R.J.-B.: On the continuity of the value of a linear program and of related polyhedral-valued multifunctions. Math. Progr. Study 24, 14–29 (1985)
Dantzig, G.B., Folkman, J., Shapiro, N.: On the continuity of the minimum set of a continuous function. J. Math. Anal. Appl. 17, 519–548 (1967)
Dontchev, A., Zolezzi, T.: Well-Posed Optimization Problems. Lecture Notes in Mathematics, vol. 1543. Springer, Berlin (1993)
Kummer, B.: Globale Stabilität quadratischer Optimierungsprobleme. Wiss. Zeitschrift der Humboldt-Universität zu Berlin. Math.-Nat. R. XXVI(5), 565-569 (1977)
Robinson, S.M.: Stability theory for systems of inequalities. Part I: linear systems. SIAM J. Numer. Anal. 12, 754–769 (1975)
Robinson, S.M.: Some continuity properties of polyhedral multifunctions. Math. Progr. Study 14, 206–214 (1981)
Walkup, D.W., Wets, R.J.-B.: A Lipschitzian characterization of convex polyhedra. Proc. Am. Math. Soc. 20, 167–173 (1969)
Cánovas, M.J., López, M.A., Parra, J., Toledo, F.J.: Lipschitz continuity of the optimal value via bounds on the optimal set in linear semi-infinite optimization. Math. Oper. Res. 31, 478–489 (2006)
Gisbert, M.J., Cánovas, M.J., Parra, J., Toledo, F.J.: Calmness of the optimal value in linear programming. SIAM J. Optim. 3, 2201–2221 (2018)
Goberna, M.A., López, M.A.: Linear Semi-Infinite Optimization. Wiley, Chichester (1998)
Renegar, J.: Some perturbation theory for linear programming. Math. Program. 65A, 73–91 (1994)
Renegar, J.: Linear programming, complexity theory and elementary functional analysis. Math. Program. 70, 279–351 (1995)
Li, W.: Sharp Lipschitz constants for basic optimal solutions and basic feasible solutions of linear programs. SIAM J. Control Optim. 32, 140–153 (1994)
Dontchev, A.L., Rockafellar, R.T.: Implicit Functions and Solution Mappings: A View from Variational Analysis. Springer, New York (2009)
Klatte, D., Kummer, B.: Nonsmooth equations in optimization: regularity, calculus, methods and applications. In: Pardalos, P. (ed.) Nonconvex Optimization Application, vol. 60. Kluwer Academic, Dordrecht (2002)
Mordukhovich, B.S.: Variational Analysis and Generalized Differentiation, I: Basic Theory. Springer, Berlin (2006)
Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis. Springer, Berlin (1998)
Cánovas, M.J., Klatte, D., López, M.A., Parra, J.: Metric regularity in convex semi-infinite optimization under canonical perturbations. SIAM J. Optim. 18, 717–732 (2007)
Cánovas, M.J., Gómez-Senent, F.J., Parra, J.: On the Lipschitz modulus of the argmin mapping in linear semi-infinite optimization. Set-Val. Var. Anal. 16, 511–538 (2008)
Cánovas, M.J., Dontchev, A.L., López, M.A., Parra, J.: Metric regularity of semi-infinite constraint systems. Math. Prog. Ser. B 104, 329–346 (2005)
Klatte, D.: Lipschitz continuity of infima and optimal solutions in parametric optimization: the polyhedral case. In: Guddat, J., Jongen, H.T., Kummer, B., Nožička, F. (eds.) Parametric Optimization and Related Topics, pp. 229–248. Akademie-Verlag, Berlin (1987)
Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton, NJ (1970)
Cánovas, M.J., López, M.A., Parra, J., Toledo, F.J.: Distance to ill-posedness and the consistency value of linear semi-infinite inequality systems. Math. Program. 103A, 95–126 (2005)
Acknowledgements
This research has been partially supported by project MTM2014-59179-C2-2-P and its associated grant BES-2015-073220, both from MINECO, Spain and FEDER, “Una manera de hacer Europa”, European Union. The authors wish to thank the referees for their suggestions and comments, which have improved the original version of the paper.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Gisbert, M.J., Cánovas, M.J., Parra, J. et al. Lipschitz Modulus of the Optimal Value in Linear Programming. J Optim Theory Appl 182, 133–152 (2019). https://doi.org/10.1007/s10957-018-01456-w
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10957-018-01456-w