Primal and dual approximation algorithms for convex vector optimization problems. (English) Zbl 1334.90160
Summary: 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.
Keywords:
vector optimization; multiple objective optimization; convex programming; duality; algorithms; outer approximationReferences:
| [1] | Ararat, Ç, Hamel, A.H., Rudloff, B.: Set-valued shortfall and divergence risk measures. submitted (2013) · Zbl 1396.91807 |
| [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) · Zbl 0908.90223 · doi:10.1023/A:1008215702611 |
| [3] | Bremner, D., Fukuda, K., Marzetta, A.: Primal-dual methods for vertex and facet enumeration. Discrete Comput. Geom. 20(3), 333-357 (1998) · Zbl 0910.68217 · doi:10.1007/PL00009389 |
| [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) · Zbl 1301.90083 |
| [5] | CVX Research. Inc.: CVX: Matlab software for disciplined convex programming, version 2.0 beta., September 2012 · Zbl 1093.90057 |
| [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) · Zbl 1245.90115 · doi:10.1007/s10898-011-9709-y |
| [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) · Zbl 1242.90210 · doi:10.1007/s10898-010-9588-7 |
| [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) · Zbl 1184.90161 |
| [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) · Zbl 1205.90223 |
| [10] | Hamel, A.H., Löhne, A.: Lagrange duality in set optimization. J. Optim. Theory Appl. (2013). doi:10.1007/s10957-013-0431-4 · Zbl 1308.90198 · doi:10.1007/s10957-013-0431-4 |
| [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 · Zbl 1330.90099 · doi:10.1007/s10898-013-0098-2 |
| [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) · Zbl 1269.91071 · doi:10.1007/s11579-013-0094-9 |
| [13] | Heyde, F.: Geometric duality for convex vector optimization problems. J. Convex Anal. 20(3), 813-832 (2013) · Zbl 1301.90083 |
| [14] | Heyde, F., Löhne, A.: Geometric duality in multiple objective linear programming. SIAM J. Optim. 19(2), 836-845 (2008) · Zbl 1173.90530 · doi:10.1137/060674831 |
| [15] | Heyde, F., Löhne, A.: Solution concepts in vector optimization: a fresh look at an old story. Optimization 60(12), 1421-1440 (2011) · Zbl 1258.90064 · doi:10.1080/02331931003665108 |
| [16] | Jahn, J.: Vector Optimization: Theory, Applications, and Extensions. Springer, Berlin (2004) · Zbl 1055.90065 · doi:10.1007/978-3-540-24828-6 |
| [17] | Kabanov, Y.M.: Hedging and liquidation under transaction costs in currency markets. Financ. Stoch. 3, 237-248 (1999) · Zbl 0926.60036 · doi:10.1007/s007800050061 |
| [18] | Löhne, A.: Vector Optimization with Infimum and Supremum. Springer, Berlin (2011) · Zbl 1230.90002 · doi:10.1007/978-3-642-18351-5 |
| [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) · Zbl 1293.91177 |
| [20] | Luc, D.: Theory of vector optimization. In: Lecture Notes in Economics and Mathematical Systems, vol. 319. Springer, Berlin (1989) · Zbl 1184.90161 |
| [21] | Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970) · Zbl 0193.18401 |
| [22] | Ruzika, S., Wiecek, M.M.: Approximation methods in multiobjective programming. J. Optim. Theory Appl. 126(3), 473-501 (2005) · Zbl 1093.90057 · doi:10.1007/s10957-005-5494-4 |
| [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) · Zbl 1211.90217 · doi:10.1007/s00186-008-0220-2 |
| [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) · Zbl 1184.90161 · doi:10.1007/s00186-007-0194-5 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
