Dissertation
Advances in convex relaxations for quadratic optimization: a study on conic programming relaxations including second-order-cone and semidefinite programming
University of Iowa
Doctor of Philosophy (PhD), University of Iowa
Summer 2023
DOI: 10.25820/etd.007220
Abstract
Quadratic optimization problems are crucial in various applications, ranging from engineering and science to economics. However, solving nonconvex quadratic problems can be computationally challenging due to their intricate structure. This thesis focuses on advancing conic programming relaxations to address the challenges, specifically using second-order-cone (SOC) programming (SOCP) and semidefinite programming (SDP.)
The thesis is structured into five chapters. Second to fourth chapters present advanced methods and computational results as the main chapters. The first chapter introduces the general concept and provides an overview of the research, while the last chapter, or the fifth, concludes the thesis with suggestions on future work direction.
In the second chapter, SOC constraints are used as a part of the convex hull representation for bounded products of variables. The proposed approach results in tighter convex relaxation for quadratic optimization problems, making them more tractable and efficient to solve.
The third chapter further extends the use of SOC constraints by introducing the Kronecker SOC (KSOC) constraint to generate additional constraints for tightening SDP relaxation. This cut-generation method of relaxation on nonconvex problems leads to even tighter relaxation compared to existing Shor relaxation, the standard SDP relaxation. The KSOC constraints are applied to a problem class called the multiple trust-region subproblems (MTRS), a generalization of the two trust-region subproblems.
The fourth chapter explicitly imposes the Kronecker product constraints to strengthen an SDP relaxation for quadratic optimization problems over the Stiefel manifold (QPS). QPS problems involve quadratic optimization with orthogonality constraints, i.e., the decision variable is a matrix with orthonormal columns. The goal is to minimize a quadratic objective function subject to these constraints. The proposed method improves the efficiency and scalability of solving QPS problems.
The connection among the three main chapters lies in utilizing two types of conic relaxations, SOCP and SDP, which are parts of conic programming. Conic programming involves minimizing quadratic objective functions subject to quadratic constraints where both are expressed in terms of convex cones. Notably, both MTRS in the third chapter and QPS in the fourth chapter have applications that include the trust-region subproblem as a special case.
In conclusion, this thesis advances the field of quadratic optimization by studying state-of-art conic programming relaxation techniques, such as SOCP and SDP. These advancements improve the efficiency and effectiveness of solving nonconvex quadratically constrained quadratic problems, providing valuable insights for decision-makers in various industries and ultimately benefiting society holistically.
Details
- Title: Subtitle
- Advances in convex relaxations for quadratic optimization: a study on conic programming relaxations including second-order-cone and semidefinite programming
- Creators
- Kyungchan Park
- Contributors
- K. M. Anstreicher (Advisor)Samuel A Burer (Advisor)Qihang Lin (Committee Member)Beste Basciftci (Committee Member)Yong Chen (Committee Member)
- Resource Type
- Dissertation
- Degree Awarded
- Doctor of Philosophy (PhD), University of Iowa
- Degree in
- Business Administration
- Date degree season
- Summer 2023
- Publisher
- University of Iowa
- DOI
- 10.25820/etd.007220
- Number of pages
- xi, 106 pages
- Copyright
- Copyright 2023 Kyungchan Park
- Language
- English
- Date submitted
- 05/15/2023
- Description illustrations
- illustrations (some color)
- Description bibliographic
- Includes bibliographical references (pages 94-106).
- Public Abstract (ETD)
In everyday life, we often face complex decisions and challenges that require exploring the best possible solution while balancing various constraints. Quadratic optimization is a mathematical method for efficient decision-making, but its complexity poses challenges. This research progresses our understanding of convex relaxations, simplifying complex and irregularly shaped problems into more manageable and accessible forms, thus improving decision-making based on quadratic optimization.
The research focuses on enhancing optimization methods by applying conic optimization, a powerful mathematical approach that helps simplify complex problems using various cones. By utilizing sophisticated cones as second-order cones and semidefinite cones, this thesis provides advanced methods to efficiently and adequately narrow down the solution space of challenging optimization problems across different domains.
The study presents state-of-arts methods on mathematical models, leading to solving optimization algorithms more efficiently. These advancements can be applied to various real-world problems, offering insights into more effective decision-making processes. By improving optimization methods, this research contributes to addressing the challenges faced by decision-makers in various fields, from engineering and science to economics.
In summary, this research helps advance our ability to solve complex quadratic optimization problems through the development of new convex relaxation techniques. By enhancing our understanding and capabilities in this area, we can ultimately improve decision-making processes in various industries to benefit society holistically.
- Academic Unit
- Tippie College of Business
- Record Identifier
- 9984454644602771
Metrics
2 File views/ downloads
32 Record Views