|} where we define as {| border="0" cellpadding="1" cellspacing="0" |- |max | | |- |s.t. |- |(1) | | |} A Lagrangian relaxation algorithm thus proceeds to explore the range of feasible values while seeking to minimize the result returned by the inner problem. Each value returned by is a candidate upper bound to the problem, the smallest of which is kept as the best upper bound. If we additionally employ a heuristic, probably seeded by the values returned by , to find feasible solutions to the original problem, then we can iterate until the best upper bound and the cost of the best feasible solution converge to a desired tolerance. Related methods The augmented Lagrangian method is quite similar in spirit to the Lagrangian relaxation method, but adds an extra term, and updates the dual parameters in a more principled manner. It was introduced in the 1970s and has been used extensively. The penalty method does not use dual variables but rather removes the constraints and instead penalizes deviations from the constraint. The method is conceptually simple but usually augmented Lagrangian methods are preferred in practice since the penalty method suffers from ill-conditioning issues. References Books Bertsekas, Dimitri P. (1999). Nonlinear Programming: 2nd Edition. Athena Scientific. . Articles Bragin, Mikhail A.; Luh, Peter B.; Yan, Joseph H.; Yu, Nanpeng and Stern, Gary A. (2015). "Convergence of the Surrogate Lagrangian Relaxation Method," Journal of Optimization Theory and Applications. 164 (1): 173-201, Convex optimization Relaxation (approximation)