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

Advertisement

Springer Nature Link
Log in

Decision uncertainty in multiobjective optimization

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

Abstract

In many real-world optimization problems, a solution cannot be realized in practice exactly as computed, e.g., it may be impossible to produce a board of exactly 3.546 mm width. Whenever computed solutions are not realized exactly but in a perturbed way, we speak of decision uncertainty. We study decision uncertainty in multiobjective optimization problems and we propose the concept of decision robust efficiency for evaluating the robustness of a solution in this case. This solution concept is defined by using the framework of set-valued maps. We prove that convexity and continuity are preserved by the resulting set-valued maps. Moreover, we obtain specific results for particular classes of objective functions that are relevant for solving the set-valued problem. We furthermore prove that decision robust efficient solutions can be found by solving a deterministic problem in case of linear objective functions. We also investigate the relationship of the proposed concept to other concepts in the literature.

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. Aubin, J., Frankowska, H.: Set-Valued Analysis. Birkhäuser, Boston (1990)

    MATH  Google Scholar 

  2. Avigad, G., Branke, J.: Embedded evolutionary multi-objective optimization for worst case robustness. In: Proceedings of the 10th Annual Conference on Genetic and Evolutionary Computation. GECCO ’08, pp. 617–624. ACM, New York (2008)

  3. Barrico, C., Antunes, C.: Robustness analysis in multi-objective optimization using a degree of robustness concept. In: IEEE Congress on Evolutionary Computation. CEC 2006, pp. 1887–1892. IEEE Computer Society, Washington (2006)

  4. Bayer, H.G., Sendhoff, B.: Robust optimization—a comprehensive survey. Comput. Methods Appl. Mech. Eng. 196(33–34), 3190–3218 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  5. Ben-Tal, A., Ghaoui, L.E., Nemirovski, A.: Robust Optimization. Princeton University Press, Princeton (2009)

    Book  MATH  Google Scholar 

  6. Ben-Tal, A., Hertog, D.D.: Immunizing conic quadratic optimization problems against implementation errors. CentER working paper series 2011-060 (2011)

  7. Ben-Tal, A., Nemirovski, A.: Robust optimization—methodology and applications. Math. Program. 92(3), 453–480 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  8. Benoist, J., Popovici, N.: Characterizations of convex and quasiconvex set-valued maps. Math. Methods Oper. Res. 57(3), 427–435 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  9. Bertsimas, D., Nohadani, O.: Robust optimization with simulated annealing. J. Glob. Optim. 48(2), 323–334 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  10. Bertsimas, D., Nohadani, O., Teo, K.M.: Robust optimization in electromagnetic scattering problems. J. Appl. Phys. 101(7), 074507 (2007)

    Article  Google Scholar 

  11. Bertsimas, D., Nohadani, O., Teo, K.M.: Nonconvex robust optimization for problems with constraints. INFORMS J. Comput. 22(1), 44–58 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  12. Bertsimas, D., Nohadani, O., Teo, K.M.: Robust optimization for unconstrained simulation-based problems. Oper. Res. 58(1), 161–178 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  13. Castellani, F., Krüger, C., Geldermann, J., Schöbel, A.: Peat and pots: resource efficiency by decision robust efficiency. Working paper (2017)

  14. Terzijska, D., Porcelli, M., Eichfelder, G.: Multi-objective optimization in the Lorentz force velocimetry framework. In: Book of Digests and Program/OIPE, International Workshop on Optimization and Inverse Problems in Electromagnetism, vol. 13, pp. 81–82. Delft (2014)

  15. Das, I.: Nonlinear multicriteria optimization and robust optimality. Ph.D. thesis, Rice University (1997)

  16. Deb, K., Gupta, H.: Introducing robustness in multi-objective optimization. Evol. Comput. 14(4), 463–494 (2006)

    Article  Google Scholar 

  17. Delahaye, J., Denel, J.: The continuities of the point-to-set maps, definitions and equivalences. Math. Program. Study 10, 8–12 (1979)

    Article  Google Scholar 

  18. Durea, M.: On the existence and stability of approximate solutions of perturbed vector equilibrium problems. J. Math. Anal. Appl. 333(2), 1165–1179 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  19. Ehrgott, M., Ide, J., Schöbel, A.: Minmax robustness for multi-objective optimization problems. Eur. J. Oper. Res. 239, 17–31 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  20. Eichfelder, G., Jahn, J.: Vector optimization problems and their solution concepts. In: Ansari, Q.H., Yao, J.C. (eds.) Recent Developments in Vector Optimization, pp. 1–27. Springer, Berlin (2012)

    Google Scholar 

  21. Fliege, J., Werner, R.: Robust multiobjective optimization & applications in portfolio optimization. Eur. J. Oper. Res. 234(2), 422–433 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  22. Georgiev, P., Luc, D., Pardalos, P.: Robust aspects of solutions in deterministic multiple objective linear programming. Eur. J. Oper. Res. 229(1), 29–36 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  23. Goberna, M.A., Jeyakumar, V., Li, G., Vicente-Pérez, J.: Robust solutions of multiobjective linear semi-infinite programs under constraint data uncertainty. SIAM J. Optim. 24(3), 1402–1419 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  24. Ha, T., Jahn, J.: New order relations in set optimization. J. Optim. Theory Appl. 148, 209–236 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  25. Ide, J., Köbis, E., Kuroiwa, D., Schöbel, A., Tammer, C.: The relationship between multi-objective robustness concepts and set valued optimization. Fixed Point Theory Appl. 2014, 83 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  26. Ide, J., Schöbel, A.: Robustness for uncertain multi-objective optimization: a survey and analysis of different concepts. OR Spectr. 38(1), 235–271 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  27. Jahn, J.: Vector Optimization, 2nd edn. Springer, Berlin (2011)

    Book  MATH  Google Scholar 

  28. Jahn, J.: A derivative-free descent method in set optimization. Comput. Optim. Appl. 60(2), 393–411 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  29. Khan, A., Tammer, C., Zălinescu, C.: Set-Valued Optimization—An Introduction with Applications. Springer, Berlin (2015)

    MATH  Google Scholar 

  30. Kuroiwa, D.: Convexity for set-valued maps. Appl. Math. Lett. 9(2), 97–101 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  31. Kuroiwa, D.: The natural criteria in set-valued optimization. RIMS Kokyuroku 1031, 85–90 (1998)

    MathSciNet  MATH  Google Scholar 

  32. Kuroiwa, D., Lee, G.M.: On robust multiobjective optimization. Vietnam J. Math. 40(2&3), 305–317 (2012)

    MathSciNet  MATH  Google Scholar 

  33. Kutateladze, S.: Convex \(\varepsilon \)-programming. Sov. Math. Dokl. 20(2), 391–393 (1979)

    MATH  Google Scholar 

  34. Lewis, A.: Robust regularization. Technical report, School of ORIE, Cornell University, Ithaca, NY (2002). http://people.orie.cornell.edu/aslewis/publications/2002.html

  35. Lewis, A., Pang, C.: Lipschitz behavior of the robust regularization. SIAM J. Control Optim. 48(5), 3080–3105 (2009)

    Article  MathSciNet  MATH  Google Scholar 

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

    Book  MATH  Google Scholar 

  37. Miettinen, K.: Nonlinear Multiobjective Optimization, vol. 12. Springer, Berlin (2012)

    MATH  Google Scholar 

  38. Nieuwenhuis, J.: Supremal points and generalized duality. Optimization 11(1), 41–59 (1980)

    MathSciNet  MATH  Google Scholar 

  39. Rodríguez-Marín, L., Sama, M.: \((\Lambda, C)\)-contingent derivatives of set-valued maps. J. Math. Anal. Appl. 335, 974–989 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  40. Rudin, W.: Functional Analysis, 2nd edn. McGraw-Hill Inc, New York (1991)

    MATH  Google Scholar 

  41. Stinstra, E., den Hertog, D.: Robust optimization using computer experiments. Eur. J. Oper. Res. 191(3), 816–837 (2008)

    Article  MATH  Google Scholar 

  42. Wiecek, M.M., Dranichak, G.M.: Robust multiobjective optimization for decision making under uncertainty and conflict, chap. 4. In: INFORMS, pp. 84–114 (2016)

