Skip to main content
SpringerLink
Log in

Continuous Selection and Unique Polyhedral Representation of Solutions to Convex Parametric Quadratic Programs

  • Published:
Journal of Optimization Theory and Applications Aims and scope Submit manuscript

Abstract

A method for obtaining continuous solutions to convex quadratic and linear programs with parameters in the linear part of the objective function and right-hand side of the constraints is presented. For parameter values for which the problem has nonunique solutions, the optimizer with the least Euclidean norm is selected. The normal cone optimality condition is utilized to obtain a unique polyhedral representation of the piecewise affine minimizer function.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Similar content being viewed by others

References

  1. Baotić, M.: An efficient algorithm for multi-parametric quadratic programming. Report AUT02-05, Institut für Automatik, ETH Zürich (2002)

  2. Bemporad, A., Morari, M., Dua, V., Pistikopoulos, E.N.: The explicit linear quadratic regulator for constrained systems. Automatica 38, 3–20 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  3. Seron, M.M., Goodwin, G.C., De Doná, J.A.: Characterization of receding horizon control for constrained linear systems. Asian J. Control 5, 271–286 (2003)

    Article  Google Scholar 

  4. Tøndel, P., Johansen, T.A., Bemporad, A.: An algorithm for multiparametric quadratic programming and explicit MPC solutions. Automatica 39, 489–497 (2003)

    Article  MATH  Google Scholar 

  5. Tøndel, P., Johansen, T.A., Bemporad, A.: Further results on multiparametric quadratic programming, In: Proceedings of the IEEE CDC, pp. 3173–3178, 2003

  6. Grieder, P., Borrelli, F., Torrisi, F., Morari, M.: Computation of the constrained infinite time linear quadratic regulator. Automatica 40, 701–708 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  7. Borrelli, F., Bemporad, A., Morari, M.: A geometric algorithm for multiparametric linear programming. J. Optim. Theory Appl. 118, 515–540 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  8. Gal, T., Nedoma, J.: Multiparametric linear programming. Manag. Sci. 18, 406–422 (1972)

    Article  MATH  MathSciNet  Google Scholar 

  9. Fiacco, A.V.: Introduction to Sensitivity and Stability Analysis in Nonlinear Programming. Academic Press, Orlando (1983)

    MATH  Google Scholar 

  10. Zhao, J.: The lower continuity of optimal solution sets. J. Math. Anal. Appl. 207, 240–250 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  11. Bank, B., Guddat, J., Klatte, D., Kummer, B., Tammer, K.: Non-linear Parametric Optimization. Birkhäuser, Berlin (1983)

    MATH  Google Scholar 

  12. Best, M.J., Ding, B.: On the continuity of the minimum in parametric quadratic programs. J. Opt. Theory Appl. 86, 245–250 (1972)

    Article  MathSciNet  Google Scholar 

  13. Hogan, W.W.: The continuity of the perturbation function of a convex program. Oper. Res. 21, 351–352 (1973)

    MATH  MathSciNet  Google Scholar 

  14. Hogan, W.W.: Point-to-set maps in mathematical programming. SIAM Rev. 15, 591–603 (1973)

    Article  MATH  MathSciNet  Google Scholar 

  15. Best, M.J., Chakravarti, N.: Stability of linearly constrained convex quadratic programs. J. Optim. Theory Appl. 64, 43–53 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  16. Phu, H.X., Yen, N.D.: On the stability of solutions to quadratic programming problems. Math. Program. 89, 385–394 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  17. Berge, C.: Topological Spaces. Oliver and Boyd Ltd., London (1963)

    MATH  Google Scholar 

  18. Dantzig, G.B., Folkman, J., Shapiro, N.Z.: On the continuity of the minimum set of a continuous function. J. Math. Anal. Appl. 17, 519–548 (1967)

    Article  MATH  MathSciNet  Google Scholar 

  19. Hausdorff, F.: Set Theory. Chelsea, New York (1957)

    MATH  Google Scholar 

  20. Michaels, E.: Continuous selections. Ann. Math. 63, 361–382 (1956)

    Article  Google Scholar 

  21. Bemporad, A., Borrelli, F., Morari, M.: Model predictive control based on linear programming—the explicit solution. IEEE Trans. Autom. Control 47, 1974–1985 (2002)

    Article  MathSciNet  Google Scholar 

  22. Spjøtvold, J., Tøndel, P., Johansen, T.A.: A method for obtaining continuous solutions to multiparametric linear programs. In: Proceedings of the IFAC World Congress, 2005

  23. Spjøtvold, J., Tøndel, P., Johansen, T.A.: Unique polyhedral representations of continuous selections for convex multiparametric quadratic programs. In: Proceedings of the American Control Conference, vol. 2, pp. 816–821, 2005

  24. Mayne, D.Q., Raković, S.V.: Optimal control of constrained piecewise affine discrete-time systems. J. Comput. Optim. Appl. 25, 167–191 (2003)

    Article  MATH  Google Scholar 

  25. Nocedal, J., Wright, S.J.: Numerical Optimization. Springer, New York (1999)

    MATH  Google Scholar 

  26. Bertsekas, D.P., Nedic, A., Ozdaglar, A.E.: Convex Analysis and Optimization. Athena Scientific, Belmont (2003)

    MATH  Google Scholar 

  27. Aubin, J.P., Frankowska, H.: Set-Valued Analysis. Birkhäuser, Boston (1990)

    MATH  Google Scholar 

  28. Berkelaar, A.B., Roos, K., Terlaky, T.: The optimal set and optimal partition approach. In: Gal, T., Greenberg, H.J. (eds.) Advances in Sensitivity Analysis and Parametric Programming, pp. 6.1–6.45. Kluwer Academic, Dordrecht (1997)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Engineering Cybernetics, Norwegian University of Science and Technology, Trondheim, Norway

    J. Spjøtvold & T. A. Johansen

  2. SINTEF ICT, Trondheim, Norway

    P. Tøndel

Authors
  1. J. Spjøtvold
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. P. Tøndel
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. T. A. Johansen
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to J. Spjøtvold.

Additional information

Communicated by D.Q. Mayne.

This research is part of the Strategic University Program on Computational Methods for Nonlinear Motion Control funded by the Research Council of Norway. We thank Dr. E.C. Kerrigan at the Department of Electrical Engineering, Imperial College, London and Dr. Colin Jones at ETH Zürich for their comments. Finally, we thank the anonymous reviewers for their comments.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Spjøtvold, J., Tøndel, P. & Johansen, T.A. Continuous Selection and Unique Polyhedral Representation of Solutions to Convex Parametric Quadratic Programs. J Optim Theory Appl 134, 177–189 (2007). https://doi.org/10.1007/s10957-007-9215-z

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10957-007-9215-z

Keywords

Search

Navigation