Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

4
votes
1answer
26 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 ...
1
vote
1answer
38 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 \...
0
votes
0answers
12 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 ...
2
votes
0answers
76 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$$ ...
0
votes
1answer
53 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 ...
1
vote
0answers
42 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 ...
0
votes
0answers
32 views

What can be the convex relaxation of a quadratic matrix inequality?

I am trying to relax the Quadratic Matrix Inequality given as: $$W \leq X^TX+Y^TY \\ W\geq 0 $$ Here, $X,Y,W \in \mathbb{R}^{n\times n}$ matrices. These two are to be solved along with one linear ...
1
vote
0answers
25 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 \...
5
votes
1answer
168 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\}^{...
1
vote
0answers
84 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 ...
1
vote
0answers
97 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 ...
3
votes
0answers
274 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\\ &...
2
votes
1answer
165 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 \{...
3
votes
1answer
324 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'?
1
vote
0answers
50 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. ...
0
votes
1answer
83 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?...
2
votes
1answer
113 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 ...
2
votes
0answers
407 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$. ...
1
vote
1answer
396 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 ...
0
votes
0answers
132 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, ...
1
vote
1answer
73 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 ...
1
vote
1answer
33 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 ...
2
votes
3answers
503 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} (...
3
votes
1answer
955 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 ...
4
votes
1answer
362 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 ...
1
vote
0answers
47 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}} \...
0
votes
1answer
384 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!, ...
1
vote
1answer
865 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 ...
0
votes
0answers
66 views

Proving tightness of a semidefinite relaxation of a nonconvex quadratic program

The Lagrangian of my semidefinite relaxation of a nonconvex QCQP (quadratically-constrained quadratic program) is \begin{align} L&=\sum_{n=1}^{N}\operatorname{tr}\left(\textbf{Q}_n\textbf{X}\right)...
2
votes
1answer
541 views

Boolean Quadratic Programming

I am new to optimization and I am trying to understand concepts of semi-definite relaxation (SDR) through examples. It seems my understanding of this topic is not fully clear as I will show in details ...
4
votes
0answers
849 views

Showing the integrality property for an Integer Linear Program

I am trying to figure out why solving a relaxed Integer Linear Program (ILP) always give an integral solution. The ILP can be summarized as: $$\min \sum_{t\in T} \sum_{s \in S} c_s k_s^t $$ subject to:...
5
votes
1answer
2k views

What is the definition of “convex relaxation” in clustering?

I have following text from a paper i am trying to understand: I don't understand what does below sentence refers to as being convex/non-convex The problem is that even though the objectives (1)...
5
votes
1answer
504 views

Semidefinite relaxation for Boolean least squares

I am working on the Boolean least squares problem, which comes up a lot in circuit design. In its raw form, it looks like this $$\begin{array}{ll} \text{minimize} & \operatorname{tr}(A^TAX) - 2b^...
5
votes
1answer
951 views

SDP relaxation of non-convex QCQP and duality gap

Short version Is there a duality gap between a QCQP problem and the SDP problem obtained through Lagrangian relaxation? A paper I'm studying is using this fact, but I cannot achieve the authors' ...
4
votes
2answers
4k views

LP relaxation for integer linear programming (ILP)

I am familiar with LP relaxation for ILP (or IP). Assume we concern with integer minimization problem, which we formalize using ILP; we then relax the ILP into LP and we say that the LP provides a ...