A method for approximating the solution set of a system of convex inequalities by polytopes (Q1182665)

The purpose of the paper is to present an algorithm for approximating the set \(Q=\{x\in R^ n\mid g_ i(x)\leq 0,\quad i\in I\}\) where \(g_ i\), \(i\in I\), is a convex not necessarily smooth function on \(R^ n\), \(I\) is a finite index set. The algorithm for a fixed \(\varepsilon>0\) produces two polytopes \(Q_ \varepsilon'\), \(Q''_ \varepsilon\) such that (i) \(Q_ \varepsilon'\subseteq Q\subseteq Q''_ \varepsilon\); (ii) \(\hbox{dist}(Q_ \varepsilon',Q''_ \varepsilon):=\hbox{sup}\{d(q,Q_ \varepsilon')\mid q\in Q''_ \varepsilon\}\leq \varepsilon\); (iii) the extreme points of \(Q_ \varepsilon'\) belong to the boundary \(\partial Q\) and the extreme points of \(Q''_ \varepsilon\) belong to the relative exterior of \(Q\). The algorithm is based on special simplicial division procedures and needs the solution of finitely many linearly singly constrained convex optimization problems. An upper estimate for the number of simplices which one has to deal with when using the algorithm is obtained.