Conic formulation of QPCCs applied to truly sparse QPs

Area of Science:

• Optimization Theory
• Mathematical Programming
• Operations Research

Background:

• Nonconvex quadratic optimization problems with complementarity constraints are challenging.
• Existing methods often require branching or large constants, limiting practical application.
• Interpretability and sparsity are crucial in many optimization applications.

Purpose of the Study:

• To establish an exact completely positive reformulation for a class of quadratic optimization problems with complementarity constraints.
• To derive conditions for strong conic duality for the reformulated problem.
• To demonstrate the application of this approach to achieving interpretable sparse solutions.

Main Methods:

• Developing purely continuous models that avoid branching and large constants.
• Establishing mild conditions based solely on constraints for the reformulation.
• Investigating the strong conic duality between the completely positive problem and its dual.

Main Results:

• An exact completely positive reformulation is established under new, mild conditions.
• Conditions for strong conic duality are identified.
• The approach successfully links quadratic problems with exact sparsity terms to copositive optimization.

Conclusions:

• The proposed method offers an efficient and exact approach for solving specific quadratic optimization problems.
• The framework is applicable to problems like sparse least-squares regression under linear constraints.
• Numerical comparisons indicate favorable objective function values compared to other approximation methods.