Examples of dual behaviour of Newton-type methods on optimization problems with degenerate constraints

We discuss possible scenarios of behaviour of the dual part of sequences generated by primal-dual Newton-type methods when applied to optimization problems with nonunique multipliers associated to a solution. Those scenarios are: (a) failure of convergence of the dual sequence; (b) convergence to a so-called critical multiplier (which, in particular, violates some second-order sufficient conditions for optimality), the latter appearing to be a typical scenario when critical multipliers exist; (c) convergence to a noncritical multiplier. The case of mathematical programs with complementarity constraints is also discussed. We illustrate those scenarios with examples, and discuss consequences for the speed of convergence. We also put together a collection of examples of optimization problems with constraints violating some standard constraint qualifications, intended for preliminary testing of existing algorithms on degenerate problems, or for developing special new algorithms designed to deal with constraints degeneracy. Research of the first author is supported by the Russian Foundation for Basic Research Grants 07-01-00270, 07-01-00416 and 07-01-90102-Mong, and by RF President’s Grant NS-9344.2006.1 for the support of leading scientific schools. The second author is supported in part by CNPq Grants 301508/2005-4, 490200/2005-2 and 550317/2005-8, by PRONEX–Optimization, and by FAPERJ Grant E-26/151.942/2004.     

Descent methods with linesearch in the presence of perturbations

We consider the class of descent algorithms for unconstrained optimization with an Armijo-type stepsize rule in the case when the gradient of the objective function is computed inexactly. An important novel feature in our theoretical analysis is that perturbations associated with the gradient are not assumed to be relatively small or to tend to zero in the limit (as a practical matter, we expect them to be reasonably small, so that a meaningful approximate solution can be obtained). This feature makes our analysis applicable to various difficult problems encounted in practice. We propose a modified Armijo-type rule for computing the stepsize which guarantees that the algorithm obtains a reasonable approximate solution. Furthermore, if perturbations are small relative to the size of the gradient, then our algorithm retains all the standard convergence properties of descent methods.     

On attraction of linearly constrained Lagrangian methods and of stabilized and quasi-Newton SQP methods to critical multipliers

It has been previously demonstrated that in the case when a Lagrange multiplier associated to a given solution is not unique, Newton iterations [e.g., those of sequential quadratic programming (SQP)] have a tendency to converge to special multipliers, called critical multipliers (when such critical multipliers exist). This fact is of importance because critical multipliers violate the second-order sufficient optimality conditions, and this was shown to be the reason for slow convergence typically observed for problems with degenerate constraints (convergence to noncritical multipliers results in superlinear rate despite degeneracy). Some theoretical and numerical validation of this phenomenon can be found in Izmailov and Solodov (Comput Optim Appl 42:231–264, 2009; Math Program 117:271–304, 2009). However, previous studies concerned the basic forms of Newton iterations. The question remained whether the attraction phenomenon still persists for relevant modifications, as well as in professional implementations. In this paper, we answer this question in the affirmative by presenting numerical results for the well known MINOS and SNOPT software packages applied to a collection of degenerate problems. We also extend previous theoretical considerations to the linearly constrained Lagrangian methods and to the quasi-Newton SQP, on which MINOS and SNOPT are based. Experiments also show that in the stabilized version of SQP the attraction phenomenon still exists but appears less persistent.     

Structural and magnetic phase transformations in the diluted laves phases Pr(Fe<Subscript>1 − <Emphasis Type="Italic">x</Emphasis></Subscript>Al<Subscript><Emphasis Type="Italic">x</Emphasis></Subscript>)<Subscript>2</Subscript>

The Pr(Fe_{1 ? x} Al _x )₂ alloys with concentrations x = 0–1 have been synthesized under a high pressure. The phase composition and lattice parameters (a and c) have been determined as a function of x. The magnetic and Mössbauer measurements have been performed at T = 90–400 K. It has been established that the Curie temperatures of alloys linearly depend on their composition.     

High-resolution Q-branches spectrum of C2H2 at 9366 and 9407 cm−1

