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.
64
questions
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 ...
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 ...
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 ...
- 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 ...
- 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 ...
- 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 ...
- 516
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 ...
- 215
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 ...
- 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\...
- 153
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 ...
- 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}}\...
- 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}
...
- 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 ...
- 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}{...
- 39
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 ...
- 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}...
- 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 ...
- 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 "...
- 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}^{'} | \...
- 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}\\&...
- 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.}&\...
- 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 ...
- 165
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)
- 389
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 =...
- 3,808
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 ...
- 401
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_{...
- 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}\\
...
- 61
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 ...
- 55
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 "...
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) + \...
- 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 ...
- 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 ...
- 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 ...
- 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\\&...
- 97
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$. ...
- 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 ...
- 3,808
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
...
- 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}...
- 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(\...
- 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 ...
- 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 ...
- 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,...
- 329
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 ...
- 329
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 ...
- 329
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 ...
- 668
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 &...
- 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\...
- 668
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 } \...
- 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 ...
- 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 ...
- 131