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 ...

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 ...

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\}$ (...

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)...

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 $\...

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 ...

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 ...

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^...

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 ...

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\}$. ...

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.

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.

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.

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+...

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} ...

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)$...

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 ...

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 ...

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
...

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,\...

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 -...

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}|\...

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=...

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 ...

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 ...

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 &...

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 ...

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

#### Related Tags

semidefinite-programming × 91convex-optimization × 36

oc.optimization-and-control × 25

linear-algebra × 23

matrices × 21

nonlinear-optimization × 10

matrix-analysis × 8

linear-programming × 8

reference-request × 7

combinatorial-optimization × 6

polynomials × 5

matrix-theory × 5

graph-theory × 4

convex-geometry × 4

eigenvalues × 4

real-algebraic-geometry × 4

integer-programming × 4

ag.algebraic-geometry × 3

fa.functional-analysis × 3

convex-analysis × 3

non-convex-optimization × 3

semialgebraic-geometry × 3

linear-matrix-inequalities × 3

inequalities × 2

computational-complexity × 2