## Invited Session Thu.2.H 1012

#### Thursday, 13:15 - 14:45 h, Room: H 1012

**Cluster 17: Nonsmooth optimization** [...]

### Policy iteration algorithms and some applications

**Chair: Hasnaa Zidani**

**Thursday, 13:15 - 13:40 h, Room: H 1012, Talk 1**

**Hasnaa Zidani**

Some convergence results for the policy iterations algorithm.

**Coauthor: Olivier Bokanowski**

**Abstract:**

In this talk, we will present some convergence results of Howard's algorithm for the resolution of equations in the form of *min*_{a ∈ A}(B_{a}x-c_{a}) = 0, where *B*_{a} is a matrix, *c*_{a} is a vector, and *A* is a compact set. We show a global superlinear convergence result, under a monotonicity assumption on the matrices *B*_{a}. An Extension of Howard's algorithm for a max-min problem of the form *max*_{b ∈ B} min_{a ∈ A}(B_{a,b}x - c_{a,b}) = 0 will be also proposed.

The algorithms are illustrated on the discretization of nonlinear PDEs arising in the context of mathematical finance (American option and Merton's portfolio problem), of front propagation problems, and for the double-obstacle problem, and Hamilton-Jacobi equations.

**Thursday, 13:45 - 14:10 h, Room: H 1012, Talk 2**

**Jan Hendrik Witte**

Penalty methods for the solution of discrete HJB equations - continuous control and obstacle problems

**Coauthor: Christoph Reisinger**

**Abstract:**

We present a novel penalty approach for the numerical solution of continuously controlled HJB equations and HJB obstacle problems. Our results include estimates of the penalisation error for a class of penalty terms, and we show that variations of Newton's method can be used to obtain globally convergent iterative solvers for the penalised equations. Furthermore, we discuss under what conditions local quadratic convergence of the iterative solvers can be expected. We include numerical results demonstrating the competitiveness of our methods.

**Thursday, 14:15 - 14:40 h, Room: H 1012, Talk 3**

**Stephane Louis Gaubert**

Policy iteration algorithm for zero-sum stochastic games with mean payoff

**Coauthors: Marianne Akian, Jean Cochet-Terrasson, Sylvie Detournay**

**Abstract:**

We develop a policy iteration algorithm to solve zero-sum stochastic

games with finite state, perfect information and ergodic payoff (mean

payoff per turn). An initial version of this algorithm was introduced

by Cochet-Terrasson and Gaubert in 2006, who assumed an exact model of

the arithmetics and the finiteness of action spaces. This algorithm

does not require any irreducibility assumption on the Markov chains

determined by the strategies of the players. It is based on a discrete

nonlinear analogue of the notion of reduction of a super-harmonic

function, which ensures the convergence even in the case of degenerate

iterations, in which the mean payoff is not improved. Hence, it can

be applied to monotone discretizations of stationary Isaacs partial

differential equations without any strong ellipticity assumption. We

report examples on Isaacs equations, as well as on a discrete

combinatorial game (variant of the infinity Laplacian on a graph) in

which degenerate iterations do occur. We also discuss numerical

issues due to ill conditioned linear problems.