Zurück zur Übersicht Donnerstag, 16.05.2019
Donnerstag | 14.15 Uhr | A Sequential Homotopy Method for Mathematical Programming Problems: Privatdozent Dr. Andreas Potschka, Universität Heidelberg, Interdisciplinary Center for Scientific Computing We consider nonconvex and highly nonlinear mathematical programming problems including finite dimensional nonlinear programming problems as well as optimization problems with partial differential equations and control constraints. We present a novel numerical solution method, which is based on a projected gradient/anti-gradient flow for an augmented Lagrangian on the primal/dual variables. We show that under reasonable assumptions, the nonsmooth flow equations possess uniquely determined global solutions, whose limit points (provided that they exist) are critical, i.e., they satisfy a first-order necessary optimality condition. Under additional mild conditions, a critical point cannot be asymptotically stable if it has an emanating feasible curve along which the objective function decreases. This implies that small perturbations will make the flow escape critical points that are maxima or saddle points. If we apply a projected backward Euler method to the flow, we obtain a semismooth algebraic equation, whose solution can be traced for growing step sizes, e.g., by a continuation method with a local (inexact) semismooth Newton method as a corrector, until a singularity is encountered and the homotopy cannot be extended further. Moreover, the projected backward Euler equations admit an interpretation as necessary optimality conditions of a proximal-type regularization of the original problem. The prox-problems have favorable properties, which guarantee that the prox-problems have uniquely determined primal/dual solutions if the Euler step size is sufficiently small and the augmented Lagrangian parameter is sufficiently large. The prox-problems morph into the original problem when taking the step size to infinity, which allows the following active-set-type sequential homotopy method: From the current iterate, compute a projected backward Euler step by applying either local (inexact) semismooth Newton iterations on the step equations or local (inexact) SQP-type (sequential quadratic programming) methods on the prox-problems. If the homotopy cannot be continued much further, take the current result as a starting point for the next projected backward Euler step. If we can drive the step size all the way to infinity, we can transition to fast local convergence. We can interpret this sequential homotopy method as extensions to several well-known but seemingly unrelated optimization methods: A general globalization method for local inexact semismooth Newton methods and local inexact SQP-type methods, a proximal point algorithm for problems with explicit constraints, and an implicit version of the Arrow--Hurwicz gradient method for convex problems dating back to the 1950s extended to nonconvex problems. We close the talk with numerical results for a class of highly nonlinear and badly conditioned control constrained elliptic optimal control problems with a semismooth Newton approach for the regularized subproblems. Adresse Mathematikon Room 02/414, 2nd Floor Im Neuenheimer Feld 205 69120 Heidelberg Homepage Veranstaltung www.iwr.uni-heidelberg.de/events Veranstalter Interdisciplinary Center for Scientific Computing (IWR) Homepage Veranstalter Kontakt Kontakt URL http://www.iwr.uni-heidelberg.de/groups/mobocon/research-group/dr-andreas-potschka/ |