What is really meant by the Lower Bound on an Optimal Solution using Lagrangian Relaxation

329 Views Asked by At

I am trying to understand a key concept in Lagrangian Relaxation. After reading some research papers, I am unclear about the lower bound on an optimal value. One paper conceptually describes a vertical line on which some optimal value for a minimization problem lies. Above this optimal value on the line will lie some Upper bound and below will lie the lower bound. Now when using Lagrangian relaxation for a minimization problem, you will most likely end up with a lower bound solution (multiplier is > 0 and penalty <= 0). My problem is understanding what is wrong with having a lower bound solution. For example, lets say I am trying to minimize some cost function and I use Lagrangian relaxation and end up with a lower bound solution. Does that mean the my lower bound value has a value less than the optimal value, in which case what's the point of trying to maximize the lower bound to be closer to the optimal value?