On attraction of Newton-type iterates to multipliers violating second-order sufficiency conditions

Assuming that the primal part of the sequence generated by a Newton-type (e.g., SQP) method applied to an equality-constrained problem converges to a solution where the constraints are degenerate, we investigate whether the dual part of the sequence is attracted by those Lagrange multipliers which satisfy second-order sufficient condition (SOSC) for optimality, or by those multipliers which violate it. This question is relevant at least for two reasons: one is speed of convergence of standard methods; the other is applicability of some recently proposed approaches for handling degenerate constraints. We show that for the class of damped Newton methods, convergence of the dual sequence to multipliers satisfying SOSC is unlikely to occur. We support our findings by numerical experiments. We also suggest a simple auxiliary procedure for computing multiplier estimates, which does not have this undesirable property. Finally, some consequences for the case of mixed equality and inequality constraints are discussed.     

Karush-Kuhn-Tucker systems: regularity conditions,error bounds and a class of Newton-type methods

 We consider optimality systems of Karush-Kuhn-Tucker (KKT) type, which arise, for example, as primal-dual conditions characterizing solutions of optimization problems or variational inequalities. In particular, we discuss error bounds and Newton-type methods for such systems. An exhaustive comparison of various regularity conditions which arise in this context is given. We obtain a new error bound under an assumption which we show to be strictly weaker than assumptions previously used for KKT systems, such as quasi-regularity or semistability (equivalently, the R ₀-property). Error bounds are useful, among other things, for identifying active constraints and developing efficient local algorithms. We propose a family of local Newton-type algorithms. This family contains some known active-set Newton methods, as well as some new methods. Regularity conditions required for local superlinear convergence compare favorably with convergence conditions of nonsmooth Newton methods and sequential quadratic programming methods. Received: December 10, 2001 / Accepted: July 28, 2002 Published online: February 14, 2003 Key words. KKT system – regularity – error bound – active constraints – Newton method Mathematics Subject Classification (1991): 90C30, 65K05     

A class of Dantzig–Wolfe type decomposition methods for variational inequality problems

We consider a class of decomposition methods for variational inequalities, which is related to the classical Dantzig–Wolfe decomposition of linear programs. Our approach is rather general, in that it can be used with certain types of set-valued or nonmonotone operators, as well as with various kinds of approximations in the subproblems of the functions and derivatives in the single-valued case. Also, subproblems may be solved approximately. Convergence is established under reasonable assumptions. We also report numerical experiments for computing variational equilibria of the game-theoretic models of electricity markets. Our numerical results illustrate that the decomposition approach allows to solve large-scale problem instances otherwise intractable if the widely used PATH solver is applied directly, without decomposition.     

New Inexact Parallel Variable Distribution Algorithms

We consider the recently proposed parallel variable distribution(PVD) algorithm of Ferris and Mangasarian [4] for solvingoptimization problems in which the variables are distributed amongp processors. Each processor has the primary responsibility forupdating its block of variables while allowing the remainingsecondary variables tochange in a restricted fashion along some easily computable directions.We propose useful generalizationsthat consist, for the general unconstrained case, of replacing exact global solution ofthe subproblems by a certain natural sufficient descent condition, and,for the convex case, of inexact subproblem solution in thePVD algorithm. These modifications are the key features ofthe algorithm that has not been analyzed before.The proposed modified algorithms are more practical andmake it easier to achieve good load balancing among the parallelprocessors.We present a general framework for the analysis of thisclass of algorithms and derive some new and improved linear convergence resultsfor problems with weak sharp minima of order 2 and strongly convex problems.We also show that nonmonotone synchronization schemesare admissible, which further improves flexibility of PVD approach.     

Convergence Analysis of Perturbed Feasible Descent Methods

We develop a general approach to convergence analysis of feasible descent methods in the presence of perturbations. The important novel feature of our analysis is that perturbations need not tend to zero in the limit. In that case, standard convergence analysis techniques are not applicable. Therefore, a new approach is needed. We show that, in the presence of perturbations, a certain -approximate solution can be obtained, where depends linearly on the level of perturbations. Applications to the gradient projection, proximal minimization, extragradient and incremental gradient algorithms are described.     

Perturbed Augmented Lagrangian Method Framework with Applications to Proximal and Smoothed Variants

Journal of Optimization Theory and Applications - We introduce a perturbed augmented Lagrangian method framework, which is a convenient tool for local analyses of convergence and rates of...     

Measurements and calculations of Ar-broadening parameters of water vapour transitions in a wide spectral region

The water vapour line-broadening (γ) and shift (δ) coefficients for 310 lines of 10 vibrational bands ν₁, ν₃, 2ν₂, ν₁+ ν₂, ν₂+ ν_3, 2ν₂ +ν₃, 2ν₁, ν₁+ ν₃, 2ν₃ and ν₁ +2ν₂ induced by argon pressure were measured with a Bruker IFS HR 125 spectrometer. The measurements were performed at room temperature, at the spectral resolution of 0.01 cm^–1 and over a wide pressure range of Ar. The calculations of the broadening coefficients γ and δ were performed in the framework of the semi-classical method. The intermolecular potential was taken as the sum of the atom–atom potential and the vibrationally and rotationally dependent isotropic induction+dispersion potential. The measured γ and δ were combined with literature data for the ν₂ and 3ν₁+ν₃, 2ν₁+2ν₂+ν₃ vibrational bands, and the optimal sets of potential parameters that gave the best agreement with the measured broadening coefficients for each vibrational band separately were found. Then, combined experimental data of 13 vibrational bands of H₂O perturbed by Ar were used to determine the analytical dependence of some potential parameters on vibrational quantum numbers.     

Concerning an Example of Paskiewich

We generalize the construction proposed by A. Paskiewich of an example of an orthonormal system which establishes the sharpness of the Men’shov-Rademacher theorem. The connection of his example with that of Men’shov is elucidated.__________Translated from Matematicheskie Zametki, vol. 78, no. 2, 2005, pp. 286–291.Original Russian Text Copyright © 2005 by A. P. Solodov.