Hayato Watanabe, Takami Sato, Kazuhide Nakata, Ken Kobayashi · 2026 · arXiv (Cornell University)
DOI: 10.48550/arxiv.2610.27727 · cited by 0 works (OpenAlex) · open-access PDF
Мы изучаем две релаксации для двулинейных терминов в переменных, ограниченных коробкой: техника реформования-линейности (RLT) релаксация и релаксация SDP-RLT, которая сочетает RLT с полуопределенным программированием (SDP). Мы представляем образец двулинейных терминов по недиректному графику, с одним вершиной для каждой переменной и одним краем для каждого двулинейного термина. Точка, осуществимая для релаксации RLT, фиксирует только часть поднятой матрицы релаксации SDP-RLT, оставляя оставшиеся входы, чтобы быть выбраны под диагональным RLT неравенства, и две релаксации различаются точно, когда эти входы не могут быть
Machine translation (Meta M2M100); the English original follows.
We study two relaxations for bilinear terms in box-constrained variables: the reformulation-linearization technique (RLT) relaxation and the SDP-RLT relaxation, which combines RLT with semidefinite programming (SDP). We represent the pattern of bilinear terms by an undirected graph, with one vertex for each variable and one edge for each bilinear term. A point feasible for the RLT relaxation fixes only part of the lifted matrix of the SDP-RLT relaxation, leaving the remaining entries to be chosen subject to the diagonal RLT inequalities, and the two relaxations differ exactly when these entries cannot always be chosen so that the matrix becomes positive semidefinite. Formulating this as a positive semidefinite matrix completion problem, we show that the feasible regions of the two relaxations coincide if and only if the graph is a forest. We also measure how large the difference can be when the graph contains a complete bipartite subgraph: a bilinear objective given by a Hadamard matrix yields optimal values whose ratio grows with the size of that subgraph.
Read in: English · Spanish · Chinese · Hindi · Arabic · Portuguese · French · German · Japanese · Russian · Korean · Indonesian · Vietnamese
Topics: Mathematics, Bilinear interpolation, Combinatorics, Vertex (graph theory), Bipartite graph, Semidefinite programming
GET https://store.agentexchange.work/gw/papers/verify?title=...&year=... (0.003 USD), fetch this record as JSON with /gw/papers/paper?id=2610.27727, or list what it cites with /gw/papers/references?id=.... Pay per call in USDC (x402) or with a 19 USD card key for 1,000 calls. Catalogue · llms.txtSources: OpenAlex (CC0), arXiv, Crossref. Agent Exchange