Vector optimization

Last updated December 14, 2020

Vector optimization is a subarea of mathematical optimization where optimization problems with a vector-valued objective functions are optimized with respect to a given partial ordering and subject to certain constraints. A multi-objective optimization problem is a special case of a vector optimization problem: The objective space is the finite dimensional Euclidean space partially ordered by the component-wise "less than or equal to" ordering.

Problem formulation

In mathematical terms, a vector optimization problem can be written as:

C\operatorname {-} \min _{x\in S}f(x)

where $f:X\to Z$ for a partially ordered vector space $Z$ . The partial ordering is induced by a cone $C\subseteq Z$ . $X$ is an arbitrary set and $S\subseteq X$ is called the feasible set.

Solution concepts

There are different minimality notions, among them:

${\bar {x}}\in S$ is a weakly efficient point (weak minimizer) if for every $x\in S$ one has $f(x)-f({\bar {x}})\not \in -\operatorname {int} C$ .
${\bar {x}}\in S$ is an efficient point (minimizer) if for every $x\in S$ one has $f(x)-f({\bar {x}})\not \in -C\backslash \{0\}$ .
${\bar {x}}\in S$ is a properly efficient point (proper minimizer) if ${\bar {x}}$ is a weakly efficient point with respect to a closed pointed convex cone ${\tilde {C}}$ where $C\backslash \{0\}\subseteq \operatorname {int} {\tilde {C}}$ .

Every proper minimizer is a minimizer. And every minimizer is a weak minimizer.^[1]

Modern solution concepts not only consists of minimality notions but also take into account infimum attainment.^[2]

Solution methods

Benson's algorithm for linear vector optimization problems.^[2]

Relation to multi-objective optimization

Any multi-objective optimization problem can be written as

\mathbb {R} _{+}^{d}\operatorname {-} \min _{x\in M}f(x)

where $f:X\to \mathbb {R} ^{d}$ and $\mathbb {R} _{+}^{d}$ is the non-negative orthant of $\mathbb {R} ^{d}$ . Thus the minimizer of this vector optimization problem are the Pareto efficient points.

Related Research Articles

Distributions, also known as Schwartz distributions or generalized functions, are objects that generalize the classical notion of functions in mathematical analysis. Distributions make it possible to differentiate functions whose derivatives do not exist in the classical sense. In particular, any locally integrable function has a distributional derivative. Distributions are widely used in the theory of partial differential equations, where it may be easier to establish the existence of distributional solutions than classical solutions, or appropriate classical solutions may not exist. Distributions are also important in physics and engineering where many problems naturally lead to differential equations whose solutions or initial conditions are distributions, such as the Dirac delta function.

Mathematical optimization or mathematical programming is the selection of a best element from some set of available alternatives. Optimization problems of sorts arise in all quantitative disciplines from computer science and engineering to operations research and economics, and the development of solution methods has been of interest in mathematics for centuries.

In mathematics, specifically in topology, the interior of a subset $S$ of a topological space $X$ is the union of all subsets of $S$ that are open in $X$ . A point that is in the interior of $S$ is an interior point of $S$ .

Hilbert's Nullstellensatz is a theorem that establishes a fundamental relationship between geometry and algebra. This relationship is the basis of algebraic geometry, a branch of mathematics. It relates algebraic sets to ideals in polynomial rings over algebraically closed fields. This relationship was discovered by David Hilbert who proved the Nullstellensatz and several other important related theorems named after him.

In mathematics, tropical geometry is the study of polynomials and their geometric properties when addition is replaced with minimization and multiplication is replaced with ordinary addition:

Convex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets. Many classes of convex optimization problems admit polynomial-time algorithms, whereas mathematical optimization is in general NP-hard.

In mathematics, hyperfunctions are generalizations of functions, as a 'jump' from one holomorphic function to another at a boundary, and can be thought of informally as distributions of infinite order. Hyperfunctions were introduced by Mikio Sato in 1958 in Japanese,, building upon earlier work by Laurent Schwartz, Grothendieck and others.

In mathematical optimization theory, duality or the duality principle is the principle that optimization problems may be viewed from either of two perspectives, the primal problem or the dual problem. The solution to the dual problem provides a lower bound to the solution of the primal (minimization) problem. However in general the optimal values of the primal and dual problems need not be equal. Their difference is called the duality gap. For convex optimization problems, the duality gap is zero under a constraint qualification condition.

