5

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

ə̷̶̸͇̘̜́̍͗̂̄︣͟
  • 5,412
  • 5
  • 22
  • 55
user3680510
  • 3,655
  • 6
  • 26
  • 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 08 '21 at 07:06
  • Is a non-convex formulation acceptable? – batwing Feb 08 '21 at 08:05
  • i was looking for something simple and easy to solve. – user3680510 Feb 08 '21 at 12:05
  • 1
    Unfortunately there is no easy general upper bound available. This is a central problem in MILP-representations in bilevel programming, and as discussed here http://www.optimization-online.org/DB_FILE/2019/04/7172.pdf it is hard – Johan Löfberg Feb 08 '21 at 13:58

0 Answers0