当前位置:天才代写 > course代写 > OPTIMIZATION代写 Linear Optimization代写 course代写 applications代写

OPTIMIZATION代写 Linear Optimization代写 course代写 applications代写

2020-12-01 10:38 星期二 所属: course代写 浏览:148

OPTIMIZATION代写

LECTURE NOTES

OPTIMIZATION代写 Abstract. These are lecture notes for co255 in the Fall 2019 term.Topics covered:(1)Linear Optimization, Convexity (4 weeks)

FOR CO255 INTRODUCTION TO OPTIMIZATION

FALL  2019

LEVENT TUNC¸ EL

Abstract. These are lecture notes for co255 in the Fall 2019 term.

Topics covered:

  • Linear Optimization, Convexity (4 weeks): Duality in linear optimization. Farkas’ Lemma and the theorems of the alternative. Duality theorem for linear programming. Complementary Slackness theorem. Simplex Method. Polyhedra and elementary convex
  • Combinatorial Optimization (4 weeks): Linear diophantine equations. Facets of polyhedra. Integrality of polyhedra. Shortest paths and optimal flows. Total Unimodularity. K˝onig’s     Max.   Flow-Min.   Cut  Theorem.   (Hungarian) Bipartite matching algorithm.OPTIMIZATION代写
  • Continuous Optimization (4 weeks): Convex functions. Analytic characteri- zations of Existence and uniqueness of optimal solutions. Separating and supporting hyperplane theorems. Lagrangian Duality. Karush-Kuhn-Tucker Theorem. Conic Optimization problems. EllipsoidMethod.

Date: Fall 2019. October 21, 2019.

Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Waterloo, Ontario, N2L 3G1, Canada (e-mail: [email protected]).

Contents OPTIMIZATION代写

1.OpeningRemarks 3

2.Farkas’ Lemma and the Theorems ofthe Alternative 3

2.1Some opening historical remarks forLinear Optimization 3

2.2Fourier’s Approach to Solving Systems of Linear Inequalities 10

2.3Example of Fourier Elimination withTwo Variables: 11

3.Duality Theorems forLinear Optimization 17

3.1WeakDuality Relation 19

3.2StrongDuality Theorems 20

3.3Complementary Slackness Conditionsand Theorems 22

3.4Duals of LP Problems inGeneral Forms 25OPTIMIZATION代写

3.5General Recipe for theDual Problem 25

4.Polyhedra and ElementaryConvex Geometry 28

4.1Extreme Points of Convex Sets, Internal Structureof Polyhedra 31

4.2Polytopes 33 OPTIMIZATION代写

5.SimplexMethod 36

5.1Lexicographicsimplex method 42

5.2StrictComplementarity Theorem 48

6.CombinatorialOptimization 50

1.OpeningRemarks

This course will provide an introduction to optimization together with a strong foun- dation to continue with more advanced undergraduate work, graduate work as well as research work.OPTIMIZATION代写

We will make a mathematical introduction to various topics in optimization in this high-pace, theoretically oriented course. Successful completion of this course would satisfy most of the prerequisites for all 400, 400/600 level optimization courses in C&O. Those are co45*, co46*, co47*.

2.Farkas’ Lemma and the Theorems of theAlternativeOPTIMIZATION代写

2.1Some opening historical remarks for Linear Optimization.

The history of Linear Optimization (or Linear Programming) is connected to various areas of  math-  ematics, operations research and mathematical economics.The applications  (both  in  practice and theory) are far reaching and are significantly beyond the disciplines where it originated.OPTIMIZATION代写

George B. Dantzig [1914–2005] is widely admired as the Father of Linear Programming. He proposed the Simplex Method in the 1940s. See his seminal book on the subject [?]. Dantzig’s father, T. Dantzig, was also a mathematician who worked with Henri Poincar´e. George Dantzig completed his Ph.D. with J. Neyman (recall Neyman-Pearson Lemma in Statistics) at UC Berkeley.OPTIMIZATION代写

The name Programming in Linear Programming does not refer to computer program- ming. When Dantzig was working for the U.S. Air Force at the Pentagon during the late 1940s, he was trying to mechanize (his choice of the word) the preparation of plans to move troops, supplies, training etc. At that time in the military terminology, program- ming meant preparing plans and proposed schedules. (They used computer code as we still do to refer to software.)

Together with Dantzig,

two other main contributors, John von Neumann [1903–1957] and Leonid Kantorovich [1912–1986] stand out as the main founders of the theory of linear optimization in the first half of the 20th century.

Linear Programming (LP) problem can be defined as the problem of optimizing (mini- mizing or maximizing) a linear function of finitely many real variables subject to finitely many linear equations and inequalities.OPTIMIZATION代写

Since the 1940’s Simplex Method has been a great success in all fronts: theory, appli- cations and efficient computations. Many variants of Dantzig’s original algorithm have been proven to have the finite termination property, many successful pivot rules for gen- eral LP problems and for special ones, e.g. network flow problems, have been proposed and studied in some detail.  Very  many practical problems, from production scheduling to managing oil refineries, have been successfully modeled as LP problems and solved by variants of the simplex method.

On the theoretical side,OPTIMIZATION代写

many extensions to multi-objective optimization, nonlinear pro- gramming etc. created very important fields. In the mid 1960’s and the early 1970’s there was a great deal of interest sparked by some optimizers and some theoretical computer scientists. The interest was in classifying computational problems as relatively easy and relatively hard with respect to  some sound mathematical  framework.  As these  thoughts  led to the development of the theory of NP-completeness and many deep extensions, the  optimizers wanted to know whether the most commonly  known  optimization  problem  Linear Programming was solvable in polynomial-time or not. As a result, LP played an important role in inspiring research work in Computational Complexity and to date it con- tinues to be very influential in the theory and practice of various areas in Mathematics, Statistics and Computer Science, in addition to its obvious impact on applications.

Theorem 1. (Fundamental Theorem of Linear Algebra) Let A Rm×n, b Rm be given. Then exactly one of the following systems has a solution:

  • Ax =b;
  • ATy = 0, bTy ƒ=0.
Notes:
  • Wemay replace bTy ƒ= 0 with bTy 1 (or any other non-zero constant) because y can be scaled as needed to match any constant.
  • Forthis course, every vector is assumed to be a column
  • Since every operation requires appropriately dimensioned vectors, when it is not statedexplicitly the vectors’/matrices’ dimensions can be assumed to  For example the 0 vector in ATy = 0 above must be n dimensional.
  • All equalities and inequalities mean all elements of the vector/matrix hold equal- ity/inequality simultaneously.OPTIMIZATION代写

An alternate statement (with a geometric interpretation below) of the Fundamental Theorem of Linear Algebra is as follows:

Let A Rm×n, b Rm be given. Then exactly one of the following statements is true:

(I)b Range(A);

(II)∃a vector in Null(AT) which makes a nonzero inner product with b.

The above is an equivalent statement to the original Fundamental Theorem of Linear Algebra. By definition, b Range(A) (range is also known as column-space, and means the set of vectors composed by a linear combination of the columns of matrix A) iff x such that Ax = b. Similarly, in (II), by definition of the nullspace (the set of vectors x such

that Ax = 0) the statement is essentially a rewritten version of the original theorem. This alternate version is particularly interesting because geometrically if b can be expressed as a linear combination of columns of A then we clearly have a solution (the coefficients of the linear combination), and when b cannot be expresses only as a linear combination of the columns of A then the orthogonal projection of b onto the nullspace of AT  is nonzero and the inner product of this projection (which is our y in this context) with b would also be nonzero.OPTIMIZATION代写

There are constructive proofs (proofs which give algorithms) for this theorem,

for ex- ample a careful implementation of Gaussian elimination. After the row  reduction  stage we would have enough information to either solve the system or recover a certificate of infeasibility.

Fundamental Theorem of Linear Algebra has the following analogue for the linear sys- tems which include linear inequalities:

Theorem 2. (Farkas’ Lemma) Let A Rm×n, b Rm be given. Then exactly one of the following systems has a solution:

(I)Ax = b, x ≥0;

(II)ATy ≥ 0, bTy <0.

In the above statement, we may replace “bTy < 0” by “bTy 1” or by “bTy  1.” The above result is deeply connected to linear optimization. Let’s start with an example: Consider the following two-person zero-sum game. There are two players: ρ and γρ secretly chooses a strategy (a number) i  {1, 2} and γ secretly chooses a strategy (anumber) j  {1, 2, 3}. Both players simultaneously reveal their strategies i and j. Basedon these values they pay each other the following amounts (below given 2-by-3 matrixdenotes payments in dollars to the player γ by ρ):

10  30 40

25 60   40

If ρ chooses 1 and γ chooses 2 , from the matrix above the payout is -30, meaning that γ pays ρ, 30 dollars.OPTIMIZATION代写

Since we  know that both players  are very smart,

we  will apply a ’mixed strategy’ for player γ.  Player  γ  chooses j  with probability xj.  So if ρ  chooses 1,  γ  will receive  10x1 30x2 + 40x3 dollars. If ρ chooses 2, γ will receive 25x1 + 60x2 40x3 dollars. Thus, γ wants to maximize the minimum of {10x1 30x2 + 40x3, 25x1 + 60x2 40x3}.Introduce the new variable x0.  γ’s problem becomes:

Maximize x0

subject to: 10x1  30x2 + 40x3  x0,

