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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.