Summary of learning linear programming and dual programming

When learning column generation and decomposition algorithms , The knowledge of linear programming and duality is frequently used , so to speak LP and DP It's the foundation . Therefore, it is important to understand the nature of linear programming and duality .

Catalog

1 Basic knowledge of —— hyperplane , Polyhedron

1.1 hyperplane （hyperplane）

1.2 Polyhedron （polyhedron）

2 The origin of simplex method

3 Simplex method

3.1 The base 、 The correspondence of fundamental solutions in geometry

3.2 Principle of simplex method , Corresponding to the geometric motion process

3.3 Solution 3 In this case （ The angle of the boundary ）

3.4 Poles and polar rays

3.5 pole 、 Properties of polar rays

4 Duality theory

4.1 LP And DP Icon

4.2 Dual properties

4.3 The use of duality

---

Simplex method is a pure algebraic operation , Jump from one vertex to another ; And we know that the optimal solution must be obtained at the vertex , But why do we always get the optimal solution at the vertex ？ Why jump from one vertex to another , By entering the base and leaving the base, we can achieve , Why do they correspond to each other ？ in addition to , The sum of poles and polar rays in the decomposition algorithm LP What kind of correspondence is the solution of ？

These problems , It should be said that we must understand the essence of linear programming and duality before we can deeply understand , Instead of getting bogged down in mindless calculations . I've probably read Mu's lessons , I feel that Mr. wangmingqiang of Shandong University has a clear teaching idea , Can have a look at .

On the surface, simplex method is algebraic calculation , The essence is geometry . When it comes to high dimensional space , We can't visualize , Therefore, it can simplify the solution process by algebraic operation , But it is not easy to understand , In other words, for better understanding , We'd better deepen our understanding from a geometric point of view .

This article is written throughout LP yes max problem , The duality is min problem .

1 Basic knowledge of —— hyperplane , Polyhedron

The more important basic knowledge is , The concepts of hyperplane and polyhedron . Because it will be used repeatedly in the subsequent derivation .

1.1 hyperplane （hyperplane）

We can understand it as ： A hyperplane is a n dimension / High dimensional plane , such as 2 The hyperplane of a dimension is a straight line ;3 The hyperplane of a dimension is a plane , Of course , Both lines and planes belong to the category of hyperplane , Or we say that a hyperplane is an extension of a two-dimensional plane to a multi-dimensional one . A hyperplane expressed mathematically is actually a linear equation .

By the way ,（n dimension ） The hyperplane will n The dimensional real number space is divided into two half spaces （halfspace）, That is to say ax<=b and ax>=b Two parts .

More directly , The hyperplane is LP The constraints of the problem . A hyperplane corresponds to a constraint ,m The common part of multiple half spaces formed by constraints is LP The feasible area of .

1.2 Polyhedron （polyhedron）

Above The common part enclosed by multiple hyperplanes is actually a polyhedron （ Corresponding LP The feasible area of ）. It is expressed by mathematical expression as ：

in addition , We can find that a polyhedron must belong to a convex set , So sometimes we call it a convex polyhedron .

also , We see that the general expression is <=. Actually >= perhaps = Also belong to polyhedron . Because it can be transformed , such as *(-1) Or stand together <= and >=, It's easy to prove .

in addition to , We can find from the expression , The edges of a polyhedron must be rigid , Because it's a strict linear constraint , So the curve of soft change does not belong to polyhedron and so on .

notes ： For each pair of points in the set , Each point on the line segment connecting the pair of points is also in the set , Then the set is convex . The mathematical expression is ：

Knowledge about convex sets and vertices , A point that cannot be represented by a linear expression of two different points is called a vertex .

2 The origin of simplex method

The complete context should be （ From graphic method to ） From exhaustive method to simplex method .

The shape of polyhedron can be seen from the example of graphic method , It can also be observed that The optimal solution will be taken at the vertex . This is an intuitive feeling , The real reason is A polyhedron is a common part of multiple hyperplanes , A polyhedron is a geometric shape with convex points , Then consider the objective function as a hyperplane , Keep moving to approach （ Or move out ） The feasible region , The first thing to touch must be a vertex of the polyhedron , therefore , The optimal solution must be obtained at the vertex .

