Skip to main content
SpringerLink
Log in

Primal and dual approximation algorithms for convex vector optimization problems

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

Two approximation algorithms for solving convex vector optimization problems (CVOPs) are provided. Both algorithms solve the CVOP and its geometric dual problem simultaneously. The first algorithm is an extension of Benson’s outer approximation algorithm, and the second one is a dual variant of it. Both algorithms provide an inner as well as an outer approximation of the (upper and lower) images. Only one scalar convex program has to be solved in each iteration. We allow objective and constraint functions that are not necessarily differentiable, allow solid pointed polyhedral ordering cones, and relate the approximations to an appropriate \(\epsilon \)-solution concept. Numerical examples are provided.

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.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

Notes

  1. by Konrad Polthier, http://www.javaview.de.

References

  1. Ararat, Ç, Hamel, A.H., Rudloff, B.: Set-valued shortfall and divergence risk measures. submitted (2013)

  2. Benson, H.P.: An outer approximation algorithm for generating all efficient extreme points in the outcome set of a multiple objective linear programming problem. J. Glob. Optim. 13, 1–24 (1998)

    Article  Google Scholar 

  3. Bremner, D., Fukuda, K., Marzetta, A.: Primal-dual methods for vertex and facet enumeration. Discrete Comput. Geom. 20(3), 333–357 (1998)

    Article  Google Scholar 

  4. Csirmaz L.: Using multiobjective optimization to map the entropy region of four random variables. Preprint http://eprints.renyi.hu/66/2/globopt.pdf (2013)

  5. CVX Research. Inc.: CVX: Matlab software for disciplined convex programming, version 2.0 beta., September 2012

  6. Ehrgott, M., Löhne, A., Shao, L.: A dual variant of Benson’s outer approximation algorithm. J. Glob. Optim. 52(4), 757–778 (2012)

    Article  Google Scholar 

  7. Ehrgott, M., Shao, L., Schöbel, A.: An approximation algorithm for convex multi-objective programming problems. J. Glob. Optim. 50(3), 397–416 (2011)

    Article  Google Scholar 

  8. Ehrgott, M., Wiecek, M. M.: Multiobjective Programming. In: Figueira, J., Greco, S., Ehrgott, M., (eds.) Multiple Criteria Decision Analysis: State of the Art Surveys. Springer Science + Business Media, Berlin, pp. 667–722 (2005)

  9. Grant, M., Boyd, S.: Recent advances in learning and control, chapter Graph implementations for nonsmooth convex programs. Lecture Notes in Control and Information Sciences. Springer, Berlin, pp. 95–110 (2008)

  10. Hamel, A.H., Löhne, A.: Lagrange duality in set optimization. J. Optim. Theory Appl. (2013). doi:10.1007/s10957-013-0431-4

    Google Scholar 

  11. Hamel, A.H., Löhne, A., Rudloff, B.: A Benson type algorithm for linear vector optimization and applications. J. Glob. Optim. (2013). doi:10.1007/s10898-013-0098-2

    Google Scholar 

  12. Hamel, A.H., Rudloff, B., Yankova, M.: Set-valued average value at risk and its computation. Math. Financ. Econ. 7(2), 229–246 (2013)

    Article  Google Scholar 

  13. Heyde, F.: Geometric duality for convex vector optimization problems. J. Convex Anal. 20(3), 813–832 (2013)

    Google Scholar 

  14. Heyde, F., Löhne, A.: Geometric duality in multiple objective linear programming. SIAM J. Optim. 19(2), 836–845 (2008)

    Article  Google Scholar 

  15. Heyde, F., Löhne, A.: Solution concepts in vector optimization: a fresh look at an old story. Optimization 60(12), 1421–1440 (2011)

    Article  Google Scholar 

  16. Jahn, J.: Vector Optimization: Theory, Applications, and Extensions. Springer, Berlin (2004)

    Book  Google Scholar 

  17. Kabanov, Y.M.: Hedging and liquidation under transaction costs in currency markets. Financ. Stoch. 3, 237–248 (1999)

    Article  Google Scholar 

  18. Löhne, A.: Vector Optimization with Infimum and Supremum. Springer, Berlin (2011)

    Book  Google Scholar 

  19. Löhne, A., Rudloff, B.: An algorithm for calculating the set of superhedging portfolios in markets with transaction costs. Int. J. Theor. Appl. Finance. (to appear)

  20. Luc, D.: Theory of vector optimization. In: Lecture Notes in Economics and Mathematical Systems, vol. 319. Springer, Berlin (1989)

  21. Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970)

    Google Scholar 

  22. Ruzika, S., Wiecek, M.M.: Approximation methods in multiobjective programming. J. Optim. Theory Appl. 126(3), 473–501 (2005)

    Article  Google Scholar 

  23. Shao, L., Ehrgott, M.: Approximately solving multiobjective linear programmes in objective space and an application in radiotherapy treatment planning. Math. Methods Oper. Res. 68(2), 257–276 (2008)

    Article  Google Scholar 

  24. Shao, L., Ehrgott, M.: Approximating the nondominated set of an MOLP by approximately solving its dual problem. Math. Methods Oper. Res. 68(3), 469–492 (2008)

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Martin-Luther-Universität Halle-Wittenberg, NWF II, 06099 , Halle (Saale), Germany

    Andreas Löhne

  2. Department of Operations Research and Financial Engineering, Princeton University, Princeton, NJ, 08544, USA

    Birgit Rudloff & Firdevs Ulus

  3. Bendheim Center for Finance, Princeton University, Princeton, NJ, 08544, USA

    Birgit Rudloff

Authors
  1. Andreas Löhne
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Birgit Rudloff
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Firdevs Ulus
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Birgit Rudloff.

Additional information

B. Rudloff: Research supported by NSF award DMS-1007938.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Löhne, A., Rudloff, B. & Ulus, F. Primal and dual approximation algorithms for convex vector optimization problems. J Glob Optim 60, 713–736 (2014). https://doi.org/10.1007/s10898-013-0136-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-013-0136-0

Keywords

Search

Navigation