Jean-Pierre Dussault The semismooth Newton method is a very efficient approach for computing a zero of a large class of nonsmooth equations. When the initial iterate is sufficiently close to a regular zero and the function is strongly semismooth, the generated sequence converges quadratically to that zero, while the iteration only requires to solve a linear system. … Read more
This paper focuses on the description and computation of the B-differential of the componentwise minimum of two affine vector functions. This issue arises in the reformulation of the linear complementarity problem with the Min C-function. The question has many equivalent formulations and we identify some of them in linear algebra, convex analysis and discrete geometry. … Read more
This paper considers a generalized form of the standard linear complementarity problem with unique solution and provides a more precise expression of an upper error bound discovered by Chen and Xiang in 2006. This expression has at least two advantages. It makes possible the exact computation of the error bound factor and it provides a … Read more
Adaptive cubic regularization (ARC) methods for unconstrained optimization compute steps from linear systems involving a shifted Hessian in the spirit of the Levenberg-Marquardt and trust-region methods. The standard approach consists in performing an iterative search for the shift akin to solving the secular equation in trust-region methods. Such search requires computing the Cholesky factorization of … Read more
The plain Newton-min algorithm for solving the linear complementarity problem (LCP) 0 ≤ x ⊥ (Mx+q) ≥ 0 can be viewed as an instance of the plain semismooth Newton method on the equational version min(x,Mx+q) = 0 of the problem. This algorithm converges for any q when M is an M-matrix, but not when it … Read more
We propose a new family of relaxation schemes for mathematical program with complementarity constraints that extends the relaxations of Kadrani, Dussault, Bechakroun from 2009 and the one of Kanzow \& Schwartz from 2011. We discuss the properties of the sequence of relaxed non-linear program as well as stationarity properties of limiting points. A sub-family of … Read more
We discuss here the convergence of relaxation methods for MPCC with approximate sequence of stationary points by presenting a general framework to study these methods. It has been pointed out in the literature, \cite{kanzow2015}, that relaxation methods with approximate stationary points fail to give guarantee of convergence. We show that by defining a new strong … Read more
In this note, we recall two solutions to alleviate the catastrophic cancellations that occur when comparing function values in descent algorithms. The automatic finite differencing approach (Dussault and Hamelin) was shown useful to trust region and line search variants. The main original contribution is to successfully adapt the line search strategy (Hager and Zhang) for … Read more
We present a new Adaptive Regularization by Cubics (ARC) algorithm, which we name \arcq\ and which is very close in spirit to trust region methods, closer than the original ARC is. We prove global convergence to second-order critical points. We also obtain as a corollary the convergence of the original ARC method. We prove the … Read more
This note discusses reformulations the brachistochrone problem suitable for solution via NLP. The availability of solvers and modeling languages such as AMPL makes it tempting to formulate discretized optimization problems and get solutions to the discretized versions of trajectory optimization problems. We use the famous brachistochrone problem to warn that the resulting solutions may be … Read more