49M15 Newton-type methods
Refine
Year of publication
Document Type
- ZIB-Report (14)
Language
- English (14)
Has Fulltext
- yes (14)
Is part of the Bibliography
- no (14)
Keywords
- optimal control (9)
- interior point methods in function space (5)
- Newton-CG (2)
- complementarity functions (2)
- finite elements (2)
- trajectory storage (2)
- Burgers' equation (1)
- Kantorovich Theorem (1)
- Linear complementarity problem (1)
- Newton methods in function space (1)
- affine conjugate Newton methods (1)
- affine invariance (1)
- affine invariant norms (1)
- compression (1)
- continuity of Nemyckii Operators (1)
- cranio-maxillofacial surgery (1)
- defibrillation (1)
- discretization error (1)
- inertia (1)
- interior point methods (1)
- interior-point algorithm (1)
- interior-point method (1)
- lossy compression (1)
- monodomain model (1)
- multigrid methods (1)
- multilev (1)
- multilevel incomplete factorization (1)
- multiplier methods (1)
- nonconvex constrained optimization (1)
- nonconvex minimization (1)
- nonlinear elastomechnics (1)
- nonlinear programming (1)
- path-following (1)
- second order sufficient conditions (1)
- semilinear parabolic PDEs (1)
- soft tissue simulation (1)
- state constraints (1)
- superlinear convergence (1)
- variational inequalities (1)
Institute
- Computational Medicine (10)
- Numerical Mathematics (9)
- ZIB Allgemein (5)
A new approach to the numerical solution of optimal control problems including control and state constraints is presented. Like hybrid methods, the approach aims at combining the advantages of direct and indirect methods. Unlike hybrid methods, however, our method is directly based on interior-point concepts in function space --- realized via an adaptive multilevel scheme applied to the complementarity formulation and numerical continuation along the central path. Existence of the central path and its continuation towards the solution point is analyzed in some theoretical detail. An adaptive stepsize control with respect to the duality gap parameter is worked out in the framework of affine invariant inexact Newton methods. Finally, the performance of a first version of our new type of algorithm is documented by the successful treatment of the well-known intricate windshear problem.
An affine invariant convergence analysis for inexact augmented Lagrangian-SQP methods is presented. The theory is used for the construction of an accuracy matching between iteration errors and truncation errors, which arise from the inexact linear system solves. The theoretical investigations are illustrated numerically by an optimal control problem for the Burgers equation.
A path following algorithm for linear complementarity problems is presented. Given a point $z$ that approximates a point $z(\tau)$ on the central path with complementarity gap $\tau$, one determines a parameter $\theta\in (0,1)$ so that this point satisfies the hypothesis of the affine invariant Kantorovich Theorem for the equation defining $z((1-\theta)\tau)$. It is shown that $\theta$ is bounded below by a multiple of $n^{-1/2}$, where $n$ is the dimension of the problem. Since the hypothesis of of the Kantorovich Theorem is satisfied the sequence generated by Newton's method, or by the simplified Newton method, will converge to $z((1-\theta)\tau)$. We show that the number of steps required to obtain an acceptable approximation of $z((1-\theta)\tau)$ is bounded above by a number independent of $n$. Therefore the algorithm has $O(\sqrt{n}L)$-iteration complexity. The parameters of the algorithm can be determined in such a way that only one Newton step is needed each time the complementarity gap is decreased.
A wide range of free boundary problems occurring in engineering andindustry can be rewritten as a minimization problem for astrictly convex, piecewise smooth but non--differentiable energy functional.The fast solution of related discretized problemsis a very delicate question, because usual Newton techniquescannot be applied. We propose a new approach based on convex minimization and constrained Newton type linearization. While convex minimization provides global convergence of the overall iteration, the subsequent constrained Newton type linearization is intended to accelerate the convergence speed. We present a general convergence theory and discuss several applications.