Optimization Example Sheet 1

F. Fischer Easter 2015

1 Minimize the following functions subject to x > 0:

(a) 3x (b) x2 − 2x + 3 (c) x2 + 2x + 3.
For each of the following functions specify the set Y of values of λ for which the function has a
finite minimum in the region specified, and for each λ ∈ Y find the minimum and all optimal
solutions.
(d) λx subject to x > 0 (e) λx subject to x ∈ R (f) λ1 x2 + λ2 x subject to x ∈ R
(g) λ1 x2 + λ2 x subject to x > 0 (h) (λ1 − λ2 )x subject to 0 6 x 6 M.

2 Show how to Pn 1
minimize i=1 (ai +xi )
Pn
subject to i=1 xi =b
xi > 0 for i = 1, . . . , n.
where ai > 0 for i = 1, . . . , n and b > 0.

3 Maximize n1 log p1 + · · · + nk log pk subject to p1 + · · · + pk = 1, p1 , . . . , pk > 0, where

n1 , . . . , nk > 0 are given. (Note that the optimal solution is the maximum likelihood estimator

n1
n
for the multinomial distribution, p(n1 , . . . , nk ) = n1 ,...,n k
p1 . . . pn k
k .)

4 A probability vector is a vector p = (p1 , . . . , pn )T such that pi > 0 for i = 1, . . . , n and

Pn
i=1 pi = 1. The entropy H(p) of probability vector p is defined as

X
n
H(p) = − pi log pi ,
i=1

where 0 log 0 = 0 by convention. What is the largest and smallest entropy of any probability
vector?

5 Maximize 2 tan−1 x1 + x2 subject to x1 + x2 6 b1 , − log x2 6 b2 , and x1 , x2 > 0, where b1

and b2 are constants such that b1 − e−b2 > 0. (Think carefully about the two cases in which
the Lagrange multiplier for the second constraint is equal to 0 or greater than 0.)

6 Consider the following optimization problems:

maximize cT x subject to Ax = b,
maximize cT x subject to Ax > b,
minimize cT x subject to Ax = b, x > 0,
minimize cT x subject to Ax 6 b, x 6 0.

For each of these problems,

 (i) determine the Lagrangian and the set of Lagrange multipliers for which the Lagrangian
has a finite minimum subject to a possible regional constraint, and write down the dual
problem;
(ii) determine the necessary and sufficient conditions for optimality; and
(iii) verify that the dual of the dual is the primal.

7 Consider the problem to

maximize x1 + x2
subject to 2x1 + x2 6 4
x1 + 2x2 6 4
x1 − x2 6 1
x1 , x2 > 0.
(a) Solve the problem graphically in the plane.
(b) Introduce slack variables x3 , x4 , and x5 and write the problem in equality form. How many
basic solutions are there? Determine the value of x = (x1 , . . . , x5 )T and of the objective
function at each of the basic solutions. Which of the basic solutions are feasible? Are all
basic solutions non-degenerate?
(c) Write down the dual problem in equality form using slack variables λ4 and λ5 , and
determine the value of λ = (λ1 , λ2 , λ3 , λ4 , λ5 ) and of the objective function at each of
the basic solutions of the dual. Which of these basic solutions are feasible?
(d) Write down the complementary slackness conditions for the problem, and show that for
each basic solution of the primal there is exactly one basic solution of the dual such that
the two have the same value and satisfy complementary slackness. How many of these
pairs are feasible for both primal and dual?
(e) Solve the problem using the simplex method. Start from the basic feasible solution where
x1 = x2 = 0, and try both choices for a variable to enter into the basis. How are the
entries in the last row of the various tableaus related to the appropriate basic solutions
of the dual?

8 Consider the problem to

maximize 3x1 + x2 + 3x3
subject to 2x1 + x2 + x3 6 2
x1 + 2x2 + 3x3 6 5
2x1 + 2x2 + x3 6 6
x1 , x2 , x3 > 0.
(a) Use the simplex method to solve this problem.
(b) Explain why each row of the final tableau must be the sum of scalar multiples of the rows
of the initial tableau, and how the multipliers can be determined from the final tableau.
(c) Let P() denote the linear program obtained by replacing the vector b = (2, 5, 6)T by the
perturbed vector b() = (2 + 1 , 5 + 2 , 6 + 3 )T . Derive a formula that describes the
optimal value of P() in terms of  when the entries of  are small. For which values of
1 does the formula hold if 2 = 3 = 0?

2
9 Use the simplex method to

maximize x1 + 3x2
subject to x1 − 2x2 6 4
−x1 + x2 6 3
x1 , x2 > 0.

Explain what happens with the help of a diagram.

10 Use the two-phase simplex method to

maximize −2x1 − 2x2

subject to 2x1 − 2x2 6 1
5x1 + 3x2 > 3
x1 , x2 > 0.

