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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
28 views

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

The standard SDP formulation is given as : \begin{equation} \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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
  • 101
1 vote
1 answer
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{equation} \begin{aligned} \text{maximize} \quad & \sum_{j=1}^k w_j\\ \text{subject to} \quad &...
user avatar
1 vote
0 answers
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. ...
user avatar
  • 803
0 votes
1 answer
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 ...
user avatar
  • 75
0 votes
1 answer
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 ...
user avatar
  • 129
0 votes
2 answers
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 ...
user avatar
  • 787
1 vote
1 answer
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 ...
user avatar
0 votes
0 answers
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....
user avatar
  • 1,165
1 vote
0 answers
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 ...
user avatar
1 vote
1 answer
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 ...
user avatar
  • 113
0 votes
1 answer
64 views

Efficient algorithm for SDP relaxation of max-cut

Given a symmetric $n\times n$ matrix $A$, I'm interested in the class of SDP problems that can be written canonically as: $$ \begin{align} \text{minimize} \quad &-\text{tr}(AX) \\ \text{subject to}...
user avatar
  • 303
2 votes
0 answers
114 views

Characterise a feasible-to-construct superset of a set

Intro: I have a non-convex set, defined by conditional constraints, that is infeasible to construct exactly. I would like your help to characterise a superset of this set that can be feasibly ...
user avatar
  • 136
0 votes
1 answer
431 views

LP Relaxation is unbounded

How do I go about proving the integer linear program has an optimal solution, but that its linear program relaxation is unbounded? \begin{equation} \begin{array}{cl} {\max} & {x_1} \\ {\text{s.t.}...
user avatar
0 votes
0 answers
56 views

While solving a MILP via subsequent Linear Relaxations are relaxed Indicator variables and constraints still useful to guide the objective function?

I have a multi objective Mixed Quadratic binary non-linear problem. Following a scalarization approach, the objective function includes the sum of some binary variables (say Z_j) minus lambda times ...
user avatar
  • 11
2 votes
1 answer
170 views

Relaxation method on a system of two second-order, coupled, non-linear ODEs (boundary value problem)

This is my first question on Stack Exchange - I welcome any suggestions if my approach to asking it does not match the usual conventions around here. So: I need to solve a system of two second-order, ...
user avatar
2 votes
1 answer
82 views

Is the Frobenius norm defining a Trust-Region for a matrix?

I am minimizing a non convex function $f$ defined over the positive semidefinite cone $S_+^n$ through linearization methods (sequential linear/convex approximation) and I would like to constraint the ...
user avatar
  • 433
2 votes
1 answer
112 views

Lagrangian relaxation of optimization problem

Use Lagrangian relaxation to solve the following optimization problem in $x, y\in \mathbb{R}$. $$\begin{array}{ll} \text{minimize} & x^2 + 2 y^2\\ \text{subject to} & x + y \geq 2\\ & x^2 +...
user avatar
2 votes
2 answers
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*} \...
user avatar
  • 1,115
4 votes
1 answer
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.
user avatar
1 vote
0 answers
25 views

Relaxation of the set given by knapsack constraints

