-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy path05.Rmd
148 lines (116 loc) · 7.37 KB
/
05.Rmd
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
# Halting Conditions
We know how to start the simplex method and how to perform the pivot steps. We'll next analyze the
halting conditions for the simplex method.
There are three different places a simplex method can fail:
1. *Phase I returns no feasible solution.*
In this case, the linear program is infeasible. This happens precisely when **the optimal
solution to the auxiliary linear program has $k_0 \neq 0$.**
2. *We cannot find an entering variable.*
In this case, there is no "direction" in the feasible region along which the objective value
increases i.e. we are at a local maxima. Because the objective function is linear this local
maxima is also an absolute maxima (Exercise \@ref(exr:local-to-global)) and provides an optimal
solution to our linear program. None of the variables enter precisely when **none of the
$\bar{c}_i$ are positive.**
3. *We cannot find a leaving variable.*
This means that we can keep on increasing the entering variable, and hence the objective value,
indefinitely without ever leaving the feasible region. None of the variables can leave precisely
when **none of the $\bar{a}_{ij}$ are positive** where $\bar{w}_i$ is entering.
Note that these three halting conditions correspond to the three types of standard linear programs
as seen in the Fundamental theorem of linear programming (Theorem
\@ref(thm:fundamental-theorem-lp)).
| | Halting condition | Linear program type |
| ------------------ | ---------------------------------------------------- | ------------------- |
| End of Phase I | No feasible solution: $k_0 \neq 0$ | Infeasible |
| After a pivot step | No entering variable: $\forall i, \bar{c}_i \le 0$ | Optimal solution |
| After a pivot step | No leaving variable: $\forall j, \bar{a}_{ij} \le 0$ | Unbounded |
::: {.exercise #local-to-global}
(You should only attempt this exercise if you're comfortable with
[convex sets](https://en.wikipedia.org/wiki/Convex_set).) Let $S$ be a convex set in $\mathbb{R}^n$
and let $f : \mathbb{R}^n \to \mathbb{R}$ be a linear function. Show that if $p \in S$ is a local
maxima of $f$ over $S$ then it is also a global maxima. Find a counterexample to this statement if
$S$ is non-convex.
:::
::: {.remark}
The notion of "unboundedness" for linear programs is more restrictive than the
geometric notion of [unboundedness](https://en.wikipedia.org/wiki/Bounded_set). It is possible to
have a linear program whose feasible region is unbounded but the linear program itself is not
unbounded, as seen in the following example.
\begin{align*} \mbox{maximize: } && -x & \\
\mbox{subject to:} && x &\ge 0. \end{align*}
It is not too hard to show that the feasible region of an unbounded linear program is always
unbounded. The above example shows that the converse is not always true.
:::
## Degeneracy
Unfortunately, the above results are insufficient to guarantee that the simplex method will always
find a solution, if one exists. It is possible for the simplex method to get stuck in a loop. This
is called **cycling**.
::: {.exercise}
Give an example showing that the variable that enters in one pivot step can become
leave in the next.
:::
::: {.exercise}
Show that the variable that leaves in one pivot step cannot enter in the next.
:::
We saw in Section \@ref(the-simplex-step) that after a pivot step the entering and leaving variables
get updated as follows: \begin{align*} \bar{x}_j & \mapsto \bar{b}_i/\bar{a}_{ij} \\
\bar{w}_i & \mapsto 0. \end{align*} This increases the value of the objective function by
$\bar{c}_j \bar{b}_i/\bar{a}_{ij}$. The way the entering and leaving variables are chosen, the
constants $\bar{c}_i$ and $\bar{a}_{ij}$ are always positive. The constant $\bar{b}_i$ equals the
value of the basic variable $\bar{w}_i$ and hence must be greater than or equal to 0. This ensures
that the objective value never decreases after a simplex step. If $\bar{b}_i > 0$, the objective
value will increase in this pivot step (and never decrease afterwards) and so we will never return
back to this BFS.
::: {.proposition}
Suppose $\bar{w}_i$ is the leaving variable. If $\bar{b}_i > 0$, the simplex
method will never return to this basic feasible solution.
:::
Hence, the only case when cycling *can* occur is when $\bar{b}_i = 0$. As mentioned above,
$\bar{b}_i$ is the value of the basic variable $\bar{w}_i$. Having more than $n$ variables vanishing
at a BFS is precisely the definition of degeneracy (Definition \@ref(def:degeneracy)).
::: {.proposition}
The simplex method can cycle only if there some degenerate BFS.
:::
Note that this is not an "if and only if" statement. Even if there is some degeneracy, there is no
certainty that the simplex method will always visit a degenerate vertex twice.
::: {.example #cycling}
Consider the following degenerate linear program: \begin{equation*}
\begin{array}{rrrrrrrrrl} \mbox{maximize:} & x_1 & - & 2x_2 & & & - & 2x_4 \\
\mbox{subject to:} & 0.5 x_1 & - & 3.5x_2 & - & 2x_3 & + & 4 x_4 & \le & 0 \\
& 0.5 x_1 & - & x_2 & - & 0.5 x_3 & + & 0.5 x_4 & \le & 0 \\
& x_1 & & & & & & & \le & 1 \\
& x_1 & , & x_2 & , & x_3 & , & x_4 & \ge & 0 \\
\end{array} \end{equation*} The following is a valid sequence of simplex steps:
1. $x_1$ enters and $w_1$ leaves,
2. $x_2$ enters and $w_2$ leaves,
3. $x_3$ enters and $x_1$ leaves,
4. $x_4$ enters and $x_2$ leaves,
5. $w_1$ enters and $x_3$ leaves,
6. $w_2$ enters and $x_4$ leaves.
At the end of the $6^{th}$ simplex step, we end up looping back to the origin.
:::
## Bland's Rule
Cycling is only possible in the presence of degeneracy. At degenerate vertices, we have some freedom
with choosing the set of basic and non-basic variables. This choice is precisely what allows us to
avoid cycling. When we revisit a basic feasible solution that is degenerate, we simply choose a
different entering and leaving variable. One can show that this is always possible and leads to an
algorithm that always halts.
There is another very efficient way for preventing cycling called **Bland's rule**. Bland's rule
says that if there are multiple candidates for the entering/variable then we choose the one with the
smallest index. (We assume that the decision variables have a smaller index than the slack
variables.) One can show that simplex method always terminates if Bland's rule is followed.
::: {.theorem name="Bland's rule" #blands-rule}
The simplex method always terminates provided that both the entering and the leaving variable are
chosen according to Bland’s rule.
:::
::: {.example}
In Example \@ref(exm:cycling), the *sixth simplex step* violates Bland's rule. Both
$x_1$ and $x_4$ can be leaving variables and we choose $x_4$ whereas Bland's rule requires us to
choose $x_1$.
:::
The proof of Theorem \@ref(thm:blands-rule) is beyond the scope of this class. Using Bland's rule
for both phases of the simplex method, we now have a complete algorithm for solving
linear programs. In fact, Theorem \@ref(thm:blands-rule) provides an algorithmic proof of the
Fundamental theorem of linear programming (Theorem \@ref(thm:fundamental-theorem-lp)). By Theorem
\@ref(thm:blands-rule), the simplex method must halt and one of the three halting conditions
mentioned at the start of this chapter must occur as there are no other halting conditions. But this
is precisely the statement of the Fundamental theorem.