Confirm that the maximum occurs at x1 = 9/16 and x2 = 1/16. Note that the first pivot
column can be chosen such that phase I ends after only one round.

11 Use the two-phase simplex method to

minimize 13x1 + 5x2 − 12x3

subject to 2x1 + x2 + 2x3 6 5
3x1 + 3x2 + x3 > 7
x1 + 5x2 + 4x3 = 10
x1 , x2 , x3 > 0.

12 Consider the problem to

minimize 2x1 + 3x2 + 5x3 + 2x4 + 3x5

subject to x1 + x2 + 2x3 + x4 + 3x5 > 4
2x1 − 2x2 + 3x3 + x4 + x5 > 3
x1 , x2 , x3 , x4 , x5 > 0.

Write down the dual problem and solve it graphically. Then deduce the optimal solution of the
primal.

3
Optimization Example Sheet 2
F. Fischer Easter 2015

1 Consider the three equations in six unknowns given by Ax = b, where

   
2 1 1 1 0 0 2
   
A =  1 2 3 0 1 0 ,
  b= 5 

.
2 2 1 0 0 1 6

(a) Let B = {1, 3, 6} and write Ax = b in the form AB xB +AN xN = b, where xB = (x1 , x3 , x6 )T
and xN = (x2 , x4 , x5 )T , and the matrices AB and AN consist of the appropriate columns
of A. For c ∈ R6 , write cT x = c> >
B xB + cN xN in terms of the non-basic variables by
eliminating xB .
(b) Let c = (3, 1, 3, 0, 0, 0)T . Compute A−1
B and the basic solution with basis B, and write
c x in terms of the non-basic variables. Prove directly from the formula for cT x that the
T

basic solution with basis B maximizes cT x subject to Ax = b and x > 0.

(c) Compare the answer with the answer to question 8 on example sheet 1 and confirm that
the final tableau contained rows corresponding to the equation xB + A−1 −1
B AN xN = AB b.
Is it accurate to say that the simplex method is just a complicated way to invert a matrix?

2 Again consider the linear program in question 7 on example sheet 1 and augment it by the
constraint x1 + 3x2 6 6. Use the simplex method to solve the new problem, letting x2 enter the
basis in the first round. Show that the basic solution where x1 = 0 and x2 = 2 is degenerate.
Use a diagram to explain what happens.

3 Show that adding slack variables to a linear program does not change the extreme points of
the feasible set, i.e., that x∗ ∈ Rn is an extreme point of {x ∈ Rn : x > 0, Ax 6 b} if and only if
∗

for some z∗ ∈ Rm , xz∗ is an extreme point of { xz ∈ Rn+m : xz > 0, Ax + z = b}.

4 Give sufficient conditions for strategies x and y to be optimal for a matrix game with payoff
matrix P and value v, and prove that they indeed guarantee optimality.

5 A matrix game with payoff matrix P is called symmetric if P = −PT . Show that symmetric
matrix games have value 0, and that they may have multiple equilibria.

6 Show that the minimax theorem characterizes the equilibria of a matrix game, i.e., that a
pair of strategies (x, y) ∈ X × Y is an equilibrium of the matrix game with payoff matrix P if
and only if
min
0
p(x, y 0 ) = max
0
min
0
p(x 0 , y 0 ) and
y ∈Y x ∈X y ∈Y

max p(x 0 , y) = min max p(x 0 , y 0 ).

x 0 ∈X 0 0
y ∈Y x ∈X

7 Consider two players who fight a duel. They start 2n + 1 paces apart from each other, each
with a single bullet. In each round, they simultaneously advance one pace and decide whether
to fire a shot or not. The probability of hitting the opponent in round i is i/n. The game ends
after n rounds or when a player is hit, whichever happens earlier. If exactly one player is hit,
that player gets payoff −1, while the other player gets payoff 1. In all other cases both players
get payoff 0. The guns are silent, so neither player knows before the end of the game whether
the other has fired a shot. Show that firing a shot in round 2 is optimal if n = 4, while the
5 5 1
mixed strategy (0, 11 , 11 , 0, 11 ) is optimal if n = 5.

8 Find all equilibria of the matrix game with payoff matrix

 
0 −2 3 0
 
 2 0 0 −3 
P= .
 −3 0 0 4 
 

0 3 −4 0

9 Consider a matrix game with payoff matrix P ∈ Rn×n , such that the entries in every row
and every column of P sum to s. Show that the game has value s/n, for example by guessing
a solution and showing that it is optimal.

10 Consider a matrix game with payoff matrix P.

(a) Show that in finding the value and optimal strategies of the game, we may assume without
loss of generality that P > 0 and thus v > 0. Simplify the LP for computing the value
and optimal strategies by minimizing 1/v instead of maximizing v, and introducing new
variables zi = xi /v for i = 1, . . . , m.
(b) Propose an alternative method for finding optimal strategies that starts from given sup-
ports for these strategies, i.e., sets of actions played with positive probability, and uses
the fact that all of them must yield the same expected payoff. Is this method restricted
to matrix games, or can it be used to find equilibria in any game, assuming they exist?
(c) Apply the two methods to the game with payoff matrix
!
1 4
P= ,
3 2

