Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
0answers
16 views

In spectrahedra, are minimal rank points always extreme points?

Consider a matrix $A$ in a spectrahedron $S$ such that $$\mbox{rank}(A) \leq \mbox{rank}(B)$$ for all $B\in S$ and assume that at least one matrix $C \in S$ we have that $\mbox{rank}(A) < \mbox{...
1
vote
2answers
42 views

Dual of an SDP ${\min}_{X \in \mathcal{S}^n} \quad \ {\rm trace}( W X )$ s.t. $X_{ii} = 1$; $X \succeq 0$

How to obtain the dual of the following semidefinite programming problem (SDP) \begin{align} \text{minimize}_{X \in \mathcal{S}^n} \quad & {\rm trace}( W X ) \\ \text{subject to }\quad & X_{...
1
vote
1answer
48 views

Closed form solution of an SDP [closed]

Given symmetric positive definite matrices $A$, $M_1$ and $M_2$, is there any closed form solution for the following convex problem in $X$? $$\begin{array}{ll} \text{maximize} & \mbox{tr}(AX)\\ \...
2
votes
0answers
62 views

Semidefinite optimization

I'm a physicist and I'm working on a problem that can be reduced to a SDP problem. My problem is: is there a theorem that assures that the result of an optimization saturates the constraint instead of ...
2
votes
0answers
75 views

Simplification of a Quadratically constrained, Quadratic objective (to apply Semidefinite relaxation)

I came up with the following optimization problem: $$\arg\max_{G_i} \quad G_1^TI^TIG_1 + ...+G_N^TI^TIG_N$$ subject to: $$\|G_i\|_2^2=1 \quad \forall i$$ $$\|G_i-G_{o_i}\|_2^2\leq c \quad \forall i$$ ...
0
votes
1answer
39 views

Describing Constraints Using Linear Algebra (Convex Optimization)

I've been learning Convex Optimization but one thing that really confused me in class was how exactly to recast a given set of constraints in matrix form, so that it can be solved using CVX. For ...
2
votes
0answers
66 views

Practical applications of semidefinite programming

I am looking for practical applications of semidefinite- programming. So far, I found that the low-rank matrix completion problem (recomendendattion matrices) can be expressed as a semidefinite ...
0
votes
1answer
35 views

How to write the SDP of the optimal problem

I want to write the SDP of the optimal problem below, but I am not sure whether the formula I rewrite is right or wrong \begin{array}{rl} \min_{F_k,\rho_k}&\sum_{k=1}^K tr(\mathbf F_k)\\ \text{s....
0
votes
0answers
47 views

SDP formulation of dual norm

I know that the dual norm of a matrix can be formulated as a semidefinite program (SDP), i.e., $\|X\|_{2,*}$ is the solution to the following SDP in $Y$: $$\begin{array}{ll} \text{maximize} & Y^T ...
0
votes
1answer
41 views

Minimization of norm distance using SDPs, cone programming, etc.

Building on top of this question Minimization of Frobenius norm using SDPs, I would like to know for what class of norms ($ \Vert \cdot \Vert $ in the following) can we represent the following problem ...
0
votes
1answer
45 views

Semidefinite relaxation

Suppose that we have an objective function that involves two binary variables, i.e. $x, y \in \lbrace 0,1 \rbrace$ ($x$ represents the assignment of category A to category B and $y$ represents the ...
2
votes
1answer
35 views

Optimizing over vector and Matrix at the same time.

I want to know if my understand (prove convexity, format as SDP) the following problem is correct: \begin{equation*} \begin{aligned} & \min_{c\in \mathbb{C}^n,D\in \mathbb{H}_+^n} && \|c\|...
0
votes
0answers
11 views

How can I transform this problem, using more than 4 data points in CVX?

I wrote this code in Matlab to find an ellipsoid circumscriving these 4 points that has minimum volume. ...
0
votes
0answers
25 views

Why can a constraint on a matrix being positive definite be rewritten as the matrix minus the identity being positive semidefinite?

My instructor today mentioned that if we have a constraint that a matrix $A$ is positive definite, then we can rewrite this constraint as $A - I$ is positive semidefinite without this affecting the ...
1
vote
1answer
60 views

Semidefinite programming relaxation of linear dynamical system to find Lyapunov function

I am considering a linear dynamical system of the form $$x_{k+1} = Ax_k$$ I know that when we have stability (that is, that $x_k$ goes to $0$ as $k$ approaches infinity), there exists an $n$-by-$n$ ...
1
vote
1answer
81 views

Formulation of spectral norm minimization as a semidefinite program

Given a matrix $F \in \mathbb{C}^{m \times n}$ such that $m > n$ and other (non-symmetric) square matrix $A$ of size $n \times n$, how can one formulate $$ \arg \min_b \left\|A- {F}^{*} \...
2
votes
1answer
50 views

The Exponential Cone and Semi-definite programming

I have a problem at the intersection of a range of topics: exponential programming, semi-definite programming and computer science, that I am having trouble finding a decent method for solving. Take $...
0
votes
1answer
58 views

Find diagonal matrix $D$ such that $A D$ is Hurwitz

Let $A \in \mathbb{R}^{m \times m}$. Give necessary and/or sufficient conditions for the existence of a matrix $D \in \mathbb{R}^{m \times m}$ such that all eigenvalues of $AD$ have negative real part ...
0
votes
0answers
31 views

What can be the convex relaxation of a quadratic matrix inequality?

I am trying to relax the Quadratic Matrix Inequality given as: $$W \leq X^TX+Y^TY \\ W\geq 0 $$ Here, $X,Y,W \in \mathbb{R}^{n\times n}$ matrices. These two are to be solved along with one linear ...
1
vote
0answers
28 views

Write problem containing inverses as Semi Definite Programming

Let $v\in\mathbb{R}^m$ and positive semidefinite $M\in\mathbb{S}^m$ be fixed. For all $x\in\mathbb{R}^n$, let $A(x)=A_0+\sum_{i=1}^nx_iA_i$, where $A_0,...,A_n\in\mathbb{S}^m$ are fixed. Write $$\...
0
votes
0answers
43 views

How to solve a non-convex programming problem?

Let $A$ and $C\ $ be $n\times n$ symmetric matrices, and $A\bullet C=Tr(A^TC)$. Let $S\subseteq [n]\times [n]\times [n]$. Define a non-convex programming problem as follows. \begin{equation} \begin{...
0
votes
0answers
34 views

Approximate symmetric matrix by minimizing condition number

We want to approximate A symmetric semi definite positive by another X that's symmetric and whose condition number $\frac{\lambda_{\max}(X)}{\lambda_{\min}(X)}$. The optimization problem can be ...
0
votes
0answers
13 views

Absolute operator in a constraint [duplicate]

I have a constraint of the following form $tr(A*X)+|(tr(A*X))|==0$ where A is constant hermitian matrix and X is a hermitian complex matrix variable. The condition on $X$ is that it should be ...
0
votes
0answers
48 views

primal and dual semi-definite programs - problem

I have following problem regarding Semi-Definite Programming (SDP): Consider the pair of primal and dual SDPs: primal $$\text{ minimize } c^Tx$$ subject to: $$F_{(x)} \leqslant 0$$ dual $$\text{ ...
3
votes
1answer
95 views

Help with Dual problem in SDP

I'm having a problem to find the Dual of a Semidefinite programing problem: $$\min\;\;(tr(U)+tr(V))/2$$ $$s.t.\;\; \left[ \begin{array}{cc} U & X \\ X^T & V \end{array} \right]\succeq0$$ $$...
3
votes
1answer
39 views

Limitations of SDP

Semidefinite programming seems to be a very powerful tool to approach NP-hard optimisation problems, for example in discrete optimisation and there are some very interesting results (like the max cut ...
0
votes
1answer
98 views

Converting SDP in standard form to inequality form

I want to convert semidefinite program min $tr(XY)$ subject to $X \succeq 0$, $tr(XA_i)+c_i = 0$) where matrices $A_i, Y$ and vector $c_i$ are given into the form with matrix inequalities that ...
1
vote
0answers
38 views

Minimize using semidefinite programming

I have the following optimization problem in $Q \in \mathbb R^{m \times n}$ $$\text{minimize} \quad \mbox{Tr}(CQ) + \|Q\|_1$$ where $\| \cdot \|_1$ denotes the sum of absolute values of the matrix ...
1
vote
0answers
40 views

Semidefinite program with objective function containing a square root

By using a software package that is compatible with YALMIP, I would like to solve an optimization program of the form \begin{align*} \begin{array}{cr} \max\limits_{X\in \mathbb{S}^n}& \frac{x_1+\...
1
vote
0answers
30 views

How to convert a semidefinite programming to an optimization probelm which can be solved by ellipsoid method

Suppose we have a set of linear inequalities in $n$ variable as following: $a_1^Tx\leq b_1$ $\vdots ~~~~~~~~~~~~~~~~~~~~~~~~~ x\in \mathbb R^n$ $a_k^Tx\leq b_k$ If the feasible set of these set ...
2
votes
1answer
37 views

Recovering a quadratic form from a finite set of values

Say I want to recover the matrix of a positive quadratic form from its values on a finite collection of points. That is, given vectors $x_i \in \mathbb{R}^n$ and the values $x_i^TAx_i$, I want to find ...
3
votes
1answer
52 views

How to approximate a 3x3 linear inequality constraint

Let $M$ be a $3\times3$ symmetric matrix (6 independent variables). The following constraint: $$M \succeq 0$$ is a convex linear matrix inequality (LMI), meaning that M is positive semidefinite. I'...
0
votes
1answer
70 views

Finding the dual of a Linear Matrix Inequality feasible set

I am stuck at the following problem about semidefinite programming and linear matrix inequalities, taken from https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-972-algebraic-...
0
votes
1answer
301 views

What is a rank-1 constraint and why is it non-convex?

When an optimal power flow problem is formulated using Semi-definite programming method, the equivalent OPF problem contains one constraint X or W = vv^H where v is a vector of bus voltages and H is ...
4
votes
0answers
48 views

How can I write my optimization problem as a SDP problem?

I have the following maximum likelihood optimization problem: $$ \hat{X}=\underset{X}{\text{argmax}} \left ( T_{1}X^{T}GX+T_{2}X^{T}Y \right ) \\ \text{s.t.} \left\{\begin{matrix} X\in \{\pm 1\}^{n}...
12
votes
2answers
159 views

A matrix inequality involving trace norm of a matrix and its inverse

Let $A,B \succeq 0$ be two positive semidefinite matrices. Can we get a closed form expression for the following quantity? $$ \inf_{X \succ 0} \mathrm{tr}(XA) + \mathrm{tr}(X^{-1}B) $$ We assume all ...
1
vote
0answers
43 views

Duality gap in polynomial optimization problem Lasserre relaxation

Consider a polynomial optimization problem of the following type \begin{equation} \begin{array}{cl} \text{maximize} & p(\mathbf{x}) \\ \text{subject to} & \mathbf{x} \in K \\ \end{array} \...
0
votes
1answer
72 views

Can I get a closed form solution of this SDP?

$$\begin{array}{ll} \text{maximize} & t\\ \text{subject to} & \mathbf{A} -t \mathbf{B} \succeq 0\end{array}$$ where $\mathbf{A}\succeq0$ and $\mathbf{B}\succeq0$. I want to ask one question. ...
0
votes
0answers
26 views

Sensitivity of a matrix rank to objective function in semidefinite optimization

I have a question regarding the effect of an objective function on getting rank-1 solution for semidefinite optimization. I'm trying to minimize the following objective function Minimize $ c_0\ (\...
0
votes
1answer
53 views

Definition of a bounded subset of the cone of positive semidefinite matrices

I cannot understand what it formally means when one says that a subset of the cone of positive semidefinite (PSD) matrices is bounded. I found a pretty general definition of a bounded set, i.e., ...
1
vote
0answers
40 views

Equivalence between the SDP and the given problem

I read in a paper that the matrix minimization problem $$ \mathbf{f(A)} = \min_{~~~~U,V\\\mathbf{A = UV'}} \max_i \mathbf{\|U_i\|} \max_i \mathbf{\|V_i\|} \\ \text{where } \mathbf{U_i} ~\text{and}~ \...
1
vote
1answer
44 views

Slater's condition in conic programming

I'm reading some PDF in conic programming. When we define duality and want to know when strong duality holds we use Slater's condition. In some references the cone should be pointed and in other ...
1
vote
0answers
41 views

Maximizing $\mbox{Tr}(MX)$ over $X \succeq 0$ with diagonal entries at most $1$

Does the following optimization problem have an analytic solution? $$\begin{array}{ll} \text{maximize} & \mbox{Tr}(MX)\\ \text{subject to} & X_{ii} \leq 1 \quad \forall i = 1, \dots, n\\ &...
1
vote
0answers
27 views

Trying to solve a feasiblity SDP

I wish to find a positive semidefinite matrix $Q \in \mathbb{R}^{n \times n}$ such that $$A \,\mbox{vec} (Q) = b$$ where matrix $A \in \mathbb{R}^{m \times n^{2}}$ and vector $b \in \mathbb{R}^m$ are ...
1
vote
0answers
91 views

About the convexity of distance metrc problems.

Suppose that we consider a pseudo-distance in $\mathbb{R}^n$ (so we admit that different points can have zero distance between them) that comes from a dot product. It is known that these distances ...
1
vote
1answer
38 views

In semidefinite programming what is the cone and what does interior for strong duality mean?

In conic programming we should have a cone that is a subset of $\mathbb R^n$; then strong duality holds if this conic program has a strictly feasible solution, i.e., the primal should have a feasible ...
3
votes
0answers
264 views

Semidefinite relaxation for QCQP with nonconvex “homogeneous” constraints

Suppose we wish to solve the quadratically constrained quadratic program (QCQP) in $x \in \mathbb R^n$ $$\begin{array}{rl} \text{minimize} & \frac{1}{2}x^\top Lx\\ \text{subject to} & Ax=b\\ &...
0
votes
0answers
199 views

Lagrangian multipliers in the dual of semidefinite programs

I have been reading about semidefinite programs and I feel completely lost as to what is going on. The lagrangian multipliers for linear, geometric and second order cone programs can be expressed as a ...
0
votes
1answer
81 views

Reformulation of nonlinear optimization problem as a semidefinite program (SDP)

Let $G \in \mathbb{R}^{n \times n}$, $H \in \mathbb{R}^{p \times n}$ and $x_i \in \mathbb{R}$ for all $i \in [1...m]$ be decision variables. Let $A\in \mathbb{R}^{p \times p}$ be a known invertible ...
0
votes
1answer
62 views

Is minimizing the sum of the reciprocals equivalent to maximizing the sum of the non-reciprocals, when the variables are coupled?

Let $G_i \in \mathbb{R}^{n_i \times n_i}$ for all $i \in [1...m]$ and $x_i \in \mathbb{R}$ for all $i \in [1...m]$. Consider the semidefinite program $$\min_{G_i\succeq0,~x_i\geq 0, \forall i\in [1......