Questions tagged [semidefinite-programming]

Filter by
Sorted by
Tagged with
-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 & \...
mhdadk's user avatar
  • 609
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 ...
mhdadk's user avatar
  • 609
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 & \...
mhdadk's user avatar
  • 609
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 ...
Erel Segal-Halevi's user avatar
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 ...
gtg's user avatar
  • 11
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 ...
mhdadk's user avatar
  • 609
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 \...
Jisun Lee's user avatar
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 ...
R. Sh's user avatar
  • 11
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....
asfiwefewrno's user avatar
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 ...
benebrue's user avatar
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 ...
cdg's user avatar
  • 49
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?
Morcus's user avatar
  • 129
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 ...
Ibrahim Amer's user avatar
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 ...
Lars H's user avatar
  • 201
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 ...
kanso37's user avatar
  • 193