The acetylene absorption spectrum in the Nd-laser range 9240–9520 cm^?1 has been recorded earlier (1), using a highly sensitive intracavity laser spectrometer. Two weak absorption perpendicular bands 2100⁰1¹ ← 0000⁰0⁰ (ν₀ = 9366.6 cm^?1) and 1200°3¹ ← 0000°0° (ν₀ = 9407.7 cm^?1) were studied and spectroscopic constants were obtained. However, the structure of the Q branches of these bands with J < 7 was unresolved because the resolution of the spectrometer was not very high.     

Study of the e+e- to hadrons via ISR at BABAR

Experimental data from the PEP-Ⅱ B-factory at 10.6 GeV center-of-mass (c.m.) energy, obtained via initial-state radiation (ISR) with the BABAR detector, are presented. The cross sections for many hadronic processes have been measured from the production threshold to 4-5 GeV of the e+e- c.m. Energy. The obtained data allow to study a number of intermediate states and determine the parameters of known resonances and their branching fractions. The exclusive cross section for some number of hadronic sub-processes are presented.     

Error bounds for 2-regular mappings with Lipschitzian derivatives and their applications

We obtain local estimates of the distance to a set defined by equality constraints under assumptions which are weaker than those previously used in the literature. Specifically, we assume that the constraints mapping has a Lipschitzian derivative, and satisfies a certain 2-regularity condition at the point under consideration. This setting directly subsumes the classical regular case and the twice differentiable 2-regular case, for which error bounds are known, but it is significantly richer than either of these two cases. When applied to a certain equation-based reformulation of the nonlinear complementarity problem, our results yield an error bound under an assumption more general than b-regularity. The latter appears to be the weakest assumption under which a local error bound for complementarity problems was previously available. We also discuss an application of our results to the convergence rate analysis of the exterior penalty method for solving irregular problems. Received: February 2000 / Accepted: November 2000?Published online January 17, 2001     

Stabilized sequential quadratic programming for optimization and a stabilized Newton-type method for variational problems

The stabilized version of the sequential quadratic programming algorithm (sSQP) had been developed in order to achieve fast convergence despite possible degeneracy of constraints of optimization problems, when the Lagrange multipliers associated to a solution are not unique. Superlinear convergence of sSQP had been previously established under the strong second-order sufficient condition for optimality (without any constraint qualification assumptions). We prove a stronger superlinear convergence result than the above, assuming the usual second-order sufficient condition only. In addition, our analysis is carried out in the more general setting of variational problems, for which we introduce a natural extension of sSQP techniques. In the process, we also obtain a new error bound for Karush–Kuhn–Tucker systems for variational problems that holds under an appropriate second-order condition.     

Nonlinear complementarity as unconstrained and constrained minimization

The nonlinear complementarity problem is cast as an unconstrained minimization problem that is obtained from an augmented Lagrangian formulation. The dimensionality of the unconstrained problem is the same as that of the original problem, and the penalty parameter need only be greater than one. Another feature of the unconstrained problem is that it has global minima of zero at precisely all the solution points of the complementarity problem without any monotonicity assumption. If the mapping of the complementarity problem is differentiable, then so is the objective of the unconstrained problem, and its gradient vanishes at all solution points of the complementarity problem. Under assumptions of nondegeneracy and linear independence of gradients of active constraints at a complementarity problem solution, the corresponding global unconstrained minimum point is locally unique. A Wolfe dual to a standard constrained optimization problem associated with the nonlinear complementarity problem is also formulated under a monotonicity and differentiability assumption. Most of the standard duality results are established even though the underlying constrained optimization problem may be nonconvex. Preliminary numerical tests on two small nonmonotone problems from the published literature converged to degenerate or nondegenerate solutions from all attempted starting points in 7 to 28 steps of a BFGS quasi-Newton method for unconstrained optimization.Dedicated to Phil Wolfe on his 65th birthday, in appreciation of his major contributions to mathematical programming.This material is based on research supported by Air Force Office of Scientific Research Grant AFOSR-89-0410 and National Science Foundation Grant CCR-9101801.