Conic optimization techniques yield sufficient conditions for set-completely positive matrix completion under arrowhead specification pattern
Markus Gabl · 2025
Read Conic optimization techniques yield sufficient conditions for set-completely positive matrix completion under arrowhead specification pattern by Markus Gabl (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-19348.txt.
Introduction
Markus Gabl, writing alone, turns a tool around: he uses optimization theory to prove a new matrix completion result. Completion asks when a partly filled symmetric matrix can be finished into a matrix of a desired type. Classic results serve positive semidefinite and completely positive matrices. Gabl treats a broader class, set-completely positive matrices, and a pattern the classic results miss: arrow-head patterns of width one, where only a border strip is given.
His conditions come from copositive optimization, a field that works with matrices that stay safe on positive inputs. The result adds to the known literature on both axes, the matrix class and the pattern. The theory is then applied to a class of quadratic problems, where answers are scored by a squared-cost rule. Completion results of this kind matter because they can slash the number of variables in large optimization problems.
Catalog record
| CREATOR | Markus Gabl |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 148 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-19348
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Conic optimization techniques yield sufficient conditions for set-completely positive matrix completion under arrowhead specification pattern Thanks: Supported by the Austrian Science Fund (project ESP 486-N). Markus Gabl Abstract Matrix completion results deal with the question of when a partially specified symmetric matrix can be completed to a member of certain matrix cones. Results from positive semidefinite matrix completion and completely positive matrix completion have been successfully applied in optimization to greatly reduce the number of variables in conic optimization problems in the space of symmetric matrices. In this text, we go the other direction and show that we can use tools from conic optimization (more precisely: from copositive optimization) to establish a new completion result that complements the existing literature in two regards: firstly, we consider set-completely positive matrix completion, which generalizes completion with respect to the traditional completely positive matrix cone. Secondly, we consider a specification pattern that is not in the scope of classical results for completely positive matrix completion. Namely, we consider arrow-head specification patterns where the width is equal to one. Our theory is applied to a class of quadratic optimization problems. Keywords: Matrix Completion \cdot Completely Positive Matrices \cdot Quadratic Optimization \cdot Copositive Optimization \cdot Conic Optimization MSC: 90C22, 15A83, 15B48 1 Introduction This text is concerned with the theory of set-completely positive matrix completion. Given a matrix, whose entries are partially unspecified, the question is whether there are values for the unspecified entries such that the matrix can be completed to a member of set-completely positive matrix cones, such as the positive semidefinite matrix cone or the completely positive matrix cone. This branch of linear algebra has been hugely influential in the field of sparse reformulations of conic optimization problems over the space of symmetric matrices, which are optimization problems that are linear except for a single, nonlinear, conic constraint. Such problems often arise from convex reformulations and relaxations of nonconvex optimization problems. Results involving the positive semidefinite matrix are plentiful and include [ 18 , 25 , 29 ] to name a few; a more exhaustive (but by no means complete) survey is given in [ 28 ] . Another strain of literature is concerned with reformulations based on the completely positive matrix cone (which contains all matrices of the form {\mathsf{B}}{\mathsf{B}}^{\mathsf{T}} , where {\mathsf{B}} is nonnegative) and its generalizations (see [ 3 , 8 , 13 ] as well as the surveys [ 4 , 6 , 12 ] ). In many interesting cases, the linear constraints and objective of these problems exhibit sparsity patterns, i.e. patterns of zeros, so that certain entries of the matrix variable appear only in the conic constraint. In such cases, sparse relaxations allow replacing the computationally costly conic constraint by a collection of such constraints on certain submatrices of the matrix variable (ideally of small order), thereby eliminating spurious entries of the matrix variable from the problem description entirely. Such reformulations can provide substantial computational benefits and have therefore been studied extensively. Results regarding the positive semidefinite matrix cone were first studied in [ 14 ] , which sparked a plethora of investigations, an excellent survey of which is given in [ 27 ] . Reformulations involving the completely positive matrix cone were discussed for example in [ 20 , 15 ] . To ensure that a sparse relaxation is exact, one typically employs matrix completion results, most importantly [ 19 ] for psd (positive semi-definite) completion and [ 11 ] for completely positive completion. Suppose the submatrices present in the sparse relaxation can be completed to a matrix that fulfills the original conic constraint. In that case, the relaxation gap can be closed and the computational benefits can be reaped at no additional cost. Unfortunately, said results on matrix completion impose a lot of restrictions on the sparsity pattern and the type of conic constraint, which we will discuss in greater detail later in the text. In this note, we want to improve upon existing results in this regard. To this end, we will consider sparsity patterns with a certain type of arrowhead structure. Matrices with this sparsity pattern are not within the domain of classical matrix completion results as far as the completely positive matrices are concerned. Our main result is a new sufficient condition for completability of matrices with arrow-head specification pattern, where the width of the diagonal is equal to one , and where the completion is with respect to certain set-completely positive matrix cones that are more general than the ’traditional’ completely positive matrix cone. Set-completely positive completion has been considered before in [ 15 ] , but results on sufficient conditions therein were very limited. We arrive at these results by employing copositive optimization techniques. This is interesting because, rather than using linear algebra results for the benefit of optimization, we use techniques from optimization in order to tackle a problem in linear algebra. However, optimization also benefits from our result since it can potentially be used to strengthen conservative approximations of sparse reformulations discussed in [ 15 ] , but we also use it in the present text to derive new ex-post certificates of exactness for sparse relaxations of a certain type of completely positive optimization problem , i.e., certificates deduced from the optimal solution of the relaxation rather than from the problem structure. We hope that our approach inspires further investigation into the subject. Before laying out our derivation in greater detail, we will briefly review some important concepts regarding conic reformulations, sparse relaxations, and matrix completion and introduce some notation and preliminaries. 1.1 Notation and preliminaries Throughout the paper, matrices are denoted by sans-serif capital letters (e.g. {\mathsf{O}} will denote the zero matrix, where the size will be clear from the context), vectors by boldface lowercase letters (e.g. \mathbf{o} will denote the zero vector), and scalars (real numbers) by simple lowercase letters. Sets will be denoted using calligraphic letters, as will be a certain function but context will clarify. For example, cones will often be denoted by {\mathcal{K}} . We use {\mathcal{S}}^{n} to indicate the set of n\times n symmetric matrices and {\mathcal{S}}_{+}^{n}/{\mathcal{S}}_{-}^{n} for the sets of n\times n positive-/negative-semidefinite matrices, respectively. Moreover, we use {\mathcal{N}}_{n} to denote the set of n\times n entrywise nonnegative, symmetric matrices. Exceptions to this rule will be the index set [l\!:\!k]\coloneqq\left\{l,l+1,\dots,k-1,k\right\}\subseteq\mathbb{N} , further \mathbb{R}^{n} , the set of real n -dimensional vectors, and its subset of nonnegative vectors denoted by \mathbb{R}^{n}_{+} . For a given set {\mathcal{A}} we denote its closure, interior, relative interior and convex hull by \mathrm{cl}({\mathcal{A}}) , \mathrm{int}({\mathcal{A}}) , \mathrm{ri}({\mathcal{A}}) , \mathrm{conv}({\mathcal{A}}) respectively. For a cone {\mathcal{K}} in some vector space {\mathcal{V}} we denote the dual cone by {\mathcal{K}}^{*}\coloneqq\left\{\mathbf{x}\in{\mathcal{V}}\colon\langle\mathbf{y},\mathbf{x}\rangle\geq 0,\ \forall\mathbf{y}\in{\mathcal{K}}\right\} . We will several times use the facts that {\mathcal{K}}^{**}=\mathrm{cl}{\color[rgb]{0,0,0}(}\mathrm{conv}({\mathcal{K}}){\color[rgb]{0,0,0})} and \mathrm{int}{\color[rgb]{0,0,0}({\mathcal{K}}^{*})}=\left\{{\color[rgb]{0,0,0}\mathbf{x}}\colon\langle{\color[rgb]{0,0,0}\mathbf{y},\mathbf{x}}\rangle>0,\ \forall{\color[rgb]{0,0,0}\mathbf{y}}\in{\mathcal{K}}\setminus\left\{\mathbf{o}\right\}\right\} for any cone {\mathcal{K}} in a finite-dimensional vector space. We also make use of the Frobenius product of two appropriately sized matrices {\mathsf{A}} and {\mathsf{B}} defined as {\mathsf{A}}\bullet{\mathsf{B}}\coloneqq\mathrm{trace}({\mathsf{A}}^{\mathsf{T}}{\mathsf{B}})=\sum_{i=1}^{n}\sum_{j=1}^{n}({\mathsf{A}})_{ij}({\mathsf{B}})_{ij} . At several points in the text, we will invoke the concept of the recession cone of a nonempty and convex set {\mathcal{C}}\subseteq\mathbb{R}^{n} , which is defined as: \displaystyle{\mathcal{C}}^{\infty}\coloneqq\left\{\bar{\mathbf{x}}\in\mathbb{R}^{n}\colon\mathbf{x}+\lambda\bar{\mathbf{x}}\in{\mathcal{C}},\ \forall(\mathbf{x},\lambda)\in{\mathcal{C}}\times\mathbb{R}_{+}\right\}, (1) The following proposition summarizes properties of recession cones relevant to our exposition. Proposition 1 .