Seminar 21

Penalty method and augmented Lagrangian method

Reminder

• Interrior point method
• Barrier method with logarithmic barrier
• Primal-dual method

Penalty method

Idea: barriers prevent iterands to move outside of the feasible set, and penalty functions leads to significantly increasing of the objective function in the case of lying iterands outside of the feasible set. However, this scenario is possible.

Equality constrained problem

Quadratic penalty method

Original problem can be reformulated as unconstrained optimization problem

where

• If constraints is not satisfied, then objective function increases proportionally to $\mu$
• While the value of $\mu$ increases, solution of the unconstrained problem is satisfied constraints more and more accurately

General scheme

def QudraticPenaltyEquality(Q, gradQ, x0, get_mu, get_tau, **kwargs):
    while True:
        # Stop when norm of gradient of Q is less than current tau
        x = MinimizeQ(Q, gradQ, x0, get_tau)
        if global_cnvergence(x, Q, **kwargs):
            break
        mu = get_mu()
        Q, gradQ = UpdateQ(mu)
        x0 = UpdateStartPoint(x, Q)
    return x

• Parameter $\mu$ has to be changed depending on the complexity opf solveing subproblem: if it is known that subproblem is solved long time, then $\mu$ has to be changed more smoothly, for example $\mu_{k+1} = 2\mu_k$. If subproblem is solved fast, then more aggresive changing of $\mu$ is acceptable, e.g. $\mu_{k+1} = 15\mu_k$.
• While increasing $\mu$, solving of the subproblem is more and more difficult due to poor conditioning of the hessian. More details below.

Convergence

Theorem 1. Assume that for every $\mu$ unconstrained optimization problem has finite global solution. Then the sequence of the subproblems solutions converges to global solution of the original problem while $\mu \to \infty$

• Issue: global optimum for some subproblems can be unreachable!

Theorem 2. Assume $\tau_k \to 0$ and $\mu_k \to \infty$ and $\| Q'(x^*_k, \mu_k) \| \leq \tau_k$. Then

• if $x^*_k \to x^*$ and $x^*$ is infeasible, then $x^*$ is stationary point of the function $\| g(x) \|^2_2$;
• if $x^*$ is feasible and gradients of the constraints in this point are linearly independent, then $x^*$ is the point in which KKT conditions are satisfied.

For any subsequence $x^*_k \to x^*, \; k \in \mathcal{C}$ the following holds

for all $i = 1,\ldots,m$, where $\lambda_i^*$ is Lagrange multipliers that satisfied KKT.

Singularity of hessian

Example. \begin{equation*} \begin{split} & \min -5x_1^2 + x_2^2\\ \text{s.t. }& x_1 = 1 \end{split} \end{equation*} Penalty function $$ Q(x, \mu) = -5x_1^2 + x_2^2 + \frac{\mu}{2}(x_1 - 1)^2 $$ Note While $\mu < 10$ function $Q(x, \mu)$ is unbounded below for $x$ and subproblem does not have finite solution

General form of hessian

where $g'(x)$ is Jacobian of the vector-function representing equality constraints.

From theorem 2, the following approximation holds near the optimum point

• hessian of Lagrangian does not depend on $\mu$
• product $(g'(x))^{\top} g'(x)$ has rank of $m \ll n$

Summary: some of the eigenvalues of hessian $Q''(x, \mu)$ are of the order $\mu$, therefore increasing $\mu$ leads to singularity of hessian

Corollary: search direction in the Newton method is very inaccurate!

How to find direction in Mewton method?

Let us introduce new variable $\xi = \mu g'(x) p$ and re-write the system in the form

• Condition numbner of this system is no longer increased while increasing $\mu$
• Dimension is increased by $m$
• Quadratic approximation can still be inadequate

Equality and inequality constraimed problem

Penalty function

where $\mu > 0$

• Difference from the equality constrained problem: second derivative of penalty function is discontinuous and consequently penalty function is no longer twice continuously differentiable

Experiment

Consider the problem \begin{equation*} \begin{split} & \min \|x\|_2 \\ \text{s.t. } & Ax = b \end{split} \end{equation*}

and solve it with the penalty functions

Pro & Contra

Pro

• automatic way to convert any constrained optimizatiomn problem to unconstrained one
• you don't need to find initial guess
• somitemes small violation of constraints are acceptable
• general scheme is simple to implement

Contra

• solution of the unconstrained optimization problen is not always solutiuon of the constrained original problem
• if objective function of the original problem is defined only on the original feasible set, then penalty method is inapplicable
• quadratic approximation $Q(x, \mu)$ may be inadequate

Augmented Lagrangian method

Motivation: in the penalty method solutions of the subproblems can violate constraints and it is known only that

Is it possible to fix $Q(x, \mu)$ in a way to prevent constraints violation?

Idea: add penalty not to the objective function, but to the Lagrangian. It is analogue of the primal-dual method, because one iteration performs updating both primal and dual variables.

Equality constrained optimization problem

Augmented Lagrangian

Necessary optimality condition for $M(x_k, \lambda^k, \mu_k)$ $$ f'(x_k) + \sum\limits_{i=1}^m (\lambda^k_i + \mu_k g_i(x_k) ) g'_i(x_k) \approx 0 $$ From this follows expression for $\lambda^{k+1}$ $$ \lambda^{k+1}_i = \lambda^k_i + \mu_k g_i(x_k) $$

Constraints violation

• In the penalty method convergence of equality constraints to zero was of the order of $1/\mu_k$
• In the augmented Lagrangian method convergence to zero is faster, because not only denominator increases, but nominator also converges to zero

Equality and inequality constraints problem

Augmented Lagrangian

where $\lambda$ are vector of dual variables corresponding to equality constraints, $\nu$ are vector of dual variables corresponding to inequality constraints

• See the derivation of $M(x, \mu, \lambda, \nu)$ in lecture notes.

Updating of dual variables corresponding to inequalities constraints

Convergence

• Convergence is local (initial guess is near optimum in primal and dual variables)
• For some sufficiently large $\mu$, solutions of the subproblems will converge to the solution of the original problem, therefore one should not increase $\mu$ infinitely
• Solving subploblems is easy than in the penalty method because $\mu$ is bounded above

Practical remarks

• Augmented Lagrangian method is preferable because solving of subproblems is as difficult as in the penalty method, but its convergence is faster
• Penalty method is preferable as regularization of the sequential quadratic programing approach (SQP)
• Packages LACELOT and MINOS) use different implementations of the augmented Lagrangian method
• The paper presents comparison of these packages, but they were developed in early 1990s using Fortran

Experiment

Consider the following problem \begin{equation*} \begin{split} & \min \|x\|_2 \\ \text{s.t. } & Ax = b \end{split} \end{equation*}

and solve it with augmented Lagrangian method.

Dependence on the parameter $\mu$

Recap

• Penalty method
• Augmented Lagrangian method