A quadratic approximation method for minimizing a class of quasidifferentiable functions

Summary An unconstrained nonlinear programming problem with nondifferentiabilities is considered. The nondifferentiabilities arise from terms of the form max [f ₁(x), ...,f _n (x)], which may enter nonlinearly in the objective function. Local convex polyhedral upper approximations to the objective function are introduced. These approximations are used in an iterative method for solving the problem. The algorithm proceeds by solving quadratic programming subproblems to generate search directions. Approximate line searches ensure global convergence of the method to stationary points. The algorithm is conceptually simple and easy to implement. It generalizes efficient variable metric methods for minimax calculations.     

A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities

In this paper we take a new look at smoothing Newton methods for solving the nonlinear complementarity problem (NCP) and the box constrained variational inequalities (BVI). Instead of using an infinite sequence of smoothing approximation functions, we use a single smoothing approximation function and Robinson’s normal equation to reformulate NCP and BVI as an equivalent nonsmooth equation H(u,x)=0, where H:ℜ ²ⁿ →ℜ ²ⁿ , u∈ℜ ⁿ is a parameter variable and x∈ℜ ⁿ is the original variable. The central idea of our smoothing Newton methods is that we construct a sequence {z ^k =(u ^k ,x ^k )} such that the mapping H(·) is continuously differentiable at each z ^k and may be non-differentiable at the limiting point of {z ^k }. We prove that three most often used Gabriel-Moré smoothing functions can generate strongly semismooth functions, which play a fundamental role in establishing superlinear and quadratic convergence of our new smoothing Newton methods. We do not require any function value of F or its derivative value outside the feasible region while at each step we only solve a linear system of equations and if we choose a certain smoothing function only a reduced form needs to be solved. Preliminary numerical results show that the proposed methods for particularly chosen smoothing functions are very promising. Received June 23, 1997 / Revised version received July 29, 1999?Published online December 15, 1999     

Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems

We show that a particular pivoting algorithm, which we call the lexicographic Lemke algorithm, takes an expected number of steps that is bounded by a quadratic inn, when applied to a random linear complementarity problem of dimensionn. We present two probabilistic models, both requiring some nondegeneracy and sign-invariance properties. The second distribution is concerned with linear complementarity problems that arise from linear programming. In this case we give bounds that are quadratic in the smaller of the two dimensions of the linear programming problem, and independent of the larger. Similar results have been obtained by Adler and Megiddo.Research partially funded by a fellowship from the Alfred Sloan Foundation and by NSF Grant ECS82-15361.     

Global Linear and Quadratic One-step Smoothing Newton Method for P 0-LCP

We propose a new smoothing Newton method for solving the P ₀-matrix linear complementarity problem (P ₀-LCP) based on CHKS smoothing function. Our algorithm solves only one linear system of equations and performs only one line search per iteration. It is shown to converge to a P ₀-LCP solution globally linearly and locally quadratically without the strict complementarity assumption at the solution. To the best of author's knowledge, this is the first one-step smoothing Newton method to possess both global linear and local quadratic convergence. Preliminary numerical results indicate that the proposed algorithm is promising.     

Solution Methodologies for the Smallest Enclosing Circle Problem

Given a set of circles C = {c ₁, ..., c _n} on the Euclidean plane with centers {(a ₁, b ₁), ..., (a _n, b _n)} and radii {r ₁, ..., r _n}, the smallest enclosing circle (of fixed circles) problem is to find the circle of minimum radius that encloses all circles in C. We survey four known approaches for this problem, including a second order cone reformulation, a subgradient approach, a quadratic programming scheme, and a randomized incremental algorithm. For the last algorithm we also give some implementation details. It turns out the quadratic programming scheme outperforms the other three in our computational experiment.     

An SQP algorithm for extended linear-quadratic problems in stochastic programming

Extended Linear-Quadratic Programming (ELQP) problems were introduced by Rockafellar and Wets for various models in stochastic programming and multistage optimization. Several numerical methods with linear convergence rates have been developed for solving fully quadratic ELQP problems, where the primal and dual coefficient matrices are positive definite. We present a two-stage sequential quadratic programming (SQP) method for solving ELQP problems arising in stochastic programming. The first stage algorithm realizes global convergence and the second stage algorithm realizes superlinear local convergence under a condition calledB-regularity.B-regularity is milder than the fully quadratic condition; the primal coefficient matrix need not be positive definite. Numerical tests are given to demonstrate the efficiency of the algorithm. Solution properties of the ELQP problem underB-regularity are also discussed.Supported by the Australian Research Council.     

A smoothing Newton method for a type of inverse semi-definite quadratic programming problem

We consider an inverse problem arising from the semi-definite quadratic programming (SDQP) problem. We represent this problem as a cone-constrained minimization problem and its dual (denoted ISDQD) is a semismoothly differentiable (SC¹${\text{SC}}^1$) convex programming problem with fewer variables than the original one. The Karush–Kuhn–Tucker conditions of the dual problem (ISDQD) can be formulated as a system of semismooth equations which involves the projection onto the cone of positive semi-definite matrices. A smoothing Newton method is given for getting a Karush–Kuhn–Tucker point of ISDQD. The proposed method needs to compute the directional derivative of the smoothing projector at the corresponding point and to solve one linear system per iteration. The quadratic convergence of the smoothing Newton method is proved under a suitable condition. Numerical experiments are reported to show that the smoothing Newton method is very effective for solving this type of inverse quadratic programming problems.     

Least Frobenius norm updating of quadratic models that satisfy interpolation conditions

Quadratic models of objective functions are highly useful in many optimization algorithms. They are updated regularly to include new information about the objective function, such as the difference between two gradient vectors. We consider the case, however, when each model interpolates some function values, so an update is required when a new function value replaces an old one. We let the number of interpolation conditions, m say, be such that there is freedom in each new quadratic model that is taken up by minimizing the Frobenius norm of the second derivative matrix of the change to the model. This variational problem is expressed as the solution of an (m+n+1)×(m+n+1) system of linear equations, where n is the number of variables of the objective function. Further, the inverse of the matrix of the system provides the coefficients of quadratic Lagrange functions of the current interpolation problem. A method is presented for updating all these coefficients in ({m+n}²) operations, which allows the model to be updated too. An extension to the method is also described that suppresses the constant terms of the Lagrange functions. These techniques have a useful stability property that is investigated in some numerical experiments.     

A trust region SQP algorithm for mixed-integer nonlinear programming

We propose a modified sequential quadratic programming method for solving mixed-integer nonlinear programming problems. Under the assumption that integer variables have a smooth influence on the model functions, i.e., that function values do not change drastically when in- or decrementing an integer value, successive quadratic approximations are applied. The algorithm is stabilized by a trust region method with Yuan’s second order corrections. It is not assumed that the mixed-integer program is relaxable or, in other words, function values are evaluated only at integer points. The Hessian of the Lagrangian function is approximated by a quasi-Newton update formula subject to the continuous and integer variables. Numerical results are presented for a set of 80 mixed-integer test problems taken from the literature. The surprising result is that the number of function evaluations, the most important performance criterion in practice, is less than the number of function calls needed for solving the corresponding relaxed problem without integer variables.