Non-differentiable optimization methods for solving large problems: application to medium-term production management.

Summary This thesis is concerned with the solution of large non-differentiable optimization problems, most often resulting from a Lagrangian relaxation of a difficult problem. This technique is commonly used to solve linear integer problems or complex convex problems. The obtained dual problem is non-differentiable -possibly separable- and can be solved by a bundle algorithm. Chapter 2 proposes a literature review of non-differentiable optimization methods. In some situations, the dual problem can itself be very difficult to solve and require adapted strategies. For example, when the number of dualized constraints is very high, an explicit dualization may be impossible or the updating of dual variables may fail. In chapter 3, we study the convergence properties when a dynamic Lagrangian relaxation is performed: only a subset of constraints is dualized at each iteration, which allows to reduce the dimension of the dual problem. Another limit of Lagrangian relaxation can appear when the dual function is separable into a large number of sub-functions, or when these sub-functions remain difficult to evaluate. A natural strategy is then to take advantage of the separable reading by performing dual iterations having evaluated only a subset of the subfunctions. In Chapter 4, we propose to use a beam method in this incremental context. Finally, Chapter 5 presents numerical applications on power generation management problems.