Lagrangian dual problem

The following Lagrangian dual problem is obtained by dualizing constraints (8) using their nonnegative Lagrange multipliers Xj, j G N. 

The Lagrangian dual problem (23)-(30) can be solved relatively easily because it decomposes into A constrained shortest-path problems, one for each OD pair. A constrained shortest-path problem... 

A Lagrangian relaxation heuristic algorithm that solves the Lagrangian dual problem (35)-(37) is presented next. It uses subgradient optimization to compute the Lagrange multipliers A. 

Set the Lagrange multipliers A to zero in the Lagrangian dual problem and initialize Z (upper bound, best known feasible solution of the original problem) to a high value. 

Solve the Lagrangian dual problem with the latest values of A (by solving a set of integer reverse knapsack problems) to obtain the optimal objective function veilue, Z (x, A), for the given A. 

Thus, using the kernel trick, the Lagrangian dual problem in the feature space will maximize the following problem ... 

Deriving outer bounds is more challenging than inner bounds and usually must exploit specific problem structure. Many outer bounds are based on the Lagrangian dual of (20). 

Using the Lagrangian function, the dual problem can also be rewritten as ... 

Then, the dual problem can be defined by using the program (A. 8). The Lagrangian relaxation appears when the dual function is evaluated for given values X. and /w. of the multipliers X and ft. Given a structure with complicating constrains, program (A.24) can be decomposed in N subproblems as follows ... 

Considering such recent relevance of SDP in quantum chemistry, this chapter discusses some practical aspects of this variational calculation of the 2-RDM formulated as an SDP problem. We first present the definition of an SDP problem, and then the primal and dual SDP formulations of the variational calculation of the 2-RDM as SDP problems (Section II), an efficient algorithm to solve the SDP problems the primal-dual interior-point method (Section III), a brief section about alternative and also efficient augmented Lagrangian methods (Section IV), and some computational aspects when solving the SDP problems (Section V). 

The derivation of the Lagrange relaxation master problem employs Lagrangian duality and considers the dualization of the i(ac,y) < 0 constraints only. The dual takes the following form ... 

Faith and Morari (1979) further develop the ideas of using dual bounding through the use of Lagrangian techniques for this problem. They describe refinements which allow one to make a good first estimate to the Lagrange multipliers (needed for the bounding) and to develop rather easily a "lower" lower bound. 

Lagrangian relaxation is a technique that is suitable for problems with complicating constraints. The idea is to apply the duality function (see Sect. A. 1.3) to this kind of problems in order to reduce their complexity (Guignard 2003). At this point, it is noteworthy that not all the problem constraints must be included in the Lagrangian function in order to construct the dual function (Bazaraa et al. 1993). The Lagrangian... 

---