Questions tagged [semidefinite-programming]
The semidefinite-programming tag has no usage guidance.
15
questions
-1
votes
1
answer
57
views
Does strong duality hold for this semidefinite program?
$\DeclareMathOperator{\Tr}{Tr}\DeclareMathOperator*{\argmax}{\arg\!\max}$Consider the following semidefinite program (SDP)
$$
\begin{aligned}
\max_V \quad & \Tr(V) \\
\textrm{s.t.} \quad & \...
1
vote
1
answer
93
views
How can I convert this semidefinite program into standard form?
$\DeclareMathOperator{\Tr}{Tr}\DeclareMathOperator*{\argmax}{\arg\!\max}$Consider the following semidefinite program (SDP)
$$
\begin{aligned}
\min_V \quad & \Tr(V) \\
\textrm{s.t.} \quad & AVB ...
2
votes
0
answers
87
views
How can I derive the sufficient KKT conditions for an SDP?
$\DeclareMathOperator{\Tr}{Tr}\DeclareMathOperator*{\argmax}{\arg\!\max}$Consider the following semidefinite program (SDP)
$$
\begin{aligned}
\min_V \quad & -\Tr(V) \\
\textrm{s.t.} \quad & \...
3
votes
1
answer
127
views
How is semidefinite programming a special case of convex programming?
In this image from Wikipedia, semidefinite programming is presented as a special case of convex programming. I do not see how this can be. Consider the following two constraints (where $\succeq$ means ...
1
vote
0
answers
54
views
Strong relaxations for binary variables
Having the following optimization problem that models $\sum_i\min(c_i, C)$:
$$
\min_{\mathbf{Y},\,\,\{x_i\}_i} \sum_i^{n} c_ix_i + C(1-x_i)
$$
and where
$C$ is a positive constant,
each $x_i$ is a ...
0
votes
1
answer
87
views
How is this problem quasi-convex?
I'm currently reading the following paper
B. Sinopoli, L. Schenato, M. Franceschetti, K. Poolla, M. I. Jordan, and S. S. Sastry, āKalman filtering with intermittent observations,ā IEEE Transactions ...
0
votes
0
answers
37
views
How to check optimality of conic optimization problem
I'm trying to solve this problem, but I'm not sure if it is possible to check the optimality of this problem.
$$\min_{K,L} \quad Tr(L^\top L)\qquad\\
\text{s.t.} \quad K^\top L = A^\top Q\\
\qquad \...
1
vote
1
answer
130
views
interior point computational complexity for SDP
I am trying to get the complexity of the SDP problem for my specific problem, but Iām facing some problems.
I found in the literature that the complexity of the SDP problem for an interior point per ...
1
vote
0
answers
54
views
Distributionally Robust Stochastic Programming - Help with derivation
I've been working through this book on robust optimization of electric energy systems, and in particular chapter 4 on distributionally robust optimization. In following the derivation of section 4.2.1....
3
votes
2
answers
111
views
Augmented Lagrangian Function for Semidefinite Programming Problems
I am currently reading the paper "Alternating direction augmented Lagrangian methods for semidefinite programming" and was wondering about how one comes up with the Augmented Lagrangian ...
4
votes
0
answers
386
views
Adequate SDP solvers for large problem instances
I have previously used MOSEK for all my SDP needs. Recently, though, I am having a hard time trying to solve some large problems, due to lack of memory. In similar questions around the forum, SCS has ...
2
votes
1
answer
353
views
Solver for nonlinear semidefinite optimization
Totally new to optimization. Is there an easy-to-use solver, package, (free) software for solving nonlinear semidefinite optimization problems?
3
votes
1
answer
1k
views
Non-symmetric Positive Definite/Semidefinite Matrix in Quadratic Program
A necessary condition in any quadratic programming to be convex is the matrix $\mathbf{Q}$ in the formulation $x^\intercal \mathbf{Q}x$ to be positive definite or positive semidefinite. Positive ...
2
votes
0
answers
111
views
Is this semidefinite constraint in fact pointless?
On Wikipedia, I encountered a statement that the semidefinite relaxation of a quadratically constrained quadratic program can be solved more efficiently (using only LP) in the case that no variable is ...
6
votes
1
answer
673
views
Conditions required for strong duality to hold for SDPs
According to Wikipedia, strong duality holds when "the primal optimal objective and the dual optimal objective are equal."
What are the necessary conditions for strong duality to hold in ...