# 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.

6 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
172 views

### Integrality gap in bilevel binary linear programming problem

I have a bilevel max-min optimization problem over binary variables, with constraints expressed using linear inequalities. The inner (minimization) problem is  \begin{alignat}2 \min\limits_x&\...
175 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,...
94 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$. ...
41 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 ...
### 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(\...