If （ Polyhedral ） The number of vertices is known , We have to name all the top points , Then find the best vertex in it , Then it must be the optimal solution . So the first question is how to find the vertex , Because vertices are often intersections , So we can use the intersection （ That is, continuous equations ） solve , But here's the thing , An intersection is not necessarily a vertex , So we have to determine the feasibility of the intersection , The intersection satisfying the feasibility is the real vertex . To sum up ： Find the intersection first —— Find the vertex again （ That is, the feasible intersection ）—— Compare all the vertices to find the best one .—— This is the idea of exhaustive method .

however , The graphical method has the following problems ：

1） All constraints need to be reduced to equality constraints ;

2） A system of equations with continuous constraints at the intersection , That is, the combinatorial problem , When there are many constraints, the amount of calculation is very large , That is, when the constraint quantity is m individual （ Including variable value constraints ）, Variable is n dimension , Then we need to solve Time ;

3） It is necessary to judge whether the intersection is feasible one by one , There is also a certain amount of work ;

4） You need to find all the intersections , Then contrast , And 1） Is the corresponding , The workload is not small .

therefore , We propose the simplex method , Through ingenious design , Take the essence of the exhaustive method （ thought ）, At the same time, avoid the disadvantages of exhaustive method .

meanwhile , Let's use the knowledge of the first part Explain the essence of lower vertex and intersection . If so Ax<=b, among A yes m*n dimension , That is to say, the variable is n Dimensional , A polyhedron is n Dimensional polyhedron .

（1） A constraint corresponds to a hyperplane , When the constraint is an equal sign constraint , Means that the hyperplane is fixed ; When the constraint is an inequality constraint , Means that the hyperplane can be moved . To make a long story short , A constraint corresponds to a hyperplane .

（2） The vertex is n The common part of a hyperplane , that n-1 The common part of a hyperplane is an edge .

3 Simplex method

（1） because LP The feasible region of is a convex polyhedron , So we know , When a vertex is better than the surrounding vertices , That means it is the optimal solution . So just compare the advantages and disadvantages of the surrounding nodes —— This avoids finding and comparing all the intersections （ Feasible solution ）, It reduces the amount of calculation .

meanwhile , When using the simplex method , After standardization ：

1） The introduction of relaxation variables directly turns constraints into equations —— There is no need to take an equal sign , It has the following advantages ;

2） The introduction of relaxation variables can directly correspond to an initial feasible solution , Because it constrains the right-hand end item b Being positive , That is, it is feasible ; At the same time, during the iteration , Each time it is transformed into a unit matrix , So the corresponding b The column is the solution itself , And in this process always keep b Being positive , So the solution is always feasible —— Avoid feasibility verification , At the same time, we can see the next solution directly ;

3） The value of the relaxation variable corresponds to the original constraint Ax<=b The satisfaction of , Violate or take, etc .

Above That is, the relaxation variable ,Ax+x'=b.

When the value is negative , namely Ax>b, The original constraint is violated ; When the value is positive , namely Ax<b, The original constraint is satisfied ; When the value is 0, That is, the original constraint is taken .

In short , There are many benefits to adding relaxation variables ！

You can see , The simplex method passes the above key design , It makes the solution more simple and intuitive .

Then there is only one key question left , How to jump from one point to the next best point ？ There are two issues involved here , One is to jump to the next , In fact, it is the best neighbor . In fact, this part of the content has been covered in the operation research textbook , Let me just mention , To ensure that you jump to the next best point , In fact, it is our careful choice , That is, by carefully selecting the principal elements , Or determined by the out base and in base variables .

Next, I will use geometric concepts , That is to say, the concept of hyperplane and polyhedron explains the steps of simplex , And each step corresponds to the motion process in geometry .

3.1 The base 、 The correspondence of fundamental solutions in geometry

（1） First , The feasible solution corresponds to the points in the feasible region of the polyhedron , This is easier to understand ;

（2） Basic solution , That is to say, after being converted into standard type , At this time, the total variable containing all relaxation variables is n dimension , Where the number of relaxation variables and the number of constraints are equal to m dimension , So it's easy to know the original variable / The solution space is n-m dimension . take n-m Non base variables are set to 0, At the same time, the columns corresponding to these non base variables are removed , remainder m Column （ Relax the dimension of the variable ） The new constraints are solved simultaneously ; Or it can be thought that n-m Non base variables are set to 0, At the same time, the remaining m Column , Get the value of the base variable . Be careful , From this solution , We can see , this m Columns must be linearly independent , Or full rank , Because only full rank , That's why ; Otherwise, the number of valid constraints < Variable dimension , unsolvable . This is why we turn the array into a unit array , That is, the full rank is always guaranteed , Have solution , Avoid unanswered situations .