Download references

Acknowledgements

The authors thank Professor Margaret Wiecek for her valuable comments on the paper. Furthermore, the authors thank two anonymous referees for their helpful and detailed remarks.

Author information

Authors and Affiliations

  1. Technische Universität Ilmenau, Ilmenau, Germany

    Gabriele Eichfelder

  2. University of Goettingen, Göttingen, Germany

    Corinna Krüger & Anita Schöbel

Authors
  1. Gabriele Eichfelder
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Corinna Krüger
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Anita Schöbel
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Corinna Krüger.

Additional information

Supported by DFG RTG 1703 “Resource Efficiency in Corporate Networks”.

Appendix: An example for monotonic objective functions

Appendix: An example for monotonic objective functions

This example illustrates Theorem 27 and shows that, after having excluded a specific part of the decision robust feasible set, all decision robust efficient solutions can be determined by Theorem 27.

Example 4

Let the feasible set, the perturbation set and the objective function be

$$\begin{aligned}&\varOmega = conv \left\{ \left( {\begin{matrix} 0 \\ 0 \end{matrix}}\right) , \left( {\begin{matrix} 1.5 \\ 0 \end{matrix}}\right) , \left( {\begin{matrix} 1.5 \\ 1 \end{matrix}}\right) , \left( {\begin{matrix} 1 \\ 1 \end{matrix}}\right) \right\} , \quad Z= [0,0.5]\times \{0\} \\ \text {and}\qquad&f:\mathbb {R}^2\rightarrow \mathbb {R}^2,\quad x\mapsto \left( {\begin{matrix} -(x_1+x_2) \\ x_1^2+x_2^2 \end{matrix}}\right) . \end{aligned}$$

