Skip to main content

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
26 views

How does McCormick envelope work for inequality constraints?

I have a question regarding the McCormick envelope in mathematical optimization. The McCormick envelope allows to create a convex relaxation for a bilinear term. Given the bilinear constraint $w = x \...
Michael's user avatar
  • 53
0 votes
0 answers
15 views

Tightening a specific constraint [closed]

I would like to know if there exists any way to reformulate the following constraint in which one can relax the binary variable $z_{j,m}$, and the solution still being an integer for that. The ...
A.Omidi's user avatar
  • 137
1 vote
0 answers
20 views

Convex Relaxation of Bilinear Constraints

I am dealing with a semi-definite program with the extra bilinear inequality constraints $$ \epsilon_{k+1} \leq \epsilon_k \sigma_{\max}(\tilde{A}_k) + \eta, \ \forall k, $$ where $\epsilon_{k},\eta &...
Josh Pilipovsky's user avatar
1 vote
0 answers
15 views

optimal ratio of maximum coverage problem with LP relaxation

Consider Maximum-Coverage problem, which means there are set $A$ and $n$ subsets of $A$, we can choose $k$ subsets to cover some elements, and Maximum-Coverage is the assignment that cover most ...
Lagranngekmno4's user avatar
1 vote
1 answer
45 views

Restore shuffled function output

There is a function $\mathbf{y} = f(\mathbf{x})$ that takes a vector $\mathbf{x}$ as input and outputs another vector $\mathbf{y}$. The function $f(\mathbf{x})$ is continuous and differentiable. I can ...
Zhengyi Li's user avatar
1 vote
1 answer
72 views

Why this ILP and LP are equivalent?

Let's consider a competition with $n$ questions. Each question has a price $p_i$ and a score $v_i$. To advance to the next round of the competition, we need to accumulate a minimum score of $D$. We ...
occasional's user avatar
6 votes
1 answer
151 views

Relaxation of $\min_{H} \text{tr}(H^T P H)$

