Scholarlink

<p>The problem of maximizing the sum-of-square of quadratic functions with bivalent variables, denoted by (P), arises from bivalent quadratic optimization with <i>K</i> quadratic disjunctive penalties. Though NP-hard in general, (P) is polynomially solvable when the input matrices can concatenate to a fixed-rank matrix. We present a nonconvex quadratic semidefinite programming (SDP) relaxation, which provides a 0.4-approximate solution for (P). We show that the quadratic SDP relaxation can be approximately and globally solved to a precision <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1339_Article_IEq1.gif" Format="GIF" Height="10" Rendition="HTML" Resolution="72" Type="Linedraw" Width="10" /> </InlineMediaObject> <EquationSource Format="TEX">\(\epsilon \)</EquationSource> </InlineEquation> via solving at most <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10878_2025_1339_Article_IEq2.gif" Format="GIF" Height="21" Rendition="HTML" Resolution="72" Type="Linedraw" Width="109" /> </InlineMediaObject> <EquationSource Format="TEX">\(O((Kn^3/\epsilon )^{K/2})\)</EquationSource> </InlineEquation> linear SDP subproblems.</p>

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

Bivalent quadratic optimization with sum-of-square of quadratic penalties

  • 期刊论文

  • 发表日期：

    2025年8月8日

查看全文
  • Tongli Zhang,
  • Yong Xia

摘要

The problem of maximizing the sum-of-square of quadratic functions with bivalent variables, denoted by (P), arises from bivalent quadratic optimization with K quadratic disjunctive penalties. Though NP-hard in general, (P) is polynomially solvable when the input matrices can concatenate to a fixed-rank matrix. We present a nonconvex quadratic semidefinite programming (SDP) relaxation, which provides a 0.4-approximate solution for (P). We show that the quadratic SDP relaxation can be approximately and globally solved to a precision \(\epsilon \) via solving at most \(O((Kn^3/\epsilon )^{K/2})\) linear SDP subproblems.