# Questions tagged [relaxations]

A relaxation of a problem is a related problem whose solution is easier in some sense to find, while providing useful information about the solution to the original problem. One common form is a linear relaxation.

58 questions
Filter by
Sorted by
Tagged with
28 views

### Conversion of SDP relaxation of Travelling Salesman Problem (TSP) to standard SDP form

The standard SDP formulation is given as : \begin{aligned} \min_{X\in H^{n}} \quad& \langle X,M_{0} \rangle\\ \textrm{s.t.} \quad& l_{s} \leq \langle X, M_{s} \rangle \leq ...
19 views

### Will Multigrid method be faster than ordinary iteration on just the coarsest grid for Poisson equation?

I am using the Jacobi iterative solver to solve Poisson heat equation discretised using the finite difference method? I am currently using the coarsest mesh I can that has a grid spacing small enough ...
• 101
1 vote
32 views

### Can I reformulate the given SDP such that the main constraint becomes and LMI?

I am new to SDP and LMI's and trying to solve an optimization problem of the following form: \begin{aligned} \text{maximize} \quad & \sum_{j=1}^k w_j\\ \text{subject to} \quad &...
1 vote
44 views

### How to maximize quadratic form with a integer variables or its relaxation

Let $A$ be a positive semidefinite matrix. Also, let $\forall i\in [1,n], x_i \in \{-1,1\}$. And finally, for some of indices $I\subset \{1,\ldots,n\}$, values of $x_i\in \{-1,1\}$ are known. ...
• 803
34 views

### Name for integrality relaxation in BQP problems

Given a binary quadratic program, what is the name for the relaxation where the binary constraints are relaxed to $[0,1]$ box constraints? For LPs this is normally called LP-Relaxation. However, since ...
• 75
32 views

### Does this relaxation have a name?

Imagine you have e.g. the following optimization objective over a joint $D$-dimensional real-valued space, i.e. $x^* = \min_{x} f(x), \quad x \in \mathbb{R}^D$ And then you have the following ...
• 129
77 views

### Why $x^TAx=\text{Tr}(AX)$?

In many optimization resources, when we reformulate an LP to an SDP, we sometimes use the fact that \begin{equation*} x^{T}Ax = Tr(AX), \end{equation*} where $X=xx^T$ is a number. But when I tried to ...
• 787
1 vote
80 views

### Is Lagrangian relaxation convexity optimization problem or not?

We know that for a regular maximization LP problem, it should be $$z^* = \max_x c^Tx \ s.t. x \in X, Ax \leq b$$ where $b \in \mathbb{R}^m$. There is a technique called Lagrangian relaxation, which ...
• 133
23 views

### Are there continuous relaxations of the notion of function composition (e.g. for automorphisms)?

An automorphism can be applied any integer number of times. Is there a sensible notion of applying it a non-integer number of times? I have the same question for more general types of transformations....
• 1,165
1 vote
20 views

### Relaxation of Chance Constraints Proof

I'm dealing with the following chance constraint $$\mathbb{P}(\|Ax\|_2 \leq c^\intercal x) \geq 1 - \delta,$$ where $x \sim \mathcal{N}(\mu,\Sigma)$ and $\delta \in (0, 0.5]$. Since $x$ follows a ...
1 vote
153 views

### How to iteratively solve Poisson's Equation with no boundary conditions?

I'm working to reimplement the results of this fantastic paper which allows you to design your own caustics. On the top left corner of page 3 there are three images: A blue and red "difference ...
• 113
64 views

90 views

### Formulation for IP of large OR statement which gives a good linear relaxation

Let $N$ be a very large number. I want a good way to program that $x$ should be one if and only if one of $x_i$ is equal to one.We can write the following Integer Programming problem: \begin{align*} \...
• 1,115
197 views

### Is there a second-order conic relaxation method for the bilinear term $z=xy$? [closed]

I hope to find a second-order conic (SOC) relaxation for $z = xy$, but it seems very hard.
• 43
1 vote
25 views

• 575
1 vote
155 views

### Upper bound for spectral radius of matrix multiplications

For Chebyshev iteration, I want to find an upper bound for the highest eigenvalue of a matrix. I have a library in C++ to find eigenvalues for symmetric matrices, but for Chebyshev I need to find the ...
• 11
1 vote
164 views

### Upper AND lower bound for the linear relaxation

Let's say i have a linear integer program IP and let LP the linear relaxation of IP. I want to maximize IP and let $z_{IP} > 0$ the optimal value of IP and $z_{LP} > 0$ the optimal value of the ...
• 43
445 views

• 151
1 vote