Presentation Transcript
Slide 1:Augmented Lagrangian Penalty Functions They can recover an exact optimum for finite penalty parameter values and they enjoy the property of being differentiable.
For simplicity, let us begin by discussing the case with only equality constraints.
Consider Problem P of minimizing f(x) subject to hi(x) = 0 for i = 1, ... , l.
If we employ the quadratic penalty function, then we typically need to let to obtain a constrained optimum for P.
Define
Slide 2:Observe that if (x, v) is a primal-dual KKT solution for P, then indeed at v = v
Whereas we needed to take to recover x in a limiting sense using the quadratic penalty function, it is possible that we only need to make large enough for the critical point x of FALAG(., v) to be its (local) minimizer.
Slide 3:Observe that FALAG is the ordinary Lagrangian function augmented by the quadratic penalty term, hence the name augmented Lagrangian penalty function.
FALAG can be viewed as the usual quadratic penalty function with respect to the following problem that is equivalent to P:
FALAG is therefore called a multiplier penalty function.
Slide 4:Theorem
Consider Problem P to minimize f(x) subject to hi(x) = 0 for i = I, . .. , l, and let the KKT solution (x, v) satisfy the second-order sufficiency conditions for a local
minimum (the Hessain is positive definite). Then, there exists a such that for ≥ , FALAG( . , v) also achieves a strict local minimum at x. If f is convex and hi are affine, then any minimizing solution x for P also minimizes FALAG(., v) for all ≥ 0.
Slide 5:Schema of an Algorithm Using Augmented Lagrangian Functions: Method of Multipliers
The method of multipliers is an approach for solving nonlinear programming problems by using the augmented Lagrangian penalty function in a manner that combines the algorithmic aspects of both Lagrangian duality methods and penalty function methods.
To monitor individual constraint violation, we can write
Slide 6:Initialization Select some initial Lagrangian multipliers v = v and positive values 1,…, l for the penalty parameters. Let xo be a null vector, and denote VIOL(xo) = , where for any x En, VIOL(x) = maximum {|hj(x)|: i = 1, ... , I} is a measure of constraint violations. Put k = 1 and proceed to the "inner loop" of the algorithm.
Inner Loop: Penalty Function Minimization Solve min FALAG(x, v) s. t. x En and let xk the optimal solution obtained. If VIOL(xk) = 0, stop with xk as a KKT point. Otherwise, if VIOL(xk) ≤ 0.25VIOL(xk-1)' proceed to the outer loop. If VIOL(xk) > VIOL(xk-1) then, for each constraint i = 1, ... , l for which |hi(xk)|> VIOL(xk-1), replace the corresponding penalty parameter i by 10 i and repeat this inner loop step.
Outer Loop: Lagrange Multiplier Update Replace v by vnew, where
Increment k by 1, and return to the inner loop.