The semidefinite-programming tag has no wiki summary.
12
votes
1answer
170 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 ...
10
votes
1answer
244 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 ...
2
votes
1answer
348 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 ...
2
votes
0answers
131 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 ...
5
votes
0answers
194 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 ...
5
votes
1answer
299 views
SDP and chromatic number upper bounds
Are there any references for finding non-trivial upper bounds to chromatic number using semidefinite programming?
4
votes
1answer
289 views
Analytic solutions in Semi-Definite Programming
From my experience in the application of Semi-definite programming (SDP) to quantum information, I have learnt that the solution to an SDP can sometimes be expressed as an analytic formula. For ...
3
votes
0answers
129 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 ...
8
votes
1answer
318 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 ...
20
votes
2answers
504 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 ...
2
votes
0answers
118 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 ...
1
vote
1answer
446 views
condition to make an adjacency matrix positive semidefinite
I would like to ask how can we transform an adjacency matrix of a graph into a positive semidefinite matrix. Of course, we could set self loops, but I do not know of any result indicating how we can ...
0
votes
0answers
124 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 ...
0
votes
0answers
337 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. Thanks
7
votes
2answers
388 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
...
29
votes
1answer
740 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 "packing" ...
3
votes
1answer
294 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 ...
22
votes
3answers
545 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 ...
7
votes
2answers
398 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 ...
