90C51 Interior-point 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
Institute
"Interior point algorithms are a good choice for solving pure LPs or QPs, but when you solve MIPs, all you need is a dual simplex." This is the common conception which disregards that an interior point solution provides some unique structural insight into the problem at hand. In this paper, we will discuss some of the benefits that an interior point solver brings to the solution of difficult MIPs within FICO Xpress. This includes many different components of the MIP solver such as branching variable selection, primal heuristics, preprocessing, and of course the solution of the LP relaxation.
In this paper we are concerned with the application of interior point methods in function space to gradient constrained optimal control problems, governed by partial differential equations. We will derive existence of solutions together with first order optimality conditions. Afterwards we show continuity of the central path, together with convergence rates depending on the interior point parameter.
Interior Point Methods in Function Space for State Constraints - Inexact Newton and Adaptivity
(2008)
We consider an interior point method in function space for PDE constrained optimal control problems with state constraints. Our emphasis is on the construction and analysis of an algorithm that integrates a Newton path-following method with adaptive grid refinement. This is done in the framework of inexact Newton methods in function space, where the discretization error of each Newton step is controlled by adaptive grid refinement in the innermost loop. This allows to perform most of the required Newton steps on coarse grids, such that the overall computational time is dominated by the last few steps. For this purpose we propose an a-posteriori error estimator for a problem suited norm.
We propose and analyse an interior point path-following method in function space for state constrained optimal control. Our emphasis is on proving convergence in function space and on constructing a practical path-following algorithm. In particular, the introduction of a pointwise damping step leads to a very efficient method, as verified by numerical experiments.
We study barrier methods for state constrained optimal control problems with PDEs. In the focus of our analysis is the path of minimizers of the barrier subproblems with the aim to provide a solid theoretical basis for function space oriented path-following algorithms. We establish results on existence, continuity and convergence of this path. Moreover, we consider the structure of barrier subdifferentials, which play the role of dual variables.
This paper is concerned with the sensitivities of function space oriented interior point approximations in parameter dependent problems. For an abstract setting that covers control constrained optimal control problems, the convergence of interior point sensitivities to the sensitivities of the optimal solution is shown. Error bounds for $L_q$ norms are derived and illustrated with numerical examples.
A thorough convergence analysis of the Control Reduced Interior Point Method in function space is performed. This recently proposed method is a primal interior point pathfollowing scheme with the special feature, that the control variable is eliminated from the optimality system. Apart from global linear convergence we show, that this method converges locally almost quadratically, if the optimal solution satisfies a function space analogue to a non-degeneracy condition. In numerical experiments we observe, that a prototype implementation of our method behaves in compliance with our theoretical results.
The paper addresses primal interior point method for state constrained PDE optimal control problems. By a Lavrentiev regularization, the state constraint is transformed to a mixed control-state constraint with bounded Lagrange multiplier. Existence and convergence of the central path are established, and linear convergence of a short-step pathfollowing method is shown. The behaviour of the regularizations are demonstrated by numerical examples.
A primal interior point method for control constrained optimal control problems with PDE constraints is considered. Pointwise elimination of the control leads to a homotopy in the remaining state and dual variables, which is addressed by a short step pathfollowing method. The algorithm is applied to the continuous, infinite dimensional problem, where discretization is performed only in the innermost loop when solving linear equations. The a priori elimination of the least regular control permits to obtain the required accuracy with comparable coarse meshes. Convergence of the method and discretization errors are studied, and the method is illustrated at two numerical examples.