Let $P \in \mathbb{R}^{N \times N}$ be a given symmetric matrix. Specially, $P$ has all zero entries on its diagonal, and all its off-diagonal entries are positive. And I want to minimize $$\begin{...
William Zheng's user avatar
2 votes
0 answers
39 views

Integer points in a closed polyhedron nearest an extreme point

This is a revision of my previous question. The question is motivated by the fact that, for a Linear Program (LP) obtained by relaxing a given Integer Linear Program (ILP), an optimal solution may be ...
avs's user avatar
  • 6,304
1 vote
0 answers
34 views

Integer lattice points in a closed convex polyhedron and close to the polyhedron's extreme points

In the 2-D Euclidean space, the angle formed by the intersection of two closed half-spaces, $H_{1}, H_{2}$, with outer normals $\hat{n}_{1}, \hat{n}_{2}$ can be measured as obtuse or acute. It is ...
avs's user avatar
  • 6,304
2 votes
1 answer
45 views

Is minimizing the degree of an approximating polynomial convex?

Let $f(x) : \{-1, 1\}^n \mapsto \mathbb{R}$ be a function such that $|f(x)| \le 1$. I would like to find the minimum-degree (multivariate) polynomial $P(x)$ such that: $$|P(x) - f(x)| \le \epsilon$$ ...
NYG's user avatar
  • 247
1 vote
0 answers
22 views

Convert a MINLP problem with semi-continuous variables to a problem with continuous variables?

Is there a way do (approximately) convert a nonlinear optimization problem with semi-continuous design variables to a problem with continuous variables? I want to avoid the use of MINLP solvers and ...
jstollberg's user avatar
1 vote
0 answers
66 views

How to numerically optimize a function with 'discontinuous' box constraints?

First of all: I am an engineer and no mathematician, therefore please excuse my 'lazy' form or prensenting the problem. I want to solve a nonlinear and constrained optimization problem: \begin{align} ...
jstollberg's user avatar
0 votes
1 answer
54 views

SDP relaxation of mixed-integer nonlinear program

I am having trouble understanding the semidefinite programming (SDP) relaxation of a mixed-integer nonlinear program (MINLP) from section 3 of this paper. The optimization problem in MINLP form is \...
Physics Penguin's user avatar
0 votes
1 answer
58 views

How to apply integer cut to a simple MILP?

I'm self-studying on cutting plane methods, and I'm reviewing the following problem from Bertsimas' book (see below). I know what cutting plane methods do, and how they eliminate infeasible solutions ...
somewhere's user avatar
0 votes
0 answers
22 views

Is there a Schur-like theorem for proving $B^TB\succeq A$?

This is in the context of semidefinite programs, and $A\in\mathbb R^{n\times n},~B\in\mathbb R^{k\times n}$ are variables. If want to show that $A-B^TB\succeq 0$ and I know $A\succeq 0$, then I can ...
Blake's user avatar
  • 66
0 votes
1 answer
66 views

Positive semidefiniteness in Boolean least-squares problem

A Boolean least-squares can be formulated as follows \begin{array}{ll} \text{minimize} & \operatorname{tr}(A^TAX) - 2b^TAx + b^Tb\\ \text{subject to} & X = xx^T\\ & X_{ii} = 1\end{array} ...
tyrela's user avatar
  • 353
0 votes
0 answers
44 views

Dual of the SDP relaxation in Yinyu Ye's paper

I was stuck in computing the dual problem in a paper by Yinyu Ye which raises an SDP relaxation such that $$ \min_{Z \in \mathcal{K}} \left\{ h(Z) := \sqrt{\sum_{(i, j) \in \mathcal{E}} \gamma_{ij}^2 (...
ENTONG HE's user avatar
1 vote
1 answer
336 views

How to approximate a rank-1 solution after exploiting semidefinite relaxation method?

For my problem, I try to optimize the vector $\mathbf{w}\in\mathbb{C}^{N}$ at first. After exploiting semidefinite relaxation (SDR) method, the variable becomes $\mathbf{W} = \mathbf{ww}^H$ and the ...
tyrela's user avatar
  • 353
2 votes
1 answer
190 views

Grothendieck's inequality guarantee of relaxation for Semidefinite problem

I am struggling to understand a proof of theorem 3.5.6 in Roman Vershynin's High-Dimensional Probability Theorem: $$\text{INT}(A) = \max_{x_i = \pm 1 \text{ for } i = 1,\ldots,n} \sum_{i,j=1}^{n} A_{...
Lose' CKi's user avatar
1 vote
1 answer
148 views

The optimal solution of a relaxation is optimal for the original problem

The question concerns the topic of relaxations in optimization problems. Moreover, proving the following, straightforward proposition. Let $z^P$ be the optimal solution for the problem $P$, $z^R$ be ...
DrDrunkenstein's user avatar
0 votes
1 answer
429 views

Prove: if a solution exists for LP and a feasible integer solution then there exists a solution to IP

If a solution exists for an optimization problem in LP and if there is a feasible integer solution then there exists a solution to the corresponding integer programming problem. This is the basic ...
reyna's user avatar
  • 2,224
2 votes
2 answers
174 views

Optimization problem involving the sum of reciprocals of variables

I'm trying to solve an optimization problem involving reciprocals. The problem has the following simple form. Can this form be transformed into a problem form that commercial optimization solvers can ...
SomeOne1's user avatar
1 vote
0 answers
200 views

Inequality constraints of convex relaxation with McCormick envelope

I have a nonconvex optimization problem for which I am calculating a lower bound using the McCormick envelope. Each bilinear term is replaced with an auxiliary variable which has the following ...
bipur24's user avatar
  • 11
1 vote
0 answers
171 views

Totally unimodular towards linear programming relaxation

I'm currently studying about totally unimodular. I was reading this link: https://ostad.nit.ac.ir/upload/Integer_Programming_1.pdf, from page 38-41 and I came across the statement: 'It is clear that ...
Michelle Gunawan's user avatar
1 vote
0 answers
44 views

The relaxation method in the Linear and Integer Programming, some goniometric stuff

I have a problem in a very nice book by Alexander Schrijver Theory of Linear and Integer Programming in the Relaxation Method. Can some give me a hint how here on the page $160$ it was obtained the ...
user122424's user avatar
  • 3,936
0 votes
1 answer
236 views

What is the opposite of relaxation

If I understand correctly, a given problem: \begin{equation} \min_{\mathbf{x}} \mathbf{c}^{\top}\mathbf{x}, \quad \mathbf{x} \in F \qquad \qquad (1) \end{equation} is said to be a relaxation of $$ \...
metsburg's user avatar
  • 135
0 votes
0 answers
25 views

Understanding the term upper bound?

I am trying to understand the meaning or intuition of upper bound in the following sentence: The relaxed problem is upper bound of the original problem. Any help in this regard will be highly ...
chaaru's user avatar
  • 71
0 votes
0 answers
67 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 ...
thePhantom's user avatar
1 vote
1 answer
103 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 &...
Lars Janssen's user avatar
1 vote
0 answers
81 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. ...
user85361's user avatar
  • 865
0 votes
1 answer
38 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 ...
carlo__'s user avatar
  • 85
0 votes
1 answer
46 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 ...
fr_andres's user avatar
  • 139
0 votes
2 answers
242 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 ...
Robert's user avatar
  • 817
1 vote
1 answer
180 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 ...
Cindy Philip's 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....
capybaralet's user avatar
  • 1,275
1 vote
0 answers
28 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 ...
Josh Pilipovsky's user avatar
1 vote
1 answer
407 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 ...
MattF's user avatar
  • 113
1 vote
1 answer
136 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}...
PeaBrane's user avatar
  • 333
2 votes
0 answers
115 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 ...
Star's user avatar
  • 206
1 vote
1 answer
683 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.}...
Ron Weals's user avatar
0 votes
0 answers
104 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 ...
Simon's user avatar
  • 11
3 votes
1 answer
374 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, ...
Al Waurora's user avatar
2 votes
1 answer
108 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 ...
yes's user avatar
  • 878
2 votes
1 answer
176 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 +...
Sylvain Lhermite's user avatar
2 votes
2 answers
111 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*} \...
HolyMonk's user avatar
  • 1,135
5 votes
1 answer
351 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.
Shuai Lu's user avatar
1 vote
0 answers
30 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 \...
Shew's user avatar
  • 1,552
2 votes
1 answer
985 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 ...
beenjaminnn's user avatar
4 votes
1 answer
96 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 ...
user2512443's user avatar
1 vote
1 answer
210 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 \...
linkho's user avatar
  • 397