Nonlocal error bounds for piecewise affine functions (Q6080421): Difference between revisions

The author extends earlier results concerning error bounds for piecewise affine functions on various types of sets. A piecewise affine function \(f\) may be represented as \(f(x)=\min_{i\in I}\max_{j\in J(i)}(a_{ij}+\left\langle \nu _{ij},x\right\rangle )\), for every \(x\in \mathbb{R}^{d}\), where \( a_{ij}\in \mathbb{R}\), \(\nu _{ij}\in \mathbb{R}^{d}\), \(i\in I=\{1,\dots ,l\} \), and \(j\in J(i)=\{1,\dots ,s(i)\}\). For any function \(f:\mathbb{R} ^{d}\rightarrow \mathbb{R}\), \(S(f)\) is the lower 0-level set of \(f\) defined as \(\{x\in \mathbb{R}^{d}\mid f(x)\leq 0\}\), \([f]_{+}(x)=\max\{f(x),0\}\), and the recession function \(f^{\infty}\) of \(f\) is defined as \(f^{\infty}(x)=\lim_{\lambda \rightarrow +\infty}f(\lambda x)/\lambda \). The author recalls properties of the lower 0-level set and of the recession function in the case of a piecewise affine function. A function \(f\) is said to have an error bound with constant \(\tau >0\) on a set \(V\subset \mathbb{R}^{d}\) if \( \tau\mathrm{dist}(x,S(f))\leq \lbrack f]_{+}(x)\), for every \(x\in V\). \(f\) is said to have a global error bound if there exists \(\tau >0\) such that the preceding inequality holds true for \(V=\mathbb{R}^{d}\). The first main result proves that if \(f\) is a piecewise affine function with \(S(f)\) nonempty, such that \( f_{i}^{\ast}\leq 0\) for all \(i\in I\), with \(f_{i}^{\ast}=\inf_{x\in \mathbb{ R}^{d}}f_{i}(x)\) and \(f_{i}(x)=\max_{j\in J(i)}(a_{ij}+\left\langle \nu _{ij},x\right\rangle )\), \(f\) has a global error bound. If there exists \(i\in I\) such that \(f_{i}^{\ast}>0\), the function \(f\) has an error bound on the set \(V=\{x\in \mathbb{R}^{d}\mid f(x)<\rho \}\) with \(\rho =\min\{f_{i}^{\ast}\mid i\in I:f_{i}^{\ast} >0\}\). This improves a result by \textit{S. M. Robinson} on error bounds for piecewise affine functions in [Math. Program. Study 14, 206--214 (1981; Zbl 0449.90090)]. The author analyzes two examples. The second main result proves that a piecewise affine function \(f\) with nonempty \(S(f)\) has an error bound on every bounded subset of \(\mathbb{R}^{d} \). The third main result proves that if \(f\) is a piecewise affine function with nonempty \(S(f)\) and \(V\) is a given subset of \(\mathbb{R}^{d}\), then for \(f\) to have an error bound on \(V\) it is sufficient that \(\liminf_{\left\Vert x\right\Vert \rightarrow +\infty ,x\in V}f(x)/\left\Vert x\right\Vert >0\). This condition becomes necessary when \(0^{+}S(f)\cap \mathrm{clcone}V=\{0\}\). This result is then specialized in the case of a cone or of a closed convex cone \( V\). The paper ends with the case of unbounded sets, the author also here analyzing examples, and in the case of systems of piecewise affine equalities and inequalities.