Refine
Language
- English (16)
Keywords
- KKT-System (1)
- LU decomposition (1)
- TR1 Update (1)
- adjoint based updating (1)
- chromatic staff notation (1)
- convergence order (1)
- equally tempered scale (1)
- local convergence (1)
- major thirds (1)
- nonlinear equations (1)
- quai-Newton (1)
- quasi-Newton (1)
- quasi-Newton methods (1)
- updating factorization (1)
Automatic, or algorithmic, differentiation addresses the need for the accurate
and efficient calculation of derivative values in scientific computing. To this
end procedural programs for the evaluation of problem-specific functions are
transformed into programs that also compute the required derivative values
at the same numerical arguments in floating point arithmetic. Disregarding
many important implementation issues, we examine in this article complexity
bounds and other more mathematical aspects of the program transformation
task sketched above.
In this paper we introduce a new method for the computation of KKT matrices that arise from solving constrained, nonlinear optimization problems. This method requires updating of null-space factorizations after a low rank modification. The update procedure has the advantage that it is significantly cheaper than a re-factorization of the system at each new iterate. This paper focuses on the cheap update of a rectangular LU decomposition after a rank-1 modification.
Two different procedures for updating the LU factorization are presented in detail and compared regarding their costs of computation and their stability. Moreover we will introduce an extension of these algorithms which further improves the computation time. This turns out to be an excellent alternative to algorithms based on orthogonal transformations.
Quasi-Newton methods based on least change secant updating
formulas that solve linear equations $Ax=b$ in $n=\dim(x)=\dim(b)$ steps
can be expected to solve corresponding smooth nonlinear
systems $n$-step quadratically, i.e. with an $r$-order
of $\rho = 2^{1/n} = 1 + 1/n +O(1/n^2)$. The best rate one can
possibly expect on general problems is given by the positive root
$\rho_n$ of $\rho^n(\rho -1)=1$, for which
$\rho_n-1 = \ln(n)/n + O(1/n^2)$. To show that this upper bound is
actually achieved one usually has to impose a priori some kind of
linear independence condition on the sequence of steps taken by the
quasi-Newton iteration in question. Without any such assumptions we
establish in this paper the convergence order $\rho_n$ for the
two-sided rank one formula proposed by Schlenkrich et al in \cite{SGW06}.
It requires the evaluation of adjoint vectors, is invariant with respect
to linear transformations on the variable domain and combines the
properties of bounded deterioration and heredity.
For the solution of nonlinear equation systems
quasi-Newton methods based on low-rank updates are of particular interest. We analyze a class
of TR1 update formulas to approximate the system Jacobian. The local q-superlinear convergence for nonlinear problems is proved for a particular subclass of updates. Moreover, we give an estimate of the r-order of convergence. Numerical results comparing the TR1 method to Newton's and other quasi-Newton methods atr presented.
Cross–derivatives are mixed partial derivatives that are obtained by differentiating at most
once in every coordinate direction. They are a computational tool in combinatorics and high–
dimensional integration. Here we present two methods of computing exact values of all cross–
derivatives at a given point both following the general philosophy of automatic differentiation.
Implementation details are discussed and numerical results given.
This paper proposes a new mathematical model for the open pit mine planning problem,
based on continuous functional analysis. The traditional models for this problem have been
constructed by using discrete 0-1 decision variables, giving rise to large-scale combinatorial
and Mixed Integer Programming (MIP) problems. Instead, we use a continuous approach
which allows for a refined imposition of slope constraints associated with geotechnical stability.
The model introduced here is posed in a suitable functional space, essentially the
real-valued functions that are Lipschitz continuous on a given two dimensional bounded region.
We derive existence results and investigate some qualitative properties of the solutions
Duality Results for Stationary Problems of Open Pit Mine Planning in a Continuous Function Framework
(2011)
Open Pit Mine Planning problems are usually considered in a Mixed Integer Programming
context. Characterizing each attainable profile by a continuous function yields a continuous
framework. It allows for a more detailed modeling of slope constraints and other material
properties of slanted layers. Although the resulting nonlinear programming problems are
in general non-convex and non-differentiable, they provide certain advantages as one can
directly compute sensitivities of optimal solutions w.r.t. small data perturbations. In this
work duality results are derived for the stationary problems of the continuous framework
employing an additional condition called convex-likeness.
Time-lag in Derivative Convergence Time-lag in Derivative Convergence for Fixed Point Iterations
(2004)
In an earlier study it was proven and experimentally confirmed on a 2D Euler code
that fixed point iterations can be differentiated to yield first and second order derivatives of
implicit functions that are defined by state equations. It was also asserted that the resulting
approximations for reduced gradients and Hessians converge with the same R-factor as the
underlying fixed point iteration.
A closer look reveals now that nevertheless these derivative values lag behind the functions
values in that the ratios of the corresponding errors grow proportional to the iteration counter
or its square towards infinity. This rather subtle effect is caused mathematically by the
occurrence of nontrivial Jordan blocks associated with degenerate eigenvalues. We elaborate
the theory and report its confirmation through numerical experiments.
On the Efficient Generation of Taylor Expansions for DAE Solutions by Automatic Differentiation
(2005)
Under certain conditions the signature method suggested by
Pantiledes and Pryce facilitates the local expansion of DAE solutions
by Taylor polynomials of arbitrary order. The successive calculation of
Taylor coefficients involves the solution of nonlinear algebraic equations
by some variant of the Gauss-Newton method. Hence, one needs to evaluate
certain Jacobians and several right hand sides. Without advocating
a particular solver we discuss how this information can be efficiently
obtained using ADOL-C or similar automatic differentiation packages.3
One-shot optimization aims at attaining feasibility and optimality simultane-
ously, especially on problems where even the linearized constraint equations
cannot be resolved economically. Here we consider a scenario where forming
and factoring the active Jacobian is out of the question, as is for example the
case when the constraints represent some discretization of the Navier Stokes
equation. Assuming that the 'user' provides us with a linearly converging solver
that gradually restores feasibility after each change in the design variables, we
derive a corresponding adjoint iteration and attach an optimization (sub)step.
The key question addressed is how the approximate reduced gradient generated
by the adjoint iteration should be preconditioned in order to achieve overall
convergence at a reasonable speed. An eigenvalue analysis yields necessary
conditions on the preconditioning matrix, which are typically not satised by
the familiar reduced Hessian. Some other projection of the Lagrangian Hessian
appears more promising and is found to work very satisfactorily on a nonlinear
test problem.
The analyzed approach is one-step in that the normal, dual and design variables
are always updated simultaneously on the basis of one function evaluation and
its adjoint. Multi-step variants are promising but remain to be investigated.
We consider a time-dependent optimal control problem, where the state
evolution is described by an ODE. There is a variety of methods for the treatment
of such problems. We prefer to view them as boundary value problems and apply to
them the Riccati approach for non-linear BVPs with separated boundary conditions.
There are many relationships between multiple shooting techniques, the Riccati
approach and the Pantoja method, which describes a computationally efficient
stage-wise construction of the Newton direction for the discrete-time optimal control
problem.
We present an efficient implementation of this approach. Furthermore, the wellknown
checkpointing approach is extended to a `nested checkpointing` for multiple
transversals. Some heuristics are introduced for an efficient construction of nested
reversal schedules. We discuss their benefits and compare their results to the optimal
schedules computed by exhaustive search techniques.
Systems of stiff ordinary differential equations (ODEs) can be integrated
properly only by implicit methods. For that purpose, one usually has to
solve a system of nonlinear equations at each time step. This system of equations
may be solved by variants of Newton's method. Here, the main computing effort lies
in forming and factoring the Jacobian or a suitable approximation to it.
In this paper, we examine a new approach of constructing an appropriate quasi-
Newton approximation for solving stiff ODEs. The method makes for the first time
explicit use of tangent and adjoint information that can be obtained using the forward
and the reverse mode of algorithmic differentiation (AD). We elaborate the
conditions for invariance with respect to linear transformations of the state space
and thus similarity transformations of the Jacobian. One new updating variant that
yields such an invariant method is presented. Numerical results for Runge-Kutta
methods and linear multi-step methods are discussed.
Adjoint Broyden a la GMRES
(2007)
It is shown here that a compact storage implementation of a quasi-Newton
method based on the adjoint Broyden update reduces in the affine
case exactly to the well established GMRES procedure. Generally,
storage and linear algebra effort per step are small multiples of $n\cdot k$,
where $n$ is the number of variables and $k$ the number of steps taken
in the current cycle. In the affine case the storage is exactly $(n+k)\cdot k$
and in the nonlinear case the same bound can be achieved if adjoints,
i.e. transposed Jacobian-vector products are available. A
transposed-free variant that relies exclusively on Jacobian-vector
products (or possibly their approximation by divided differences)
requires roughly twice the storage and turns out to be somewhat slower
in our numerical experiments reported at the end.