Skip to main content

Questions tagged [semidefinite-programming]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
36 votes
1 answer
2k views

Toy Examples for Plotkin-Shmoys-Tardos and Arora-Kale solvers

I would like to understand how the Arora-Kale SDP solver approximates the Goemans-Williamson relaxation in nearly linear time, how the Plotkin-Shmoys-Tardos solver approximates fractional "...
Luca Trevisan's user avatar
31 votes
2 answers
1k views

What classes of mathematical programs can be solved exactly or approximately, in polynomial time?

I am rather confused by the continuous optimization literature and TCS literature about which types of (continuous) mathematical programs (MPs) can be solved efficiently, and which cannot. The ...
Bart's user avatar
  • 516
30 votes
2 answers
888 views

Is there a polynomial time algorithm to determine if the span of a set of matrices contains a permutation matrix?

I would like to find a polynomial time algorithm that determines if the span of a given set of matrices contains a permutation matrix. If any one knows if this problem is of a different complexity ...
Nick's user avatar
  • 483
22 votes
1 answer
3k views

Solving semidefinite programs in polynomial time

We know that linear programs (LP) can be solved exactly in polynomial time using the ellipsoid method or an interior point method like Karmarkar's algorithm. Some LPs with super-polynomial (...
Arindam Pal's user avatar
  • 1,591
22 votes
3 answers
624 views

Educational Source or Survey on Analysis of Semidefinite Program?

