Almost convex function

The almost convex functions (English convex-like functions ) form a generalization of the convex functions and are used in mathematical optimization , since simple regularity requirements such as the Slater condition apply to them, under which strong duality applies and thus also the Karush-Kuhn- Tucker terms apply.

definition

Let be real vector spaces and an order cone on as well as a non-empty subset of . Then a figure is called almost convex if the set ${\displaystyle V_{1},V_{2}}$ ${\displaystyle K\,}$ ${\displaystyle V_{2}}$ ${\displaystyle D_{1}}$ ${\displaystyle V_{1}}$ ${\displaystyle f\colon D_{1}\mapsto V_{2}}$

${\displaystyle M:=f(D_{1})+K}$

is convex. The set can be equivalently described as ${\displaystyle M}$

${\displaystyle M=\{y\in V_{2}\,|\,\exists x\in D_{1}{\text{ so dass }}f(x)-y\in -K\}}$

If the cone is a real cone and thus defines a generalized inequality , then this set reads ${\displaystyle \preccurlyeq _{K}}$

${\displaystyle M=\{y\in V_{2}\,|\,\exists x\in D_{1}{\text{ so dass }}f(x)\preccurlyeq _{K}y\}}$

Examples

Looking at the function with and the real cone as well , so is . So is . This set is convex and so the sine function is almost convex. ${\displaystyle f\colon \mathbb {R} \mapsto \mathbb {R} }$ ${\displaystyle f(x)=\sin(x)}$ ${\displaystyle K=\mathbb {R} _{+}=\{x\in \mathbb {R} \,|\,x\geq 0\}}$ ${\displaystyle D_{1}=[0,2\pi ]}$ ${\displaystyle \sin(D_{1})=[-1,1]}$ ${\displaystyle M=[-1;1]+\mathbb {R} _{+}=\{x\in \mathbb {R} \,|\,x\geq -1\}}$

Looking at the function ${\displaystyle f(x)={\begin{cases}-1&{\text{ falls }}x\leq 0\\1&{\text{ falls }}x>0\end{cases}}}$

and defined by ${\displaystyle g\colon \mathbb {R} \mapsto \mathbb {R} ^{2}}$

${\displaystyle g(x)={\begin{pmatrix}f(x)\\5x\end{pmatrix}}}$

on with the order cone . For each point of the image set is of the form and thus is . Analogously it follows with that . So is ${\displaystyle D_{0}=\mathbb {R} }$ ${\displaystyle K=\mathbb {R} _{+}\times \{0\}}$ ${\displaystyle x\in D_{1}=\{x\in \mathbb {R} \,|\,x\leq 0\}}$ ${\displaystyle (-1,5x)}$ ${\displaystyle g(D_{1})=\{y\in \mathbb {R} ^{2}\,|\,y_{1}=-1,y_{2}\leq 0\}}$ ${\displaystyle D_{2}=\{x\in \mathbb {R} \,|\,x>0\}}$ ${\displaystyle g(D_{2})=\{y\in \mathbb {R} ^{2}\,|\,y_{1}=1,y_{2}>0\}}$

${\displaystyle {\begin{aligned}g(D_{1})+K=\{y\in \mathbb {R} ^{2}\,|\,y_{1}\geq -1,y_{2}\leq 0\}\\g(D_{2})+K=\{y\in \mathbb {R} ^{2}\,|\,y_{1}\geq 1,y_{2}>0\}\end{aligned}}}$

But since is, the set cannot be convex, since for example the points and are contained in, but none of the points on the line between them. For example, the midpoint of this line is but not included in. ${\displaystyle D_{0}=D_{1}\cup D_{2}}$ ${\displaystyle g(D_{0})+K=g(D_{1}\cup D_{2})+K=\left(g(D_{1})+K\right)\cup \left(g(D_{2})+K\right)}$ ${\displaystyle (-1,0)^{T}}$ ${\displaystyle (1,1)^{T}}$ ${\displaystyle g(D_{0})+K}$ ${\displaystyle (0,0{,}5)}$ ${\displaystyle g(D_{0})+K}$

properties

Every convex function is almost convex with respect to the natural cone . This follows directly from the convexity of the epigraph . In the same way every K-convex function is almost convex with respect to its cone. ${\displaystyle K=\mathbb {R} _{+}}$

use

The almost convex functions are a class of functions that are defined in such a way that if they satisfy the Slater condition , strong duality applies. So be a shape optimization problem

${\displaystyle {\begin{aligned}{\text{Minimiere }}&f(x)\\{\text{unter den Nebenbedingungen }}&g(x)\in -K\\&x\in R\end{aligned}}}$

given for a trim cone with non-blank heart and figures and . Thereby normalized real vector spaces are defined and the function is almost convex with respect to the cone . Furthermore, let us be an arbitrary non-empty subset of . ${\displaystyle K\,}$ ${\displaystyle f\colon V\mapsto \mathbb {R} }$ ${\displaystyle g\colon V\mapsto Y}$ ${\displaystyle V,Y}$ ${\displaystyle K\colon V\mapsto \mathbb {R} \times Y}$ ${\displaystyle K(x)=(f(x),g(x))}$ ${\displaystyle \mathbb {R} _{+}\times K}$ ${\displaystyle R}$ ${\displaystyle V}$

The problem now satisfies the Slater condition if there is a feasible point . That is , so that is. It denotes the interior of a set. ${\displaystyle {\tilde {x}}}$ ${\displaystyle {\tilde {x}}\in R,\,g({\tilde {x}})\in -K}$ ${\displaystyle g({\tilde {x}})\in \operatorname {int} (-K)}$ ${\displaystyle \operatorname {int} (M)}$

If such a problem with almost convex functions now fulfills the Slater condition, then strong duality applies and thus, for example, the Karush-Kuhn-Tucker conditions as well . The concept of the almost convex function extends the duality theory of convex functions to problems that do not necessarily have to be convex. This has the advantage that, in contrast to many other regularity conditions or “constraint qualifications”, the Slater condition provides the regularity of the entire problem, and not just the regularity in one point.

literature

• Johannes Jahn: Introduction to the Theory of Nonlinear Optimization. 3. Edition. Springer, Berlin 2007, ISBN 978-3-540-49378-5 .