An algorithm for discrete approximation by quasi-convex functions on \(R^m\) (Q1767886)

Let \(T\) be a convex subset of \(R^m\). A function \(k'\) on \(T\) is said to be quasi-convex if \[ {\;k'(\lambda s+(1-\lambda t)\leq \max(k'(s),k'(t))} \] for all \({s,t\in T}\) and all \({\lambda\in [0,1]\;}\). Let \(S\) be a finite subset of \(R^m\), \({card(S)=n}\). A function \(k\) on \(S\) is said to be quasi-convex if there exists a quasi-convex function \(k'\) on the convex hull of \(S\) such that \({k=k'}\) on \(S\). Given a real function \(f\) on \(S\), the problem is to find a best quasi-convex approximation \(g\) to \(f\) in the uniform norm. Denote by \(K_f\) the set of all quasi-convex functions \(k\) on \(S\) such that \({k\leq f}\) on \(S\). The function \[ \hat f(s)=\sup\{k(s):\;k\in K_f\}, \;\;s\in S, \] is the greatest quasi-convex minorant of \(f\). The best quasi-convex approximation to \(f\) is obtained as \({q=\hat f+\Delta}\), where \({\Delta=(1/2)\| f-\hat f\| }\). An algorithm for computing this best approximation is developed and its complexity is analyzed. In the case \({m=2}\) the worst case complexity of the algorithm is \({O(n(\log n \log r+r))}\), where \(r\) is the cardinality of the set \({\{f(s):\;s\in S\}}\). Some observations that will speed up the algorithm in the average case are given.