title: Advances in convex relaxations for quadratic optimization
title: a study on conic programming relaxations including second-order-cone and semidefinite programming
titleType: Subtitle
Creators: name: Park, Kyungchan
Publisher: name: University of Iowa
Year: 2023
Subjects: conic programming relaxation
convex relaxation
quadratic optimization
second order cone programming
semidefinite programming
public abstract

description: 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.)
description: 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.
description: 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.
description: 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.
description: 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.
description: 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.
description: 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.