Let's talk about it again ： Basic solution , That is, the non base variable is 0, Find the base variable , The basic solution is obtained by combining the base variable and the non base variable . Note that the non base variable is 0 It is our hard and fast rule . Basic solution yes n Constraints are solved at the same time , namely n The intersection of two hyperplanes , To sum up, it is necessary to enclose a feasible region n The intersection of two hyperplanes . Be careful , there n Is the dimension of the solution space , That is, in the previous paragraph n-m.

（3） The basic feasible solution corresponds to the vertex of the feasible region .

The basic solution may not be feasible , When the base solution is a vertex + feasible （ All variables >0）, That is, basic solvable , It corresponds to the intersection of feasible regions .

3.2 Principle of simplex method , Corresponding to the geometric motion process

（1） Standardization at the beginning , There are the following benefits ：

a） There is a base, the unit matrix , And b List as positive , That is, there is an initial feasible solution ;

b） After that, the line transformation is easy ;

（2） iteration , That is, one-step basis , Once out of the base .

a） In fact, it corresponds to the change process of the hyperplane , When entering the base , That is, the value of the non base variable is no longer 0, That is, you can take values freely （ This constraint is no longer satisfied , The remaining n-1 Dimensional hyperplane ）, Then the corresponding constraint or hyperplane begins to move ; Out of the base variable means that the truncation moves , That is, the hyperplane keeps moving , Until you hit the next hyperplane , A new group n The dimensional hyperplane forms a new intersection , At the same time, because the simplex table has always maintained b' List as positive , That is to say, the adjacent vertex is reached .

From this process , We can see , When you start moving freely , The original n-1 The common region of a dimensional hyperplane is an edge , That is, move along the edge ; When you touch a new hyperplane , The original n-1 Dimensional hyperplane + The hyperplane touched = new n Dimensional hyperplane , Form a new intersection , Because it moves along the edge , And it is always guaranteed to be feasible , So one in base one out base ensures that you jump from a vertex to an adjacent vertex . That is, remove a hyperplane , Add a new hyperplane , It can realize jumping from one vertex to adjacent vertices ; In other words , Adjacent vertices differ only by one non base variable , A base variable is different .

b） We know , There are many adjacent vertices , And there is no local optimum , Therefore, iteration is the hope to move in a better direction . So we want to go to the next best vertex , According to the derivation, we know that , When Greater than 0, It means that the current solution can be improved ; So we find the largest increment, of course, the greatest improvement , That is to jump to the best critical point .（ Be careful , The whole story here is max problem .）—— This determines the base column .

c） At the same time, in order to ensure that the solution is always feasible in the iterative process , We have also carefully chosen . Two factors are considered in the selection of , One is feasible , That is, all variables >=0, therefore Take it in a small direction ; At the same time, because of the reason of the base , The new non base variable should =0, So only one vertex can be reached .—— This determines the base variable .

To sum up ：

The basis determines the optimization direction of the iteration , The base determines the forward step of the iteration . At this point, let's recall the above mentioned ： A hyperplane moves , How to determine the optimization direction in which direction to move , That is, move in the direction of entering the base ; All the way to the new hyperplane and the original n-1 The intersection of dimensional hyperplanes , stop it , That is, the forward step . Such a recollection , You will find the connection and correspondence between the two .

3.3 Solution 3 In this case （ The angle of the boundary ）

At first we learned LP, Common is 4 In this case ： unsolvable ; The only optimal solution ; Multiple optimal solutions ; Infinite optimal solution .

Now let's change the angle , To illustrate the case of the lower solution .

（1） unsolvable —— That is to say, there is no corresponding solution , No feasible region

• If feasible region is an empty set , Its dual problem is unbounded , Then the original problem is unbounded , The target value of the model can be infinitesimal , Lose the meaning of solution .

（2） Bounded solution （ Unique solution , Multiple solutions and infinite solutions ）

• If the feasible region is not empty and bounded , Optimal solution It must be at some pole of the feasible region On .

（3） Unbounded solution （ Unique solution , Multiple solutions and infinite solutions ）

