1
$\begingroup$

Given a linear objective function and a system of linear constraints, is there any known closed form lower bounds for it? to clearly express the problem assume that $$ z(\mathbf{a,B,c})=\mathop {\inf} \left\{ {\bf{a^Tx} |\quad\bf{Bx-c}\le0} \right\} $$ is any closed form (rather linear) function $y(\mathbf{a,B,c})$ versus $\mathbf{a,B,c}$ such that $y(\mathbf{a,B,c})\le z(\mathbf{a,B,c})$.

As I know, any feasible dual solution for the above problem is a lower bound for it. However, the dual problem take the similar form of the primal problem. How can I obtain a close form lower bound for the above problem?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ In that general form you should not expect a closed-form solution. That is precisely why there are several algorithms (simplex, ellipsoid and interior-point methods) for linear programming. $\endgroup$
    – Cristóbal Guzmán
    Commented Jul 6, 2014 at 23:39

1 Answer 1

Reset to default
2
$\begingroup$

Take the dual. Any dual feasible solution will give you a lower bound, by weak duality (assuming your problem is feasible and not unbounded).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .