Civil Engineering Reference
In-Depth Information
ables to reduce the number of delay constraints from an exponential number
to a number that is linear in the circuit size. The optimizer employs two varia-
tions of the Lagrange multiplier approach, the augmented Lagrangian algorithm
and the projected Lagrangian algorithm [Lue84, Mar86]. The augmented La-
grangian algorithm uses a penalty term that helps to steer the solution towards
the feasible region and, hence, has the desirable property of global convergence.
The projected Lagrangian method, a quadratic approximation method that is
similar to Newton's method, has a fast convergence rate. However, it is not
globally convergent, and requires that the initial solution be close enough to
the optimum solution in order to converge. COP starts with the augmented
Lagrangian technique to take advantage of its global convergence. When the
gradient of the Lagrangian becomes less than a certain small number, it
switches to the projected Lagrangian algorithm, to converge more quickly to
the solution.
8.5.2
Lagrangian relaxation methods
The approach in [CCW99] presents a detailed analysis of the Lagrangian of
Equation (8.3). The problem can be rewritten as
where
It was shown that regardless of the delay model used‚ the linear relations in
the arrival time constraints lead to a following flow-like requirement on some
of the Lagrangian multipliers:
This leads to the restatement of the problem as
