Mathematics Stack Exchange
Mathematics 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.

(Wikipedia) Semidefinite programming is a relatively new field of optimization which is of growing interest for several reasons. Many practical problems in operations research and combinatorial optimization can be modeled or approximated as semidefinite programming problems.

In automatic control theory, SDPs are used in the context of linear matrix inequalities. SDPs are in fact a special case of cone programming and can be efficiently solved by interior point methods.

All linear programs can be expressed as SDPs, and via hierarchies of SDPs the solutions of polynomial optimization problems can be approximated.

Semidefinite programming has been used in the optimization of complex systems. In recent years, some quantum query complexity problems have been formulated in term of semidefinite programs.

388 questions
1
vote
1 answer

Can a line be a cone or not?

Can we say that a line is a cone? That is, if I am given set $S$, containing all the points on a line, then that must be cone because for a cone, we require $x \in S$. Then, $cx$ must also be in the set $c \geq 0$
thetatheta
  • 227
1
vote
0 answers

Semidefinite program with equality constraints expressed as matrix product

Consider a semi-definite program with equality constraints where the variable $X$ is a block matrix. Denoting the different blocks of $X$ by $X_j$ where $j$ is an index, the standard form of the equality constraints is $$\sum_j {\rm tr}(A_{ij}…
Matt Hastings
  • 111
1
vote
0 answers

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{tr}(CX)$, where $C$ is a known matrix. The goal…
Tan
  • 621
1
vote
0 answers

What is the importance of the maximum determinant PSD completion?

For a symmetric $p\times p$ matrix $X$, where $X$ has sparsity $E$ ($X_{ij} = 0$ if $i\neq j$ and $\{i,j\}\not\in E$) we say that $X$ has a positive semidefinite completion if there exists some $Z$ positive semidefinite and $X_{ij} = Z_{ij}$…
Y. S.
  • 1,816
0
votes
1 answer

Obtaining Symmetric Positive Semi-Definite Matrices from Sum of Squares Variables

I am a bachelor student and have the following question. I am currently working on converting constraint functions into new constraints as sum of squares since I would like to solve the optimization problem through SDP-solvers. Thanks to SOS-Tools…
Atamert
  • 3
0
votes
1 answer

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(\begin{array}{cc}I & M c_{i}-y \\ \left(M c_{i}-y\right)^{T} &…
SandyX
  • 301
0
votes
0 answers

How to solve a Semidefinite problem with fractional Objective function

I have a Semidefinite problem of the form \begin{align} \min_{t\epsilon R,A \epsilon S_{+}^n}~& 1/t \\ &t>0\\ &A>=t C\\ &A\odot C_M=T_M\\ &\left\lvert\lvert A \right\rvert\rvert _F^2 <=r \end{align} or a more general form…
user85361
  • 845