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.
4
questions
24
votes
5
answers
5k
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?...
- 2,077
12
votes
1
answer
291
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 = ...
- 1,468
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 =...
- 3,980
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