Generalized inequality

A generalized inequality (engl. Generalized inequality ) is a partial order on the , by means of a cone is defined and the a parent vector space makes. Generalized inequalities are used in the optimization in order to be able to compare points with one another in a meaningful way even in higher dimensions. In addition, with generalized inequalities one can generalize the concept of convex functions to vector-valued functions . ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle \mathbb {R} ^{n}}$

definition

Given is a closed, pointed and convex cone that has a non-empty interior. Then defined ${\displaystyle K}$

${\displaystyle x\preccurlyeq _{K}y{\text{ genau dann, wenn }}y-x\in K}$

a partial order . The cone thus contains all "positive" elements, that is, those for which applies. Analog can pass through ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle 0_{n}\preccurlyeq _{K}y}$

${\displaystyle x\prec _{K}y{\text{ genau dann, wenn }}y-x\in K^{\circ }}$

to define a strict partial order . Here is the inside of the cone. ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle K^{\circ }}$

The inequalities with respect to this partial order are called generalized inequalities (with respect to the partial order induced by the cone ). ${\displaystyle K}$

If the cone is too dual , then ( ) is called the ( ) dual (strict) partial order or dual generalized inequality. ${\displaystyle K^{*}}$ ${\displaystyle K}$ ${\displaystyle \preccurlyeq _{K^{*}}}$ ${\displaystyle \prec _{K^{*}}}$ ${\displaystyle \preccurlyeq _{K}}$ ${\displaystyle \prec _{K}}$

properties

The generalized inequality has the following properties: ${\displaystyle \preccurlyeq _{K}}$

• It is complete with regard to addition: is and , so is . ${\displaystyle a\preccurlyeq _{K}b}$ ${\displaystyle c\preccurlyeq _{K}d}$ ${\displaystyle a+c\preccurlyeq _{K}b+d}$
• It is closed with regard to the multiplication by positive scalars: is and , so is . ${\displaystyle \lambda \in [0,\infty )}$ ${\displaystyle a\preccurlyeq _{K}b}$ ${\displaystyle \lambda a\preccurlyeq _{K}\lambda b}$
• It is transitive, that is, is, and so is . ${\displaystyle a\preccurlyeq _{K}b}$ ${\displaystyle b\preccurlyeq _{K}c}$ ${\displaystyle a\preccurlyeq _{K}c}$
• It is reflexive, that is, it is always . ${\displaystyle a\preccurlyeq _{K}a}$
• It is antisymmetric, that is, is and so is . ${\displaystyle a\preccurlyeq _{K}b}$ ${\displaystyle b\preccurlyeq _{K}a}$ ${\displaystyle a=b}$

The strictly generalized inequality has the following properties: ${\displaystyle \prec _{K}}$

• It is closed with respect to the multiplication by real positive scalars, that is, is and , so is ${\displaystyle \lambda >0}$ ${\displaystyle a\prec _{K}b}$ ${\displaystyle \lambda a\prec _{K}\lambda b}$
• It is complete with regard to addition: is and , so is . ${\displaystyle a\prec _{K}b}$ ${\displaystyle c\preccurlyeq _{K}d}$ ${\displaystyle a+c\prec _{K}b+d}$
• It is not reflexive, that is, it does not apply . ${\displaystyle a\prec _{K}a}$

The dual (strict) generalized inequality ( ) has the following properties: ${\displaystyle \preccurlyeq _{K^{*}}}$ ${\displaystyle \prec _{K^{*}}}$

• ${\displaystyle a\preccurlyeq _{K}b}$if and only if that applies to all . ${\displaystyle y\succcurlyeq _{K^{*}}0}$ ${\displaystyle \langle y;a\rangle \leq \langle y;b\rangle }$
• ${\displaystyle a\prec _{K}b}$if and only if that applies to all . ${\displaystyle y\succ _{K^{*}}0\,,y\neq 0}$ ${\displaystyle \langle y;a\rangle <\langle y;b\rangle }$

