Scholarlink

<p>We study a multi-period mixed-integer convex quadratic optimization problem, where the state evolves dynamically as an affine function of the state and action (control) variables in each period. We begin by projecting out the state variables using linear dynamics, resulting in a mixed-integer quadratic optimization problem with a positive-definite (block-)factorizable cost matrix. Employing this expression, we construct a closed convex hull representation of the epigraph of the quadratic cost over the feasible region in an extended space. Subsequently, we establish a tight second-order cone programming formulation with <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\mathscr {O}(n^2)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <msup> <mi>n</mi> <mn>2</mn> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> conic constraints. We further propose a polynomial-time algorithm based on a reformulation of the problem as a shortest path problem on a directed acyclic graph. To illustrate the applicability of our results across diverse domains, we present case studies in statistical learning and hybrid system control.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Convexification of multi-period quadratic programs with indicators

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年7月22日

查看全文
  • Jisun Lee,
  • Andrés Gómez,
  • Alper Atamtürk

摘要

We study a multi-period mixed-integer convex quadratic optimization problem, where the state evolves dynamically as an affine function of the state and action (control) variables in each period. We begin by projecting out the state variables using linear dynamics, resulting in a mixed-integer quadratic optimization problem with a positive-definite (block-)factorizable cost matrix. Employing this expression, we construct a closed convex hull representation of the epigraph of the quadratic cost over the feasible region in an extended space. Subsequently, we establish a tight second-order cone programming formulation with \(\mathscr {O}(n^2)\) O ( n 2 ) conic constraints. We further propose a polynomial-time algorithm based on a reformulation of the problem as a shortest path problem on a directed acyclic graph. To illustrate the applicability of our results across diverse domains, we present case studies in statistical learning and hybrid system control.