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
0 votes
0 answers
30 views

Dual prices remain stable but negative in column generation

I arrive at an objective function value that I know to be optimal. However, dual prices remain negative (which leads me to believe another pattern can be added, but when I do, the dual prices don't ...
user11638's user avatar
5 votes
2 answers
293 views

Simple OLS problem can only be solved in SCS. Is the dual infeasible?

Essentially, I am trying to solve a simple orthogonal least-squares (OLS) problem with some constraints — the coefficients must sum to $1$, no coefficient can be less than $0$, and no coefficient can ...
Pipob Puthipiroj's user avatar
4 votes
2 answers
164 views

What happens to the dual and primal feasibility when a constraint is removed after finding an optimal solution?

Assuming I had solved the a problem to optimality, I want to remove a constraint. What happens to primal feasibility? What happens to dual feasibility? How to solve this new problem efficiently? My ...
Morpheus's user avatar
  • 241
4 votes
3 answers
259 views

Existence of extreme points in primal and dual LP

If the nonempty feasible set of a primal LP has extreme points does its dual also have extreme points? I know that a standard form LP (nonempty) always has extreme points. But I am not sure if we can ...
T_k's user avatar
  • 77
3 votes
2 answers
110 views

Partial Lagrangian in the Max-Flow problem

In the question: "Partial" Lagrangian Dual in LP It is argued that considering a partial Lagrangian $L_{partial}$, where we Dualize only some of the constraints, results in a tighter ...
Cris's user avatar
  • 143
5 votes
1 answer
197 views

Dantzig-Wolfe vs Benders Decomposition on the dual problem - Computational differences

My question is a follow-up to this one: Relationship between Benders’ decomposition and Dantzig-Wolfe decomposition. Here what is being discussed is the relationship between the two methods, and it is ...
J. Dionisio's user avatar
1 vote
2 answers
57 views

Number of solutions to geometric program

Is it possible to determine if a Geometric Program (GP) has one, none, or infinite (primal) solutions by its structure (e.g., in terms of the number of variables, constraints, or product terms ...
Apprentice's user avatar
3 votes
0 answers
122 views

How to find robust counterpart of sum of logit functions?

Suppose function $\mu_i(y):\mathbb{R} \rightarrow \mathbb{R}$ is a logit function, $\mu_i(y)=1/(1+\exp(-y))$. Also, we assume that $\mathbf{x}_i\in \mathbb{R}^d$ and $\theta \in \mathbb{R}^d$. I am ...
Amin's user avatar
  • 2,140
2 votes
1 answer
90 views

How do you recover dual variables for a minimum weight bipartite perfect matching problem?

I feel like I must be missing something obvious but this is confusing me. Let's say I have an optimal solution $x^*$ to a minimum-weight perfect bipartite matching problem on $2n$ nodes, $$\min\sum_i\...
Kathryn Twomey's user avatar
4 votes
2 answers
528 views

How do you get the primal solution of an LP from the dual solution?

I am new to Optimization so I think the following question may be very easy, but I'm not sure how to solve it. The dual of an LP is an LP. If we solve the dual LP, we can get the optimal value for the ...
Helix's user avatar
  • 141
3 votes
2 answers
256 views

Related to Lagrangian dual

In my research class our professor discuss a paper wherein the solution is obtained via a Lagrangian duality. The original problem is given below: minimize $t$ subject to $\sum_{j \in \mathcal{M_i}}\...
chaaru's user avatar
  • 33
1 vote
0 answers
45 views

Proof related to dual prices of constraints

I have a master problem as follows: \begin{equation} \min \sum_{\vec{s} \in S} \sum_{\vec{z} \in \Xi_{\vec{s}}} c(\vec{s}, \vec{z}) \times \chi(\vec{s}, \vec{z}) \label{eqADP4} \\ \end{equation} ...
mdslt's user avatar
  • 529
4 votes
2 answers
186 views

Phase I of the simplex method and Farkas certificates

Phase I of the simplex method solves an auxiliary optimization problem to determine an initial basic feasible solution, or concludes that no such exists. Is there a way to use the solution of this ...
fmg's user avatar
  • 213
3 votes
1 answer
147 views

Convex optimization with linear constraints. Can I solve it analytically?

I have a constrained convex optimization problem with linear equality and inequality constraints. \begin{align} \label{eq:costf} \text{minimize}\ \ &f(x_1,\dots,x_m) = \sum_{i=1}^m \frac{1}{...
newman_ash's user avatar
1 vote
1 answer
136 views

Dual solution when solving a primal degenerate LP with the interior point algorithm

Say, we're working with an LP that is primal degenerate (optimal solution is at a vertex but with multiple bases) and not dual degenerate (optimal solution is not at a face). If we were to solve it ...
Samarth's user avatar
  • 173
1 vote
0 answers
61 views

Dual of a quadratic constraint

This is my model. \begin{align} \min_x&\quad\sum_{e\in E} X_e p_e \\ \text{s.t.}&\quad\sum_{e \in E: T(e)=i} X_e - \sum_{e \in E: H(e)=i} X_e = \begin{cases}1, \;\text{if}\;i=s\\-1,\;\text{if}...
orpanter's user avatar
  • 423
1 vote
1 answer
129 views

Help with dual of a problem

Could anyone confirm me if I write the correct dual for my problem? The different sets confuse me a lot. $s$ is the source node and $t$ the sink node. I'm uncertain if the last dual constraint in ...
orpanter's user avatar
  • 423
6 votes
1 answer
119 views

Light weight proof of strong duality in linear programming

For teaching purposes, I believe it can be good to use very light-weight proofs of deep results, as it often answers the question "why is it true" better than other types of proofs. By "...
Sune's user avatar
  • 6,072
5 votes
0 answers
69 views

Linear programming approach to dynamic programming - an initial pair of state-decisions

I aim to solve the following Bellman equation: \begin{equation} v(\vec{s}) = \min_{\vec{x} \in \Xi_{\vec{s}}} \big\{c(\vec{s}, \vec{x}) + \lambda \times \sum_{\vec{s}^{'}\in S} p(\vec{s}^{'} | \...
mdslt's user avatar
  • 529
2 votes
1 answer
158 views

What is the dual of this LP?

Here is my simple LP problem for a constant symmetric positive matrix $d$ and continuous decision variables $x$: \begin{align}\max&\quad\sum{x_i}\\\text{s.t.}&\quad x_i + x_j \leq d_{ij}\\&...
Brannon's user avatar
  • 762
3 votes
1 answer
155 views

min max inside a linear program

Although this sounds like a standard minimax problem, I'm not sure how to deal with feasibility issues. Consider a maximin linear program \begin{align}\max_x\min_y&\quad c^\top y\\\text{s.t.}&\...
ericf's user avatar
  • 159
6 votes
0 answers
218 views

Airline revenue management re-solving problem

I am considering a bid prices (shadow price of the capacity constraint) problem (from Chen, L. and Homem-de Mello, T. (2009)., page 14) where the acceptable classes for booking requests for ...
SimonCello94's user avatar
3 votes
0 answers
60 views

Dual of the alternative solutions

Suppose we have two alternative solutions for a linear program. Are their corresponding dual solutions the same? (in terms of the values for each dual variable)
Junior MIP's user avatar
9 votes
2 answers
836 views

"Partial" Lagrangian Dual in LP

Consider the optimization problem \begin{align}\label{opt-lp}\tag{Primal} \begin{array}{cl} \underset{x \in \mathbb{R}^n}{\text{minimize}} & c^\top x \\ \text{subject to} & Ax = a \\ & Bx =...
independentvariable's user avatar
4 votes
2 answers
1k 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 ...
AyamGorengPedes's user avatar
4 votes
1 answer
109 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_{...
Keith's user avatar
  • 155
6 votes
1 answer
362 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}\\ ...
pozyavas's user avatar
3 votes
1 answer
106 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 ...
Lee Adolin's user avatar
7 votes
1 answer
174 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 "...
Mehdi Iranpoor's user avatar
3 votes
1 answer
129 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) + \...
user56202's user avatar
  • 193
2 votes
1 answer
410 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 ...
user56202's user avatar
  • 193
2 votes
1 answer
236 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 ...
bm1125's user avatar
  • 131
4 votes
1 answer
203 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 ...
convxy's user avatar
  • 405
1 vote
0 answers
98 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\\&...
diabolik's user avatar
7 votes
0 answers
117 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$. ...
Pete S's user avatar
  • 123
4 votes
1 answer
464 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 ...
independentvariable's user avatar
1 vote
1 answer
95 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 ...
convxy's user avatar
  • 405
3 votes
1 answer
112 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}...
convxy's user avatar
  • 405
2 votes
0 answers
62 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(\...
convxy's user avatar
  • 405
0 votes
1 answer
2k 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 ...
BCLC's user avatar
  • 59
4 votes
1 answer
350 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 ...
Mitch's user avatar
  • 93
11 votes
1 answer
297 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,...
George Chang's user avatar
6 votes
1 answer
117 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 ...
George Chang's user avatar
5 votes
2 answers
174 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 ...
George Chang's user avatar
5 votes
1 answer
614 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 ...
Divyam Aggarwal's user avatar
1 vote
1 answer
151 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 &...
Edward's user avatar
  • 381
2 votes
1 answer
130 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\...
Divyam Aggarwal's user avatar
6 votes
1 answer
185 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 } \...
Kuifje's user avatar
  • 12.3k
7 votes
2 answers
261 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 ...
Simon's user avatar
  • 1,122
3 votes
0 answers
45 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 ...
Sakazuki Akainu's user avatar