An Interior-Point Algorithm for Large Scale Optimization
This paper describes an interior-point algorithm for solving large scale nonlinear programming problems. The fundamental step of the algorithm requires solution of a sparse symmetric indefinite linear system. Rowand column scaling are used to ensure that
- PDF / 1,668,402 Bytes
- 15 Pages / 439 x 666 pts Page_size
- 58 Downloads / 232 Views
Mathematics and Engineering Analysis, The Boeing Company, P.O. Box 3707, MC 7L-21, Seattle, Washington 98124-2207 Expedia, Inc. 13810 SE Eastgate Way, Suite 400, Bellevue, WA 98005
Abstract. This paper describes an interior-point algorithm for solving large scale nonlinear programming problems. The fundamental step of the algorithm requires solution of a sparse synunetric indefinite linear system. Rowand column scaling are used to ensure that the system is well-conditioned. A globalization strategy based on a nonlinear filter is used instead of a merit function. The computational performance of the algorithm is demonstrated on a high index partial differentialalgebraic equation application.
1
Introduction
When a physical process modeled by a partial differential equation is discretized, the result is often a large scale optimization problem. Usually inequality constraints are required in order to accurately model the process. When there are many inequality constraints, determining the correct set of active constraints can be an extremely costly computational burden. To address the shortcomings of active set algorithms, there has been considerable interest in another class of methods for nonlinear applications. In these interior-point or barrier methods [5,8,9], some of the combinatorial issues are dealt with by incorporating the inequality constraints into the objective using a barrier transformation. A sequence of these equality constrained problems is solved with the solution of each subsequent subproblem being used to provide an improvement in the estimate of the solution of the original inequality constrained problem. In addition to attempting to avoid the computational complexity of active-set methods, these barrier methods possess a second attribute that makes them attractive for large-scale optimization. Specifically, the form of the underlying sparse linear equations can be exploited by state of the art direct factorization techniques. The purpose of this paper is to describe a basic interior-point algorithm designed for large-scale applications. First we define the nonlinear program in a format that is convenient for development of barrier methods. We then present the barrier method including descriptions of important operations. We conclude with a section on computational results. Although our current results were obtained using direct linear algebra, it is expected that most of L. T. Biegler et al. (eds.), Large-Scale PDE-Constrained Optimization © Springer-Verlag Berlin Heidelberg 2003
Interior-Point Algorithm for Large Scale Optimization
185
the methods will extend to applications that require iterative solution of the linear systems.
2
The Nonlinear Programming Problem
The nonlinear programming problem can be stated as follows: Minimize the function
fey) == f(x)
(1)
of the n variables
(2) subject to the
mE
nonlinear equality constraints
(3) and the
mB
linear bounds
(x - ~)Bl (x-x)B 2 bey) ==
(8 - !!X)B3
(4)
(ax - 8)B4
Observe that this internal format explicitly includes user-
Data Loading...