25x1 + 60x2  40x3 x0, x1 + x2 + x3 = 1,

x1  0,

x2  0,

x3  0.

The other player, ρ’s problem is:

Minimize y0

subject to: 10y1  25y2  y0,

30y1 + 60y2  y0,

40y1  40y2 y0, y1 + y2 = 1,

y1  0,

y2  0.

Let us generalize the above game to an arbitrary number of strategies for each player. Fix integers m, n 2. m is the number of strategies (moves) for ρ and n is the number of strategies for γ. An m-by-n matrix A, completely known to both players, determines thepayoff to γ  by ρ.  (The negative entries denote the payment to ρ by γ—recall the  term zero-sum game.) The matrix A is called the payoff matrix.

Similar to the above,

ρ secretly chooses a strategy (a number) i  {1, 2, . . . , m} and γ secretly chooses a strategy (a number) j  {1, 2, . . . , n}. Both players simultaneouslyreveal their strategies i and j. As a result, ρ pays γaij dollars. (Again, if aij < 0, then γ pays ρ, aij dollars.)

Note that the model has applications way beyond two people gambling with their money.   For  example,  each player  may  correspond to a company in a given sector,  i {1, 2, . . . , m} and j  {1, 2, . . . , n} may represent the marketing and or pricing strategies for  the respective companies. Alternatively,  players may  represent governments,  i  {1, 2, . . . , m} and j ∈ {1, 2, . . . , n} may represent some diplomatic strategies (and/or other moves) for the respective governments.

Let us assume that the players engage in this game many many times and let xj denote the probability that γ plays j. We want to compute the optimal mixed strategy for γ.(To maximize her winnings, how often should she play strategy j?) Then x  Rand nj=1xj = 1. Assuming ρ is smart, we can expect that ρ will choose the strategy for himself that is the best for him in this situation:

argmini {(Ax)i} .

Therefore, γ’s problem is to maximize this minimum value which can be expressed as a linear optimization problem:

max x0

s.t.

1x0 + Ax    0,

1Tx = 1,

x    0,

where we denoted by 1 the vector of all ones of appropriate dimension (size m or n

depending on the context here).

min y0

s.t.

1y0 + ATy  0,

1Ty = 1,

y  0

which is ρ’s problem for the same game!  Hence the connection between LP duality theory and Game Theory for Two-Person Zero-Sum Games.

2.1.1Somefurther historical remarks.

 Just as Dantzig was developing his ideas on Linear Programming, independently of Dantzig, von Neumann was working on Game Theory.

The first meeting between Dantzig and von Neumann is well covered in the literature, including an account of it by Dantzig himself.

Game Theory had many excited supporters; however, there were also a few who were very critical of its assumptions. Mathematician Norbert Wiener [1894-1964] who is con- sidered a founder of cybernetics was also a kind of a nemesis of John von Neumann [1903-1957]. Perhaps in our 21st century language, they were frenemies. Wiener pro- moted a continuous and analog view of the World. von Neumann, although famous for many variational results, seems to have  favored discrete and algebraic approaches more in his work and his mathematical modelling. Apparently, Wiener once criticized von Neumann’s work in Game Theory by stating:  “von  Neumann’s  picture  of  a  player  as  acompletely intelligent, completely ruthless person is an abstraction and a perversion of the facts.

2.1.2Definition of Linear Programming (LP) problems.

The above example is a linear programming problem(LP).

A function f : Rn  R is called an affine function, is there exist a  Rn and α  R such that f (x) = aTx + α. An affine function is linear if α = 0.

A linear constraint is any of the following

