Skip to main content

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
1 vote
1 answer
122 views

Graphical understanding of the primal and dual problem

I have a relatively simple question. Assuming we have a simple numerical example of an LP with two decision variables and two constraints (non-negativity excluded), how can I visualize the graphical ...
Derd Cff's user avatar
0 votes
0 answers
59 views

What's the dual of an LP in its general form?

For an LP written as \begin{align} \min_{x\in \mathbb{R}^n} ~~~ &c^\top x \\ s.t. ~~& l^{s}\leq Ax \leq u^{s},\\ &l^{x}\leq x \leq u^{x} \end{align} how can we get its dual ...
andy's user avatar
  • 77
1 vote
1 answer
88 views

Economic interpretation of shadow/dual variables in LP

I have recently read a text which deals with the dual variables attached to constraints. In an economic sense, one can interpret them as shadow variables indicating market clearing for resource ...
Marlon Brando's user avatar
2 votes
1 answer
69 views

How to implement self-adjusting smoothing in column generation?

I am currently trying to implement the "Smoothing with a Self-Adjusting Parameter" methodology (on the right in Table 1) from Pessoa et. al (2018) in my MILP. Unfortunately, I am not quite ...
marvelfab12's user avatar
0 votes
0 answers
61 views

Dual stabilization doesnt work properly

I am currently trying to speed up my column generation approach to reduce the tailing-off effect. I have modified my master problem as follows. For this I have introduced $\phi_{ts}^+,\phi_{ts}^-,\...
nflgreaternba's user avatar
2 votes
1 answer
126 views

How to improve a column generation algorithm

I have been busy the last few weeks implementing this model with Column Generation in Gurobi and then solving it. The whole thing is now working quite well and I have also run a few calculation ...
nflgreaternba's user avatar
0 votes
1 answer
66 views

Does strong duality hold for this semidefinite program?

$\DeclareMathOperator{\Tr}{Tr}\DeclareMathOperator*{\argmax}{\arg\!\max}$Consider the following semidefinite program (SDP) $$ \begin{aligned} \max_V \quad & \Tr(V) \\ \textrm{s.t.} \quad & \...
mhdadk's user avatar
  • 639
0 votes
0 answers
44 views

Lagrange Duality in Robust Optimization

I am learning Robust Optimization and been stuck on this example. I've brushed up on my knowledge of Lagrange duality and referred to a couple of textbooks on Linear Programming but not able to ...
stuckinlocal's user avatar
1 vote
0 answers
60 views

Quadratic conic program duality

I am working on a problem relating to what is known as the "Good Deal risk measure" for production valuation in incomplete markets. I have created the following primal optimization problem, ...
Mikkel Honningsvåg Sandhaug's user avatar
0 votes
1 answer
53 views

Lagrange multiplier associated to an active inequality constraint

Why is the Lagrange multiplier associated to an active inequality constraint is positive. How can we see this from the KKT conditions?
DSPinfinity's user avatar
0 votes
0 answers
32 views

Unclear points in derivation of Lagrange duality for a quadratic optimization problem

Problem0: $\displaystyle \min_{\mathbf{u} \in \mathbf{R}^L}\frac{1}{2}\mathbf{u}^TQ\mathbf{u}+\mathbf{p}^T\mathbf{u}$ $\,$ subject to $\,$ $\mathbf{a}^T\mathbf{u} \ge c$ Problem1: $\displaystyle \...
DSPinfinity's user avatar
0 votes
1 answer
76 views

Dual of second order cone programming with both equality and inequality constraints

How to derive the dual of a second order cone programming with both equality and inequality constraints? Here is the optimization problem I want to handle: $$ \begin{array}{rl}\min_{\mathbf{x},\mathbf{...
Kaiming Zhang's user avatar
2 votes
1 answer
56 views

Is there a way to find out which original constraints are violated when a feasibility cut is generated in benders?

I've been dealing with Benders Decomposition and I've been wondering, if I have an unbounded solution of the dual subproblem, is it possible to find out which constraint from the original problem is ...
Arctic_Skill's user avatar
2 votes
1 answer
80 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
58 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
75 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
165 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
81 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
  • 900
2 votes
0 answers
75 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
126 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
153 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
81 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 ...
Инженер человеческих душ's user avatar
3 votes
1 answer
97 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
139 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
65 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
  • 517
0 votes
0 answers
42 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
491 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
424 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
367 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 ...
Krypt's user avatar
  • 97
3 votes
2 answers
149 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
412 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
65 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
134 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,160
2 votes
1 answer
107 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
2k 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
283 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
274 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
  • 223
3 votes
1 answer
198 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
167 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
67 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
  • 517
1 vote
1 answer
157 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
  • 517
6 votes
1 answer
149 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,562
5 votes
0 answers
77 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
186 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
  • 900
4 votes
1 answer
187 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
  • 179
6 votes
0 answers
225 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
67 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
1k 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
5 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
119 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