Superlinearly Convergent Affine Scaling Interior Trust-Region Method for Linear Constrained LC 1 Minimization

We extend the classical affine scaling interior trust region algorithm for the linear con- strained smooth minimization problem to the nonsmooth case where the gradient of objective function is only locally Lipschitzian. We propose and analyze a new affine scaling trust-region method in associ- ation with nonmonotonic interior backtracking line search technique for solving the linear constrained LC 1 optimization where the second-order derivative of the objective function is explicitly required to be locally Lipschitzian. The general trust region subproblem in the proposed algorithm is defined by minimizing an augmented affine scaling quadratic model which requires both first and second order information of the objective function subject only to an affine scaling ellipsoidal constraint in a null subspace of the augmented equality constraints. The global convergence and fast local convergence rate of the proposed algorithm are established under some reasonable conditions where twice smoothness of the objective function is not required. Applications of the algorithm to some nonsmooth optimization problems are discussed. Keywords trust region method, backtracking, nonmonotonic technique, interior point, LC 1 mini- mization, affine scaling