5
$\begingroup$

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

Improve this question
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ – T_O Feb 8 at 7:06
  • $\begingroup$ Is a non-convex formulation acceptable? $\endgroup$ – batwing Feb 8 at 8:05
  • $\begingroup$ i was looking for something simple and easy to solve. $\endgroup$ – user3680510 Feb 8 at 12:05
  • 1
    $\begingroup$ 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 $\endgroup$ – Johan Löfberg Feb 8 at 13:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.