A set $\mathcal{A}$ is the relaxation of another set $\mathcal{B}$, if $\mathcal{B} \subseteq \mathcal{A}$. I have a set of points defined as $$ \mathcal{X} = \{x \in \mathcal{Z}^n_{+}: w^{\top}x \...
user avatar
  • 1,414
2 votes
1 answer
424 views

Subgradient procedure for lagrangian relaxation of GAP

I'm trying to solve the general assignment problem by relaxing the capacity constraint and applying the subgradient procedure. GAP (from here): Relaxation (same source as above): Subgradient method ...
user avatar
4 votes
1 answer
75 views

Probabilistic interpretation of optimality gap in Integer Program

Suppose I have an integer program model in the form of a minimization. I noticed that Gurobi (my solver) often finds a very good upper bound (i.e., feasible solution) whereas it takes a significant ...
user avatar
1 vote
1 answer
123 views

is optimal solution of the original problem always the same as the relaxed problem Or is this just an accident?

I want to solve the following problem with GAMS software: $ \min y+\frac{1}{0.05} \sum_s p^s u^s $ $s.t$ $\sum_{j \in V}\delta_j=b$ $\sum_{j\in W^s} x_j^s +q^s=1 \ \ \forall s\in S$ $ x_j^s \...
user avatar
  • 367
1 vote
0 answers
24 views

Minimization in Chan-Vese convex relation model

I am working on an assignment with the Chan-Vese convex relaxation model for two-phase image segmentation, i.e., coming up with two regions — the object and the background. Specifically, I need to ...
user avatar
  • 11
2 votes
0 answers
92 views

Simplification of a Quadratically constrained, Quadratic objective (to apply Semidefinite relaxation)

I came up with the following optimization problem: $$\arg\max_{G_i} \quad G_1^TI^TIG_1 + ...+G_N^TI^TIG_N$$ subject to: $$\|G_i\|_2^2=1 \quad \forall i$$ $$\|G_i-G_{o_i}\|_2^2\leq c \quad \forall i$$ ...
user avatar
  • 621
0 votes
1 answer
143 views

Semidefinite relaxation

Suppose that we have an objective function that involves two binary variables, i.e. $x, y \in \lbrace 0,1 \rbrace$ ($x$ represents the assignment of category A to category B and $y$ represents the ...
user avatar
1 vote
0 answers
126 views

Solving PDEs by adding small perturbation terms and taking limits

When trying to solve some PDE problem, sometimes we made approximation problem that is easier to solve than the original one. We do that by adding a new term(s) in the original problem. Then we try to ...
user avatar
  • 538
1 vote
0 answers
192 views

Solving linear systems of equations consists of block-diagonal part + small sparse part

guys i have system of the following form $A*x = b, A = BD+\epsilon * S$ where $BD$ is block-diagonal system , S - some sparse system, $\epsilon$ -- some small constant, for clearity $\lvert\lvert BD \...
user avatar
1 vote
0 answers
53 views

Non-convex objective function + (non-convex constraint function vs. convex constraint function)

In the optimization problem, both objective function and the constraint functions are non-convex. (topology optimization) - objective function: force on structure - constraint functions: material ...
user avatar
6 votes
1 answer
320 views

$n$-sphere enclosing the Birkhoff polytope

I am not a mathematician by training, so please feel free to correct my logic or descriptions when necessary: Let $P$ denote a $\textit{permutation matrix}$: $$ \begin{equation} P := \{X \in \{0,1\}^{...
user avatar
1 vote
0 answers
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 ...
user avatar
  • 11
1 vote
0 answers
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 ...
user avatar
  • 43
3 votes
0 answers
445 views

Semidefinite relaxation for QCQP with nonconvex "homogeneous" constraints

Suppose we wish to solve the quadratically constrained quadratic program (QCQP) in $x \in \mathbb R^n$ $$\begin{array}{rl} \text{minimize} & \frac{1}{2}x^\top Lx\\ \text{subject to} & Ax=b\\ &...
user avatar
2 votes
1 answer
261 views

LP relaxation of the symmetric TSP problem integrality for n=5

The Dantzig-Fulkerson-Johnson formulation for the symmetric TSP Polytope is given as: $x(\delta(v))=2 \quad \forall v \in V$, $x(\delta(S))\geq2 \quad \forall \emptyset \subset S \subset V$, $x \in \{...
user avatar
3 votes
1 answer
818 views

What does it mean to dualize a constraint in the context of Lagrangian relaxation?

In the context of Lagrangian relaxation of discrete optimization problems, what does it mean to 'dualize a constraint'?
user avatar
  • 1,448
1 vote
0 answers
103 views

Iterative methods for linear systems - Gauss-Southwell rule

I want to implement an iterative method for linear systems with the GS rule in MATLAB: at each step we pick the equation whose corresponding component of the residual is the largest in absolute value. ...
user avatar
  • 305
0 votes
1 answer
142 views

Exercise LP Relaxation [closed]

$\max Z = 6x_1 + 7x_2$ Constraints: $-2x_1 + 2x_2 \le 3\\ 7x_1 + 3x_2 \le 22$ $x_1,x_2 \ge 0$ and $x_1, x_2 \in \Bbb Z$ How to solve this problem with relaxation LP by graphical method?...
user avatar
2 votes
1 answer
212 views

Determining if a set is convex, and if not, finding a convex relaxation

This is for an advanced course in Chemical Engineering, and I do not have much previous experience with matrix mathematics so this question has me stumped. The way the material was presented, it ...
user avatar
3 votes
0 answers
723 views

Convex relaxation of rank constraint

I would like to approximate a symmetric matrix $X\in \mathbb{R}^{n\times n}$ by a matrix of rank no more than $r$, i.e., a matrix $Z=EE'$ where $E\in\mathbb{R}^{n\times r}$, for some given $r\leq n$. ...
user avatar
1 vote
1 answer
865 views

LP relaxation solves the integer program but the constraint matrix is not totally unimodular

I am solving an integer program (IP) whose constraint matrix is not totally unimodular (TU). The linear programming (LP) relaxation and the original IP always have the same optimal solution, or the LP ...
user avatar
  • 154
0 votes
0 answers
211 views

lagrangian relaxation - relaxing multiple constraints - linear programming

I am having problem understanding how to relax multiple constrains in linear programming. I know how to relax just one constrain of LP, but I have problem understanding how to constrain for example, ...
user avatar
1 vote
1 answer
113 views

SDP relaxation for the sparset cut

On page 338 of Williamson & Shmoys's The Design of Approximation Algorithms, the presentation of the ARV algorithm for the sparsest cut over a graph $G(V,E)$ has the following formulation ...
user avatar
2 votes
1 answer
52 views

(When) can I assume boundary values in an LP relaxation are fixed in the MIP?

Suppose I have an integer programming problem, specifically one with a set of binary decision variables $x_i \in \{0, 1\}$. So I'm trying to optimize a function $c=w \cdot x$ where $w$ is a vector of ...
user avatar
  • 14.7k
4 votes
3 answers
1k views

Minimize trace($MX$) with $M$ rank-deficient and $X$ positive semidefinite

I have an optimization problem of the following form: $$\min_{X\succeq0} \mathrm{trace\;} MX$$ under the linear constraint $\mbox{diag} (X) = \mathrm{Id}$ and the non-convex constraint $\mbox{rank} (...
user avatar
4 votes
1 answer
2k views

In an optimization problem, why is a rank-1 constraint non-convex?

I was studying a problem in a paper in which the author tries to use the semidefinite relaxation (SDR) technique in order to solve it. After changing the original problem using the SDR technique, a ...
user avatar
  • 453
4 votes
1 answer
516 views

Equivalence of a binary linear program and its relaxation

We know that given a binary (0-1) linear program, we can find lower/upper bounds using its relaxation. But, there are instances (such as shortest path problem with non-negative cycles, bipartite ...
user avatar
  • 1,025
1 vote
0 answers
64 views

How to solve this trace minimization problem (non-convex)?

Would you please help in solving the following: $\mathop {\min }\limits_{\mathbf{G}_{\textrm{p}}}\hspace{5pt} \hspace{4pt} \textrm{trace} \Big(\mathbf {G}_{\textrm{tx}}\mathbf {G}_{\textrm{p}} \...
user avatar
  • 11
0 votes
1 answer
519 views

for Which values $w$ the SOR method is convergent?

hope you can help me, I've got stuck on this. Consider the following matrix. $$A =\begin{bmatrix} 1 & p\\ -p & 1 \end{bmatrix}$$ for which $w$ values the SOR method is convergent? thanks!, ...
user avatar
  • 151
1 vote
1 answer
1k views

Linear Relaxation vs Lagrangian Relaxation

Let's say we are using Integer Programming in order to minimize an objective function. We are interested in computing a lower bound for the problem. My question is: when should we use a Linear ...
user avatar
  • 35