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?

  • $\begingroup$ I'd need more information about what you're reading to make sense of this paragraph. Are you only considering linear or convex objectives on convex sets, so there's no duality gap? Or more general settings, like continuous or lower semi-continuous functions where there might be a strictly positive duality gap? ( Actually, maybe this would help you think about this: en.wikipedia.org/wiki/Duality_gap ) $\endgroup$
    – user807138
    Sep 11, 2020 at 3:39
  • $\begingroup$ I am looking at solving the economic load dispatch decision for the unit commitment problem. That is I have some generators and assuming I know which units I want to use, I need to figure out how much power each generator should produce so as to meet some load demand at the lowest possible cost. This is what I have reading just to understand the Lagrangian Relaxation method: people.brunel.ac.uk/~mastjjb/jeb/natcor_ip_rest.pdf $\endgroup$ Sep 11, 2020 at 13:31


You must log in to answer this question.

Browse other questions tagged .