When designing approximation algorithms one sometimes solves a semidefinite program followed by a rounding step. An often used example to illustrate this is Max-Cut. (See e.g. Approximation Algorithms ...
Michael's user avatar
  • 436
18 votes
1 answer
2k views

Polynomial speedups with algorithms based on semidefinite programming

This is a followup of a recent question asked by A. Pal: Solving semidefinite programs in polynomial time. I am still puzzling over the actual running time of algorithms that compute the solution of ...
Alessandro Cosentino's user avatar
10 votes
2 answers
610 views

What can be solved with semidefinite programming that can't be solved with linear programming?

I'm familiar with linear programs in that they can solve problems with linear objective functions and linear constraints. But what can semidefinite programming solve that linear programming can't? I ...
user11094's user avatar
  • 203
10 votes
3 answers
768 views

When is the duality gap of semidefinite programming (SDP) zero?

I haven't been able to find in the literature a precise characterization of the vanishing of the SDP duality gap. Or, when does "strong duality" hold? For example, when one goes back and forth ...
gradstudent's user avatar
  • 1,453
10 votes
1 answer
549 views

Systematic studies of sum of quadratic polynomials squared

I'm wondering if there exists systematic studies of sums of quadratic forms squared, similar to the quadratic forms, which is practically reflected in eigenvalue decomposition (that has huge practical ...
mkatkov's user avatar
  • 537
9 votes
2 answers
1k views

Techniques for proving bounds on integrality gap in LP(SDP)

A reference to techniques for proving that the size of an integrality gap is bounded by some expression for a particular LP(or SDP, but less important) is needed. Also it would be nice to have a ...
Grigory Yaroslavtsev's user avatar
8 votes
1 answer
591 views

Is the feasible region of this SDP polyhedral?

We have a semidefinite program (SDP) whose feasible region contains only a finite number of rank-$1$ matrices. Can we conclude that the feasible region of this SDP is polyhedral? We believe this to ...
Pawan Aurora's user avatar
8 votes
1 answer
1k views

Positivstellensatz and sum of squares method

This question comes from many online resources that introduce Sum-of-Squares method, such as the survey of Barak and Steurer (http://arxiv.org/abs/1404.5236). Let me focus on Theorem 2.1 of this ...
anurag anshu's user avatar
8 votes
2 answers
1k views

SDP relaxation of independent set

I'm looking at page 28 of Lovasz "Semidefinite programs and combinatorial optimization" and it gives the following approximation of independence number of the graph $$\max u' Z u$$ subject to $$Z\...
Yaroslav Bulatov's user avatar
7 votes
1 answer
640 views

SDP and chromatic number upper bounds

Are there any references for finding non-trivial upper bounds to chromatic number using semidefinite programming?
v s's user avatar
  • 2,208
7 votes
0 answers
3k views

Time complexity of standard semidefinite programming solvers

I am interested in exact scaling of the ellipsoid method and interior point methods for solving SDPs. (I am not interested in algorithms like multiplicative weights updates method.)
postasaguest's user avatar
6 votes
1 answer
945 views

Analytic solutions in semidefinite programming (SDP)

From my experience in the application of semidefinite programming (SDP) to quantum information, I have learnt that the solution to an SDP can sometimes be expressed as an analytic formula. For example,...
Juan Miguel Arrazola's user avatar
6 votes
1 answer
168 views

Brute force search algorithm for semidefinite programming (representation of spectrahedron)

I was wondering if there exists a brute force search algorithm for semidefinite programming problems. Specifically, can we find finite number of points in the positive semidefinite cone such that for ...
Steve's user avatar
  • 451
6 votes
0 answers
515 views

Fastest exact algorithm for MAXCUT

Is the algorithm introduced in the following paper still the fastest exact algorithm for general MAXCUT problems? TIA Ryan Williams, A new algorithm for optimal $2$-constraint satisfaction and its ...
Omar Shehab's user avatar
6 votes
0 answers
363 views

Approximating the diameter of a convex set defined by semidefinite constraints

A convex subset $C$ of $\mathbb{R}^{n^2}$ is given as the set of positive semidefinite $n\times n$ matrices whose coefficients fulfill some affine equations. Now, if you want to minimize a linear ...
Vincent Nesme's user avatar
5 votes
1 answer
503 views

Unique Games versus SDP procedures

Unique Games results provide very interesting barriers to results through semidefinite programming. Lovasz theta ($\vartheta(G)$) function is an incarnation of SDP. Is UG conjecture true $\iff \...
Turbo's user avatar
  • 13k
4 votes
1 answer
156 views

Generalizations of linear programming

Linear problems can be solved in polynomial time. So can semidefinite programs and, presumably, many other useful classes of optimization programs. Is there a survey/lecture notes describing ...
user2316602's user avatar
4 votes
0 answers
106 views

Bounding a Solution of an SDP

It's common for convex optimization procedures to require a bounded region containing an optimal solution, either as input, like the initial ellipsoid of the ellipsoid method, or for run time bounds, ...
sbnietert's user avatar
4 votes
0 answers
251 views

Testing emptiness property complexity in Sum of Squares Proof systems

Take the set $$\mathcal T=\{f_1(x_1,\dots,x_n)=\dots=f_m(x_1,\dots,x_n)=0, h_1(x_1,\dots,x_n)\geq a_1,\dots,h_t(x_1,\dots,x_n)\geq a_t\}$$ where $$h_1(x_1,\dots,x_n),\dots,h_t(x_1,\dots,x_n)\in\mathbb ...
VS.'s user avatar
  • 539
3 votes
1 answer
242 views

How is SDP an extension of spectral algorithms?

In one of his lectures, Uri Feige described semidefinite programming (SDP) as ... an algorithmic technique that extends both linear programming and spectral algorithms. I know the basic ...
user2316602's user avatar
3 votes
1 answer
426 views

Applications and benchmarks for binary quadratic program algorithms

I have an algorithm that on all examples I was running finds an arbitrary approximation of global minimum of binary quadratic program. The algorithm find the minimum in polynomial time. Binary ...
mkatkov's user avatar
  • 537
3 votes
1 answer
182 views

SOS hardness of $Max-2-Lin(\mathbb{Z}_2)$?

Do we know of instances of $Max-2-Lin(\mathbb{Z}_2)$ which have a integrality gaps w.r.t to high degree (> 4) SOS relaxations? Or if we specialize to Max-CUT do we know of graphs whose Max-CUT ...
gradstudent's user avatar
  • 1,453
3 votes
1 answer
596 views

What is a "level-r pseudo expectation functional"?

In the context of the SOS hierarchy papers, it seems that a "level-r psuedo expectation functional" is the same as an operator taking expectations of functions just that this one has the restriction ...
user6818's user avatar
  • 281
3 votes
0 answers
77 views

Are there applications of Hyperbolic Programming other than Linear Programming and Semidefinite programming?

Title. It seems the most important special cases are LPs and SDPs. Are there other interesting special cases/applications for hyperbolic programming? (Apart from being super cool math on of itself) I ...
user3508551's user avatar
  • 1,153
3 votes
0 answers
110 views

Can the Lasserre relaxation be defined over the reals?

If one wants to say minimize a function $f : \{-1,1\}^n \rightarrow \mathbb{R}$ on its domain then a degree$-d$ Lasserre relaxation of it would be to solve the problem of $\min \mathbb{E}_\mu [f(x)]$ ...
gradstudent's user avatar
  • 1,453
3 votes
0 answers
153 views

SOS and the small set expansion property

For what graphs do we know that their small set expansion property has a low degree SOS proof? Is this known to be true for say the complete graphs? A terminology issue about what is ``low degree" :...
gradstudent's user avatar
  • 1,453
3 votes
0 answers
89 views

First-order methods for solving SDP with geometric convergence or better

Is there any first-order method that can solve general SDP in a geometric (linear) rate? or super-geometric (super-linear) rate?
Minkov's user avatar
  • 862
3 votes
0 answers
114 views

Quantum annealing or adiabatic quantum optimization with continuous optimization problems

How do quantum annealing or adiabatic quantum optimization deal with continuous optimization problems such as SDP?
Wuchen's user avatar
  • 131
3 votes
0 answers
225 views

The Quality of SDP relaxation on MaxCut

My question is: given a maxcut instance, if it costs too much to solve it to optimal practically but we can get an optimal solution of SDP relaxation quickly, can we assess the quality of this SDP ...
Ben's user avatar
  • 31
3 votes
0 answers
159 views

Gram matrix of Max-Cut relaxation

It seems that Goemans and Williamson give a unique representation for each graph of the semidefinite relaxation (elements $y_{ij}$ of Y). However, semidefinite programming may give the same maximum ...
N27's user avatar
  • 573
2 votes
1 answer
2k views

Using MATLAB's CVX Package for Semidefinite Programming in Quantum Information

I'm attempting to formulate the semidefinite programs used in the paper "Hedging Bets with Correlated Quantum Strategies" (specifically those on page 7) into CVX so that I can play around with the ...
Vincent Russo's user avatar
2 votes
1 answer
206 views

State of the art on approximating quadratic assignment problem

I was wondering what is the state of the art on approximating the quadratic assignment problem (QAP). In particular, I am interested in the following instance. Suppose the $A = (a_{ij}) \in \{0,1\}^{n ...
passerby51's user avatar
2 votes
0 answers
41 views

Are those two Sum-Of-Squares approach for unconstrained polynomial optimization related? [closed]

This is a crosspost of mathoverflow/345282 I found 2 approaches to solve an unconstrained polynomial optimization problem using the Lasserre / SOS hierarchy: $$\inf_{x\in\mathbb{R}^n}\quad p(x)$$ ...
guigux's user avatar
  • 121
2 votes
0 answers
188 views

A variant of the Maximum Weight Clique problem

I am trying to solve a problem that I could reduce to the following: Given a graph $G=(V,E)$ with both edge and vertex weights, all weights being non-negative, find a clique $Q\subseteq V$ s.t. $\sum_{...
Pawan Aurora's user avatar
2 votes
0 answers
74 views

Is there a relationship between the probabilistic interepretation of Sherali-Adams SDP hierarchy and the Lasserre SDP hierarchy?

Firstly note this paper http://ttic.uchicago.edu/~madhurt/Papers/reductions.pdf where a Lasserre SDP is being setup for the independent set probblem at the bottom of page 4 where the author says says, ...
gradstudent's user avatar
  • 1,453
2 votes
0 answers
479 views

SDP Feasibility

I have a decision problem that I have formulated as a feasibility SDP. The answer to the decision problem depends on whether the SDP is feasible or not. It is known that a SDP can be solved to ...
Pawan Aurora's user avatar
1 vote
1 answer
165 views

Approximation algorithm for balanced bipartite independent set?

The Problem: Given a bipartite graph $G = (L,R,E)$ with $|L|=|R|=n$, the balanced bipartite independent set problem asks us to output the largest vertex subsets $A\subseteq L, B\subseteq R$ of equal ...
Bell's user avatar
  • 53
1 vote
1 answer
432 views

Optimal value of a semidefinite program

Is a local optimum value of a SDP always the global one? If not, what are the conditions for that?
N27's user avatar
  • 573
1 vote
0 answers
71 views

Equivalent SDP problems different solving times

I have two SDP problems which are proved to be equivalent (in terms of optimal objective values) to each other in theory. Moreover, they have same number of constraints and variables respectively. ...
justaskquestion's user avatar
1 vote
0 answers
167 views

Ramsey theory through semidefinite programming

Could we realize good bounds on Ramsey theoretic problems using semidefinite programming? Example: Is there a good bound on Ramsey numbers $R(r,s)$ from semidefinite programming? Does number of ...
Turbo's user avatar
  • 13k
1 vote
0 answers
144 views

Unit distance representation of a graph through Semidefinite Programming

I would like to ask on the number of different drawings of the unit distance representation of a graph, found through a semidefinite program (see www.cs.elte.hu/~lovasz/semidef.ps , p. 20-22). Since ...
N27's user avatar
  • 573
0 votes
1 answer
232 views

Max-k-cut with negative edge weights

Let $G=(V,E,w)$ be a graph and for edge $e\in E$, there is associated weight $w_e$. The max-k-cut wants to partition V into k subsets $P_1,\cdots,P_k$ and maximize $\sum_{1\leq r<s\leq k}\sum_{i\in ...
Daogao Liu's user avatar
0 votes
1 answer
70 views

Solving non-linear programming with large number of variables

Let $n \in \mathbb{N}, [n] = \{1,2,\ldots,n\}$ and consider the following optimization problem: $$\max \sum_{i \in [n]} \sum_{j \in [n]} x_i \cdot x_j \cdot c_{i,j}$$ $$s.t.~~~~~~~~~~~~~~~~~~~~~~~~~~~~...
John's user avatar
  • 412
0 votes
0 answers
32 views

Decidability of Mixed-Integer Semidefinite Programs

Semidefinite programs (SDP) have an "efficient" solution, as a convex problem, by e.g. the ellipsoid method; but this comes with standard caveats as the output can be exponentially long (...
Alex Meiburg's user avatar
0 votes
0 answers
112 views

Examples of SDP constant approximation algorithms on minimisation problems

I was recently going through a survey on semidefinite programming and its use in approximation algorithms. Here are some problems I am familiar with that have SDP approximations: Max Cut ($\approx 0....
user3508551's user avatar
  • 1,153
-3 votes
1 answer
126 views

What is wrong with this procedure to convert quadratic programming to convex quadratic programming?

Consider the feasibility quadratic program with constraint $$\sum_{i=1}^nc_{i1}x_{i}\leq \ell_1$$ $$\vdots$$ $$\sum_{i=1}^nc_{it}x_{i}\leq \ell_t$$ $$\sum_{i,j=1}^na_{ij}x_{i}x_{j}+\sum_{i=1}^nb_{i}x_{...
Turbo's user avatar
  • 13k