Abstract
In this paper, we establish the equivalence between the half-space representation and the vertex representation of a smooth parametric semiclosed polyhedron. By virtue of the smooth representation result, we prove that the solution set of a smooth parametric piecewise linear program can be locally represented as a finite union of parametric semiclosed polyhedra generated by finite smooth functions. As consequences, we prove that the corresponding marginal function is differentiable and the solution map admits a differentiable selection.
Similar content being viewed by others
References
Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970)
Arrow, K.J., Barankin, E.W., Blackwell, D.: Admissible points of convex sets. In: Kuhn, H.W., Tucker, A.W. (eds.) Contribution to the Theory of Games, pp. 87–92. Princeton University Press, Princeton (1953)
Luc, D.T.: Smooth representation of a parametric polyhedral convex set with application to sensitivity in optimization. Proc. Am. Math. Soc. 125, 555–567 (1997)
Luc, D.T., Dien, P.H.: Differentiable selection of optimal solutions in parametric linear programming. Proc. Am. Math. Soc. 125, 883–892 (1997)
Yang, X.Q., Yen, N.D.: Structure and weak sharp minimum of the Pareto solution set for piecewise linear multiobjective optimization. J. Optim. Theory Appl. 147, 113–124 (2010)
Zheng, X.Y., Yang, X.Q.: The structure of weak Pareto solution sets in piecewise linear multiobjective optimization in normed spaces. Sci. China Ser. A 51, 1243–1256 (2008)
Zheng, X.Y.: Pareto solutions of polyhedral-valued vector optimization problems in Banach spaces. Set-Valued Anal. 17, 389–408 (2009)
Conn, A.R., Mongeau, M.: Discontinuous piecewise linear optimization. Math. Program. 80, 315–380 (1998)
Fang, Y.P., Meng, K.W., Yang, X.Q.: Piecewise linear multi-criteria programs: the continuous case and its discontinuous generalization. Oper. Res. 60(2), 398–404 (2012)
Bank, B., Guddat, J., Klatte, D., Kummer, B., Tammer, K.: Nonlinear Parametric Optimization. Academic Verlag, Berlin (1982)
Bonnans, J.F., Shapiro, A.: Perturbation Analysis of Optimization Problems. Springer, New York (2002)
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)
Dentcheva, D., Henrion, R., Ruszczyński, A.J.: Stability and sensitivity of optimization problems with first order stochastic dominance constraints. SIAM J. Optim. 18, 322–337 (2007)
Fiacco, A.V.: Introduction to Sensitivity and Stability Analysis in Nonlinear Programming. Academic Press, New York (1983)
Goberna, M.A., Terlaky, T., Todorov, M.I.: Sensitivity analysis in linear semi-infinite programming via partitions. Math. Oper. Res. 35, 14–26 (2001)
Hadigheh, A.G., Terlaky, T.: Sensitivity analysis in linear optimization: invariant support set intervals. Eur. J. Oper. Res. 169, 1158–1175 (2006)
Higle, J.L., Wallace, S.W.: Sensitivity analysis and uncertainty in linear programming. Interfaces 33, 53–60 (2003)
Hladík, M.: Multiparametric linear programming: support set and optimal partition invariancy. Eur. J. Oper. Res. 202, 25–31 (2010)
Heuts, R., Klein, J.: An (s,q) inventory model with stochastic and interrelated lead times. Nav. Res. Logist. 42, 839–859 (1995)
Kamimura, K., Nishimo, H.: An efficient method for determining economical configurations of elementary packet-switched networks. IEEE Trans. Commun. 39, 278–288 (1991)
Kim, D., Pardalos, P.M.: A solution approach to the fixed charge network flow problem using a dynamic slope scaling procedure. Oper. Res. Lett. 24, 195–203 (1999)
Kim, D., Pardalos, P.M.: Dynamic slope scaling and trust interval techniques for solving concave piecewise linear network flow problems. Networks 35, 216–222 (2000)
Young, M.R.: A minimax portfolio selection rule with linear programming solution. Manag. Sci. 44, 673–683 (1998)
Vielma, J.P., Keha, A.B., Nemhauser, G.L.: Nonconvex, lower semicontinuous piecewise linear optimization. Discrete Optim. 5, 467–488 (2008)
Ziegler, G.M.: Lectures on Polytopes. Springer, New York (1995)
Acknowledgements
The authors would like to thank the anonymous referees and the editor for their helpful comments and suggestions which have led to the improvement of the early version of this paper. This work was supported by the National Science Foundation of China (11001187, 108311009) and the Research Grants Council of Hong Kong (PolyU5306/11E).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Fang, Y.P., Huang, N.J. & Yang, X.Q. Local Smooth Representations of Parametric Semiclosed Polyhedra with Applications to Sensitivity in Piecewise Linear Programs. J Optim Theory Appl 155, 810–839 (2012). https://doi.org/10.1007/s10957-012-0089-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10957-012-0089-3