Explicit convex hull description of bivariate quadratic sets with indicator variables

• 成果类型: Article; Early Access
• 署名作者: De Rosa, Antonio; Khajavirad, Aida
• 署名单位: Bocconi University; Bocconi University; Lehigh University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-024-02173-1
• 发表日期: 2024
• 关键词: integer nonlinear programs; relaxations; constraints

摘要

We consider the nonconvex set Sn={(x,X,z):X=xxT,x(1-z)=0,x >= 0,z is an element of{0,1}n}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathcal {S}}}_n = \{(x,X,z): X = x x<^>T, \; x (1-z) =0,\; x \ge 0,\; z \in \{0,1\}<^>n\}$$\end{document}, which is closely related to the feasible region of several difficult nonconvex optimization problems such as the best subset selection and constrained portfolio optimization. Utilizing ideas from convex analysis and disjunctive programming, we obtain an explicit description for the closure of the convex hull of S2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathcal {S}}}_2$$\end{document} in the space of original variables. In order to generate valid inequalities corresponding to supporting hyperplanes of the convex hull of S2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\mathcal {S}}}_2$$\end{document}, we present a simple separation algorithm that can be incorporated in branch-and-cut based solvers to enhance the quality of existing relaxations.