All of these properties follow directly from the properties of the defining cones.

Minimal elements and minimum

An element of a set is called a minimum of if that applies to all . Equivalent to this is that . ${\displaystyle x}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle y\in S}$ ${\displaystyle x\preccurlyeq _{K}y}$ ${\displaystyle S\subset x+K}$

An element of the set is called a minimal element of if it follows from with that . Equivalent to this is that . ${\displaystyle x}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle y\preccurlyeq _{K}x}$ ${\displaystyle y\in S}$ ${\displaystyle y=x}$ ${\displaystyle (x-K)\cap S=\{x\}}$

The terms maximum and maximum element can also be defined in the same way. The terms can coincide but generally don't! An example of a minimum or maximum element of a set is the Pareto optimum .

Examples

• Be given in the cone . Then the order induced by this cone coincides with the order on and the zero is both the minimum and the minimum element of the set ${\displaystyle \mathbb {R} ^{1}}$ ${\displaystyle K=\{x\geq 0\}}$ ${\displaystyle \mathbb {R} }$ ${\displaystyle [0,1]}$
• If one considers the n unit vectors and the convex hull spanned by them , then a smallest cone can be constructed that contains this set. This cone then contains all points of where all n components are positive. The generalized inequality produced by this cone is precisely the component-wise comparison: ${\displaystyle \mathbb {R} ^{n}}$

${\displaystyle x\preccurlyeq _{K}y{\text{ genau dann wenn }}x_{i}\leq y_{i}\,{\text{ für alle }}i=1,\dots ,n}$.

• Not all points are comparable with each other. The point is neither larger nor smaller than that with respect to the partial order defined above. This follows from the fact that it is generally not a total order . ${\displaystyle x,y}$ ${\displaystyle (1,-1)}$ ${\displaystyle 0_{\mathbb {R} ^{2}}}$
• If one considers the vector space of the real symmetric matrices, provided with the cone of the positive semidefinite matrices , the corresponding generalized inequality is the Loewner partial order , as it is used, for example, in semidefinite programming . ${\displaystyle n\times n}$ ${\displaystyle S_{+}^{n}}$ ${\displaystyle \preccurlyeq _{S_{+}^{n}}}$

use

Generalized inequalities play an important role in vector optimization in order to guarantee the comparability of vectors. In addition, generalized inequalities allow the generalization of convex functions to vector-valued functions, the so-called K-convex functions . These find a role, for example, in the formulation of conical programs .

Modifications and alternative notations

In the optimization, cones are sometimes used to define orders whose interior is empty. This has the advantage that equation and inequality restrictions can be written into a function component by component. If, for example, is a cone, then sets and defines the function , then exactly if and . The disadvantage is that the associated strict inequality can no longer be defined, which means that some statements, such as the Slater condition, are cumbersome to formulate. ${\displaystyle K=\{0\}\times \mathbb {R} _{\geq 0}\subset \mathbb {R} ^{2}}$ ${\displaystyle x\leq _{K}y\iff y-x\in K}$ ${\displaystyle f(x)=(g(x),h(x))^{T}}$ ${\displaystyle f(x)\leq _{K}0}$ ${\displaystyle g(x)=0}$ ${\displaystyle h(x)\leq 0}$

Occasionally one also finds instead of the formulation

${\displaystyle g(x)\preccurlyeq _{K}0}$

the notation

${\displaystyle g(x)\in -K}$,

which is equivalent if is a real cone. Most of the time, however, it is just an order cone . The second notation is preferred when one sets weaker conditions for the cone and / or moves in infinite-dimensional vector spaces. ${\displaystyle K}$

literature

• Boyd, Stephen; Vandenberghe, Lieven (2004). Convex Optimization. Cambridge University Press. ISBN 978-0-521-83378-3 . ( online )
• Johannes Jahn: Introduction to the Theory of Nonlinear Optimization. 3. Edition. Springer, Berlin 2007, ISBN 978-3-540-49378-5 .