Fitting enclosing cylinders to data in \(\mathbb R^n\) (Q861741)

The paper is devoted to the development of a simple iterative algorithm for finding a stationary point of the (nonconvex) problem of finding the smallest enclosing \((n-d)\)-cylinder to discrete data in \(\mathbb R^n\), that is a cylinder whose axis is a \(d\)-dimensional linear manifold. The algorithm considered in the paper is intended to find the smallest enclosing (usual) cylinder, when \(n=3\) and \(d=1\). It is based on the solution of a sequence of second order cone programming problems (SOCPs) for a class of problems which includes finding enclosing cylinders in \(\mathbb R^3\). These are problems which involve the minimization of a linear objective function over the intersection of an affine set and the product of second order (quadratic) cones. The algorithm realization uses standard, readily available software. As it is stated in the paper, it converge to a stationary point of the problem, and although the rate of convergence is unpredictable, evidence for the smallest enclosing cylinder problem suggests that it is satisfactory. Much depends on the accuracy required, although this is less important in the context of genuinely error contaminated data. A starting approximation is suggested which might be favorable for finding the global solution to this non-convex problem, although guaranteeing a global solution remains a live issue.