Esiry.com
Focus on Machine Learning.

Lagrangian duality

Lagrangian duality

When I read the chapter “Statistical Learning Methods” Support Vector Machine, I saw “Apply Lagrangian Duality (see Appendix C), and get the optimal solution of the original problem by solving the dual problem,” then recursively Take a look at the Lagrangian duality of Appendix C. The name is learned, but in fact it is excerpted, adding a small amount of personal understanding and background supplement. After all, theorems and inferences can be understood, and it is impossible to write flowers. Even the original work did not give proof of partial inference, just knowing that there is such a thing, the next time you have to remember to come over and take a look. The following is the body of the excerpt:

In the constraint optimization problem, the Lagrange duality is often used to transform the original problem into a dual problem, and the solution to the original problem is obtained by solving the dual problem. This method is used in many statistical learning methods, such as maximum entropy models and support vector machines. Here is a brief description of the main concepts and results of Lagrange’s duality.

Original problem

Hypothesis
Lagrangian dualityIs a continuous differentiable function defined on Rn. Consider constrained optimization problems

Lagrangian duality

Call this constraint optimization problem the original optimization problem or the original problem.

First, introduce a generalized Lagrange function

Lagrangian duality

Here,
Lagrangian dualityIs a Lagrange rider,
Lagrangian duality. Consider the function of x:

Lagrangian duality

Here, the subscript P indicates the original question.

Suppose that given an x, if x violates the constraints of the original problem, there is some i

Lagrangian dualityOr there is some j so that
Lagrangian dualityThen there is

Lagrangian duality

Because if an i makes a constraint
Lagrangian dualityCan make
Lagrangian dualityIf j makes
Lagrangian dualityCan make
Lagrangian dualityMake
Lagrangian dualityAnd the rest of each
Lagrangian dualityBoth are taken as 0.

Conversely, if x satisfies the constraint formula (C.2) and formula (C.3), then from equations (C.5) and (C.4),
Lagrangian duality(The two of the two are non-positive, one is 0. If you want to take the maximum value, of course, both must be 0). therefore,

Lagrangian duality

So if you consider the minimization problem

Lagrangian duality

It is equivalent to the original optimization problem (C.1) ~ (C.3), that is, they have the same solution. problem
Lagrangian dualityIt is called the minimal maximization problem of the generalized Lagrangian function. In this way, the original optimization problem is expressed as a minimal maximal problem of the generalized Lagrangian function. For convenience, define the optimal value of the original problem

Lagrangian duality

The value called the original question.

2. Dual problem

Definition

Lagrangian duality

Consider maximizing again
Lagrangian duality, which is

Lagrangian duality

problem
Lagrangian dualityA very small minimum problem called a generalized Lagrangian function.

The maximal minimization problem of the generalized Lagrangian function can be expressed as a constrained optimization problem:

Lagrangian duality

A dual problem called the original problem. Define the optimal value for the dual problem

Lagrangian duality

The value called the dual problem.

3. The relationship between the original problem and the dual problem

The relationship between the original problem and the dual problem is discussed below.

Theorem C.1

If both the original problem and the dual problem have optimal values, then

Lagrangian duality

prove

From the formula (C.12) and the formula (C.5), for any of α, β and x, there are

Lagrangian duality

which is

Lagrangian duality

Since both the original problem and the dual problem have optimal values,

Lagrangian duality

which is

Lagrangian duality

This seems to be well understood that the upper bound of the minimum of the same function is less than the lower bound of its maximum.

Corollary C.1

Assume
Lagrangian dualityAre the feasible solutions of the original problem (C.1)~(C.3) and the dual problem (C.12)~(C.13), respectively, and
Lagrangian dualitythen
Lagrangian dualityThey are the optimal solutions for the original problem and the dual problem.

Under certain conditions, the optimal values of the original problem and the dual problem are equal.
Lagrangian duality. At this time, the solution to the original problem can be replaced by the solution to the dual problem. The relevant important conclusions are described below in the form of theorems without proof.

Theorem C.2

Consider the original question (C.1) ~ (C.3) and the dual question (C.12) ~ (C.13). Hypothetical function
Lagrangian dualitywith
Lagrangian dualityIs a convex function,
Lagrangian dualityIs an affine function;

Bean knowledge affine function

An affine function is a special convex function. A function that is both a convex function and a concave function is called an affine function. It must be the sum of a linear function and a constant. In a finite dimensional space, an affine function is a linear function. The importance of the function is that the lower semi-continuous convex function on the local convex space (including the normed linear space and the finite dimensional space) must be the upper envelope of the continuous affine function family.

– “Mathematics Ci Hai Volume III” (Unfortunately, I generally do not understand Chinese academic books, can only understand the red sentence.)

Affine functions represent vector-valued functions of the form

Lagrangian duality

The coefficients can be scalars or dense or sparse matrices. The constant term is a scalar or a column vector.

In geometry, an affine transformation or affine map (from the Latin, affinis, “connected with”) between two vector spaces consists of a linear transformation followed by a translation. In a geometric setting, these are precisely the functions that map straight lines to straight lines.

——https://mathworld.wolfram.com/AffineFunction.html (English is very easy to understand, the affine function is a linear function, the input is an n-dimensional vector, the parameter A can be a constant, or a matrix of m*n, b can be a constant, or can be an m-dimensional column vector, The output is an m-dimensional column vector. Geometrically, an affine function is a transformation from one linear space to another.)

And assume inequality constraints
Lagrangian dualityIs strictly feasible, that is, there is x, for all i have
Lagrangian duality, then there exists
Lagrangian dualityMake
Lagrangian dualityIs the solution to the original problem,
Lagrangian dualityIs the solution to the dual problem, and

Lagrangian duality

Theorem C.3

For the original problem (C.1) ~ (C.3) and the dual problem (C.12) ~ (C.13), the hypothesis function
Lagrangian dualityand
Lagrangian dualityIs a convex function,
Lagrangian dualityIs an affine function and inequality constraints
Lagrangian dualityIs strictly feasible, then
Lagrangian dualityand
Lagrangian dualityThe necessary and sufficient conditions for the solution of the original problem and the dual problem are respectively; the following Karush-Kuhn-Tucker (KKT) conditions are satisfied:

Lagrangian duality

Lagrangian duality

In particular, the formula (C.24) is called the dual complement condition of KKT. According to this condition, if
Lagrangian duality,thenLagrangian duality.

Reference

Statistical Learning Method

Your support will encourage us to be creative continuously!

Use [WeChat] Scan QR code for Appreciation

Use [Alipay] Scan QR code for Appreciation

Jumping to PayPal...
赞(0)
Please indicate the source:Esiry » Lagrangian duality

Comment 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址