The tag has no usage guidance.

learn more… | top users | synonyms

4
votes
0answers
47 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 ...
0
votes
0answers
33 views

Vector Product in the constrinats on an optimization problem

Can the following optimization problem be solved using Semi-Definite Programming or Linear Programming. We are given a data matrix $A$, which is known. We have the following optimization problem. This ...
4
votes
1answer
147 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 ...
1
vote
0answers
33 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. ...
0
votes
0answers
63 views

Approximate $\gamma_2$ norm of a matrix in standard SDP form

The $\gamma_{2}$ norm of a matrix $A\in\mathbb R^{m\times n}$, a well-known measure of matrix complexity, is defined in its matrix-factorization form as $$\gamma_{2}(A):=\min_{XY^{T}=A}\|X\|_{2\...
3
votes
0answers
45 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?
3
votes
0answers
54 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?
3
votes
1answer
204 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 ...
0
votes
0answers
132 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 ...
5
votes
1answer
342 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 \...
7
votes
1answer
249 views

Is the feasible region of this SDP polyhedral?

We have a semidefinite program (SDP) with feasible region containing only a finite number of rank-$1$ matrices. Can we conclude that the feasible region of this SDP is polyhedral? We believe this to ...
2
votes
1answer
91 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 ...
7
votes
2answers
321 views

what can be solved with semidefinite programming that can't be solved with linear programs?

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 programs can't? I ...
5
votes
0answers
559 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.)
21
votes
1answer
431 views

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

Precisely what the title says, I'm looking to find a polynomial time algorithm that given some set of matrices, will find if their span contains a permutation matrix. If any one knows if this ...
14
votes
1answer
455 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 ...
13
votes
1answer
816 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
1k 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
255 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
264 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 ...
6
votes
1answer
449 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
532 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
158 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 ...
9
votes
1answer
433 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 ...
27
votes
2answers
753 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
133 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 ...
3
votes
2answers
1k 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 ...
1
vote
0answers
132 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 ...
1
vote
0answers
351 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
559 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\...
30
votes
1answer
1k 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
366 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
566 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
563 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 ...