Time filter

Source Type

Izmailov A.F.,Moscow State University | Kurennoy A.S.,Tambov State University | Solodov M.V.,IMPA Institute Matematica Pura e Aplicada
Mathematical Programming | Year: 2016

It is known that when the set of Lagrange multipliers associated with a stationary point of a constrained optimization problem is not a singleton, this set may contain so-called critical multipliers. This special subset of Lagrange multipliers defines, to a great extent, stability pattern of the solution in question subject to parametric perturbations. Criticality of a Lagrange multiplier can be equivalently characterized by the absence of the local Lipschitzian error bound in terms of the natural residual of the optimality system. In this work, taking the view of criticality as that associated to the error bound, we extend the concept to general nonlinear equations (not necessarily with primal–dual optimality structure). Among other things, we show that while singular noncritical solutions of nonlinear equations can be expected to be stable only subject to some poor “asymptotically thin” classes of perturbations, critical solutions can be stable under rich classes of perturbations. This fact is quite remarkable, considering that in the case of nonisolated solutions, critical solutions usually form a thin subset within all the solutions. We also note that the results for general equations lead to some new insights into the properties of critical Lagrange multipliers (i.e., solutions of equations with primal–dual structure). © 2016 Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society

Fernandez D.,National University of Cordoba | Izmailov A.F.,Moscow State University | Solodov M.V.,IMPA Institute Matematica Pura e Aplicada
SIAM Journal on Optimization | Year: 2010

As is well known, Q-superlinear or Q-quadratic convergence of the primal-dual sequence generated by an optimization algorithm does not, in general, imply Q-superlinear convergence of the primal part. Primal convergence, however, is often of particular interest. For the sequential quadratic programming (SQP) algorithm, local primal-dual quadratic convergence can be established under the assumptions of uniqueness of the Lagrange multiplier associated to the solution and the second-order sufficient condition. At the same time, previous primal Q-superlinear convergence results for SQP required strengthening of the first assumption to the linear independence constraint qualification. In this paper, we show that this strengthening of assumptions is actually not necessary. Specifically, we show that once primal-dual convergence is assumed or already established, for primal superlinear rate one needs only a certain error bound estimate. This error bound holds, for example, under the second-order sufficient condition, which is needed for primal-dual local analysis in any case. Moreover, in some situations even second-order sufficiency can be relaxed to the weaker assumption that the multiplier in question is noncritical. Our study is performed for a rather general perturbed SQP framework which covers, in addition to SQP and quasi-Newton SQP, some other algorithms as well. For example, as a byproduct, we obtain primal Q-superlinear convergence results for the linearly constrained (augmented) Lagrangian methods for which no primal Q-superlinear rate of convergence results were previously available. Another application of the general framework is sequential quadratically constrained quadratic programming methods. Finally, we discuss some difficulties with proving primal superlinear convergence for the stabilized version of SQP. © 2010 Society for Industrial and Applied Mathematics.

Izmailov A.F.,Moscow State University | Kurennoy A.S.,Moscow State University | Solodov M.V.,IMPA Institute Matematica Pura e Aplicada
Mathematical Programming | Year: 2013

We prove a new local upper Lipschitz stability result and the associated local error bound for solutions of parametric Karush-Kuhn-Tucker systems corresponding to variational problems with Lipschitzian base mappings and constraints possessing Lipschitzian derivatives, and without any constraint qualifications. This property is equivalent to the appropriately extended to this nonsmooth setting notion of noncriticality of the Lagrange multiplier associated to the primal solution, which is weaker than second-order sufficiency. All this extends several results previously known only for optimization problems with twice differentiable data, or assuming some constraint qualifications. In addition, our results are obtained in the more general variational setting. © 2012 Springer and Mathematical Optimization Society.

Fernandez D.,National University of Cordoba | Solodov M.V.,IMPA Institute Matematica Pura e Aplicada
SIAM Journal on Optimization | Year: 2012

We establish local convergence and rate of convergence of the classical augmented Lagrangian algorithm under the sole assumption that the dual starting point is close to a multiplier satisfying the second-order sufficient optimality condition. In particular, no constraint qualifications of any kind are needed. Previous literature on the subject required, in addition, the linear independence constraint qualification and either the strict complementarity assumption or a stronger version of the second-order sufficient condition. That said, the classical results allow the initial multiplier estimate to be far from the optimal one, at the expense of proportionally increasing the threshold value for the penalty parameters. Although our primary goal is to avoid constraint qualifications, if the stronger assumptions are introduced, then starting points far from the optimal multiplier are allowed within our analysis as well. Using only the second-order sufficient optimality condition, for penalty parameters large enough we prove primal-dual Q-linear convergence rate, which becomes superlinear if the parameters are allowed to go to infinity. Both exact and inexact solutions of subproblems are considered. In the exact case, we further show that the primal convergence rate is of the same Q-order as the primal-dual rate. Previous assertions for the primal sequence all had to do with the weaker R-rate of convergence and required the stronger assumptions cited above. Finally, we show that under our assumptions one of the popular rules of controlling the penalty parameters ensures their boundedness. © 2012 Society for Industrial and Applied Mathematics.

Izmailov A.F.,Moscow State University | Solodov M.V.,IMPA Institute Matematica Pura e Aplicada | Uskov E.I.,Moscow State University
SIAM Journal on Optimization | Year: 2012

We consider global convergence properties of the augmented Lagrangian methods on problems with degenerate constraints, with a special emphasis on mathematical programs with complementarity constraints (MPCC). In the general case, we show convergence to stationary points of the problem under an error bound condition for the feasible set (which is weaker than constraint qualifications), assuming that the iterates have some modest features of approximate local minimizers of the augmented Lagrangian. For MPCC, we first argue that even weak forms of general constraint qualifications that are suitable for convergence of the augmented Lagrangian methods, such as the recently proposed relaxed positive linear dependence condition, should not be expected to hold and thus special analysis is needed. We next obtain a rather complete picture, showing that, under this context's usual MPCC-linear independence constraint qualification, feasible accumulation points of the iterates are guaranteed to be C-stationary for MPCC (better than weakly stationary), but in general need not be M-stationary (hence, neither strongly stationary). However, strong stationarity is guaranteed if the generated dual sequence is bounded, which we show to be the typical numerical behavior even though the multiplier set itself is unbounded. Experiments with the ALGENCAN augmented Lagrangian solver on the MacMPEC and DEGEN collections are reported, with comparisons to the SNOPT and filterSQP implementations of the SQP method, to the MINOS implementation of the linearly constrained Lagrangian method, and to the interior-point solvers IPOPT and KNITRO. We show that ALGENCAN is a very good option if one is primarily interested in robustness and quality of computed solutions. © 2012 Society for Industrial and Applied Mathematics.

Discover hidden collaborations