Skip to main content
8 votes
Accepted

Structure of a real 3x3 positive-semidefinite matrix whose eigenvalues verify the triangle inequalities

Condition $$E_{11}+E_{22}\ge E_{33}$$ is equivalent to $$E_{11}+E_{22}+E_{33}\ge 2 E_{33}$$ or $$E_{33} \le \frac12 tr\ A$$ since the sum of eigenvalues is equal to the trace. Combining with the ...
F_G's user avatar
  • 837
7 votes

Exactness of the semidefinite programming (SDP) relaxation of maximum cut (Max-Cut)

This question was studied somewhat in the early '90s (before Goemans--Williamson, in fact; note that it was Delorme and Poljak who first gave a poly-time SDP algorithm for Max-Cut, conjecturing that ...
Ryan O'Donnell's user avatar
5 votes
Accepted

Strict complementary slackness for semidefinite programs with strong duality

Studying certain semidefinite programs arising in spectral graph theory, I discovered a semi-definite primal/dual pair satisfying strong duality but not strict complementarity. Let $E=\{12,23,34\}$ (...
M. Winter's user avatar
  • 12.7k
5 votes

When does a finite metric induce a matrix norm?

Not a complete answer, but a sufficient condition. The equation $(e_i - e_j)^TQ(e_i - e_j) = d(i,j)^2$ tells us that $q_{i,i} + q_{j,j} - 2q_{i,j} = d(i,j)^2$, so $q_{i,j} = (q_{i,i} + q_{j,j} - d(i,j)...
Nathaniel Johnston's user avatar
5 votes

Positive-definite block matrix with constant block sums

This is not possible unless $n=1$. If $x$ is the vector $$ (1,\dots,1,-1,\dots,-1,0,\dots,0) $$ ($m$ entries equal to $1$, $m$ entries equal to $-1$, $(n-2)m$ entries equal to $0$), then we have $\...
Guillaume Aubrun's user avatar
4 votes
Accepted

Advantages of hyperbolic programming over semidefinite programming?

Disclaimer: I'm not an expert in the area, just a fellow curious. Update (2023): In the pre-print "Sums of Squares Representations on Singular Loci" by Ngoc Hoang Anh Mai and Victor Magron ...
Tadashi's user avatar
  • 1,580
4 votes

About optimization with Renyi divergence

For the requested examples see Rényi Divergence and Kullback-Leibler Divergence (2012). • Two continuous distributions: Equation 10 gives the Rényi divergence between two Gaussian distributions (mean ...
Carlo Beenakker's user avatar
4 votes
Accepted

Full rank submatrices of positive semidefinite matrix

Yes, this is true. To see this note that for $A$ positive semidefinite, $v^T A v = 0$ if and only if $Av = 0$. For the less obvious direction, write $A = B^TB$ for a real matrix $B$. Then $0 = v^...
Noah Stein's user avatar
  • 8,433
3 votes
Accepted

Convex Hull of Outer Products of (Normalised) Nonnegative Vectors

Your characterization of $\text{conv} (\mathcal{A})$ needs one additional restriction---that $M$ is positive semidefinite (the equivalence of these two sets follows fairly quickly from the spectral ...
Nathaniel Johnston's user avatar
2 votes
Accepted

Standard solution to semidefinite program

I will assume throughout that the definition of positive semidefiniteness includes symmetry. The problem is to find the Euclidean projection of $b$ onto the convex set $R = \{Qa \mid Q\succeq 0\}$. ...
Noah Stein's user avatar
  • 8,433
2 votes
Accepted

When does a finite metric induce a matrix norm?

Your quadratic form $Q$ is uniquely defined by $d$ on the hyperplane $H$ defined by $\sum x_i=0$. Further, $Q|_H\ge 0$ if and only if your metric space is isometric to a subset of a Eulcidean space.
Anton Petrunin's user avatar
2 votes

When does a finite metric induce a matrix norm?

A necessary condition is that the Cayley-Menger determinant has to be non-negative.
M. Winter's user avatar
  • 12.7k
2 votes
Accepted

Matrix Completion SDP Relaxation and Duality

The derivation of this dual is provided in example 8.8 "Sum of singular values revisited" of section 8.6 "Semidefinite duality and LMIs" of Mosek Modeling Cookbook 3.2.1.
Mark L. Stone's user avatar
2 votes

Perturbation of positive semidefinite matrix

Converted from (now-deleted) a comment by Christian Remling: This is false: $$ A=\begin{pmatrix} 0 & 0\\ 0& 1\end{pmatrix},\quad B=\begin{pmatrix} 0 & 1\\ 1 & 0\end{pmatrix}$$ Then $A+...
Federico Poloni's user avatar
1 vote
Accepted

Monotonicity of kernel matrices with respect to hyperparameters

This example may be a little bit ridiculous, but suppose we take $\mathcal{X}=\mathbb{R}$ and let $\Phi$ be any parametric subset of the set of PSD kernels itself. We define $$ \mathbf{K}(\phi)_{i,j} ...
Bill Bradley's user avatar
  • 3,819
1 vote

Solving linear programming without solving linear programming

$\newcommand\R{\mathbb R}$Suppose that $\det M_{J,J}\ne0$ for some set $J\subseteq[n]:=\{1,\dots,n\}$ of cardinality $|J|=k$, where $M_{J,J}:=(v_i\cdot v_j\colon (i,j)\in J\times J)$, the $(J\times J)$...
Iosif Pinelis's user avatar
1 vote
Accepted

Relaxations for the spectral norm maximization problem

Minimizing a concave function subject to convex constraints is Concave Programming. If the constraints of a Concave Programming problem are compact, as in your example, there must be a global optimum ...
Mark L. Stone's user avatar
1 vote

What is the convex cone generated by the pair of rank 1 matrix and its eigenvector?

Are you really interested in the convex cone, or in the convex envelop ? The latter is easily determined by taking the intersection of the half-spaces containing all the pairs $(hh^T,h)$. Their ...
Denis Serre's user avatar
  • 51.8k
1 vote
Accepted

Convexity of a positive definite objective with min(x,y)-nonlinearity

$f(x)$ is not convex. Here is a counterexample to its convexity in MATLAB notation. C = [2 1;1 2] x1 = [1 2]' x2 = [2 1]' x3 = 0.5*(x1 + x2) Then ...
Mark L. Stone's user avatar
1 vote
Accepted

Matrix norm minimization and matrix inner product

The comments to this question of mine show that, in general, the operator-norm and Frobenius-norm minima are distinct for this problem. Let me summarize the argument here. Let $M=diag(\alpha,\beta,\...
Federico Poloni's user avatar
1 vote

Matrix norm minimization and matrix inner product

I hope I haven't missed anything here, but isn't the constraint $A(x) = -A(x)^T$ redundant since we know $A_i = -A_i^T$? I would have thought that we necessarily have $$ -A(x)^T = -x_1 A_1^T - \ldots -...
occassional user's user avatar
1 vote

Max-norm projection of a Hermitian matrix onto the set of positive semidefinite matrices

Partial answer regarding an algorithm to find projection, not a closed form. The problem is of the following convex SDP: $$ \min_{t,M} ~~~~~~~t\\ \mbox{subject to}\\ \hspace{5cm} |A_{i,j}-M_{i,j}|\...
DSM's user avatar
  • 1,204
1 vote

Exactness of the semidefinite programming (SDP) relaxation of maximum cut (Max-Cut)

An obvious sufficient condition is that the SDP in question has a rank-$1$ optimal solution. Indeed, the SDP provides you with an upper bound on the MAXCUT value, and then you pay the price of $\alpha=...
Dima Pasechnik's user avatar
1 vote

Subspaces of real $n \times n$ matrices of dimension $O(n)$

An example is the commutative sub-algebra generated by a matrix $M$: it has dimension less than or equal to $n$ because of the Cayley-Hamilton theorem. The same is true for commutative algebras with ...
Pietro Majer's user avatar
  • 57.7k
1 vote

Subspaces of real $n \times n$ matrices of dimension $O(n)$

Tridiagonal matrices fit the requirement, and they are a lot more general; for instance, they do not have any trivial common eigenvector, and every matrix in $\mathbb{R}^n$ is similar to a tridiagonal ...
Federico Poloni's user avatar
1 vote

Strict complementary slackness for semidefinite programs with strong duality

Take the SDP program \begin{align*} \min~& x_3\\ s.t.~& X = \begin{bmatrix} x_1 & x_2 & 0 & 0 \\ x_2 & 0 & 0 &...
Daniel Porumbel's user avatar
1 vote

Is this parametrized semidefinite program convex?

Yes, this is convex because the objective function and all constraints are convex. The objective function is affine (linear), which is convex. The semidefinjite constraint on X is convex. The trace ...
Mark L. Stone's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible