优化-拉格朗日乘子法简述

Lagrange Multipliers are used to solve the optimal value of multivariate functions under a group of constraints. By lagrange multipliers, we can convert an optimal problem with d variables and k constraints to one with d+k variables without constraint.

  1. Equality Constraint
    Suppose xRd, we would like to solve some optimal value x s. t. minxf(x) and g(x)=0, i.e.
    minxf(x),s.t.g(x)=0

    For simplicity, we omit the geometric explanation of the optimal problem. Define the Lagrange multiplier λ0 s.t.
    f(x)+λg(x)=0

    Define the corresponding Lagrange funcntion as
    L(x,λ)=f(x)+λg(x)

    So
    xL(x,λ)=f(x)+λg(x)=0

    λL(x,λ)=g(x)=0

    Obviously, the original optimal problem is converted to the new optimal problem with no constraint.
  2. Inequality Constraint
    In the inequality constraint case, the optimal problem can be defined as
    minxf(x),s.t.g(x)0

    When g(x)<0, the constraint g(x)0 makes no sense which means that we can take f(x)=0 to solve the optimal problem. In addition, when g(x)=0, the inequality constraint degrades to the equality constraint.
    In summary, the KKT (Karush-Kuhn-Tucker) conditions are always satisfied:
    g(x)0;λ0;λg(x)=0

    With efficiency concerned, we show the solution of the optimal problem together with next problem. Go on.
  3. Multi-constraints
    Consider an optimal problem with m equality constraints and n inequality constraints. In addition there is a feasible region DRd:
    minxs.t.f(x)hi(x)=0,i=1,2,,m,gj(x)0,j=1,2,,n

    Define the lagrange function as
    L(x,λ,μ)=f(x)+i=1mλihi(x)+j=1nμjgj(x)

    Since there are inequality constraints, the KKT condition is followed:
    gj(x)0;μj0;μjgj(x)=0.

    Solving the original optimal problem, also known as primal problem, can be achieved by solving the corresponding dual problem. Then the Lagrange dual function Γ:Rm×RnR is defined as
    Γ(λ,μ)=infxDL(x,λ,μ)=infxDf(x)+i=1mλihi(x)+j=1nμjgj(x)

    Evidently, mi=1λihi(x)+nj=1μjgj(x)0. Let x~D, then
    Γ(λ,μ)=infxDL(x,λ,μ)L(x~,λ,μ)f(x~)
    That is to say, the dual function shows the lower bound of the value of the primal problem. Then the dual problem is given by
    maxλ,μΓ(λ,μ)s.t.μ0

    The dual problem is always a convex optimal problem, regardless of the convexity of the primal problem.

Let p be the optimal value of the primal problem, d be the optimal value of the dual problem. It has been shown that dp which is also known as weak duality. If d=p, then strong duality holds. Generally, the strong duality does not always hold. However, when the primal problem is a convex optimal problem, i.e. f(x),gj(x) are convex functions, hi(x) are affine functions and there exists a least one x~ making the inequality constraints strictly hold, the strong duality holds. In this case, take the derivative of the Lagrange function over x, λ and μ and set it to be zero. Then we can solve the dual problem as well as the primal problem.

上一篇:Android程序开发重新开始一


下一篇:ARM64 linux kernel virtual address layout