Set-valued Optimization

Set-valued optimization is a vibrant and expanding branch of applied mathematics that deals with optimization problems where the objective map and/or the constraint maps are set-valued maps acting between abstract spaces. Since the notion of set-valued maps subsumes single-valued maps, set-valued optimization provides an important generalization and unification of scalar as well as vector optimization problems. Therefore, this relatively new discipline has justifiably attracted a great deal of attention in recent years.

In this chapter, first, we give an introduction to order relations and cone properties. Then we present a detailed overview of solution concepts in vector-valued as well as set-valued optimization. We introduce and discuss the following solution concepts for set-valued optimization problems

In this chapter we present continuity notions for set-valued mappings and corresponding properties under convexity assumptions. Furthermore, we introduce Lipschitz properties for single-valued and set-valued maps. Concepts of generalized differentiability and corresponding calculus rules are recalled.

Tangent cones of first-order and tangent cones and tangent sets of higher-order play a very important role in set-valued optimization. For instance, derivatives and epiderivatives of set-valued maps are commonly defined by taking tangent cones and tangent sets of graphs and epigraphs of set-valued maps. Moreover, properties of tangent cones and tangent sets are quite decisive in giving calculus rules for derivatives and epiderivatives of set-valued maps. Furthermore, optimality conditions in set-valued optimization are also most conveniently expressed by using tangent cones and tangent sets. Sensitivity analysis, constraints qualifications, and many other issues in set-valued optimization heavily rely on tangent cones and tangent sets.

In this chapter we introduce nonlinear scalarization methods that are very important from the theoretical as well as computational point of view. We introduce different scalarizing functionals and discuss their properties, especially monotonicity, continuity, Lipschitz continuity, sublinearity, convexity. Using these nonlinear functionals we show nonconvex separation theorems. These nonlinear functionals are used for deriving necessary optimality conditions for solutions of set-valued optimization problems in Sect. 12.8 and in different proofs, especially in the proof minimal point theorems in Chap. 10. Moreover, we study characterizations of solutions of set-valued optimization problems by means of nonlinear scalarizing functionals. Finally, we present the extremal principle by Kruger and Mordukhovich and discuss its relationship to separation properties of nonconvex sets. This extremal principle will be applied in Sect. 12.9 for deriving a subdifferential variational principle for set-valued mappings and in Sect. 12.11 in order to prove a first order necessary condition for fully localized minimizers of set-valued optimization problems.

In this chapter we present a generalization of the Hahn–Banach–Kantorovich extension theorem to K-convex set-valued maps, as well as Yang’s extension theorem. We also present classical separation theorems for convex sets, the core convex topology on a linear space, and a criterion for the convexity of the cone generated by a set.

To each type of efficiency for optimization problems it is possible to associate notions of conjugate and subdifferential for vector valued functions or set-valued maps. In this chapter we study the conjugate and the subdifferential corresponding to the strong efficiency as well as the subdifferentials corresponding to the weak and Henig type efficiencies. For the strong conjugate and subdifferential we establish similar results to those in the convex scalar case, while for the other types of subdifferential we establish formulas for the subdifferentials of the sum and the composition of functions and set-valued maps.

In this chapter we present duality assertions for set-valued optimization problems in infinite dimensional spaces where the solution concept is based on vector approach, on set approach as well as on lattice approach. For set-valued optimization problems where the solution concept is based on vector approach we present conjugate duality statements. The notions of conjugate maps, subdifferential and a perturbation approach used for deriving these duality assertions are given. Furthermore, Lagrange duality for set-valued problems based on vector approach is shown. Moreover, we consider set-valued optimization problems where the solution concept is given by a set order relation introduced by Kuroiwa and derive corresponding saddle point assertions. For set-valued problems where the solution concept is based on lattice structure, we present duality theorems that are based on an consequent usage of infimum and supremum (in the sense greatest lower and least upper bounds with respect to a partial ordering). We derive conjugate duality assertions as well as Lagrange duality statements.

In this chapter we establish several existence results for minimal points with respect to transitive relations; then we apply them in topological vector spaces for quasiorders generated by convex cones. We continue with the presentation of several types of convex cones and compactness notions with respect to cones. We end the chapter with existence results for vector and set optimization problems.

In this chapter we present existence results for minimal points of subsets of the Cartesian product of a complete metric space and a topological vector space with respect to order relations determined by generalized set-valued metrics; such results are useful for deriving EVP type results for vector and scalar functions. Then we derive EVP results of Ha’s type as well as an EVP result for bi-set-valued maps. We end the chapter with an application to error bounds for set-valued optimization problems.

In set-valued optimization, derivatives, epiderivatives, and coderivatives of set-valued maps play the most fundamental role. We give optimality conditions by using derivatives, epiderivatives, and coderivatives. Sensitivity analysis is another important area where these objects are the building blocks. Numerical solutions of set-valued optimization problems are also computed by expressing optimality in terms of derivatives, epiderivatives, and coderivatives.

Let X and Y be normed spaces, let S ⊆ X be a nonempty set, let C ⊂ Y be a cone inducing a partial ordering in Y, and let \(F: X \rightrightarrows Y\) be a set-valued map.

Sensitivity analysis, the quantitative analysis of the perturbation map, is of paramount interest in optimization theory and has applications in several branches of pure and applied mathematics. During the last five decades, substantial progress has been made in sensitivity analysis for optimization problems with scalar objectives. On the other hand, the differentiability issues of the perturbation map for vector optimization problems and set optimization problems are rather involved and they require modern tools from variational analysis. The main difficulty here stems from the fact that the perturbation map for such problems is, in general, set-valued.

In this chapter we present solution procedures for solving set-valued optimization problems. In Sect. 14.1 a Newton method for solving general set-valued optimization problems is shown. For a special class of set-valued optimization problems where the objective map is polyhedral, convex and set-valued, we present an algorithm in Sect. 14.2.

Applying the duality assertions for set-valued problems given in Sect. 8.3 we derive duality statements for vector optimization problems in this section.