The envelope theorem is a result about the differentiability properties of the value function of a parameterized optimization problem. As we change parameters of the objective, the envelope theorem shows that, in a certain sense, changes in the optimizer of the objective do not contribute to the change in the objective function. The envelope theorem is an important tool for comparative statics of optimization models.

In mathematics, a cardinal function is a function that returns cardinal numbers.

Bilevel optimization is a special kind of optimization where one problem is embedded (nested) within another. The outer optimization task is commonly referred to as the upper-level optimization task, and the inner optimization task is commonly referred to as the lower-level optimization task. These problems involve two kinds of variables, referred to as the upper-level variables and the lower-level variables.

In mathematics, Maass forms or Maass wave forms are studied in the theory of automorphic forms. Maass forms are complex-valued smooth functions of the upper half plane, which transform in a similar way under the operation of a discrete subgroup $of as modular forms. They are Eigenforms of the hyperbolic Laplace Operator defined on and satisfy certain growth conditions at the cusps of a fundamental domain of . In contrast to the modular forms the Maass forms need not be holomorphic. They were studied first by Hans Maass in 1949.$

In mathematics, the Pettis integral or Gelfand–Pettis integral, named after Israel M. Gelfand and Billy James Pettis, extends the definition of the Lebesgue integral to vector-valued functions on a measure space, by exploiting duality. The integral was introduced by Gelfand for the case when the measure space is an interval with Lebesgue measure. The integral is also called the weak integral in contrast to the Bochner integral, which is the strong integral.

A sum-of-squares optimization program is an optimization problem with a linear cost function and a particular type of constraint on the decision variables. These constraints are of the form that when the decision variables are used as coefficients in certain polynomials, those polynomials should have the polynomial SOS property. When fixing the maximum degree of the polynomials involved, sum-of-squares optimization is also known as the Lasserre hierarchy of relaxations in semidefinite programming.

In discrete mathematics, ideal lattices are a special class of lattices and a generalization of cyclic lattices. Ideal lattices naturally occur in many parts of number theory, but also in other areas. In particular, they have a significant place in cryptography. Micciancio defined a generalization of cyclic lattices as ideal lattices. They can be used in cryptosystems to decrease by a square root the number of parameters necessary to describe a lattice, making them more efficient. Ideal lattices are a new concept, but similar lattice classes have been used for a long time. For example cyclic lattices, a special case of ideal lattices, are used in NTRUEncrypt and NTRUSign.

In functional analysis, a branch of mathematics, the algebraic interior or radial kernel of a subset of a vector space is a refinement of the concept of the interior. It is the subset of points contained in a given set with respect to which it is absorbing, i.e. the radial points of the set. The elements of the algebraic interior are often referred to as internal points.

In mathematical optimization, the perturbation function is any function which relates to primal and dual problems. The name comes from the fact that any such function defines a perturbation of the initial problem. In many cases this takes the form of shifting the constraints.

Benson's algorithm, named after Harold Benson, is a method for solving multi-objective linear programming problems and vector linear programs. This works by finding the "efficient extreme points in the outcome set". The primary concept in Benson's algorithm is to evaluate the upper image of the vector optimization problem by cutting planes.

Regularized least squares (RLS) is a family of methods for solving the least-squares problem while using regularization to further constrain the resulting solution.

Multi-objective linear programming is a subarea of mathematical optimization. A multiple objective linear program (MOLP) is a linear program with more than one objective function. An MOLP is a special case of a vector linear program. Multi-objective linear programming is also a subarea of Multi-objective optimization.

References

↑ Ginchev, I.; Guerraggio, A.; Rocca, M. (2006). "From Scalar to Vector Optimization" (PDF). Applications of Mathematics. 51: 5. doi:10.1007/s10492-006-0002-1.
1 2 Andreas Löhne (2011). Vector Optimization with Infimum and Supremum. Springer. ISBN 9783642183508.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[scalar2vector-1] Ginchev, I.; Guerraggio, A.; Rocca, M. (2006). "From Scalar to Vector Optimization" (PDF). Applications of Mathematics. 51: 5. doi:10.1007/s10492-006-0002-1.

[Lohne-2] 1 2 Andreas Löhne (2011). Vector Optimization with Infimum and Supremum. Springer. ISBN 9783642183508.

[1]

[2]