Questions tagged [semidefinite-programming]
This tag is for questions regarding semidefinite programming (SDP) which is a subfield of convex optimization concerned with the optimization of a linear objective function (an objective function is a user-specified function that the user wants to minimize or maximize) over the intersection of the cone of positive semidefinite matrices with an affine space, i.e., a spectrahedron.
400 questions
0
votes
0
answers
17
views
How to represent a standard linear program (LP) as a semidefinite program (SDP)?
I'm trying to understand how to express a simple LP in the standard semidefinite programming (SDP) form.
In particular, consider the following linear program:
$$
\begin{aligned}
\min_{x_1, x_2} \;&...
- 241
1
vote
0
answers
63
views
Sufficient conditions for PSD matrix completion
I am interested in whether the following structured partial symmetric matrix can be completed to a positive semidefinite (PSD) matrix.
The matrix $Z$ is a real symmetric $(n+1) \times (n+1)$ matrix.
...
- 11
1
vote
0
answers
50
views
Semidefinite relaxation for a binary quadratic program with an $\ell_1$ penalty term
I am considering the following regularized binary quadratic optimization problem with a sparsity penalty
$$ \min_{{\bf x} \in \{\pm 1\}^n} \; {\bf x}^\top {\bf C} \, {\bf x} + \| {\bf A} {\bf x} - {\...
- 93
0
votes
0
answers
85
views
Maximum number of points on a sphere in $\mathbb R^n$ such that squared Euclidean distance is a metric
Let $V\subset \mathbb{R}^n$ be a set of points on the $n$ dimensional unit sphere. I want to find the maximum size of $V$ such that $d(x,y)=\|x-y\|_2^2$(the square of the usual Euclidean distance) is ...
- 17
2
votes
0
answers
36
views
Small examples of SDPs with equality constraints and no rank-$1$ optimal solutions
I've been trying to provide some examples of semidefinite programs (SDPs) with only equality constraints, but I'm having a surprising amount of trouble! In particular, I was hoping to find symmetric ...
- 116
2
votes
0
answers
175
views
Kalman filter solution via LMI: summary of methods
Given matrices $Q$ and $R \succ 0$, the Kalman filter problem is
$$ \begin{array}{ll} \underset {P \succeq0, K} {\text{minimize}} & \operatorname{tr} (P) \\ \text{subject to} & (A - K C) P (A -...
- 690
2
votes
2
answers
255
views
Finding the left root of $-x^2 + 2x + 1$ via convex optimization
Can we formulate as a linear matrix inequality (LMI) one of the regions in which a concave quadratic polynomial is negative (without solving its roots)?
Let the quadratic polynomial $f \in {\Bbb R} [x]...
- 690
0
votes
0
answers
47
views
How to apply KKT conditions and determine corresponding dual variables with semidefinite constraints?
I have the following convex optimization problem:
$$ \begin{array}{ll} \underset {{\bf A}, {\bf B}, {\bf X},{ \bf Y}} {\text{minimize}} & \sum\limits_{k \in \mathcal{K}} {\left\| {\bf x}_k \right\|...
- 31
2
votes
0
answers
88
views
Rank-minimization while maximizing sum of entries
I want to find a low-rank symmetric positive semidefinite matrix, subject to some linear constraints, while maximizing a secondary cost that depends on the sum of the entries of this matrix.
$$ \begin{...
- 115
1
vote
0
answers
52
views
How do I interpret this picture of a spectrahedron?
On the Wikipedia page on spectrahedron, it shows the following picture of a spectrahedron (I avoid using the term image since it seems to have special meaning in this context)
I understand everything ...
- 265
3
votes
0
answers
91
views
Semidefinite program to compute Z-eigenvalues
I have a Hermitian matrix $H \in \mathbb{C}^{n^2 \times n^2}$ and I want to solve the following optimization problem.
$$\max_{v \in \mathbb{C}^n, \ v^\dagger v = 1} \ (v \otimes v)^\dagger H (v \...
- 75
1
vote
0
answers
70
views
Methods to prove local optimality for rank-constrained semidefinite programs
I am trying to solve the following optimization problem (with application in sensor placement)
$$
\begin{align}
\max_{x,y,\eta} \quad & \eta\\
\text{s.t.}\quad & y \leq a\\
& x^2+\eta \leq ...
3
votes
0
answers
371
views
Relations between the optimal solutions of two related Semi-Definite Programs.
In system theory, we often encounter Semi-Definite Programs (SDPs) with Linear Matrix Inequality (LMI) constraints, such as those presented in this paper. I have introduced new variables based on the ...
- 83
3
votes
0
answers
125
views
Equivalence of Convex Optimization Problems
I have the following convex program that is derived from the theory of distributionally-robust optimization.
\begin{align*}
&\inf \quad y_0 + \gamma (\rho^2 - \|\hat\mu\|^2 - \mathrm{tr}[\hat\...
- 334
1
vote
1
answer
90
views
Uniqueness of quadratic minimum subject to semidefinite constraints
Let $X, Y \in \mathbb{R}^{n \times p}$ be generic. Let $M^*\in \mathbb{R}^{p\times p}$ minimize $\left\|Y - X M\right\|^2$ subject to the semidefinite constraint $M \geq 0$. Under what conditions is $...
- 1,347