[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Optimization over the Pareto outcome set associated with a convex bi-objective optimization problem: theoretical results, deterministic algorithm and application to the stochastic case

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

Abstract

Our paper consists of two main parts. In the first one, we deal with the deterministic problem of minimizing a real valued function \(f\) over the Pareto outcome set associated with a deterministic convex bi-objective optimization problem (BOP), in the particular case where \(f\) depends on the objectives of (BOP), i.e. we optimize over the Pareto set in the outcome space. In general, the optimal value \(U\) of such a kind of problem cannot be computed directly, so we propose a deterministic outcome space algorithm whose principle is to give at every step a range (lower bound, upper bound) that contains \(U\). Then we show that for any given error bound, the algorithm terminates in a finite number of steps. In the second part of our paper, in order to handle also the stochastic case, we consider the situation where the two objectives of (BOP) are given by expectations of random functions, and we deal with the stochastic problem \((S)\) of minimizing a real valued function \(f\) over the Pareto outcome set associated with this Stochastic bi-objective Optimization Problem (SBOP). Because of the presence of random functions, the Pareto set associated with this type of problem cannot be explicitly given, and thus it is not possible to compute the optimal value \(V\) of problem \((S)\). That is why we consider a sequence of Sample Average Approximation problems (SAA-\(N\), where \(N\) is the sample size) whose optimal values converge almost surely to \(V\) as the sample size \(N\) goes to infinity. Assuming \(f\) nondecreasing, we show that the convergence rate is exponential, and we propose a confidence interval for \(V\). Finally, some computational results are given to illustrate the paper.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

References

  1. An, L.T.H., Muu, L.D., Tao, P.D.: Numerical solution for optimization over the efficient set by d.c. optimization algorithms. Oper. Res. Lett. 19, 117–128 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  2. Benson, H.P.: Optimization over the efficient set. J. Math. Anal. Appl. 98, 562–580 (1984)

    Article  MATH  MathSciNet  Google Scholar 

  3. Benson, H.P., Lee, D.: Outcome-based algorithm for optimizing over the efficient set of a bicriteria linear programming problem. J. Optim. Theory Appl. 88, 77–105 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  4. Benson, H.P.: Generating the efficient outcome set in multiple objective linear programs: the bicriteria case. Acta Math. Vietnam. 22, 29–51 (1997)

    MATH  MathSciNet  Google Scholar 

  5. Benson, H.P.: Further analysis of an outcome set-based algorithm for multiple objective linear programming. J. Optim. Theory Appl. 97, 1–10 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  6. Benson, H.P.: Hybrid approach for solving multiple objective linear programs in outcome space. J. Optim. Theory Appl. 98, 17–35 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  7. 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. Global Optim. 13, 1–24 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  8. Benson, H.P.: A finite, non-adjacent extreme point search algorithm for optimization over the efficient set. J. Optim. Theory Appl. 73, 47–64 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  9. Bolintinéanu, S.: Optimality conditions for minimization over the (weakly or properly) efficient set. J. Math. Anal. Appl. 173(2), 523–541 (1993)

  10. Bolintinéanu, S.: Necessary conditions for nonlinear suboptimization over the weakly-efficient set. J. Optim. Theory Appl. 78, 579–598 (1993)

  11. Bolintinéanu, S.: Minimization of a quasi-concave function over an efficient set. Math. Program. 61, 89–110 (1993)

    Article  MATH  Google Scholar 

  12. Bolintinéanu, S.: Necessary conditions for nonlinear suboptimization over the weakly-efficient set. J. Optim. Theory Appl. 78, 579–598 (1993)

  13. Bonnel, H., Collonge, J.: Stochastic optimization over a pareto set associated with a stochastic multi-objective optimization problem. J. Optim. Theory Appl. (2013). doi:10.1007/s10957-013-0367-8

  14. Bonnel, H., Kaya, C.Y.: Optimization over the efficient set of multi-objective control problems. J. Optim. Theory Appl. 147(1), 93–112 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  15. Craven, B.D.: Aspects of multicriteria optimization. In: Recent Developments in Mathematical Programming, pp. 93–100 (1991)

  16. Dauer, J.P.: Optimization over the efficient set using an active constraint approach. J. Oper. Res. 35, 185–195 (1991)

    MATH  MathSciNet  Google Scholar 

  17. Dauer, J.P., Fosnaugh, T.A.: Optimization over the efficient set. J. Global Optim. 7, 261–277 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  18. Eichfelder, G.: Adaptative Scalarization Methods in Multiobjective Optimization. Springer, Berlin (2008)

    Book  Google Scholar 

  19. Ehrgott, M.: Multicriteria Optimization. Springer, Berlin (2000)

    Book  MATH  Google Scholar 

  20. Fliege, J., Xu, H.: Stochastic multiobjective optimization: sample average approximation and applications. J. Optim. Theory Appl. 151, 135–162 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  21. Fülöp, J.: A Cutting Plane Algorithm for Linear Optimization Over the Efficient Set, Generalized Convexity, Lecture Notes in Economics and Mathematical System 405. Springer, Berlin (1994)

    Google Scholar 

  22. Göpfert, A., Riahi, H., Tammer, C., Zălinescu, C.: Variational Methods in Partially Ordered Spaces. Springer, Berlin (2003)

    MATH  Google Scholar 

  23. Chen, G.-Y., Huang, X., Yang, X.: Vector Optimization: Set Valued and Variational Analysis. Springer, Berlin (2005)

    Google Scholar 

  24. Horst, R., Thoai, N.V.: Maximizing a concave function over the efficient or weakly-efficient set. Eur. J. Oper. Res. 117, 239–252 (1999)

    Article  MATH  Google Scholar 

  25. Horst, R., Thoai, N.V., Yamamoto, Y., Zenke, D.: On optimization over the efficient set in linear multicriteria programming. J. Optim. Theory Appl. 134, 433–443 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  26. Jacod, J., Protter, P.: Probability Essentials. Springer, Berlin (2004)

    Book  Google Scholar 

  27. Jahn, J.: Vector Optimization. Springer, Berlin (2004)

    Book  MATH  Google Scholar 

  28. Kim, N.T.B., Thang, T.N.: Optimization over the efficient set of a bicriteria convex programming problem. Pac. J. Optim. 9, 103–115 (2013)

    MATH  MathSciNet  Google Scholar 

  29. Konno, H., Thach, P.T., Yokota, D.: Dual approach to minimization on the set of Pareto-optimal solutions. J. Optim. Theory Appl. 88, 689–707 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  30. Konno, H., Inori, M.: Bond portfolio optimization by bilinear fractional programming. J. Oper. Res. Soc. Jpn. 32, 143–158 (1989)

    MATH  MathSciNet  Google Scholar 

  31. Luc, D.T.: Theory of Vector Optimization, Lecture Notes in Economics and Mathematical Systems 319. Springer, Berlin (1989)

    Google Scholar 

  32. Miettinen, K.M.: Nonlinear Multiobjective Optimization. Kluwer, Dordrecht (1998)

    Book  Google Scholar 

  33. Philip, J.: Algorithms for the vector maximization problem. Math. Program, vol. 2, pp. 207–229 (1972)

  34. Shapiro, A., Dentcheva, D., Ruszczynski, A.: Lectures on Stochastic Programming: Modeling and Theory. MPS/SIAM, Ser. Optim (2009)

  35. Shapiro, A., Xu, H.: Stochastic mathematical programs with equilibrium constraints, modeling and sample average approximation. Taylor Francis Group Optim. 57(3), 395–418 (2008)

    MATH  MathSciNet  Google Scholar 

  36. Yamamoto, Y.: Optimization over the efficient set: an overview. J. Global Optim. 22, 285–317 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  37. Yu, P.L.: Multiple-Criteria Decision Making. Plenum Press, New York (1985)

    Book  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. ERIM, University of New Caledonia, B.P. R4, 98851, Noumea Cedex, New Caledonia

    Henri Bonnel & Julien Collonge

Authors
  1. Henri Bonnel
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Julien Collonge
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Henri Bonnel.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Bonnel, H., Collonge, J. Optimization over the Pareto outcome set associated with a convex bi-objective optimization problem: theoretical results, deterministic algorithm and application to the stochastic case. J Glob Optim 62, 481–505 (2015). https://doi.org/10.1007/s10898-014-0257-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-014-0257-0

Keywords

Mathematics Subject Classification

Search

Navigation