1
$\begingroup$

I am trying to solve a conic optimization problem where one of my length $n$ vector decision variables is the sum of all of the $n$ unique diagonal bands of any $n \times n$ semidefinite matrix. I can represent this as a linear equality constraint between a dummy semidefinite matrix variable and my actual variable of interest, however this introduces too many additional variables to my program (order $n^2$ rather than order $n$). In my case $n$ is about 2500, and the large semidefinite matrix variable leads to a very long solve time with large memory requirements.

Since the sum of the diagonal bands of a PSD matrix is a positive linear transformation of a convex cone, my actual decision variable is also constrained to lie in a (much lower dimension) convex cone (the image of the semidefinite cone under the diagonal band sum). I would like to know if there is a more compact way of representing such a constraint without introducing dummy variables for the semidefinite matrix variable using smaller cone commonly available in optimization software (e.g. exponential, power, semidefinite, second-order, etc.)


Example of a vector in the cone

Consider the case where $n=3$. The vector $\begin{bmatrix} 2.9002 & 1.86160 & 0.64852 \end{bmatrix}^\top$ is in the cone I want to represent, because it is the sum of the diagonal bands of a PSD matrix. For example: $$\begin{bmatrix} 0.66136 & 0.873396 & 0.648521\\ 0.873396 & 1.46622 & 0.988205\\ 0.648521 & 0.988205 & 0.772622 \end{bmatrix}$$ However, the vector $\begin{bmatrix} 2 & 7 & -1\end{bmatrix}^\top$ is not in the cone I want to represent since it is impossible for a PSD matrix to have those values as the sum of its diagonal bands.

Example of a representation of the cone for $n=2$:

In the case of $n=2$, the vector $\begin{bmatrix} x & y \end{bmatrix}^\top$ is in the cone if and only if $x \ge 0$, $x \ge 2y$, and $x \ge -2y$. This follows from Sylvester’s criterion applied to a $2 \times 2$ matrix and maximizing for the product of a positive diagonal that sums to $x$. In this case the cone is in fact polyhedral, but I don’t see a way to generalize this to larger $n$.

What I have tried so far that hasn't worked:

I can formulate linear constraints representing a diagonally dominant symmetric Toeplitz matrix with diagonal band sums that match my length $n$ vector decision variable, but that set is too restrictive (perhaps not surprising since all symmetric diagonally dominant matrices are PSD, but the converse does not hold).

I have looked at finding a barrier function that can represent this cone directly, however the standard barrier function for a semidefinite cone uses $\log(|\cdot|)$ which doesn't have a nice form under the appropriate inverse transformation and does not seem to be easily adaptable to my cone.

I have considered using the pseudoinverse of the diagonal band sum transformation to expand my smaller length $n$ decision variable into a symmetric matrix and then constraining it to be PSD with an affine conic constraint, but this set is also too small, as the expanded matrix can fail to be PSD even if the decision variable results from the sum of the diagonal bands of some other PSD matrix.

I have tried using a dummy semidefinite matrix variable, but the problem size to large in terms of solve time and memory.

$\endgroup$
8
  • $\begingroup$ Thanks, I have looked at the question you linked. It appears to focus on finding a Toeplitz matrix that is close (by the norm of the difference) to a given non-Toeplitz matrix. Here, I am looking for a way to represent the cone of sums of diagonal bands of PSD matrices, without having to use a dummy variable for the underlying semidefinite matrix. I've update my questions with an example to help illustrate what I am looking for. $\endgroup$ Commented May 26, 2023 at 17:13
  • $\begingroup$ Testing float values for equality is dangerous $\endgroup$ Commented May 26, 2023 at 17:21
  • 1
    $\begingroup$ In the example you gave, you have $6$ degrees of freedom (main diagonal plus strict upper or lower triangular). Use basis matrices. Something like the following $$\sum_{i,j} x_{ij} {\bf B}_{ij} \succeq 0$$ $\endgroup$ Commented May 26, 2023 at 17:22
  • $\begingroup$ I guess what I am saying is that there is really only 3 degrees of freedom. I don't need the semidefinite matrices for anything, I just need to be able to represent the set of $n$-vectors such that their components are the sum of diagonal bands of some PSD matrix. If I use a PSD matrix variable either with a Linear Matrix Inequality as you suggest, or by using a vector representation, then I have to find values for all the free choices in an $n \times n$ PSD matrix and then sum them to obtain the sum of the diagonal bands. That increases my variable count by a factor of $(n+1)/2$ $\endgroup$ Commented May 26, 2023 at 19:17
  • $\begingroup$ I've updated my question to clarify that I am seeking to represent the cone of n-vectors and that I don't actually need to find a PSD matrix who's diagonal bands have any specific sum. $\endgroup$ Commented May 26, 2023 at 19:24

0

You must log in to answer this question.