# Tagged Questions

The tag has no usage guidance.

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 ...
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 ...
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 ...
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. ...
63 views

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" ...
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 ...