f (x g(x)

f (x) = g(x)

f (x g(x),

where f, g are affine functions. (The first and the last are linear inequalities; the middle one is a linear equation.)

We are ready to define the set of optimization problems called Linear Programming problems.

Linear Programming (LP) problem is the problem of optimizing (maximizing or min- imizing) an affine function of finitely many real variables subject to finitely many linear equations and linear inequalities on these variables.

Note that the inequalities are never strict inequalities, so would be used, not <. At certain points in our discussion we will address strict inequalities as well; but, if some strict inequalities are present, the optimization problem is not an LP. As we develop the theory, we will mostly focus on LP problems in

(1)standard inequalityform

Max cTx

s.t. Ax  b,

x 0,

(2)standard equalityfrom

Max cTx

s.t. Ax b,

x 0,

where A Rm×n, b  Rm,  and c  Rn.  Every LP problem can be put into the above  forms.

x¯  Rn  satisfying all constraints is called a feasible  solution.  A feasible solution xˆ  Rn such that it has the best objective value among all feasible solutions, is called an optimal solution.  E.g., for the maximization problems above, it is a xˆ feasible in the corresponding problem such that cTxˆ  cTx feasible solutions x.

For the problems in standard equality form, we will typically assume rank(A) = m.

This assumption can be made without loss of generality, for solving LP problems. (We first solve the linear system of equations Ax = b. If rank(A) < m, then either Ax = b has no solution—then the LP is infeasible—or we find all the linearly dependent equations inAx b and eliminate them; we then have a linear system A˜x = ˜b whose solution set isthe same as that of Ax b and A˜ has full row rank.)

2.1.3.An Integer ProgrammingProblem.

Integer Programming (IP) problems are ob- tained from LP problems by requiring a nonempty subset of variables to be integers. InIP formulations in addition to the linear constraints (as defined above), we allow the following:

xj Z, x Zn, xj ∈ {0, 1}, x ∈ {0, 1}n.

As an example, consider the following problem:

A new university, SPIT (Smart People’s Institute of Technology), was established near the North Pole. Even though the buildings have been used for only a few years, because of the harsh weather conditions there is a need for renovation. The university planning committee is to decide on how to assign three functions (laboratory, library, tennis courts) to three available buildings (Building A,B,C). Cost of renovation for each of the nine possible matches of a building with a function/activity is given below (in millions of dollars):

Lab Lib Tennis Co
Building A 6 1 2
Building B 7 6 5
Building C 6 2 4

How can the university planning committee assign functions to the buildings so as to minimize the total renovation cost?

Let’s generalize to n buildings and n functions (for a given integer n  3).  Let cij

denote the given cost for renovating building i to serve the function/activity j. We define

2.1.4.A Nonlinear ProgrammingProblem.

Consider Fermat’s Last Theorem: There do not exist positive integers x, y, z and an integer n 3 suchthat

xn yn = zn.

Next consider a nonlinear optimization problem with four variables:

inff (x1, x2, x3, x4) := (xx4 + xx4  xx4 )2+(sin(πx1))2+(sin(πx1))2+(sin(πx1))2+(sin(πx1))subject to:

x1 1, x2 1, x3 1, x4 3.

It is not difficult to prove that the infimum above (the optimal value of the nonlinear programming problem) is zero. However, proving that this optimal value  is not attained is equivalent to proving Fermat’s Last Theorem.

2.2Fourier’s Approach to Solving Systems of Linear Inequalities.

Let’s go back to studying LP problems.  How  do we  determine whether an LP has a feasible solution? Itturns out that the question is essentially equivalent to solving for an optimal solution.

Without loss of generality, we may assume our system is Ax  b, with A  Rm×nb  Rm.

Next, we ask: Can we eliminate a variable? If we can, and generate another system of linear inequalities, we might be able to keep reducing the number of variables until we end up with a trivial problem to solve.

Notable work on solving systems of linear inequalities goes back at least to Joseph Fourier (recall Fourier series and Fourier transform) [1768–1830]. Fourier’s paper from 1826 addresses systems of linear inequalities.  Related work of Theodore Motzkin [1908– 1970] in 1936 popularized the results. Fourier elimination eliminates the variables one  at a time, incurring a potential cost of roughly squaring the number of linear inequalities in the worst-case. Most importantly, these results lead to a finite algorithm for solving systems of linear inequalities and in the case that the original system is infeasible, the method provides an infeasibility certificate (as in Farkas’ Lemma).

Let  A  Rm×n,  b  Rm    be given. Suppose we want to solve the system of linear inequalities

Ax b.

Here,  solving  means  either  find  xˆ   Rn   such  that  Axˆ   b  or  prove  that  Ax   b  is  not solvable.  The main idea is to focus on one variable at a time, say  xn, and eliminate it   by possibly introducing many linear inequalities so that the new system is feasible iff the old system was.

To this end, let J ⊆ {1, 2, . . . , m} denote the index set of the original inequalities in which the coefficient of xn is negative. Let J+ ⊆ {1, 2, . . . , m} denote the index set of the original inequalities in which the coefficient of xn is positive. (For the sake of simplicity of our presentation, we assume J ƒ=  and J+ .) Let J0 denote the index set of the remaining inequalities.

By definition, xn does not appear in the inequalities indexed by J0. Then the role of xn in the original system is completely explained by

 

Now,

we can conclude that the original system is feasible iff there exists an assignment of values to x1, x2, . . . , xn1 such that LB U B and all the inequalities in J0 are satisfied. The latter two conditions only involve the variables x1, x2, . . . , xn1. So, if we can express the condition LB  U B as a finite system of linear inequalities on these (n  1) variables, then we are in business!

Indeed, this is possible. For each pair (A, k) for A J and k J+, we  write  the inequality

OPTIMIZATION代写
OPTIMIZATION代写

This leads to a linear system of (|J0| + |J| · |J+|) inequalities in (n 1) variables. Continuing with this idea, we can reduce the initial system to a system of linear inequalities on a single variable for which both LB and U B become constants that we can compute. Note that each new linear inequality generated by this method is a nonnegative linear combination of the linear inequalities in the original system. Thus, if we find at the end that LB > U B, this observation leads to an algebraic proof of infeasibility of the original system.

2.3. Example of Fourier Elimination with Two Variables:

Ax b

is give below:

So, using one step of Fourier  Elimination, we  start with a linear system of inequalities    Ax b in n variables and produce a system of linear inequalities Ajxj bj in (n 1) variables. In particular, in the above example we have 2 x1 2, thus a feasible solution to the original system of inequalities is x¯ = (1, 0)T.

In general, we have

Lemma 3.

The system Ax b is feasible iff Ajxj bj is feasible. Moreover, every feasible  solution  (x¯1, x¯2, …, x¯n1)T  of  Ajxj    bj  can  be  extended  to  a  feasible  solution (x¯1, x¯2, …, x¯n1, β)T of Ax  b, for some β  .

Proof.  We  proved  above in deriving the system Ajxj bj that every linear inequality in    the new system is a consequence of linear inequalities of the original system Ax b. (The inequalities in J0 are identical to those  in  Ax  b,  the  inequality  indexed  by  (A, k)  in Ajxj bj is a nonnegative linear combination of inequalities indexed A and k in Ax b.) Thus, “Ax  b is feasible” implies Ajxj  bj is.

For the converse, note that in the above derivation, the solution set of Ax b and the solution set of the following system

OPTIMIZATION代写
OPTIMIZATION代写

In the above  definitions,  if  J is  empty,  then  LB  :=  −∞ and  if  J+  is  empty,  then U B := +. In any case, since the interval [LB, U B] R is not empty, we can pick any β  [LB, U B R. Q

Remark 4. (Fourier Elimination)

Suppose we are given A Rm×n, b Rm, and we want to solve for Ax b (system of linear inequalities). Fourier Elimination partitions the index set {1, 2, . . . , m} of the rows, into J0, J+, J, and generates a new system of linear inequalities eliminating xn.

(1)For each step of Fourier Elimination wewould compute

So, in each iteration, we have

LB(x1, x2, . . . , xj1) xj U B(x1, x2, . . . , xj1),

with the convention that at such an iteration, is J+  is empty,  then U B  := +∞  and if J is empty then LB := −∞. If the system has a solution, then we  will end up in the last iteration with the trivial system of linear inequalities

LB x1 U B,

where U B LB. Therefore, setting x1 to any value in [LB, U B] R will solve this system.  So, we choose such a value for x1, call it x¯1  and go to the previous iteration.  Now we plug in the value x¯1 and end up with another trivial system:

LB(x¯1 x2  U B(x¯1).

We choose x¯2  [LB(x¯1), U B(x¯1)]  R and continue .  .  .

choose x¯j  [B(x1, x2, . . . , xj1), U B(x1, x2, . . . , xj1)]  R

…  until we have the whole x¯.  (Note that we have been applying Lemma 3.)

(2)In the new system of inequalities, all the new rows generated are nonnegative linear combinations of previous rows. In particular, the inequality generated from  A Jand k J+ in the first iteration, is precisely   1   .the Ath row of Ax  bΣ +  1 .the kth row of Ax bΣ .

Moreover,

nonnegative  linear  combination  of  nonnegative  linear  combinations  of   the system Ax b is  a  nonnegative  linear  combination  of  the  system  Ax  ≤  b. Let’s verify. Let u, v  Rm and consider the linear inequalities

and

uTAx  uTb

Further let α, β be nonnegative real numbers. Then, the inequality

αuTAx + βvTAx αuTb + βvTb

is

wTAx wTb,

where w := αu + βv. Since u, v are both nonnegative vectors and since α and

β are nonnegative real numbers, w is a nonnegative vector and hence, the linear inequality

αuTAx + βvTAx αuTb + βvTb

is a nonnegative linear combination of inequalities in Ax b.

Therefore, every new inequality generated during a run of Fourier Elimination can be expressed as wTAx wTb for some w Rm.

(3)As in Gaussian Elimination, the computation of Fourier Eliminationcorresponds to pivoting of rows. In Gaussian Elimination we can use any number as the coefficient of the linear combination, however in Fourier Elimination we restrict ourselves to positive numbers to preserve the direction of inequality.

Theorem 5.

Let A Rm×n and b Rm. Then, exactly one of the following has a solution:

(I)Ax b;

(II)ATu = 0, u 0and bTu < 0.

Proof. Suppose that both systems have solutions (we are seeking a contradiction). That is, x¯  Rn  such that Ax¯  b, and u¯  Rmu¯  0 such that ATu = 0 and bTu < 0.

Claim 1. (I) and (II) cannot both have solutions.

A contradiction!

Therefore, (I) and (II) cannot both have solutions.

Claim 2.

¬(I) (II) Suppose (I) has no solution, then we apply Fourier  Elimination to Ax b. By the last lemma and Remark 4. part (2), at the last iteration of Fourier Elimination we obtain the following inequality:

After we go through the Fourier Elimination, we will eliminate all variables x1, . . . , xn. Thus we will be left with 0Tx γ, Here γ is the difference between lower and upper bound on x1, and hence γ < 0.  Therefore, we have u¯  such that ATu = 0, bTu¯ = γ < 0.  i.e.

(II) has a solution.

Remark  6. (1) Given the appropriate x for (I) or u for (II) in the previous theorem,  these claims (solvability or non-solvability) are very easy to verify, for computers or for your boss!

(2)Such a theorem is called a Theorem of theAlternative.

Theorem 7.

(Another Theorem of the Alternative) Let A Rm×n and  b  Rm.  Then, exactly one of the following has a solution:

(I)Ax b, x 0;

(II)ATu 0, u 0, and bTu <0.

Proof.  Let A˜ := Σ A Σ, ˜b := ΣbΣ.  Now, we apply the previous theorem to A˜ and ˜b.Bydefinition,  A˜x   ˜b  iff  Ax   b  and  x   0.  For  the  alternative  system  (note  that  A˜ has (m + n) rows and so does the u vector in this case),

A˜Tu = 0, u  0, ˜bTu < 0 ATv  w = 0, v  0, w  0, bTv < 0

⇐⇒ ATv 0, v  0, bTv < 0, 

where we  denoted the first m  components of u  by  v  and the remaining n components of u by w.

Remark 8.

A˜ := Aand ˜b :=b .  Then, apply Theorem 7 to the pair A˜, ˜b.b

As we will see soon, these theorems are sufficient to establish much of Duality Theory for linear optimization.

The result known as Farkas’  Lemma [?] mentioned in the first lecture, came in during the early 1900’s. Hermann Minkowski [1864–1909] also had similar results in his pioneering work on Convex Geometry.

There are many related results involving different forms of inequalities, some using strict inequalities. See below the theorems by Gordan and Stiemke.

Theorem 9.

 (Gordan’s  Theorem  [1873]) Let  A Rm×n  be  given.  Then exactly one of  the following systems has a solution:

(I)Ax >0;

(II)ATy = 0, y 0, y ƒ= 0.

Theorem 10. (Stiemke’s Theorem [1915]) Let A Rm×n be given. Then exactly one of the following systems has a solution:

(I) Ax = 0, x > 0;

(II) ATy 0, ATy ƒ= 0.

 3.Duality Theorems for LinearOptimization

Let us start with an example.

Example 11. Consider

(P )   max  z(x) := 2x1 +x2

x1 2x2 2 4x1 +2x2  10

x1  0

x2  0.

Consider x = Σx1Σ := Σ 0 Σ is clearly a feasible solution.

Its objective value is Σ2 1Σ · Σ 0 Σ = 10.

Claim 1. x is an optimal solution.

Consider the matrix representation of constraints of P :

OPTIMIZATION代写
OPTIMIZATION代写

Note:  This is a consequence of previous inequalities, i.e., x such that Ax  b  u¯TAx u¯Tb.  (Note that converse doesn’t necessarily hold.)

Here, we proved that x  R2  which satisfies all the constraints also satisfy:

z(x) = 2x1 + x2  10.

Moreover, x achieves the objective function value of 10.

x is indeed optimal!

Remark 12. (1) In other words, for x Rn, if z(x) > 10, then x is not a feasible solution of the above LP.

(2) In fact, we will show that we can do this for all LP problems which have optimal solutions!

Now we give a graphical representation of this example in Fig. 1.

A few notes on this example:

  • The shaded area is called feasible region which is the set of all feasible
  • Optimal solution is attained at an extreme point of the feasible region. (We will provethis is always the case for LP s in either standard )
  • Theobjective function vector is a non-negative linear combination of the constraint vectors. (We will prove this, )
  • In this case, xis the unique optimal solution. However, in general, optimal solution may not be  A small modification of our example can result in infinitely many optimal solutions. For example, let z := 0 or z := 4x1 + x2 instead.

An LP problem is unbounded if for every M R, there exists a feasible solution of the LP whose objective value is better than M .

Given a set S Rn, we say that S is bounded if there exists a positive real number M

such that

S ⊆ {x Rn : M 1 x M 1} .

If no such M exists, we say that the set S is unbounded. Note that an LP problem being unbounded is not equivalent to the statement that the feasible region of the  LP  problem  is unbounded. In fact, some LP problems may have optimal solution(s) even if their feasible regions are unbounded.

In general, an LP problem can:

  • have an optimal solution orsolutions,
  • beinfeasible,
  • beunbounded,

and these are the three only possibilities.

3.1Weak Duality Relation.

Let A Rm×n, b Rm, c Rn be Consider,

Max cTx

s.t. Ax  b,

x 0.

We call this the primal problem (P ).

Then we define its dual problem (D), based on the same data (A, b, c):

Min bTy

s.t. ATy  c,

x 0.

Then we have

Theorem  13.OPTIMIZATION代写

  (Weak  Duality  Relation)  For  every  feasible  solution  x¯ feasible solution y¯ of (D), we have of (P ) and every

cTx¯  bTy¯.

Proof.  Suppose x¯ and y¯ are feasible solutions of (P ) and (D) respectively.  Then

cTx¯  (ATy¯)Tx¯ = y¯T(Ax¯)  y¯Tb bTy¯,

where  the  first  inequality  follows  from  ATy¯  c, x¯   0;  the  first  equation  follows  frommatrix transposition and the associativity of matrix multiplication; the second inequalityfollows from Ax¯  b, y¯  0; finally, the last equation is just the transpose of a scalar being equal to itself.

Corollary  14.

  If x¯ and y¯ are feasible solutions of (P and (Drespectively and

cTx¯ = bTy¯

then x¯ is optimal in (P and y¯ is optimal in (D).

Proof. Forevery feasible solution x of (P ), by the last theorem, we have

cTx  bTy¯ = cTx¯.

Thus, by definition (of an optimal solution), x¯ is an optimal solution of (P ).

Similarly, for every feasible solution y of (D), by the last theorem, we have

bTy  cTx¯ = bTy¯.

Thus, by definition (of an optimal solution), y¯ is an optimal solution of (D).

Corollary 15. If (P ) is unbounded, then (D) is infeasible.  If (D) is unbounded, then (P )is infeasible.

Proof.  Assume (D) has a feasible solution y¯.  Then, by the Weak Duality Relation, cTx bTy¯, for every feasible solution x of (P ).  Therefore, (P ) cannot be unbounded.

Similarly, assume (P ) has a feasible solution x¯.  Then, by the Weak Duality Relation,bTy  cTx¯, for every feasible solution y of (D).  Therefore, (D) cannot be unbounded. Q

3.2. Strong Duality Theorems.OPTIMIZATION代写

Theorem 16. (A Strong Duality Theorem) Suppose both (P ) and (D) have feasible so- lutions. Then, they both have optimal solutions x, y. Moreover,

cTx = bTy.

Proof.  Suppose x¯ and y¯ are feasible solutions of (P ) and (D) respectively.  Then consider

If this system has a solution, then by a corollary of the Weak Duality Relation, that is Corollary  14,  we  have  x˜,  y˜ feasible  in  (P)  and  (D)  with  cTx˜  =  bTy˜,  and  hence,  we  are done.

We may assume the system has no solution.

By the Theorem of the Alternative, there exist u Rm. v Rn , α R+ such that:

Focus on α.
OPTIMIZATION代写
OPTIMIZATION代写

Lemma 17. If (P) is feasible and (D) is infeasible, then (P) is unbounded.

Proof.  Suppose x˜ is a feasible solution of (P) and (D) is infeasible.  Then ATy  c

y 0has no solution. By the Theorem of the Alternative, d Rn, d 0, Ad 0, cTd < 0. Equivalently, Ad 0, d  0, cTd > 0.

Consider x(λ) := x˜ + λd, where λ  R+. For every λ  R+, x(λ) is a feasible solution of

(P):

OPTIMIZATION代写
OPTIMIZATION代写

Moreover, the objective function value:

˛¸0cTx(λ) = cT(x˜ + λd) = cTx˜ + λ(cTd +, as λ  +.  Therefore, (P) is unbounded.

Theorem 18.

 (A Strong Duality Theorem) If (P) has an optimal solution, then so does (D) and their optimal objective values are the same.

Proof. Since (P) has feasible solution(s), if (D) also has feasible solution(s), then we are done by the previous theorem. If (D) has no solutions, then (D) is infeasible and by the previous lemma we reach a contradiction.

Theorem 19. (Fundamental Theorem of LP) Every LP problem has one of the following properties:

(I)LP has optimalsolution(s);

(II)LP isunbounded;

(III)LP isinfeasible.

Proof. (P) is either feasible or infeasible. If (P) is infeasible, then it satisfies (III).

if (P) is feasible and (D) is infeasible, then by the last lemma, (P) is unbounded. So it satisfies (II).

if (P) is feasible and (D) is feasible, then by The Strong Duality Theorem, (P) has optimal solution(s).  So it satisfies (I).

Note that the dual of the dual of an LP problem is equivalent to the primal problem itself. Possibilities for (P) and (D)

(P) \ (D) has optimal solution(s) unbounded infeasible
has optimal solution(s) X X
unbounded X X
infeasible X

In the above, “X” means “impossible,” “” means “possible.” As a by-product of our work so far,

we proved:

Proposition 20. For every A Rm×n, b Rm and c Rn, the set of primal-dual optimal solution pairs is:

This result also indicates that solving LP problems is equivalent to solving systems of linear inequalities.

3.3ComplementarySlackness Conditions andTheorems.

  Let’s look at the proofof Weak Duality Relation from the point of view of characterizing optimality.

For every feasible x¯ in (P ),  feasible y¯ in (D), we have:

cTx¯  (ATy¯)Tx¯ = y¯T(Ax¯)  y¯Tb.

Then x¯ is optimal in (P ), y¯ is optimal in (D), if and only if:

cTx¯ = (ATy¯)Tx¯ = y¯T(Ax¯) = y¯Tb.

Thus, x¯,y¯ are optimal in their respective problems if and only if:

Definition 21. Complementary Slackness (CS) conditions:

j  {1, 2, . . . , n}, either x¯j = 0 or (ATy¯  c)j = 0, possibly both; and i  {1, 2, . . . , m}, either y¯i = 0 or (b  Ax¯)i = 0, possibly both.

Theorem  22.  Let  x¯ be  feasible  in  (P ),  y¯ be  feasible  in  (D).  Then  x¯ and  y¯ are  optimal in (P ) and (D) respectively, if and only if they satisfy C.S. conditions.

Theorem  23.  (Complementary  Slackness  Conditions)  Let  x¯  Rn   then  x¯  is  optimal  in

(P ) if and only if:

(I)x¯is feasible in (P )

(II)∃y¯ Rm, such that y¯ is feasible in (Dand satisfies S. conditions for x¯

OPTIMIZATION代写
OPTIMIZATION代写

y¯ is feasible in (D).  Therefore, xˆ is optimal in (P ) and y¯ is optimal in (D).

Even though the above theorem can be very useful in many cases, in others, it may be useless. For example, given A  Rm×nc  Rn, consider the following problem called (P ):

Max cTx

s.t. Ax  0

x 0.

Is x¯ := 0 optimal for (P )?

x¯ is at least feasible in (P). Let’s look at the dual problem (D).

Min 0Ty

s.t. ATy  c

y 0.

However,

  • Ax¯= 0  Nothing about y from Complementary Slackness.
  • x¯= 0  Nothing about y from Complementary Slackness.
  • x¯ is optimal in (P ) iff (D) has a feasible Slackness.

3.4Dualsof LP Problems in General Forms.

  Every LP problem can be put into standard inequality from and we defined the dual for the latter, therefore we implicitly defined duals of all LP problems. Now, we make this more concrete.

3.4.1.Transformations.
OPTIMIZATION代写
OPTIMIZATION代写

With y := u  v, we get

min bTy

s.t. ATy  c

y free.

3.5General Recipe for the Dual Problem.

Where the Primal Problem has objec- tive function ”max …”, the Dual has objective function ”min…”.

Primal Dual
i’th constraint is ”” type i’th constraint is ”” type i’th constraint is ”=” type i’th variable is restricted to ” 0” i’th variable is restricted to ” 0” i’th variable is free
j’th variable is restricted to ” 0” j’th variable is restricted to ” 0” j’th variable is free j’th constraint is ”” type j’th constraint is ”” type j’th constraint is ”=” type

We can take this table as the rigorous definition of the dual of an LP problem. Re- call that the dual of the dual of an LP problem is equivalent to the primal problem itself.

Example (for using the general recipe):
OPTIMIZATION代写
OPTIMIZATION代写

Summary of Theorems for LPs in an Arbitrary Form

Theorem 25. (Strong Duality Theorem for general form LPs) Let (P) and (D) be  a pair of primal dual LP problems. Then,

(a)If (P) and (D) both have feasible solutions, then they both have optimal solutions and their optimal objective values are the

(b)If one of (P),(D) has an optimal solution, so does the other and their optimal objective values are the same.

Theorem 26.

(CS Theorem for general LPs) Let (P), (D) be a pair of primal-dual LP problems and letx¯,y¯  be  a  feasible  solutions  for  (P)  and  (D)  respectively.   Then,x¯  is optimal in (P) and y¯ is optimal in (D) iff

(a)∀j, either x¯j = 0 or y¯ satisfies the jth  dual constaint with equality  and

(b)∀i, either y¯i = 0 or x¯ satisfies the ith  primal constraint with equality.

4.Polyhedra and ElementaryConvex Geometry

Figure  Examples of convex sets and nonconvex sets in R2

Definition 27.

 A set S  Rn is convex if  u, v  S and  λ  [0, 1], [λu + (1  λ)v S i.e, for every pair of points in the set, the line segment joining the pair lies entirely in the    set.

It can be seen that if λ is chosen to be 1 then the resulting point will be u and if λ is chosen to be 0 then the resulting point will be v. Any other value of λ will result in a point between u, v. If λ is chosen to be 0.5 then it will result in a point exactly halfway between u, v.OPTIMIZATION代写

Some examples of convex sets are:
  • Empty set,
  • Closed unit ball {x Rn : ||x||2 1}
  • Open unit ball {x Rn : ||x||2< 1}
  • Ellipsoids
  • Linearsubspaces
  • Halfspaces

Example 28. Let A Rm×n, b Rm. Is F := {x Rn : Ax b, x 0} convex?

Let u, v F then,

u 0, v 0, Au b and Av b.

Let λ  [0, 1] consider the vector,

[λu + (1 λ)v] .

 Then,

OPTIMIZATION代写
OPTIMIZATION代写
Proposition 29. Intersection of any family of convex sets is convex. 

Definition 30. S Rn is a polyhedron if it is the intersection of finitely many closed half-spaces.

Closed half-space is defined as: {x Rn : aTx α} for some a Rn, α R.

Remark 31.OPTIMIZATION代写

(1)Feasible regions of LPs are convex.

(2)The set of optimal solutions of LPs are convex.

Let S Rn. Then the convex hull of S is the intersection of all convex sets containingS. We denote it by conv(S).Given  x(1), x(2), . . . , x(k)  Rn, then Σk λjx(j) is called a convex combination of x(1), x(2), . . . , x(k) if λ 0 and 1Tλ = 1.

Proposition 32. S Rn is a convex set iff it contains all convex combinations of its points. 

Note that the above result provides an ”internal” definition for convex hulls.

Proof. (=) Since S contains all convex combinations of its elements, it suffices to apply to every pair of elements, establishing the convexity of S.

(=) We will proceed by induction on the number of points in a convex combination.

k = 1 is trivial.OPTIMIZATION代写

k = 2 follows from the definition of convex set.

Suppose the claim holds for all k A.

Let x(1), …, x(A+1) S, let λ RA+1, 1Tλ = 1. We may assume λ > 0. Then,

Therefore,  xˆ  is  a  convex  combination  of  x(1), . . . , x(A)  and  by  the  induction  hypothesis,xˆ  S.

By  ()  and  the  assumption  that  S  is  convex  (since  xˆ, x(A+1)    S  and  λA+1    (0, 1)),A+1 (i)i=1

Corollary 33. For every S  Rn, the convex hull of S is the set of all convex combinations of elements of S.

Theorem  34.  (Carath´eodory  [1907])  Let  S   Rn.  Then  every  point  in  conv(S)  can  be expressed as a convex combination of (n + 1) or fewer points in S.

Proof.  Let  x¯    conv(S)  and  x(1), …, x(k)    S  such  that  x¯

k i=1λix(i), where λ Rn , 1Tλ = 1.

We may assume k n + 2 and λ > 0.

OPTIMIZATION代写
OPTIMIZATION代写

In the above proof,  we used the observation that the vectors .x(1)Σ, .x(2)Σ, . . . , .x(k)Σ Rn+1  are linearly dependent (since k n + 2). This leads us to a definition:

A set of vectors .x(1), . . . , x(k)Σ  Rn  is affinely independent  if

Affine dependence is defined similarly.OPTIMIZATION代写

Note that x(1), . . . , x(k) Rn is affinely independent iff

x(2)  x(1), x(3)  x(1), . . . , x(k)  x(1)  Rn is linearly independent.

In this statement, choice of x(1) is arbitrary (any x(i) in its place would do). This equiva- lent definition highlights the fact that the notions of affine independence/dependence are invariant under translation of the set by any  point in Rn. Note that the same is not true  for the notions of linear dependence/independence.

4.1. Extreme Points of Convex Sets, Internal Structure of Polyhedra.

Let S ⊆ Rn be a convex set. Then,

x¯ = 1 u 1 v.x¯   S  is  an  extreme  point  of  S  if  $u, v   S\{x¯} such  that

Theorem 35. Let S  Rn  be a convex set.  Then x¯  S is an extreme point of S iff S\{x¯}is convex.

Given x¯  Rn  such that Ax¯  b, denote by A= is the matrix formed by the rows of for which x¯ satisfies x satisfifies (Ax)i bi with equality.

Theorem  36.

  Let  A   Rm×n,  b   Rm,  F  :=  {x   Rn   :  Ax   b},  x¯   F .   Also  let{A=x b=} denote the subset of inequalities in {Ax b} satisfied as equality by

Then, x¯ is an extreme point of F  iff rank(A=) = n.OPTIMIZATION代写

Proof. (): Suppose rank(A=) ƒ= n. Then rank(A=) < n.x¯.

Thus, a linear dependence d Rn\{0} among the columns of A= such that A=d = 0. There exists ε > 0, small enough such that A<(x¯ ± εd b<,

Moreover, A=(x ± εd) = A=x ±ε A=d = b=.

Therefore, x¯ is not an extreme point of F .OPTIMIZATION代写

We will use the following lemma for the remaining part of the proof.

Lemma 36.

(a) Let a, x¯  Rnα  R such that aTx¯ = α.  Then for every x(1), x(2)  Rn, such that aTx(1)  αaTx(2)  αx¯ = 1 x(1) + 1 x(2), we have aTx(1) = aTx(1) = α.

Proof. Let a,x¯,  x(1),  x(2),  α be as above.  Then,

α  1 aTx(1) + 1 aTx(2) = aT Σ 1 x(1) + 1 x(2)Σ = aTx¯ = α.

Since aTx(1) α, aTx(2) α, we  have  aTx(1) = aTx(1) = α. Q

Proof of the theorem continued:

():  Suppose rank(A=) = n.  Further suppose x¯ is not an extreme point of F . (We are seeking a contradiction.)

Then,  x(1)x(2)  F \{x} such that x¯ = 1 x(1) + 1 x(2).OPTIMIZATION代写

By the last lemma, A=x(1) = A=x(2) = b=.

However, rank(A=) = n, which implies A=x = b= has a unique solution, we have three distinct solutions x, x(1), x(2), a contradiction. Q

Corollary 37.

(I)Ifrank(A< n, then F has no extreme 

(II)Thenumber of extreme points of every polyhedron is 

(E.g., in the above case, m is an upper bound on the number of extreme points.)

Definition 38. A polyhedron in Rn is called pointed if it does not contain any lines.

Note that every polyhedron of the form {x Rn : Ax b, x 0} is pointed. So is

{x Rn : Ax = b, x 0}.OPTIMIZATION代写

Recall, every line in Rn  can be expressed as  {λx(1) + (1 λ)x(2) : λ R} for some pair   of points x(1), x(2)  Rn.

Proposition 39. Suppose P Rn is a nonempty polyhedron. Then, P is pointed iff P has at least one extreme point.OPTIMIZATION代写

Theorem 40. If an LP problem has an optimal solution and its feasible region is pointed (i.e. it contains no lines) then the LP problem has an optimal solution which is an extreme point of the feasible region.

Proof. We may assume that our LP is in the form:

Max        cTx

s.t. x F where F := {x Rn : Ax  b}.

Pick an optimal solution x¯ of the LP such that x¯ satisfies as many inequalities of {Ax  bas possible with equality.  We claim that x¯ is an extreme point of F .

Assume  not  (we  are  seeking  a  contradiction). Then  x(1), x(2)    F   \{x¯} such  thatx¯ x(1)+  x(2) .   By  Lemma  36(a),  cTx¯= cTx(1) = cTx(2). Also by this lemma, since

 A=x¯ = b=x(1) and x(2) also satisfy the same equations with equality – that is, they both satisfy A=x = b=.

Now consider the line L going through x(1) and x(2),

that is L := {λx(1) + (1 λ)x(2) : λ  R}.  Recall that x¯  L.  Expanding on the same arguments used before, we observethat  every  point  x   L  satisfies  cTx  =  cTx¯  and  A=x  =  b=.  Since  F  contains no  lines,there is a maximum or minimum value of λ for which λx(1) + (1  λ)x(2)  F :  call it λ¯.Then xj λ¯x(1) + (1  λ¯)x(2) is optimal, but it satisfies at least one more inequality fromA<x  b<  with equality, a contradiction.  Thus x¯  is an extreme point, and the proof is complete.OPTIMIZATION代写

Remark 41.This theorem provides an algebraic characterization of a fundamental, geo- metric object (as we will crystalize in the upcoming theorems). Moreover, it indicates, among other things, a finite (though very silly and inefficient) algorithm to solve LPs; every LP can be solved by putting it into one of the stated forms and enumerating all the extreme points of the feasible region of the reformulation. However, this algorithm does not address detecting unboundedness of the LP at hand (this can be addressed by considering extreme rays of F and obtaining a similar algebraic characterization of them).

4.2. Polytopes.

Definition 42. A bounded polyhedron is called a polytope. Bounded polyhedra are called polytopes.

Note that polytopes are compact (closed & bounded).

Theorem 43. Let F Rn be a polytope. Then, F is equal to the convex hull of its extreme points.

Proof. We may assume F ƒ= . Let {v1), . . . , v(k)} be the extreme points of F (there is at least one, and there are finitely many by Theorem 36).  Let F¯  denote the convex hullof F , i.e.  F¯ := conv{v(1), …, v(k)}.  By definition of convex hull and convexity of F F¯  F .OPTIMIZATION代写

Assume for a contradiction that the other containment is not true, i.e., x¯  F  \F¯.  Now consider the system:

kj=1 kλjv(j) = x¯λj = 1

j=1

λ 0.

This system has no solution due to the internal characterization of convex hulls.  By a  theorem of the alternative (specifically, Farkas’ Lemma), µ Rn, η R such that

Since F is a polytope, F contains no lines and since it is nonempty and bounded, by the Fundamental Theorem of LPs, this LP has an optimal solution(s). By the last theorem,there is an optimal solution that is also an extreme point of F . However, the condition (1) implies that none of the extreme points of F is optimal, which is a contradiction. Thus,

F  F¯. Q

It is also true that:

Theorem 44. Convex hull of any finite set in Rn is a polytope.

For any pair of sets S1, S2 Rn, the Minkowski sum of S1 and S2 is defined by

S1 + S2 := {u + v : u S1, v S2} .

K Rn is a polyhedral cone if it is a polyhedron and it is a cone. In particular, every nonempty polyhedral cone in Rn can be expressed as

K = {x  Rn : Ax  0}

for some A Rm×n, for some positive integer m.OPTIMIZATION代写

Theorem  45. Let  F  Rn  be  a nonempty  pointed polyhedron. Then, there exists a polytope P Rn and a pointed polyhedral cone K Rn such that

F = P + K.

The above decomposition of F is not unique in general. However,  let ext(F ) denote the set of extreme points of of F . Then, we can have a unique decomposition of such F , with P := ext(F ).

S Rn is an affine subspace if there exist, an integer m, A Rm×n and b Rm such that

S = {x  Rn : Ax = b} .

Theorem 46. Let F Rn be a nonempty polyhedron. Then, there exists a polytope

P Rn, a pointed polyhedral cone K Rn, and an affine subspace L Rn such that

F = P + K + L,

where L is the lineality space of F .OPTIMIZATION代写

Similar to the comment we made following Theorem 45, we can take P := ext(F ) in the above theorem.

Related to above characterizations of polytopes, there is a generalization to infinite- dimensional spaces (known as the Krein-Milman Theorem). Below, we state a version of it for Euclidean spaces (definitions of some of the terms below will be covered later in the course, e.g., cl(·) denotes the closure of a set):

Let C Rn be a compact convex set, and let S C. Then, the following are equivalent:

(i)cl (conv(S)) =C;

(ii)inf  hTx : x S = min hTx : x C ;

(iii)ext(C) cl(S).

5.SimplexMethod

We will explain after designing the algorithms the name “Simplex Method.” However, first let’s cover what the word simplex means in this context.

A simplex in Rn is the convex hull of (n+1) affinely independent points υ(1), υ(2), …, υ(n+1) Rn.

Points υ(1), υ(2), …, υ(k) Rn are affinely independent if

Rn+1 are linearly independent. Simplicies in Rn:

We will work with LPs in standard equality form:

(P )  Max cTx

s.t. Ax b,

x 0.

where A Rm×n, b Rm, and c Rn.

Wlog, we may assume rank(A) = m. If not, apply row reduction to [ A|b ] either proving that Ax = b has no solution ((P) is infeasible) or finding redundant equations and then

eliminating these redundant equations from Ax = b.

Given B ⊆ {1, 2, …, n}, we define N = {1, 2, …, n}\B. We write:

A := [A1 A2··An]

B and N give a partition of the columns of A:

AB := [Ai : i B]

AN := [Aj : j N ]

A subset B ⊆ {1, 2, …, n} is called a basis of A if |B| = m and AB is non-singular (i.e. invertible).OPTIMIZATION代写

A basic solution of Ax = b is the unique solution of Ax b .xN = 0

Theorem 47. Let A Rm×n, b Rm such that rank(A) = m. Further let

F := {x Rn : Ax = b, x  0}

and suppose x¯  F .  Then, the following are equivalent:

(i)x¯is a basic feasible solution of Ax b ;x 0

(ii){Ajx¯j > 0} is linearly independent;

(iii)x¯is an extreme point of F .

Moreover, x¯ is a basic feasible solution of Ax b  x 0 iff x¯ is an extreme point of F .

Suppose we are working with an LP problem in standard equality form:

(P ) :  Max  z = cTx

s.t. Ax = b, x  0,

where A is an m-by-n matrix of rank m.OPTIMIZATION代写

Denote A = A1 ….. An , where Ai represents the columns of the matrix A. Let

B ⊆ {1, 2, …, n} be a basis for A and N = {1, 2, …, n}\B, then, we have

OPTIMIZATION代写
OPTIMIZATION代写

Definition 48. feasible basis B of (P ):

A basis B of A such that the basic solution determined by B is a basic feasible solution of {Ax = b, x  0}.

Suppose further that we set xN := 0, then the system

(*) Ax = b ⇐⇒ ABxB + AN xN b

uniquely identifies the current basic feasible solution

(since A1 is non-singular).

x¯ =

x¯B = B

x¯N  0

So, how do we change our current solution to improve the objective value z? Since we

have set xN = 0, if we want to consider other feasible solutions of (*), we have to pick at least one j N and set xj to some nonzero value.OPTIMIZATION代写

Assume k N is the one we pick. To maintain feasibility of the new solution, we must set

xk := α 0.

Moreover, to maintain Ax = b, by the relation

ABxB + Akxk = b,

 

(Note that the LP problem (P ) may not be unbounded.) If the above case does not occur,x¯new  is our new basic feasible solution.OPTIMIZATION代写

How can we be sure that the k  N that we’ve picked actually did improve the objective value z? Let’s take a look at z:

z cTx cTB xB cTN xN ,

by (*), we see that for all basic feasible solutions xB,

z =  cTB A1b  (A1AN xN ) + cTN xN

=  cTB A1b + (cTN   cTB A1AN )xN

Let y¯ be the unique solution to the system:  ATB y cB, then,

z = cTB A1b

= objective valuse of˛t¸he cxurrent solution x¯

+(cTN   y¯TAN )xN

=  constant + ΣjN  c¯jxj,

where c¯jj  N  are the entries of the vector c¯N  := cTN   y¯TAN  and is called the reduced cost of xj with respect to the current basis B.OPTIMIZATION代写

From  the  above,  we  see  that  c¯k  behaves  like  the  partial  derivative  of  the  objective function with respect to xk: c¯k and in order to improve our current solution, we need to choose a k N such that c¯j  j  N .

Claim. If the inequality

c¯k > 0.

holds  (based  on  the  current  index  sets  B,  N),  then  the  current  solution  x¯  is  an  optimal solution for (P).

We provide two proofs here.

Proof. (1)

For all feasible solutions x, recall that

The above proves that the current basic feasible solution x¯ is optimal for (P ).  The abovearguments can be adopted to prove that if c¯j < 0 for every j  N , then the current basicfeasible solution x¯ is the unique optimal solution of (P ).  To see this, notice that for everyfeasible solution of (P ) except x¯, we must have xj  > 0 for some j  N .  Since c¯j  < 0 for every j  N , this implies that for every feasible solution of (P ) except x¯, we have

z < cTx¯.OPTIMIZATION代写

Therefore, x¯ is the unique optimal solution of (P ) in this case.

Proof. (2)

Consider the dual problem of (P):

(D) :   Min bTy

s.t. ATy  c,

y free.

Since ATB y¯ = cB, and by the assumption cTN   y¯TAN   0T, we immediately see that y¯ is a feasible solution of (D). Let’s check if it is an optimal solution. Indeed,

bTy¯ = bT(ATcB) = cTB A1b cTx¯.

Hence,  by  the  corresponding  corollary  of  the  Weak  Duality  Theorem,  x¯  is  an  optimal solution for (P) and y¯ is an optimal solution of (D).

where A  Rm×n, rank(A) = m.

Simplex Method OPTIMIZATION代写

Input A, b, c for an LP in SEF, a basic feasible solution x¯ determined by a basis B  ofA.(A, b, c, x¯, B), N  := {1, 2, …, n}\{B}.

(1)SolveATB y cB.

(2)Computec¯j := cj  yTAj, j  N .

Ifc¯j  0, j  N  then STOP

x¯ is an optimal solution of (P), y is an optimal solution of (D) else pick k N such that c¯k > 0.OPTIMIZATION代写

(4)Solve ABd =Ak,

(5)If d 0 (or, equivalently d¯ 0) thenSTOP

(P) is unbounded (proof:  x¯, d¯)

x(λ) := x¯ + λd feasible in (P), λ  0 and cTx(λ) = cTx λc¯k  + as λ  +

(D) is infeasible (proof: d¯)

d¯ satisfies: d¯ 0, Ad¯ = 0, cTd¯ = c¯k > 0

(6)Pick r B such that dr> 0 and

x¯r dr = min¯xi di : i B, di > 0 =: ¯α

(7)  x¯ := x¯ + α¯d¯

Steps (3) and (6) only mention eligibility rules for entering and leaving indices (k and r). They do not uniquely specify these choices. To make steps (3) and (6) well-defined, consider for example, the Smallest Subscript Rule (also known as Bland’s Rule).

Among all j N such that c¯j > 0 pick k := min{j  N : c¯j > 0}.

Among all A B such that dA > 0 and

OPTIMIZATION代写
OPTIMIZATION代写

Theorem 49. If Simplex Method applied to an LP in SEF, with a starting basic feasible solution,  never  encounters  α¯  =  0,  then  in  at  most  .n Σ  iterations  it  terminates,  either providing optimal solutions for (P) and (D), or a proof that (P) is unbounded and (D) is infeasible.OPTIMIZATION代写

Proof.  There are at most n feasible bases and since α¯c¯k > 0, in every iteration, no basis will be repeated.

Definition  50.  A basic solution  x¯  for Ax  b,  determined by a basis B  of A  is called degenerate  if for some i  Bx¯i = 0.  Otherwise, x¯ is a nondegenerate  basic solution.

We similarly define degenerate basis, degenerate basic feasible solution.

Definition 51. (P) is called nondegenerate if every basis B of A is nondegenerate.

Theorem 52. Simplex Method applied to an LP in SEF, with a starting basic feasible solution, and using the smallest subscript rule (Bland’s Rule), terminates in at most .n Σ iterations.

Proof.  Proof will be provided later, as part of Assignment 3.

Suppose we are using well-defined deterministic rules for the choice of k and r so that the rules are consistent under given basis B, which means if the algorithm picks k and r when B is the current bases, the next time algorithm encounters B as the current basis, it again chooses k and r.

If such implementation of the simplex method dose not terminate, then it must cycle.

For example,the sequence of feasible bases: B0, B1, . . . , Bl, . . . , Bl+q, Bl, Bl+1, . . .

s a  ˛cy¸cle x

leads to cycling. Note that all basic feasible solutions in the cycle here are degenerate, which means that the objective value as well as the basic feasible solution x¯ remains the same.

Hoffman [1953] was the first to construct an example and prove that Simplex Method can cycle. Of course, smallest subscript rules prevent cycling. We will see another, far- reaching idea to remedy the situation next.

5.1.Lexicographic simplex method.

This result goes back to 1951. The mainidea

goes much farther back. Let A Rm×n, b Rm, c Rn be given. Consider,

OPTIMIZATION代写
OPTIMIZATION代写

 

Note that we can view b as the most significant digit and sm as the least significant digit.

When we apply simplex method to (P j), we can compare xiilexicographically.

For a basis B of (P ), we have

XB := hAB1b AB1iin (P j)

in (P0)

Note that even when (P) is degenerate, which means there exists zero entry of A1b, XBdoes not have a zero entry, since this would mean, it has a whole row of zeroes which is impossible as A1is nonsingular. Therefore, (P j) is nondegenerate. Note that this approach induces a strict order among the feasible bases of B.

We have proved the following proposition.OPTIMIZATION代写

Proposition 53. The LP problem (P j) is nondegenerate.

Practical Interpretation: Choose a very small value of s and perturb the right hand side b explicitly, say by randomly chosen positive values for each i, with mean s), then later in the computation, when it is safe, remove the perturbation.

In practice the danger is not cycling but stalling (going through a very long sequence  of degenerate solutions without changing x)

Theorem 54. Lexicographic Simplex Method applied to (P’) terminates in at most n iterations. If it terminates proving (P’) is unbounded  then this leads to a proof that (P)  is unbounded; If it terminates with an optimal basis B for (P’) then B is an optimal basis for (P).

i.e.Solving (P’) solves(P).

Summary:

Degeneracy can lead to:

(i)Cycling (but this turns out not to be a problem inpractice)

(ii)Stalling (this is a potential problem inpractice)OPTIMIZATION代写

Main Idea: Perturb the original problem. We can do this by modifying bi by a small amount, but different amounts for each bi

Remark: Non-degeneracy is generic in the sense that randomly generated LP’s are non-degenerate. One should note however that in practice LP’s are often formulated which are degenerate.

There are two interpretations of this.

1)Theoretical: Lexicographic Simplex Method (we can implement without mentionings’s)

2)Practical: We pick values fors.

e.g., si randomly distributed with mean 1012 and an even smaller variance. (Note that this is not choosing increasing powers of s.)

At this point, we would be forgiven for being a bit skeptical of the Simplex Method. The method is certainly well-known and used widely in practice. We have heard that the method is very efficient but at the present moment, we cannot use it. Remember, the Simplex Method takes us from one basic feasible solution to another. Given a basis B with  basic  feasible  solution  x¯,  the  Simplex  Algorithm  will  choose  a  new  basis  Bj,  withm  1 indices from B and one new index from B’s complement N , and also compute thecorresponding basic feasible solution xˆ.  That is all well and good, but we currently have no way of choosing an initial basis B and its corresponding basic feasible solution.OPTIMIZATION代写

Of course,

we do not want to check through all possible bases until we find a suitable starting point. That would potentially lead to checking all n bases, which would be inefficient and, if we did end up checking all bases, render the Simplex method pointless (as we would have seen all possible basic feasible solutions already, and so we would just pick the one with the largest objective value).  This is clearly not the standard practice,  so how can we efficiently choose a starting basis?

As it turns out, choosing a feasible basis can be reformulated as solving an auxiliary LP problem which has an obvious feasible basis. We can apply simplex method to the auxiliary LP problem to give us a basis B for the original LP problem, then use simplex algorithm on the original LP with B as our initial basis.

To see how this works,

let us start by solving another issue with simplex method. Cur- rently, our method requires an LP problem in standard equality form. Suppose we are given the following LP in standard inequality form.OPTIMIZATION代写

max cTx

s.t. Ax  b x  0.

with b 0. Then we introduce slack variables xn+1, …, xn+m 0 and consider

OPTIMIZATION代写
OPTIMIZATION代写

Note that in thisΣcase, BΣ= {n + 1, n + 2, . . . , n + m} is a feasible basis (we can see this (P )  max cTs.t. Ax = b x  0,

but with no obvious starting basic feasible solution.

We may assume b 0 (since we can multiply rows by 1 if necessary).

Let’s introduce something we will call artificial variables xn+1, . . . , xn+m 0, (unlike when we introduced slack variables above, these artificial variables are not really a part of the problem) and consider the following auxiliary problem (Paux).

Remarks:
  1. B{xn+1, . . . , xn+m} is a feasible basis for (Paux)OPTIMIZATION代写
  2. (Paux)has feasible solutions (see Remark 1). This LP is not  The optimal

objective value is bounded above by zero. Recall that the objective function is equalto Σmmi=1xn+i. All components of x are nonnegative so i=1 xn+i is nonnegative, so always has an optimal solution(s).

  1. (P ) is infeasible iff the optimal objective value of (Paux) is negative. (If the optimal valueof (Paux) is negative, then the optimal solution has nonzero variables from{xn+1, . . . , xn+m}. A better solution would have all nonzero variables come from  the original variables {x1, . . . , xn}. If such a solution cannot be found the original problem must be infeasible.)

This suggests the two phase method.OPTIMIZATION代写

Two Phase Method

0.Givenan LP (P ) in standard equality form, make sure rank(A) = m and b  0

1.Solve (Paux) using simplex

2.Ifthe optimal objective value of (Paux) is negative  (P ) is infeasible, current y¯ is proof.

(Daux)  min bTy

s.t. ATy  0

y ≥ −1

If  y¯  is  an  optimal  solution  of  (Daux)  with  bTy¯  <  0  then  we  have  ATy¯   0 and bTy¯ < 0 (by Farkas’ Lemma, (P ) is infeasible).

  1. We have a basic feasible solution of (Paux) with objective value Therefore,it
determines a basic feasible solution for (P ), say x¯.
  1. Solve(P ) starting with the basic feasible solution x¯ of (P ).

Note that some additional work may be necessary to find a basis B determining the basic feasible solution x¯ in Step 4 (between Phase I and Phase II).

Another Approach: Try to solve OPTIMIZATION代写

(P¯)   max 0Tx (D¯ )   min bTy

s.t. Ax = b s.t. ATy  0

x 0

y¯ := 0 is a basic feasible solution to (D¯ ), so we can apply simplex method to (D¯ ) starting with the basic feasible solution y¯.  At the end of solving (D¯ ) Simplex Method either proves that y¯ is an optimal solution of (D¯ ),  or it proves that (D¯ ) is unbounded.  In the lattercase, the proof of unboundedness of (D¯ ) leads to a proof of infeasibility of (P ) as before. The following is such an algorithm (i.e., an algorithm that applies the Simplex Method to the dual problem; from the point-of-view of the primal problem, it maintains dual feasibility and complementary slackness in every iteration, while striving to reach primal feasibility). Namely, Revised Dual Simplex Method : … OPTIMIZATION代写

The Simplex Interpretation of the Simplex Method (Dantzig) Suppose the given LP is in the form:

(P j) Max z := cTx

s.t. Ax = b Tx = 1 x  0

  • Theform (P j) is general enough that if one has an algorithm to solve (P j) then that algorithm can be used as a black box, relatively efficiently to solve an arbitrary LP problem (P ).
  • Thefeasible region of (P j) is bounded (it is a subset of the unit Simplex), therefore (P j) cannot be
  • Thefeasible regions of (P j) and of the original problem (P ) are not necessarily equal.

The special form of (P j) allows us to interpret its feasible solutions as convex combina- tions of columns of A. In this interpretation, (P j) is feasible iff b is in the convex hull of columns Aj of A. This gives us a way of interpreting and representing solutions x (which are in Rn) in the column geometry given by A and b in Rm.

Therefore, including the objective function, we have a representation of (P j) in Rm+1 as depicted in the following figure.OPTIMIZATION代写
  • The polygon in the above figure is not the feasible region of (P j); but it represents it. Every point in the intersection of the polygon with the line defined by [z, bT]Trepresents a feasible solution of (P j).
  • Thedotted lines connecting points [ cj  ATj   ]T are m-dimensional simplices (they are convex hulls of (m + 1) points). Each such simplex corresponds to a basis. Note that in (P j), there are (m + 1) equations and a basis needs (m + 1) indices. Once a basis is picked, we have the (m + 1) corresponding points [cj, ATj  ]T, for j   B. If the convex hull of these (m + 1) points in Rm+1 intersect the line defined by [z, bT]T, then we have that the basis B defines a basic feasible solution.
  • Thesepoints (corresponding to the Q points in the picture) represent feasible solutions, but they are not feasible solutions themselves.
  • Inthe figure, the algorithm starts from the basic feasible solution determined by the basis B = {6, 7}. Here x6 and x7 are positive (and they add up to one) and
OPTIMIZATION代写
OPTIMIZATION代写
Figure 2. Geometric intuition behind the Simplex Algorithm.

all other xj’s are zero.  In the first iteration, index 7 leaves the basis and index 8 enters the basis. The new basis is B = {6, 8} and it determines a basic feasible solution where x6 and x8 are positive (and they add up to one) and all other xj’s are zero. … Eventually, we arrive at the basis B = {1, 3} which determines the optimal solution where x1 and x3 are positive (and they add up to one) and all other xj’s are zero.

According to Dantzig, this is why he named the algorithm “Simplex Method”, and why he believed it would be efficient.OPTIMIZATION代写

5.2.Strict Complementarity Theorem.

We will conclude with a refinement of the Complementary Slackness Theorem.

Theorem 55 (Strict Complementarity Theorem). Suppose (P ) in standard equality form has optimal solution(s). Then (P ) and (D) have optimal solution x, y, such that for all j  {1, 2, . . . , n}, we have xj (ATy  c)j = 0 and xj  + (ATy  c)j > 0.

Proof. By the Strong Duality Theorem, both (P ) and (D) have optimal solutions with

the same objective value,  say z.  For  each j  ∈ {1, 2, . . . , n},  we will either  construct

an optimal solution x(j) of (P ) with x(j) > 0, or an optimal solution y(j) of (D) with

(ATy(j) c)j > 0. For each j, consider the primal-dual pair of LPs:

(Pj) Max xj

s.t. Ax = b

cTx z x 0

(Dj) Min bTy + zη

s.t. ATy + ηc  ej η  0.

The problem (Pj) has been formulated such that its feasible region is the set of optimal solutions of the original problem (P ). If (Pj) has feasible solution(s) with xj > 0, then we have  an optimal solution x(j)  of (P ), as desired. Otherwise, the optimal objective value  of (Pj) is zero.OPTIMIZATION代写

By  the  Strong  Duality  Theorem,  (Dj)  has  an  optimal  solution  y¯,  η¯ such  that  bTy¯ =zη¯.

Case 1  η¯ =  0.  Then  ATy¯  ej,  bTy¯ =  0.  Take  any  optimal  solution  yˆ of  (D),  and  let y(j)  := yˆ + y¯.  This y(j)  satisfies constraint j  with slack  1, and all others with slack  0.

Case 2  η¯ < 0.  Take y(j) :=   y¯ .  Then ATy(j)  c  1 ejbTy(j) = bTy¯  = zη¯  = z. 

Let B denote the set of indices j for which we constructed x(j), and let N be its

complement. Then, by convexity of the optimal solution sets,

x :=  1 x(j)

|B| jB

y :=  1 y(j)

|N| jN

are desired optimal solutions.  Note that one of B or N may be empty.  If B , then

x = 0.  If N  = , then y is the unique solution of ATy c.OPTIMIZATION代写

6.Combinatorial Optimization OPTIMIZATION代写

Example 56. Assignment Problem

We have a set of jobs J and there is a set of workers W who can perform these jobs and we are given cij  R, i  W, j  J representing compatibility of worker i and job j.  The problem is to assign workers to jobs such that every worker gets one job and every job is assigned one worker and total compatibility of the assignment is maximized.

Let’s formulate as an optimization problem.

OPTIMIZATION代写
OPTIMIZATION代写

Such optimization problem, LPs + integrality constraints on a nonempty subset of vari- ables are called integer programming problems.OPTIMIZATION代写

Sometimes we make a distinction between two types of integer programming (IP) prob- lems.

  • if all variables are required to be integers([pure] integer programmingproblems).
  • if some variables are required to be integers and some are real-valued (mixed integerprogramming).OPTIMIZATION代写

The following is a MATLAB code that generates the LP formulation of the Assignment problem:

G = (V, E),

where G  represents a graph,  V  is the set of nodes in the graphs,  E  is the set of edges in the graph. Edges are sets of pairs of nodes: e {i, j} where e represents edge, i, j  V .

V = {1, 2, 3, 4, 5}

E = {{1, 2}, {1, 5}, {2, 3}, {2, 5}, {3, 4}, {3, 5}, {4, 5}}

Such graphs are sometimes called undirected graphs, and sometimes simply graphs.

A graph is bipartite if there exists a partition [W, J] of V (i.e., W J V, W J ) such that all edges in E have one endpoint in W and the other in J.OPTIMIZATION代写

A matching in G is a subset of edges M such that every node in G is an endpoint of at most one edge in M . A perfect matching in G is a matching in G where |M | = |V | .

Given weights we, e E, optimal matching problem is to find a matching M in G

eMsuch that we is maximized.

Assignment Problem is equivalent to optimal perfect matching problem on complete bipartite graphs.

 A  directed  graph  (diagraph)  is  G˙  =  (V, E˙)  where  the  edges  of  the  graph  e   E˙are directed (such edges are called arcs) and have the form (i, j).

OPTIMIZATION代写
OPTIMIZATION代写

A subset C V in~G = (V, ~E) is called closure if no arc in~G leaves C.

Note that the set V , and empty set are closures.OPTIMIZATION代写

Given weights Cv  R for v  V ,the optimal closure problem is to find a closure C  in G˙ such that cv  is maximized.

A path (directed path, dipath) in a graph is a sequence OPTIMIZATION代写

v0e1v1e2v2…vk1ekvk

where vi  V  and ei  E(or ei  E˙). Sometimes we use the term walk for a path.

A path is called simple if all v0, v1, …, vk are distinct. A path is a cycle if v0 = vk.

A cycle is a circuit if v0, v1, …vk1 are distinct.

NOTE: Our graphs in this course will not have self-loops or parallel edges (arcs) unless explicitly specified. Further note that for directed graphs, arcs (i, j) and (j, i) are different, as a result, they are not considered parallel arcs in this context.

A simple path in G (or in G˙) is a Hamiltonian path  if {v0, v1, …, vk} V .

A  circuit  in  G  (or  G˙)is  a  Hamiltonian  cycle  (or  equivalently,  Hamiltonian  circuit)  if {v0, v1, …, vk1} = V .

Suppose we are given costs ce, e  E(ore  E˙).OPTIMIZATION代写

Shortest path problem is to find a simple path from some node s V to some nodes t of minimum cost.

For example, the costs can be the time needed to complete a task.

Longest path problem is to find a simple path from s V to t V of maximum cost. It can be used to find the bottleneck in completing a task(the costs are the times) or to determine which task consumes the most amount of resources.

NOTE: If the costs are ce  0e  E(e  E˙)and the shortest path problem is very easy, the longest path problem is NP-hard. If ce 0, the shortest path is the difficult one.Finding a Hamiltonian path or Hamiltonian cycle in general is NP-hard. It is because when ce = 1, the longest path problem is to find a Hamiltonian path.

Remark 57. Matching problem can be solved efficiently.

Given an undirected graph G = (V, E), a stable set (independent set)S in G is S V such that i, j  S  implies {i, j} / E.  (I.e.  for every edge in G at most one point can be in a stable set S).

Note that an empty set, or any singleton (the set made up from a single node) is also a stable set.

Given weights wv, v V , the optimal stable set problem is to find a stable set S such that

vS wv is maximized.OPTIMIZATION代写

This problem is NP-hard even when wv = 1, v  V . Let’s formulate the optimal closure problem as an LP:

OPTIMIZATION代写
OPTIMIZATION代写
Given costs ce for all edges (or arcs), the problem of finding a minimum cost Hamiltonian Circuit in G is called the Traveling Salesman Problem (TSP):
  • G = (V, E) symmetric TSP
  • G˙ = (V, E˙ asymmetric TSP

TSP is very popular:

(1)many applications where core problem isTSP

(2)TSPhas been a key example on which most new IP, Combinatorial Optimization techniques are tried.

OPTIMIZATION代写
OPTIMIZATION代写

更多其他:C++代写 考试助攻 C语言代写 计算机代写 report代写 project代写 数学代写 java代写 程序代写 algorithm代写 C++代写 r代写 代写CS 代码代写 金融经济统计代写 function代写

合作平台:天才代写 幽灵代写 写手招聘 Essay代写

 

天才代写-代写联系方式