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
2 votes
1 answer
76 views

Reducing optimality to feasibility in non-linear programs

It is well-known that, given a linear program: minimize $c^T x$ such that $A x\leq b$, it is possible to reduce the program to deciding feasibility of the following set of constraints: $Ax \leq b, A^T ...
Erel Segal-Halevi's user avatar
1 vote
0 answers
44 views

Distributionally Robust Stochastic Programming - Help with derivation

I've been working through this book on robust optimization of electric energy systems, and in particular chapter 4 on distributionally robust optimization. In following the derivation of section 4.2.1....
asfiwefewrno's user avatar
1 vote
1 answer
65 views

Question about Pricing Problem in Column Generation

In column generation, we need to solve the following pricing problem : $$\min c_j-\bf{c}^T_B\bf{B}^{-1}\bf{N}_j$$ In the book, I saw authors say that according to duality theory, $\bf{y}^T = \bf{c}^...
Lin Sen's user avatar
  • 25
1 vote
1 answer
136 views

Primal-Dual Simplex Algorithm

Are there any recommended textbooks or notes to learn the details about the primal-dual simplex algorithm?
Lin Sen's user avatar
  • 25
1 vote
1 answer
53 views

how do I find the dual when a variable has an upper bound?

What is the dual of this primal LP? $$ max~c^Tx $$ $$ s.t.~Ax=0 $$ $$ 0 \leq x \leq d,~d \in \mathbb{R}_+^n $$
Brannon's user avatar
  • 892
2 votes
0 answers
62 views

Approximating an LP with an exponential number of variables and an almost-separation-oracle to its dual

Problem settings: we have $n$ agents and a set $\mathcal{S}$ of possible world-states, where the size of $\mathcal{S}$ is exponential with respect to $n$. Each agent $j$ has a utility function $u_j\...
eden hartman's user avatar
1 vote
2 answers
111 views

Persisting Subproblem Infeasibility Benders Decomposition

I'm currently working on an optimization problem where I'm using Benders decomposition to solve a complex problem involving the installation of charging stations. The master problem determines the ...
bcoulier's user avatar
2 votes
1 answer
59 views

How do you derive the Benders feasibility cuts?

starting off with a MIP that I want to solve using Benders. so in Benders Decomposition, you add feasibility cuts in the following form: $v^j (b - Ax) \geq 0$ with $j \in J$ being the set of extreme ...
Arctic_Skill's user avatar
4 votes
1 answer
68 views

Can dual values smoothing lead to generating duplicate columns?

When using smoothing for dual values stabilization in column generation, the duals used in the subproblem lie on the segment joining the stability center (inside the dual feasible region) and the ...
3 votes
1 answer
89 views

Dual norm definition: adding new constraints

For some $c >0$ and $z \in \mathbb{R}^n$, the optimal value of \begin{align} \begin{array}{cl} \sup_{x \in \mathbb{R}^n}& z^\top x \\\text{s.t.}& \lVert x \rVert \leq c \end{array} \end{...
independentvariable's user avatar
1 vote
1 answer
114 views

Equivalent condition for indicator function

We have the following two conditions: $C1.$ $l(x) \geq 0$ for all $x\in \mathbb{R}^n$, $C2.$ $l(x) \geq 1$ for all $x\in \mathbb{R}^n$ such that $a+b^Tx \leq 0.$ Here $l(x) = \begin{bmatrix} x^T 1 \...
Cherryblossoms's user avatar
0 votes
0 answers
57 views

What the dual constraints mean?

I have a primal problem that is a network-flow: $$ min_x \sum_{a \in A} c_a x_a \\ \text{s.t.} \sum_{a \in A:n = v} X_{a}-\sum_{a \in A:n' = v} X_{a} = \begin{cases} \;\;\;1, \; v=n^{in} \\ -1, \; v=n^...
orpanter's user avatar
  • 507
0 votes
0 answers
38 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
423 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
319 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
  • 253
4 votes
3 answers
308 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
121 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
293 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
61 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
127 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,150
2 votes
1 answer
102 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
3 answers
1k 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
264 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
4 votes
2 answers
235 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
180 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
151 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
65 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
  • 507
1 vote
1 answer
151 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
  • 507
6 votes
1 answer
137 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,352
5 votes
0 answers
75 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
  • 615
2 votes
1 answer
174 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
  • 892
3 votes
1 answer
161 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
223 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
66 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
952 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
2k 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
116 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
396 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
111 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
212 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
136 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
520 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
296 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
228 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
102 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
120 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
594 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
113 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
115 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
63 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