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.

Filter by
Sorted by
Tagged with
0 votes
1 answer
26 views

Image of a $3 \times 3$ PSD cone under a linear transformation

Let $X \in \mathcal{S}_+^3$ be a $3 \times 3$ positive semidefinite matrix, and let $\mathcal{A}$ be a linear transformation from $\mathcal{S}^3 \rightarrow \mathbb{R}^3$ defined as follows: \begin{...
user avatar
  • 579
0 votes
1 answer
38 views

How does barrier function method for semidefinite programming avoid the case when even eigenvalues are negative?

Log-barrier function adds the expression $-\log(\det X)$ to the objective function to ensure that the matrix $X$ is positive definite.But when even eigenvalues of X is negative this expression is ...
user avatar
  • 31
3 votes
1 answer
35 views

Eigenvalue of PSD matrices by constrained SDP program

Given Lemma 1, I want to prove the following corollary. lemma 1 (Rayleigh Quotient): Given matrix $A \succeq 0$, \begin{equation} \lambda_{\min} (A) = \min_{x \in \mathbb R^n}\frac{x^\top A x}{x^\...
user avatar
  • 33
0 votes
0 answers
32 views

How do you convert the following optimization problem with LMI constraints from the standard form given to the Semi Definite Programming(SDP) form?

We are currently working on an engineering project involving convex optimization. The project relates to a low earth orbit spacecraft rendezvous. In the course of this project, we are required to ...
user avatar
1 vote
0 answers
54 views

SDP problem with Schur complement-like constraint

I'm interested in what we can conclude about the following question. Let $\mathbf{Y} \in \mathbb{R}^{n \times n}$ be in the convex hull of projection matrices of rank at most $k$ (equivalently, $\...
user avatar
  • 407
0 votes
0 answers
6 views

Semi Definite Relaxation (SDR) Optimization

I want to optimize the function in the figure using Semi Definite Relaxation method, can anyone of you give me idea on how could i do so !
user avatar
0 votes
1 answer
57 views

Is there any hint how to prove this?

Let's consider matrix M is defined as follows: $M = \begin{bmatrix} P & v \\ v^t & d \end{bmatrix}$, where $P \succ 0$, d is a scalar, and v is a vector. Problem: :To $M \succ 0$ be a ...
user avatar
  • 139
0 votes
0 answers
14 views

Relationship between PSD matrix rank and its convexity

I know that the matrix $W=vv^T$ is PSD and of rank 1. I also know that the set of rank-1 matrices is not convex. My question may be trivial but I would appreciate your feedback. If $W$ is PSD, it ...
user avatar
0 votes
0 answers
75 views

Converting to standard forms of semidefinite programming

Let $A$ and $B$ be given matrices. Let the matrix $X$ be positive semidefinite. We say that $C \preceq D$ whenever $D-C$ is positive semidefinite, i.e., $D - C \succeq 0$. For constraints in the form ...
user avatar
  • 31
1 vote
0 answers
42 views

Minimize a convex function subject to concave quadratic constraints

I am looking into the following optimization problem $$\begin{array}{ll} \underset{\Delta X}{\text{minimize}} & trace(\Delta X^H \Delta X)\\ \text{subject to} & (X+\Delta X)'Q(X + \Delta X) \...
user avatar
0 votes
0 answers
17 views

Interior point method for SDP and LP by hand

Can a SDP optimization problem be solved by hand? I'm looking for a simple example "if that exists" where the problem was solved by hand? If not, is there any example where a simple linear ...
user avatar
0 votes
1 answer
43 views

Characterization of matrices with same column spaces

Given $G = \begin{pmatrix} A & B \\ B^T & C \end{pmatrix}$ symmetric positive semi-definite and $B$ symmetric positive semi-definite, is there a way to impose that \begin{equation} ...
user avatar
  • 27
1 vote
2 answers
74 views

Maximizing linear objective over spectraplex

I have the following instance of a semidefinite program (SDP): $$ d + f \to \max $$ $$ a + b + c = 1 $$ $$ \begin{pmatrix} a & d & e\\ d & b & f\\ e & f & c \end{pmatrix} \...
user avatar
0 votes
0 answers
59 views

Cholesky decomposition for a Hermitian matrix in SDP

I have a variable matrix $W$ that is Hermitian and is used in two SDP problems. Problem 1 has constraints that depend on the real diagonal elements of $W$. Example of the constraint is $W_{ii}+x_{ij}...
user avatar
1 vote
0 answers
46 views

How to efficiently maximize $\log \det$?

$$\begin{array}{ll} \underset{{\bf A} \in \Bbb R^{n \times h}}{\text{maximize}} & \log \det \left({\bf I} + {\bf Z} {\bf Z}^{T}\right)\\ \text{subject to} & {\bf Z} = {\bf A} {\bf X} \\ & \...
user avatar
  • 75
0 votes
0 answers
33 views

Trace minimization with additional constraint on $X$

Consider the following SDP problem: \begin{align*} \min_X \; & \mathrm{Tr}[AX]\\ \mathrm{s.t.}\; & X \succeq 0\\ & X \succeq \begin{bmatrix}0 & 0.5\\0.5 & 0\end{bmatrix}, \end{...
user avatar
  • 149
1 vote
0 answers
24 views

Convex Relaxation Problem (theory )

I was wondering if any of you folks could help me with this optimization problem. I want to show if I find a solution $X^*$ for $(P'')$ for which $rank(X ^* ) = 2$, then $X ^* = uu^T $. Here is the ...
user avatar
2 votes
1 answer
142 views

Strong duality and KKT for SDP with inequality constraints

The standard form of semidefinite program (SDP) is \begin{align*} p^* = \inf C \bullet X\\ s.t. A_i \bullet X = b_i\\ X \succeq 0 \end{align*} where $C, A_i$ are symmetric matrices. The dual SDP is \...
user avatar
  • 157
1 vote
1 answer
27 views

H2-filtering of unstable LTI systems. Can this problem be reformulated as convex optimization problem with LMI constraints?

Consider the discrete-time generalized LTI plant with minimal state-space realization $$x_{k+1}=A_d x_k + B_{d1}w_k\\z_k=C_{d1}x_k+D_{d11}w_k\\y_k=C_{d2}x_k+D_{d21}w_k$$ For the Schur-stable $A_d$ ...
user avatar
0 votes
1 answer
45 views

Problem of solving a large scale Quadratic Problem with Quadratic Inquality Constraint (QCQP)

I am trying to solve following large-scale quadratic fractional (QF) problem: \begin{equation} \begin{aligned} \min_{x\in\Re^{n\times1}} &\frac{x^\top H x + f^\top x + C_e}{x^\top R x}\\ \text{s.t....
user avatar
1 vote
1 answer
26 views

Can I reformulate the given SDP such that the main constraint becomes and LMI?

I am new to SDP and LMI's and trying to solve an optimization problem of the following form: \begin{equation} \begin{aligned} \text{maximize} \quad & \sum_{j=1}^k w_j\\ \text{subject to} \quad &...
user avatar
0 votes
0 answers
173 views

Comparison between SOCP and SDP in terms of computational complexity

Dears If I have an optimization problem with n variables and m constraints that can be solved using the SOCP and SDP, how can I compare the performance of both algorithms using the Big-O notation? I ...
user avatar
1 vote
0 answers
22 views

Why objective function is always linear in semidefinite programing?

Almost all the semidefinite programming paper I found has a linear objective function, which is $\mbox{tr}(CX)$. Why? For example, in this paper and Wikipedia, the objective function is always $\mbox{...
user avatar
  • 511
0 votes
0 answers
27 views

Missing a sign in dual problem of semidefinite program $\text{max}_{Q} \langle X,Q\rangle$

I'm a beginner to the subject so I try to make everything explicit. The optimization is $$\begin{aligned} \max_{Q} & &\langle X,Q\rangle \\ \text{subject to} & & \begin{bmatrix} I_m &...
user avatar
3 votes
0 answers
40 views

Correctness of QCQP formulation of an SDP problem

Consider the following semidefinite program: \begin{split} \max_{X,Y} \; & X_{12}^\top B + \mathrm{Tr}[(X_{11} + Y_{11})A]\\ \mbox{s.t.}\; & \mathrm{Tr}[X_{11} + Y_{11} - 2X_{12} E^\top - 2Y_{...
user avatar
  • 149
0 votes
0 answers
26 views

Question about SDP complexity

If I have two constraints that look like the following: Wii+x+y=0 R(Wij)+Im(Wij)+x+y=0 Where Wii and Wij belong to the W matrix that is positive SD, Wii is real and Wij is complex. x and y are other ...
user avatar
0 votes
0 answers
17 views

Constrain the form of the matrix Y in a standard semidefinite program problem, such that it is composed on kronecker products of matrices

Consider the following standard form of a semidefinite program: \begin{align} \min_{Y\geq0}\text{Tr}[F_0Y]\\ \text{subject to } \text{Tr}[F_iY]=c_i \end{align} I wish to know if I can constrain the ...
user avatar
  • 282
0 votes
0 answers
21 views

Bounded-length sum-of-squares representations for nonnegative polynomials in two variables.

I am considering real polynomials $p \in \mathbb{R}[x_1, x_2]$ which are nonnegative on compact semialgebraic sets, or even for simplicity the product of intervals $[-1,1]^2$. Numerous results exist ...
user avatar
0 votes
0 answers
70 views

Optimization with positive definite constraints

Suppose I have a function $f$ that is strictly convex on the positive semidefinite sets. I wonder if it is generally possible to minimize $f$ with positive definite constraints? $$\text{minimize } f(X)...
user avatar
  • 511
2 votes
0 answers
80 views

SemiDefinite representable set that is not Conic Quadratic representable.

Let $X \subset \mathbb{R}^n$. We say that $X$ is Conic Quadratic representable (CQr for short) if $$X=\left\{x \in \mathbb{R}^n: \exists u, A_j\begin{pmatrix}x \\ u\end{pmatrix}-b_j \in L^{m_j}, \ j=1,...
user avatar
  • 1,035
1 vote
0 answers
56 views

Minimizing the trace of a SPD-matrix subject to two trace equality constraints

I've encountered a problem where I need to check many (approximately $10^4$-$10^5$) minimum trace solutions subject to two trace inequality constraints. I've written this problem as an SDP and my gut ...
user avatar
0 votes
1 answer
91 views

Multiple SDP constraints

I have the following semidefinite program with $N$ semidefinite constraints, \begin{equation*} \begin{aligned} \min_{\theta \in \mathbb{R},\; 0 \leq w \leq 1}&\quad \theta\\ \text{st:}&\...
user avatar
  • 282
0 votes
0 answers
35 views

Find $(P,\Psi)$ such that $\alpha P\geqslant \Psi^TP\Psi\geqslant \beta P$

Given constants $\alpha\geq \beta>0$, find a nonsingular matrix $\Psi\in\mathbb{R}^{n\times n}$ and a postive definite matrix $P$ such that $$ \begin{aligned} \alpha P\geqslant \Psi^TP\...
user avatar
0 votes
0 answers
37 views

How to find dual of optimization problem and prove if it is feasible or not?

Given $A\in\mathbb{C}^{n\times n}$, I want to find out if the dual of the following problem is always solvable: \begin{array}{ll} \underset{X\in\mathbb{C^{n\times n}}}{\text{minimize}} & \mathrm{...
user avatar
  • 1,559
1 vote
2 answers
72 views

Minimization of Trace(XS) subject to [X,I;I,S]>=0

I have the following trace minization problem $$ \min_{X,S\in \mathbb{R}^{n\times n}} \text{Trace}(XS)\\ \text{subject to } \begin{bmatrix}X&I\\I&S\end{bmatrix}\geqslant 0,\\ ~~~~~~~~~~~~~~~~~...
user avatar
0 votes
0 answers
27 views

A minimization problem be formulated as a simple semi-definite program.

Consider the following block matrix: $$ A=\left(\begin{array}{ccccc} \sqrt{t} \mathbb{I}_{d_{1}} & \dot{\tilde{K}}_{0}^{\dagger} & \dot{\tilde{K}}_{1}^{\dagger} & \ldots & \dot{\tilde{...
user avatar
  • 175
0 votes
1 answer
72 views

Help with SDP and Schur's Complement

I'm trying so hard to understand SDP and how Schur's complement is used and what does it even mean? Is there a good and simple reference with some numerical examples that can answer my question ...
user avatar
0 votes
0 answers
59 views

Are there semidefinite programming bounds for the number of kissing spheres in the upper hemispace with respect to the central sphere?

For dimensions n=5-7 there are good known lower bounds for the number of n-dimensional spheres that that can touch (kiss) the central sphere, but the maximum number of spheres that can do so is not ...
user avatar
  • 1
0 votes
1 answer
52 views

Why the inequation is the semidefinite constraint of its elements?

This Lecture notes (p. 19) shows that in the problem $$ \begin{aligned} & M C P: & \text { minimize }_{M, y} &-2 \ln (\operatorname{det}(M)) \\ &&\text { s.t. } &\left(\...
user avatar
  • 271
0 votes
1 answer
75 views

Extracting solution of SDP problem in CVX

Assume we are given the following semidefinite program (SDP) written in MATLAB using CVX: ...
user avatar
  • 2,119
2 votes
1 answer
26 views

Are elements in each stage of the Lasserre hierarchy convex?

The Lasserre hierarchy is a schema for proving multivariate polynomials positive via a sum of squares decomposition. At the first level, a polynomial $p$ is written $$p = \sum_i f_i^2$$ where each $\...
user avatar
  • 2,414
0 votes
1 answer
39 views

Data Matrices Definiteness In Semidefinite Programming

I'm little bit confused about the data matrices associated with an SDP program. Consider the following SDP program: I know that the Matrix $X$ must be positive semidefinite i.e. $X \succeq 0$ as the ...
user avatar
0 votes
0 answers
20 views

Finding and Plotting Spectrahedra Defined by a Matrix

I'm trying to find a spectrahedron defined by the following inequality $$\mathcal{S}=\{(x,y,z)|\begin{bmatrix} 1+x & y & 0 & 0\\ y & 1-x & 0 & 0\\ 0 & 0 & 1+z & 0\\ ...
user avatar
0 votes
0 answers
12 views

Removing quadratic constraints from SDP relaxation

as I am new to SDP relaxation this question might be quite obvious. I have the following problem. Given: $$\underset{\Gamma,X}{\text{min }} tr(P\Gamma) + tr(X^TQX\Gamma)$$ and a few constraints, such ...
user avatar
  • 1
0 votes
1 answer
74 views

Dual of a SDP primal with an extra constraint

Consider the following (standard) primal SDP: $$ \begin{aligned} \min_{} & \quad \langle{C,X}\rangle \\ {\rm s.t.} & \quad \langle A_i,{X}\rangle = b_i, \\ & \...
user avatar
  • 2,119
0 votes
0 answers
17 views

Conversion of scalar optimisation problem to standard SDP

I want to transform the following program into standard form SDP. The problem in consideration is: $$ {\rm min} \,\, u, \\ {\rm s.t.} \, V \succeq 0 \\ \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, {\rm Tr}(L)=1 ...
user avatar
  • 2,119
0 votes
0 answers
75 views

Reducing convex QCQP to SDP or something better

I am trying to solve the following QCQP $$\begin{array}{ll} \underset{x}{\text{minimize}} & x^T P_0 x + q_0^Tx + r_0\\ \text{subject to} & x^T P_1 x + r_1< 0\end{array}$$ where symmetric ...
user avatar
  • 149
0 votes
1 answer
144 views

Quadratic programming to SDP

Assume I have an quadratic program of the form: \begin{align*} \min&&&\|LA-B\|^2\\ \text{s.t.}&&& \text{Tr}A=1\\ &&&A \succeq 0 \end{align*} Here $A,B,C,L$ are all $...
user avatar
  • 2,119
0 votes
0 answers
54 views

Analytic solution of a semidefinite program (SDP)?

I am interested in the following optimization problem: $$ \min_{\lambda > 0} \| \lambda A - I \|_{2}, $$ where $A$ is an arbitrary matrix and $\| \cdot \|_2$ is the spectral norm. As suggested by ...
user avatar
1 vote
2 answers
33 views

Proving these two matrix LMIs are the same.

For a matrix A $\in R^{nxn}$, the two statements are equivalent: There exists matrix $P > 0$, such that $A^TP+PA<0$ There exists matrix $P \geq 0$, such that $A^TP+PA+I\leq0$ Is this true?
user avatar

1
2 3 4 5
7