Virginia Tech
    • Log in
    View Item 
    •   VTechWorks Home
    • ETDs: Virginia Tech Electronic Theses and Dissertations
    • Masters Theses
    • View Item
    •   VTechWorks Home
    • ETDs: Virginia Tech Electronic Theses and Dissertations
    • Masters Theses
    • View Item
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Preconditioning of Karush--Kuhn--Tucker Systems arising in Optimal Control Problems

    Thumbnail
    View/Open
    etd.pdf (1.499Mb)
    Downloads: 274
    Date
    1996-06-14
    Author
    Battermann, Astrid
    Metadata
    Show full item record
    Abstract
    This work is concerned with the construction of preconditioners for indefinite linear systems. The systems under investigation arise in the numerical solution of quadratic programming problems, for example in the form of Karush--Kuhn--Tucker (KKT) optimality conditions or in interior--point methods. Therefore, the system matrix is referred to as a KKT matrix. It is not the purpose of this thesis to investigate systems arising from general quadratic programming problems, but to study systems arising in linear quadratic control problems governed by partial differential equations. The KKT matrix is symmetric, nonsingular, and indefinite. For the solution of the linear systems generalizations of the conjugate gradient method, MINRES and SYMMLQ, are used. The performance of these iterative solution methods depends on the eigenvalue distribution of the matrix and of the cost of the multiplication of the system matrix with a vector. To increase the performance of these methods, one tries to transform the system to favorably change its eigenvalue distribution. This is called preconditioning and the nonsingular transformation matrices are called preconditioners. Since the overall performance of the iterative methods also depends on the cost of matrix--vector multiplications, the preconditioner has to be constructed so that it can be applied efficiently. The preconditioners designed in this thesis are positive definite and they maintain the symmetry of the system. For the construction of the preconditioners we strongly exploit the structure of the underlying system. The preconditioners are composed of preconditioners for the submatrices in the KKT system. Therefore, known efficient preconditioners can be readily adapted to this context. The derivation of the preconditioners is motivated by the properties of the KKT matrices arising in optimal control problems. An analysis of the preconditioners is given and various cases which are important for interior point methods are treated separately. The preconditioners are tested on a typical problem, a Neumann boundary control for an elliptic equation. In many important situations the preconditioners substantially reduce the number of iterations needed by the solvers. In some cases, it can even be shown that the number of iterations for the preconditioned system is independent of the refinement of the discretization of the partial differential equation.
    URI
    http://hdl.handle.net/10919/9579
    Collections
    • Masters Theses [19415]

    If you believe that any material in VTechWorks should be removed, please see our policy and procedure for Requesting that Material be Amended or Removed. All takedown requests will be promptly acknowledged and investigated.

    Virginia Tech | University Libraries | Contact Us
     

     

    VTechWorks

    AboutPoliciesHelp

    Browse

    All of VTechWorksCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    Log inRegister

    Statistics

    View Usage Statistics

    If you believe that any material in VTechWorks should be removed, please see our policy and procedure for Requesting that Material be Amended or Removed. All takedown requests will be promptly acknowledged and investigated.

    Virginia Tech | University Libraries | Contact Us