Schenk/nlpkkt240
Symmetric indefinite KKT matrix, O. Schenk, Univ. of Basel
Name 
nlpkkt240 
Group 
Schenk 
Matrix ID 
1905 
Num Rows

27,993,600 
Num Cols

27,993,600 
Nonzeros

760,648,352 
Pattern Entries

774,472,352 
Kind

Optimization Problem 
Symmetric

Yes 
Date

2008 
Author

O. Schenk, A. Waechter, M. Weiser 
Editor

T. Davis 
Structural Rank 
27,993,600 
Structural Rank Full 
true 
Num Dmperm Blocks

1 
Strongly Connect Components

1 
Num Explicit Zeros

13,824,000 
Pattern Symmetry

100% 
Numeric Symmetry

100% 
Cholesky Candidate

no 
Positive Definite

no 
Type

real 
Download 
MATLAB
Rutherford Boeing
Matrix Market

Notes 
Symmetric indefinite KKT matrices, O. Schenk, Univ. of Basel,
Switzerland
Nonlinear programming problems for a 3D PDEconstrained optimization
problem with boundary control as a function of the discretization
parameter N using 2ndorder finite difference approximations.
O. Schenk, A. W\"achter, and M. Weiser, Inertia Revealing
Preconditioning For LargeScale Nonconvex Constrained Optimization,
Technical Report, Unversity of Basel, 2008, submitted.
Abstract: Fast nonlinear programming methods following the
allatonce approach usually employ Newton's method for solving
linearized KarushKuhnTucker (KKT) systems. In nonconvex problems,
the Newton direction is only guaranteed to be a descent direction if
the Hessian of the Lagrange function is positive definite on the
nullspace of the active constraints, otherwise some modifications to
Newton's method are necessary. This condition can be verified using
the signs of the KKT's eigenvalues (inertia), which are usually
available from direct solvers for the arising linear saddle point
problems. Iterative solvers are mandatory for very largescale
problems, but in general do not provide the inertia. Here we present
a preconditioner based on a multilevel incomplete LBL^T
factorization, from which an approximation of the inertia can be
obtained. The suitability of the heuristics for application in
optimization methods is verified on an interior point method applied
to the CUTE and COPS test problems, on largescale 3D PDEconstrained
optimal control problems, as well as 3D PDEconstrained optimization
in biomedical cancer hyperthermia treatment planning. The efficiency
of the preconditioner is demonstrated on convex and nonconvex
problems with 1503 state variables and 1502 control variables, both
subject to bound constraints.
