Questions tagged [duality]

For questions on duals of (primal) mathematical programs that optimize the complementary bound. When minimizing, for example, primal solutions are upper bounds, and dual solutions lower bounds on the optimal value.

Filter by
Sorted by
Tagged with
5
votes
2answers
425 views

What is the relation between dual variables and reduced costs?

My background: Pure math current Undergrad, learned the theory of Operations Research, but pretty basic. All we covered have been dealing with problems that have only 1 constraint matrix. I have dealt ...
3
votes
1answer
61 views

Convex-Constrained Nonconvex-Nonconcave Minimax Problem

In the mathematical optimization theory, I have taken a glance at many papers which deal with the unconstrained convex-concave or nonconvex-concave minimax optimization, i.e., $$ \min_{x\in X}\ \max_{...
6
votes
1answer
250 views

Dual of a model to obtain reduced costs

I have the following model which I am going to solve with column generation. \begin{align} \max & \sum_{b \in B} \sum_{s \in S} \sum_{r \in \Omega_s}\beta_{bs}p_r y_{br}\label{objective-set1}\\ ...
3
votes
1answer
95 views

dual variable with constraints dealing different time limit

I am working on a unit commitment problem where I need to turn the constraints to dual. But the constraints do not deal with the same time period which makes dual process confusing. for a simple ...
7
votes
1answer
110 views

Is there any academic reference which suggests/uses dual values as initialization of Lagrangian multipliers?

The Lagrangian relaxation approach is used to generate lower (upper) bounds for minimization (maximization) problems by moving some constraints to the objective function and multiplying them by "...
3
votes
1answer
102 views

Method of Multipliers: Why is the next iterate always dual feasible?

I am reading this expository paper on ADMM by Boyd, et. al. Consider the problem \begin{align*} &\min f(x)\\ & \ \text{s.t.} \ \ \ Ax = b \end{align*} with Lagrangian $L(x, \lambda) = f(x) + \...
2
votes
1answer
101 views

Recovering Primal Solution from Dual solution

Consider the problem \begin{align*} &\min f(x)\\ & \ \text{s.t.} \ \ \ Ax = b \end{align*} In this expository paper, Boyd claims (top of page $8$) that if: $\lambda^*$ is a dual optimal ...
2
votes
1answer
107 views

Finding the dual problem of a minimum problem

How to convert the following primal problem into its dual problem: \begin{align} \min_{x,z}&\quad a^\top x + b^\top z\\\text{s.t.}&\quad Ax-d \le Cz \\&\quad x\ge 0, z \le 0. \end{align} I ...
3
votes
1answer
102 views

Following code doesn't work in matlab with CVX

Given the following problem \begin{align}\min&\quad x_1+2x_2+3x_3+4x_4+\sum_{i=1}^4x_i\ln(x_i)\\\text{s.t.}&\quad e^\top x=1\\&\quad x\geq0\end{align} I was asked to solved the dual ...
1
vote
0answers
68 views

How to start the Dantzig-Wolfe decomposition?

I have the following problem: \begin{align}\min&\quad3x_1+5x_2+3x_3-2x_4+3x_5\\\text{s.t.}&\quad x_1+x_2+x_3+x_4\geq3\\&\quad3x_1+x_2+5x_3+x_4-2x_5\geq6\\&\quad x_1+2x_3-x_4\geq2\\&...
7
votes
0answers
101 views

Estimate lagrangian multiplier based on instance characteristics

Assume we have a simple resource allocation problem, where all players have the same cost, but a different utility $a_s$. The resources assigned to a certain player must be between $L$ and $M$. ...
4
votes
1answer
237 views

Column generation for a linear optimization problem

I have an LP that has exponentially many constraints, and just linearly many variables. The dual of the problem, therefore, has exponentially many variables, while just linearly many constraints. My ...
1
vote
1answer
51 views

Find a dual problem with one dual decision variable to the problem of finding the orthogonal projection of a given vector

Given the set $T_{\alpha}=\{x\in\mathbb{R}^n:\sum x_i=1,0\leq x_i\leq \alpha\}$ For which $\alpha$ the set is non-empty? Find a dual problem with one dual decision variable to the problem of finding ...
3
votes
1answer
98 views

Find the dual problem of $\min_x\{||x-a_1||+||x-a_2||+||x-a_3||,a_i\in\mathbb{R}^n\}$

Find the dual problem of $$\min_x\{||x-a_1||+||x-a_2||+||x-a_3||,a_i\in\mathbb{R}^n\}$$ I've tried the following but got stuck $$\min_x\{||x-a_1||+||x-a_2||+||x-a_3||,a_i\in\mathbb{R}^n\}=\min_{x,z_i}...
2
votes
0answers
55 views

Prove $\sum_{i=1}^{m}\lambda_i^*\leq\frac{f(\hat{x})-f^*}{\underset{i=1,\ldots,m}{\min}(-g_i(\hat{x}))}$

Consider the primal problem \begin{align}f^*=\min&\quad f(x)\\\text{s.t.}&\quad g_i(x)\le0\tag P\end{align} where $f,g_i$ are convex functions. Suppose there exists $\hat{x}$ such that $g_i(\...
0
votes
1answer
544 views

Is optimal solution to dual not unique if optimal solution to the primal is degenerate?

If optimal solution to the primal is degenerate, does it necessarily follow that optimal solution to dual not unique? That is, is uniqueness an unnecessary assumption? Spin-off from here. In my ...
3
votes
1answer
195 views

Derive "true" shadow price for degenerated LPs using commercial solvers (e.g. Gurobi)

In linear programming for an optimal primal degenerate solution the values of the dual variables are in general not identical with the corresponding shadow prices. Several proposals on how to find the ...
11
votes
0answers
191 views

Finding primal feasible solution from optimal dual

I'm reading Boyd's notes on forming the dual problem in order to decompose the primal problem. On page 4, right before the start of the next section, he talks about how given the optimal dual solution,...
6
votes
1answer
97 views

Does strong duality hold when I dualize only a subset of the constraints?

Suppose I know that for some non-convex program: \begin{align}\min_x&\quad f(x)\\\text{s.t.}&\quad g_i(x)\leq 0, i \in C\end{align} strong duality holds for this problem. Now, suppose I form ...
6
votes
2answers
125 views

Local optimum of dual of non-linear program

In general, suppose you have a non-convex optimization problem with constraints and you form the dual problem. If you find a local optimum for the dual problem, will the corresponding primal solution ...
5
votes
1answer
165 views

Physical Interpretation of a dual of an LP

I was recently asked to physically interpret a dual of an LP for an audience who does not know mathematics/OR (without LP, dual, bounds, etc.). Though I attempted it and was very close to what the ...
1
vote
1answer
98 views

Simple nonlinear programming using convexity analysis and KKT

I want to solve the following two-variate nonlinear programming using KKT conditions: $$ \begin{align} \begin{split} \max \quad & 15 \sqrt{x_{1}} + 16 \sqrt{x_{2}} \\ \text{s.t.} \quad &...
2
votes
1answer
93 views

On dual-formulation of a given primal for a set-covering problem

I need to solve an LP-relaxation of an airline crew pairing optimization problem (CPOP). The problem formulation is a modified SCP and is as follows: Primal of the CPOP: \begin{align}\min&\quad\...
6
votes
1answer
118 views

When using column generation, can I delete a node with negative reduced cost from my subproblem?

I am solving a minimization problem with a column generation procedure. The master problem is of the form $$ \min \sum_{i\in \Omega}c_i \lambda_i $$ subject to $$ \sum_{i\in \Omega \mid v \in i } \...
7
votes
2answers
216 views

Is the iteration-limited Simplex dual solution of a MIP node useful?

Idea Sometimes I encounter problems where Simplex spends many iterations for final convergence to the optimal objective value. Let's suppose, this happens when solving branch and bound-tree nodes as ...
3
votes
0answers
42 views

Derivations for two formulae for obtaining optimal dual variable values from the optimal primal tableau

We're being taught Industrial Engineering and Operations Research for the first time this semester. Referring to the book by Hamdy A. Taha, I noticed the mention of two formulae for swiftly obtaining ...
7
votes
1answer
105 views

Ridge Regression lagrange duality

In every machine learning book we see that it is roughly mentioned that the ridge regression: $$p_1^* = \min\limits_{\beta} \ \left( \mathrm{RSS} + \lambda\sum_{j=1}^p \beta_j^2 \right)$$ is ...
10
votes
2answers
496 views

Can we have all reduced costs (strictly) positive?

I had a number of students claim on their homework that "All $z_j-c_j$ values are positive, therefore the solution is optimal." Of course, I noted that they should say "non-negative" instead of "...
15
votes
2answers
974 views

Dual bounds of integer programming problems

I often read in papers when branch-and-X algorithms are used to solve mixed integer programming problems, that the lower bound (in the minimization case) obtained from solving a linear programming ...
12
votes
0answers
176 views

Integrality gap in bilevel binary linear programming problem

I have a bilevel max-min optimization problem over binary variables, with constraints expressed using linear inequalities. The inner (minimization) problem is $$ \begin{alignat}2 \min\limits_x&\...
9
votes
1answer
382 views

Is there any relationship between KKT and duality?

I noticed the similarities between KKT and complementary slackness, but I do not fully understand it.
9
votes
1answer
151 views

Finding Dual Objective

I have the following simplified optimization problem: \begin{align}\max &\quad ax+by\\\text{s.t.}&\quad0 \le x \le \overline X\\&\quad0 \le y \le\overline Y\\&\quad z = E-x+\beta\cdot ...
15
votes
1answer
650 views

Duality in mixed integer linear programs

I know that the standard duality theory for the linear programming problem does not hold for mixed integer linear programming problems. I was wondering why an integer program does not have a dual ...
13
votes
1answer
170 views

Robust counterpart: why is dual reformulation not working?

I am trying to solve robust optimisation problems, but I am getting nonsensical solutions most of the time… Here is a very simplified example: \begin{alignat}{2}\max&\quad x+z&\\\text{s.t.}&...
17
votes
2answers
1k views

Tool to get dual problem from any linear optimization problem (.lp)

Is there a tool that reads any linear optimization problem (for example an .lp or .mps file), converts it to the dual problem and prints the dual problem?
11
votes
1answer
150 views

How to relate dual values of valid inequality to the dual values of the original problem?

I have a given formulation that looks like this (just for the constraints): $$\sum_i \beta_{i,j} \geq \alpha_j,\qquad\forall j$$ $$\alpha_j \geq \sum_i f_{i,j},\qquad\forall j$$ $$\alpha_j \geq 0, ...
12
votes
1answer
216 views

Recovering primal optimal solutions from dual sub gradient ascent using ergodic primal sequences

My question concerns recovering a primal optimal solution while performing dual sub gradient ascent. Denoting by $y_i$ the dual multiplier in the $i^{\text{th}}$ iteration, let \begin{equation} x_i = ...
13
votes
2answers
1k views

Correct way to get a dual extreme ray for an infeasible LP in CPLEX / C++

We are coding a Benders decomposition using CPLEX/Concert (C++) and we are having some troubles to generate a feasibility cut because we are not sure how to get an extreme ray of the dual for a primal ...
16
votes
3answers
281 views

How to take the dual of a conic optimization problem?

Given a conic problem $$\min \{c^\top x \mid Ax \succeq_\mathit{C} b\}$$ for an arbitrary cone $C$, how can I construct the dual to the problem? Moreover, in Linear Programming one constructs the ...
19
votes
4answers
934 views

How can I remember the rules for taking the dual of a linear program (LP)?

When taking the dual of a linear program (LP), is there a trick/easy way to remember the rules for the directions of the inequalities, signs of the variables, etc.? A trick with a catchy name, perhaps?...