{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/116209"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/116209","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Inexact interior point methods for constrained convex quadratic optimization problems","abstract":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-11-15 without embargo terms","abstract_html":"Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-11-15 without embargo terms","abstract_has_math":false,"creators":["Karim, Samah"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Solomonik, Edgar","Gropp, William","Olson, Luke","Chow, Edmond"],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2022,"date_issued":"2022-08","date_published":"2022-08","updated_at":"2026-07-22T22:24:55Z","subjects":["Primal-dual interior point methods","KKT systems","Krylov subspace methods","Preconditioning"],"languages":["en","eng"],"rights":["Copyright 2022 Samah Karim"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/2142/116209","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Solomonik, Edgar","Gropp, William","Olson, Luke","Chow, Edmond"]},{"key":"dc:creator","label":"Author","values":["Karim, Samah"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2022-08","2022-07-12"]},{"key":"dc:type","label":"Dc Type","values":["text","Thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Primal-dual interior point methods","KKT systems","Krylov subspace methods","Preconditioning"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en","eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2022 Samah Karim"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["https://hdl.handle.net/2142/116209"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-11-15 without embargo terms","The student, Samah Karim, accepted the attached license on 2022-07-11 at 13:46.","The student, Samah Karim, submitted this Dissertation for approval on 2022-07-11 at 14:00.","This Dissertation was approved for publication on 2022-07-12 at 12:56.","DSpace SAF Submission Ingestion Package generated from Vireo submission #18220 on 2022-11-15 at 17:38:43","This work proposes a new inexact interior point algorithm for convex quadratic programming problems with both equality and inequality constraints. Our method uses new preconditioned iterative methods to solve the linear systems that arise at every Newton step. These preconditioned conjugate gradient methods operate on an implicit Schur complement of the KKT system at each iteration. In contrast to standard approaches, the Schur complement we consider enables the reuse of the factorization of a fixed KKT subsystem across all interior point iterations. Further, the resulting reduced system admits preconditioners that directly alleviate the ill-conditioning associated with the strict complementarity condition in interior point methods. We propose two preconditioners that provably reduce the number of unique eigenvalues for the coefficient matrix (CG iteration count). One is efficient when the number of equality constraints is small, while the other is efficient when the number of remaining degrees of freedom is small. Numerical experiments with synthetic problems and problems from the Maros-Mészáros QP collection show that our preconditioned inexact interior point solvers are effective at improving conditioning and reducing cost relative to the best alternative preconditioned method for each problem. We first assume positive-definiteness of the Hessian then consider two additional cases distinguished by the invertibility of the KKT subsystem. We adapt the formulation of our inexact interior point method, as well as new preconditioners that account for the singularity of the Hessian, and the KKT subsystem respectively."]},{"key":"dc:format","label":"Dc Format","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Inexact interior point methods for constrained convex quadratic optimization problems"]}]}],"canonical_facts":{"dc:contributor":["Solomonik, Edgar","Gropp, William","Olson, Luke","Chow, Edmond"],"dc:creator":["Karim, Samah"],"dc:date":["2022-08","2022-07-12"],"dc:description":["Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-11-15 without embargo terms","The student, Samah Karim, accepted the attached license on 2022-07-11 at 13:46.","The student, Samah Karim, submitted this Dissertation for approval on 2022-07-11 at 14:00.","This Dissertation was approved for publication on 2022-07-12 at 12:56.","DSpace SAF Submission Ingestion Package generated from Vireo submission #18220 on 2022-11-15 at 17:38:43","This work proposes a new inexact interior point algorithm for convex quadratic programming problems with both equality and inequality constraints. Our method uses new preconditioned iterative methods to solve the linear systems that arise at every Newton step. These preconditioned conjugate gradient methods operate on an implicit Schur complement of the KKT system at each iteration. In contrast to standard approaches, the Schur complement we consider enables the reuse of the factorization of a fixed KKT subsystem across all interior point iterations. Further, the resulting reduced system admits preconditioners that directly alleviate the ill-conditioning associated with the strict complementarity condition in interior point methods. We propose two preconditioners that provably reduce the number of unique eigenvalues for the coefficient matrix (CG iteration count). One is efficient when the number of equality constraints is small, while the other is efficient when the number of remaining degrees of freedom is small. Numerical experiments with synthetic problems and problems from the Maros-Mészáros QP collection show that our preconditioned inexact interior point solvers are effective at improving conditioning and reducing cost relative to the best alternative preconditioned method for each problem. We first assume positive-definiteness of the Hessian then consider two additional cases distinguished by the invertibility of the KKT subsystem. We adapt the formulation of our inexact interior point method, as well as new preconditioners that account for the singularity of the Hessian, and the KKT subsystem respectively."],"dc:format":["application/pdf"],"dc:identifier":["https://hdl.handle.net/2142/116209"],"dc:language":["en","eng"],"dc:rights":["Copyright 2022 Samah Karim"],"dc:subject":["Primal-dual interior point methods","KKT systems","Krylov subspace methods","Preconditioning"],"dc:title":["Inexact interior point methods for constrained convex quadratic optimization problems"],"dc:type":["text","Thesis"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:24:55Z"}