## 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**

**Abstract:**

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**

**Abstract:**

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

**Abstract:**

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.