Then \(f_1\) is strongly decreasing and \(f_2\) is strongly increasing on \(\mathbb {R}^2_+\) and therefore also on the decision robust feasible subset X of \(\varOmega \), which is illustrated in Fig. 4.

We show next that the set of decision robust [\(\cdot \)/strictly] efficient solutions is

$$\begin{aligned} Y=conv \left\{ \left( {\begin{matrix} 0 \\ 0 \end{matrix}}\right) , \left( {\begin{matrix} 1 \\ 1 \end{matrix}}\right) \right\} . \end{aligned}$$

We first show that the elements of \(X\backslash Y\) can not be decision robust efficient.

For all \(s\in (0,2)\) we define the set \(L_s=\{x\in X\ | \ x_1+x_2=s\}\) and \(y^s=\frac{1}{2}\cdot \left( {\begin{matrix} s \\ s \end{matrix}}\right) \in L_s\), which is illustrated in Fig. 5.

Let \(s\in (0,2)\) and let \(x\in L_s\backslash \{y^s\}\). Then \(x_1>x_2\) and there exists \(0<t\le \frac{s}{2}\) such that \(x_1=\frac{s}{2}+t\) and \(x_2=\frac{s}{2}-t\). For each \(z\in Z\) it holds

$$\begin{aligned} f_1(x+z) = -(x_1+x_2+z_1) = -(s + z_1) = -\left( y^s_1 + y^s_2 + z_1\right) = f_1(y^s + z) \end{aligned}$$

as well as

$$\begin{aligned} f_2(y^s +z) = \frac{s^2}{2} + s\cdot z_1 + z_1^2 \end{aligned}$$

and

$$\begin{aligned} f_2(x+z) = \underbrace{\frac{s^2}{2} + s\cdot z_1 + z_1^2}_{=f_2(y^s +z)} + \underbrace{2t^2}_{>0} + \underbrace{2tz_1}_{\ge 0} > f_2(y^s +z). \end{aligned}$$

Consequently, \(f(y^s+ z) \le f(x + z)\) for all \(z\in Z\). Since \(x\in L_s\) was arbitrarily chosen, we have for all \(x\in L_s\backslash \{y^s\}\)

$$\begin{aligned} f_Z(y^s) \subseteq f_Z(x)-\mathbb {R}^2_+\backslash \{0\}, \end{aligned}$$

which is visualized in Fig. 5. Hence, the set of decision robust [\(\cdot \)/strictly] efficient solutions is a subset of Y. Furthermore, because of the transitivity of \(\leqq \), every element in Y that is not decision robust [\(\cdot \)/strictly] efficient is dominated by another element of Y. Since Y and Z are totally ordered with respect to \(\leqq \), \(f_1\) is strongly de- and \(f_2\) is strongly increasing, Theorem 27 can be applied, leading to the conclusion that all \(y\in Y\) are decision robust [\(\cdot \)/strictly] efficient.

Fig. 4
figure 4

The feasible set \(\varOmega \) and the decision robust feasible set X in Example 4

Full size image
Fig. 5
figure 5

Illustration of Example 4. The sets Y and \(L_s\) for \(s=1\) are illustrated on the left hand side. On the right hand side, inclusions of the sets \(f_Z\) for different elements of \(L_1\) are displayed

Full size image

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Eichfelder, G., Krüger, C. & Schöbel, A. Decision uncertainty in multiobjective optimization. J Glob Optim 69, 485–510 (2017). https://doi.org/10.1007/s10898-017-0518-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-017-0518-9

Keywords