Robust best approximation with interpolation constraints under ellipsoidal uncertainty: Strong duality and nonsmooth Newton methods

In this paper we present a duality approach for finding a robust best approximation from a set involving interpolation constraints and uncertain inequality constraints in a Hilbert space that is immunized against the data uncertainty using a nonsmooth Newton method. Following the framework of robust optimization, we assume that the input data of the inequality constraints are not known exactly while they belong to an ellipsoidal data uncertainty set. We first show that finding a robust best approximation is equivalent to solving a second-order cone complementarity problem by establishing a strong duality theorem under a strict feasibility condition. We then examine a nonsmooth version of Newton's method and present their convergence analysis in terms of the metric regularity condition. (C) 2012 Elsevier Ltd. All rights reserved.