inexact newton method

Communication-Efficient Distributed Optimization of Self-Concordant Empirical Loss

  • Lin Xiao
  • Yuchen Zhang
    • Categories Convex Optimization, Statistics Tags , , , ,

    We consider distributed convex optimization problems originated from sample average approximation of stochastic optimization, or empirical risk minimization in machine learning. We assume that each machine in the distributed computing system has access to a local empirical loss function, constructed with i.i.d. data sampled from a common distribution. We propose a communication-efficient distributed algorithm to … Read more

    Convergence Analysis of an Inexact Feasible Interior Point Method for Convex Quadratic Programming

  • Jacek Gondzio
    • Categories Linear, Cone and Semidefinite Programming Tags , , , , ,

    In this paper we will discuss two variants of an inexact feasible interior point algorithm for convex quadratic programming. We will consider two different neighbourhoods: a (small) one induced by the use of the Euclidean norm which yields a short-step algorithm and a symmetric one induced by the use of the infinity norm which yields … Read more

    A Family of Newton Methods for Nonsmooth Constrained Systems with Nonisolated Solutions

  • Francisco Facchinei
  • Andreas Fischer
  • Markus Herrich
    • Categories Complementarity and Variational Inequalities, Nonlinear Optimization Tags , , , ,

    We propose a new family of Newton-type methods for the solution of constrained systems of equations. Under suitable conditions, that do not include differentiability or local uniqueness of solutions, local, quadratic convergence to a solution of the system of equations can be established. We show that as particular instances of the method we obtain inexact … Read more

    Local path-following property of inexact interior methods in nonlinear programming

  • Paul Armand
  • Jean-Pierre Dussault
  • Joël Benoist
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , , ,

    We study the local behavior of a primal-dual inexact interior point methods for solving nonlinear systems arising from the solution of nonlinear optimization problems or more generally from nonlinear complementarity problems. The algorithm is based on the Newton method applied to a sequence of perturbed systems that follows by perturbation of the complementarity equations of … Read more

    A sufficiently exact inexact Newton step based on reusing matrix information

  • Anders Forsgren
    • Categories Constrained Nonlinear Optimization, Linear Programming, Nonlinear Systems and Least-Squares Tags , ,

    Newton’s method is a classical method for solving a nonlinear equation $F(z)=0$. We derive inexact Newton steps that lead to an inexact Newton method, applicable near a solution. The method is based on solving for a particular $F'(z_{k’})$ during $p$ consecutive iterations $k=k’,k’+1,\dots,k’+p-1$. One such $p$-cycle requires $2^p-1$ solves with the matrix $F'(z_{k’})$. If matrix … Read more