and discuss which of them requires a greater effort.

11 Find a maximum flow and a minimum cut of the following network with source s and
sink t:
2

4 5
4 2
3
s t
3 2
5 4

2
12 Explain how the Ford-Fulkerson algorithm can be used to find a maximum flow in an
undirected network. Find a maximum flow from s to t in the following network, and prove that
it is indeed optimal:

13 5 7

s 4 10 t
15 12

14 1
2 8 11
6 3
9

13 Show that a bipartite graph G = (L ] R, E) with |L| = |R| has a perfect matching if and
only if |N(X)| > |X| for every X ⊆ L, where N(X) = {j ∈ R : i ∈ X, (i, j) ∈ E}. (The implication
in one direction is obvious. For the other direction, again consider the flow network discussed
in the lecture notes, where a source s is connected to nodes in L and a sink t is connected to
nodes in R, both via edges of capacity 1. Show that if G does not have a perfect matching, then
this network has a cut S with s ∈ S, t ∈ V \ S, and C(S) < |L|. Let LS = L ∩ S, RS = R ∩ S,
and LT = L \ S, and show that the capacity of S is exactly |LT | + |RS |. Use this to prove that
|N(LS )| < LS .)

14 Suppose that a standard deck of 52 playing cards is dealt into 13 piles of 4 cards each. Show
that it is possible to select exactly one card from each pile such that the selected cards contain
one card of each of the 13 ranks Ace, 2, . . . , 10, Jack, Queen, and King. (Consider a graph
with 80 nodes, labeled A, a1 , . . . , a13 , b1 , . . . , b52 , c1 , . . . , c13 , B. For i = 1, . . . , 13, add arcs
(A, ai ) and (ci , B), each of capacity 1. For each i = 1, . . . , 13 add uncapacitated arcs (ai , bj )
and (bj , ci ) for j ∈ Bi , where Bi ⊆ {b1 , . . . , b52 } and |Bi | = 4, such that for all j = 1, . . . , n, bj
has degree 2. Show that the size of a minimum cut separating A from B is 13.)

15 Explain how a network flow problem can be augmented by constraints on the flow through
a vertex. Now consider the following network of one-way streets between locations s and t, in
which both streets and intersections are labeled with their capacities:
7
12 13
10 5 15
25 12
s 30 10 t
5 15
5 11
25
10
10 8 20
10 8
10
15 16

Determine the maximum flow from s to t. Suppose that the capacity constraint of one of the
intersections could be removed completely by building a flyover. For which intersection should
this be done in order to increase the maximum flow as much as possible?

3
16 Use the transportation algorithm to solve the problem given by the following tableau:

10
5 4 3 1
11
5 6 9 3
8
6 3 5
7
3 3 9 14
Note that in finding an initial basic feasible solution, it may be beneficial to deviate from the
procedure described in the lecture notes and instead look for a solution with small cost.

17 A taxi company wants to send n taxis to pick up n customers, one per taxi, in a way
that minimizes the sum of customers’ waiting times. The time required by taxi i to pick up
customer j is tij .
(a) Model this situation as an instance of the transportation problem (no pun intended).
Which additional properties, if any, should a solution satisfy? Is the optimal solution
guaranteed to satisfy these properties? Can the problem still be solved if the number of
taxis exceeds the number of customers?
(b) What happens if we try to solve this problem with the transportation algorithm? Observe
that a solution with overall waiting time zero is always optimal, and show that the set of
optimal solutions does not change if we add or subtract the same value from all waiting
times for a given taxi or customer. Use these insights to solve the problem for waiting
times given by  
5 9 3 6
 
 8 7 8 2 
T =  .
6 10 12 7

 
3 10 8 6

18 The transportation algorithm can be generalized to the so-called network simplex method,
which is able to solve minimum-cost flow problems on arbitrary networks. Consider the follow-
ing network (V, E), in which each edge is labeled with a flow xij , and a triple (mij , mij , cij )
indicating the lower and upper bound and the cost for that edge:
(2, 4, 2)
2
2 3
(1, 4, 0) (1, 4, 3)
(2, 4, 3) 4 5 (1, 6, 2)
(2, 5, 2) (0, 1, 4)
2 1
6
(0, ∞, −6)

Note that the current flow x is associated with a spanning tree (V, T ) of the network such that
xij ∈ {mij , mij } for all (i, j) ∈
/ T , and use this fact to find values for the dual variables λi . Find
all edges that violate dual feasibility, and show that there are two ways of pushing flow along a
cycle of the network such that overall cost is reduced. Now show that for one of them, pushing
the maximum amount of flow results in an optimal solution.