• If the feasible region is not empty and unbounded , Optimal solution It must be determined by some polar direction of the feasible region Express .

among , Unbounded means that you can get positive / Negative infinity .

The benefits of changing thinking are , The solution can be explained from the perspective of poles and polar rays . That is to say, the latter two cases of bounded solution and unbounded solution , Corresponding to pole and polar ray respectively . The pole can be understood as the vertex of a polyhedron , Polyhedron is LP The part enclosed by the feasible region of ; Polar rays are associated with unbounded .

3.4 Poles and polar rays

Let's use mathematical expressions to describe the poles and polar rays ：

（1） pole （extrame point）
The vertices of a polyhedron are also called poles （extreme point）, It's defined as ： For polyhedron , If you can't find any two different from x The point of x1 and x2,  And a scalar λ∈[0,1], bring x = λx1+(1−λ) x2, be x For the extreme . This definition is very similar to the definition of vertex , Feeling can be understood as a thing .（ namely x Not in the line between any two points in a polyhedron ）.

The poles can be solved by solving this linear programming , The optimal solution is a pole . Because the optimal solution of linear programming always exists at the poles . Or make n A linear independent constraint takes the equal sign , Solve the equation to get , among n Is the dimension of a polyhedron .

（2） Polar rays （extrame ray）

The ray of a polyhedron is defined as ： For a vector d, If for a polyhedron Any point of x And any nonnegative scalar λ, There are x+λd∈P, said d Is a polyhedron The rays of .
Polar rays of polyhedron Defined as ： For polyhedron Any two linearly independent rays in d1,d2. If ray d It can't be expressed as d=λ1d1+λ2d2, among d1 and d2 Is a scalar greater than zero , be d The polar ray of a polyhedron . Geometric meaning ： The rays on the polyhedral boundary are polar rays .

The outgoing ray is required , To use another definition of it ： For a polyhedron {x∣Ax≥b}, Its polyhedral cone （ Also called degenerate cone , Because it degenerates from polyhedron ） by {x∣Ax≥0}, hypothesis x Yes n Dimensions , be n-1 A linear independent constraint takes the equal sign , And meet the remaining conditions , Then a polar ray can be obtained .

notes ： The polar ray is a vector , So the polar ray can have multiple solutions , It can be obtained by solving a linear programming problem with auxiliary variables （ The auxiliary variable is a 0-1 Variable , The objective function is to maximize the value of this auxiliary variable , Constraints ： Choose randomly n-1 Take the equal sign of the constraints and put them in , The rest of the constraints are put in , Let one of the variables be equal to 1）.

for example , The arrows in this polyhedron , Are all rays of the polyhedron . among , The red line indicates the polar ray . Or we can intuitively think that The polar ray is the edge of a polyhedral cone , A polyhedral cone is a cone surrounded by multiple hyperplanes .

3.5 pole 、 Properties of polar rays

（1） If a polyhedron has polar rays , Then the polyhedron is unbounded .—— Polar ray properties 1

（3）Ad=0.—— Polar ray properties 2

because x Is the point in the polar direction , be x+λd It is also a point in the polar direction ,d Is the polar direction ,λ It controls the moving step in the polar direction . So there are A(x+λd)=b,Ax+λAd=0, because Ax=b, therefore Ad=0.

（4）c'd<0 Then there is no boundary .—— Polar ray properties 3

If you have any c'(x+λd)<c'x, Just increase the step size , Then the objective function can be reduced all the time , Until it reaches negative infinity . namely ,c'x+λc'd<c'x, therefore c'd<0. here c' Express c The transpose .

The above two properties refer to （1） and （2）. This part , That is, any point in a polyhedron can be represented by a convex combination of poles and polar rays , That is to say Minkowski Theorem , Not too much sorting , But it is often used in practice . 

4 Duality theory

If the original problem is on the basis of ensuring feasibility , Make the feasible solution better . That is, to guarantee b' Being positive （ feasible ） Under the condition of , So that all inspection numbers are <0, There is no room for improvement / Or let the dual problem work , At this time, it is optimal .

So the dual problem is similar , To ensure that it is feasible （ The inspection number is not positive ） On the basis of , Improve the quality of the solution . That is, when the inspection number is not positive , Because the inspection number = Negative dual variable , A non positive test number means that the dual variable is non negative , That is, the dual problem is feasible ; On this basis, let the original problem be feasible , namely b' Being positive .

