Contributed Session Thu.3.MA 313

Thursday, 15:15 - 16:45 h, Room: MA 313

Cluster 3: Complementarity & variational inequalities [...]

Algorithms for complementarity and related problems I


Chair: Walter Morris



Thursday, 15:15 - 15:40 h, Room: MA 313, Talk 1

Artur L. Pogosyan
Semismooth Newton-type methods for lifted mathematical programs with complementarity constraints

Coauthors: Alexey F. Izmailov, Mikhail V. Solodov


We consider a reformulation of mathematical programs with complementarity constraints, where by introducing an artificial variable the constraints are converted into equalities which are once but not twice differentiable. This approach can be regarded as a development of the lifted reformulation of complementarity constraints proposed earlier by O.Stein. We show that the Lagrange optimality system of such a reformulation is semismooth and BD-regular at the solution under reasonable assumptions. Thus, fast local convergence can be obtained by applying the semismooth Newton method. Moreover, it turns out that the squared residual of the Lagrange system is continuously differentiable (even though the system itself is not), which opens the way for a natural globalization of the local algorithm. However, from the practical viewpoint, it seems more promising to use a non-smooth exact penalty function instead of the squared residual of the Lagrange system which leads to the semismooth sequential quadratic programming method. Preliminary numerical results for problems from MacMPEC test collection demonstrate that the approach is very promising.



Thursday, 15:45 - 16:10 h, Room: MA 313, Talk 2

Evgeny Ivanovich Uskov
Global convergence of augmented Lagrangian methods applied to optimization problems with degenerate constraints, including problems with complementarity constraints

Coauthors: Alexey F. Izmailov, Mikhail V. Solodov



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 obtain a rather complete picture, showing that under the usual in this context MPCC-linear independence constraint qualification accumulation points of the iterates are C-stationary for MPCC (better than weakly stationary), but in general need not be M-stationary (hence, neither strongly stationary). Numerical results demonstrate that in terms of robustness and quality of the outcome augmented Lagrangian methods are absolutely competitive with the best existing alternatives and hence, they can serve as a promising global strategy for problems with degenerate constraints.



Thursday, 16:15 - 16:40 h, Room: MA 313, Talk 3

Walter Morris
Efficient computation of a canonical form for a generalized P-matrix


We use recent results on algorithms for Markov decision problems to show that a canonical form
for a generalized P-matrix can be computed, in some important cases, by a strongly polynomial algorithm.


  There are three major facts that should be watched out for in all payday loans in the United States. But at the same time, it acts only with sexual arousal. Buy Viagra Online has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.