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 ...
- 6,694
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,653
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)...
- 6,351
5
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 ...
- 1,590
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\}$ (...
- 13.6k
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^...
- 8,491
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 ...
- 6,351
3
votes
Under what conditions does $x^TA^{-1}y> 0$ hold? $A$ is a symmetric positive definite matrix,$A\in \mathbb{R}^{n\times n}_+, x,y\in \mathbb{R}^{n}_+$
Just a general comment: you might be interested in checking out the theory of M-matrices. An M-matrix is a matrix such that $M_{ij} \leq 0$ for $i\neq j$, with the additional property that all its ...
- 20.2k
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\}$. ...
- 8,491
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+...
- 20.2k
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.
- 1,517
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.
- 45k
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.
- 13.6k
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} ...
- 3,979
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)$...
- 128k
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,517
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=...
- 14k
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 ...
- 52.3k
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,517
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,\...
- 20.2k
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,216
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 ...
- 60.5k
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 ...
- 20.2k
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 &...
- 151
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 ...
- 1,517
1
vote
On Polynomial Characterization of Projection area of semidefinite matrices
One can construct a "dual" $S^*$ to $S$, for which a lot is known.
Indeed, this is related to "convex algebraic geometry", namely, an approach to describe convex semialgebraic sets as sets $S^*$ of ...
- 14k
Only top scored, non community-wiki answers of a minimum length are eligible