# Bounding the size of the dual solution

Given an primal optimization with bounded feasible set: $$\max \{cx: Ax \leq b\}$$.

The feasible region of the dual is $$D = \{y:y^\top A = c^\top, y \geq 0\}$$.

If the primal feasbile region is a polytope, then the dual might still by an polyhedron (not bounded in all directions).

Each polyhedron can be written as a convex part plus a cone ($$V$$-representation of polytopes).

How can I get an upper bound $$u$$ on the values of $$y$$ in the convex part? (the bound should say that all verticies of $$D$$ have entries smaller than $$u$$?)

The bound obviously needs to depend on $$c$$ and $$A$$.

• You could use Cramer's rule on all possible basic solutions of the dual to obtain some bound. Still, I think this is of no practical use. – T_O Feb 8 at 7:06
• Is a non-convex formulation acceptable? – batwing Feb 8 at 8:05
• i was looking for something simple and easy to solve. – user3680510 Feb 8 at 12:05
• Unfortunately there is no easy general upper bound available. This is a central problem in MILP-representations in bilevel programming, and as discussed here optimization-online.org/DB_FILE/2019/04/7172.pdf it is hard – Johan Löfberg Feb 8 at 13:58