Martin Neuenhofen

Martin Neuenhofen

In this text I present a couple of new principles and thereon based iterative methods for numerical solution of sequences of systems of linear equations with fixed system matrix and changing right-hand-sides. The use of the new methods is to recycle all subspace information that is obtained anyway in the solution process of a former system, to solve subsequent systems. All these principles and methods are based on short recurrences and small storage requirements. The principles are based on the IDR-theorem and the Horner scheme for polynomials.

Martin Neuenhofen

We introduce a particular optimization problem that minimizes the sum of a non-convex quadratic function and logarithmic barrier-functions in a $\ell_\infty$-trust-region (i.e. cube). Our paper covers three topics. We explain the relevance of the considered problem. We lay out how solutions of this problem can be used as efficient step-directions in solution methods for nonlinear programming. We present a theoretical algorithm for solving the problem. We show that this algorithm has weak polynomial time-complexity. A practical method is under development. In the outlook we discuss how the given method can be accelerated for better practical performance. We also lay out where the difficulties live when trying to formulate an accelerated primal-dual variant.

Martin Neuenhofen

The Augmented Lagrangian Method (ALM) is an iterative method for the solution of equality-constrained non-linear programming problems. In contrast to the quadratic penalty method, the ALM can satisfy equality constraints in an exact way. Further, ALM is claimed to converge in less iterations, indicating that it is superior in approach to a quadratic penalty method. It is referred to as an advantage that the ALM solves equality constraints in an exact way, meaning that the penalty parameter does not need to go to infinity in order to yield accurate feasibility for the constraints. However, we sometimes actually want to minimize an unconstrained problem that has large quadratic penalty terms. In these situations it is unclear how the ALM could be utilized in the correct way. This paper presents the answer: We derive a modified version of the ALM that is also suitable for solving functions with large quadratic penalty terms.

Martin Neuenhofen

We are concerned with the fastest possible direct numerical solution algorithm for a thin-banded or tridiagonal linear system of dimension $N$ on a distributed computing network of $N$ nodes that is connected in a binary communication tree. Our research is driven by the need for faster ways of numerically solving discretized systems of coupled one-dimensional black-box boundary-value problems. Our paper presents two major results: First, we provide an algorithm that achieves the optimal parallel time complexity for solving a tridiagonal linear system and thin-banded linear systems. Second, we prove that it is impossible to improve the time complexity of this method by any polynomial degree. To solve a system of dimension $m\cdot N$ and bandwidth $m \in Ω(N^{1/6})$ on $2 \cdot N-1$ computing nodes, our method needs time complexity $\mathcal{O}(\log(N)^2 \cdot m^3)$.

Martin Neuenhofen

In this paper we present a novel numerical method for computing local minimizers of twice smooth differentiable non-linear programming (NLP) problems. So far all algorithms for NLP are based on either of the following three principles: successive quadratic programming (SQP), active sets (AS), or interior-point methods (IPM). Each of them has drawbacks. These are in order: iteration complexity, feasibility management in the sub-program, and utility of initial guesses. Our novel approach attempts to overcome these drawbacks. We provide: a mathematical description of the method; proof of global convergence; proof of second order local convergence; an implementation in \textsc{Matlab}; experimental results for large sparse NLPs from direct transcription of path-constrained optimal control problems.

Martin Neuenhofen

Cyclic reduction is a method for the solution of (block-)tridiagonal linear systems. In this note we review the method tailored to hermitian positive definite banded linear systems. The reviewed method has the following advantages: It is numerically stable without pivoting. It is suitable for parallel computations. In the presented form, it uses fewer computations by exploiting symmetry. Like Cholesky, the reviewed method breaks down when the matrix is not positive definite, offering a robust way for determining positive definiteness.

Martin Neuenhofen

We propose a numerical method, based on the shift-and-invert power iteration, that answers whether a symmetric matrix is positive definite ("yes") or not ("no"). Our method uses randomization. But, it returns the correct answer with high probability. A thorough proof for the probability is presented. If the method answers "yes", the result is true with a high constant probability. If it answers "no", it provides proof that the matrix is not positive definite. The method has the following benefits: The cost for a constant probability of success scales logarithmically with the condition number. Further, since essentially consisting of vector iterations, our method is easy to implement.

Martin Neuenhofen

In a recent work (arXiv-DOI: 1804.08072v1) we introduced the Modified Augmented Lagrangian Method (MALM) for the efficient minimization of objective functions with large quadratic penalty terms. From MALM there results an optimality equation system that is related to that of the original objective function. But, it is numerically better behaved, as the large penalty factor is replaced by a milder factor. In our original work, we formulated MALM with an inner iteration that applies a Quasi-Newton iteration to compute the root of a multi-variate function. In this note we show that this formulation of the scheme with a Newton iteration can be replaced conveniently by formulating a well-scaled unconstrained minimization problem. In this note, we briefly review the Augmented Lagrangian Method (ALM) for minimizing equality-constrained problems. Then we motivate and derive the new proposed formulation of MALM for minimizing unconstrained problems with large quadratic penalties. Eventually, we discuss relations between MALM and ALM.

Martin Neuenhofen

We present a numerical method for the local solution of nonlinear programming problems. The SUMT approach of Fiacco and McCormick results in a merit function with quadratic penalties and logarithmic barriers. Our NLP solver works by directly minimizing this merit function. In our method, we use different concepts that each shall aim at the efficient treatment of one respective special feature of this merit function. The features are: large quadratic penalty terms, and badly scaled logarithmic barriers. The quadratic penalties are treated with a modified Augmented Lagrangian technique. It enables large step sizes despite nonlinearity of the equality constraints. The logarithmic barriers we treat with a primal-dual interior-point path-following technique. We prove global convergence of the method and local quadratic convergence. We further prove weak polynomial time-complexity in the special case where the nonlinear program is a linear program. We also use a trust-funnel so to avoid that the method converges to any stationary points that are infeasible to the constraints.