In the above description , I've actually used the duality theorem . Strong duality , That is, when both the primal problem and the dual problem have feasible solutions and are equal , At the same time, the optimal . alike , The dual simplex table assumes that the solutions of the primal problem and the dual problem are equal , Then it is only necessary to consider that the other party is feasible ; For example, in solving LP At the time LP Where feasible , send DP feasible ; For example, in solving DP At the time DP Where feasible , send LP feasible .

Actually ,LP Matrix description is usually used , Its purpose is actually to finally launch , The test number is a negative dual variable ; The position of the original unit matrix in the final simplex table is B The inverse of ; And for the subsequent sensitivity analysis .

What is already in the book will not be repeated , The duality property is introduced below .

4.1 LP And DP Icon

If the original question , namely LP The question is about x Of max problem ; The dual problem is about y Of min problem . Then we can deduce the following properties （ because max and min They are dual to each other （ Intuitive understanding is symmetry ）, So the reverse can also be deduced by the same logic , But we should pay attention to the upper and lower bounds ）.

4.2 Dual properties

The original question maxc'x, The dual problem b'y

（1） Weak duality theorem

if x and y They are the original 、 Feasible solution of dual problem , Then there are c'x<=b'y. Note that there c' and b' respectively c and b The transpose （ I will not admit that I am lazy and do not use the formula .）

in other words ：

The objective function of any feasible solution of the primal problem is the lower bound of the dual problem ;

The objective function of any feasible solution of the dual problem is the upper bound of the original problem .

We can intuitively feel , The original problem is to maximize obj, The dual problem is minimization obj, Eventually the two will reach the same destination , Then the primal problem is always smaller than the dual problem , Until they meet , At the same time, it is optimal . review 4.1 Graph , That is, the primal problem is under the dual problem ; The dual problem is above the original problem .

（2） Boundlessness

  Intuitively understand , According to weak duality , The primal problem provides a lower bound for the dual problem , The dual problem provides an upper bound for the original problem .

a） When the original problem is unbounded , Maximize unbounded , That is to say, we get positive infinity , There is no lower bound for the dual problem （ Or take up all the solution space , There is no territory for duality problems ）, Then the dual problem has no feasible solution .

If the dual problem is unbounded , Minimize unbounded , That is, take negative infinity , There is no upper bound for the original problem （ Or take up all the solution space , There is no territory for the original problem ）, Then the original problem has no feasible solution .

b） If the original problem has a feasible solution , The dual problem has no feasible solution , Then the original problem is unbounded . Intuitive understanding is ： The original problem has a feasible solution , That is, it occupies a certain region in the solution space , But the dual problem has no feasible solution, that is, it does not occupy any region , Then the original problem can only be unbounded, that is, it occupies all the regions .

c） If the original problem is unsolved , That is, it does not occupy any region in the solution space , Or the dual problem has no solution , That is, it does not occupy any region in the solution space ; Or unbounded , Occupy all the solution space , Take it all the way to negative infinity .

（3） Optimality

The above dual simplex method , In fact, this is what is used . in addition to , When the two are not equal , The difference between the two , It's called dual gap , That is, when the dual gap =0 when , The relaxation problem is equivalent to the original problem ; otherwise , Only one boundary can be provided for it . This is a relaxation problem , For example, the later Lagrangian relaxation will also be used .

（4） Strong duality theorem

There is no explanation for this .

It is worth explaining that the above table . I personally feel that this watch is more important .

4.3 The use of duality

In fact, we all know the above dual properties , But not necessarily .

  such as ：

（1） Solve both primal and dual problems , Can quickly determine whether the original problem is bounded , In other words, more information can be obtained quickly . It is easy to judge whether a problem has a solution , Finding the solution that satisfies the constraint is the feasible solution ; But it is difficult to judge whether the problem is bounded , The dual problem can easily let us know whether the problem is bounded , It is as difficult to solve as to judge whether the problem has a solution .

（2） You can convert complexity between constraints and objective functions . such as , stay Benders Breaking down , We see because y Value change , Cause the constraint variable to change all the time , That is, the feasible region is changing ; And through duality ,y Is transferred to the objective function , Then the feasible region remains unchanged , It's just that the objective function is changing .

（3） The dual problem provides a bound for the primal problem , The quality of the solution can be known at any time .

These three points are more important , But there are not many direct points in the book .