# Optimization

### Jump to year

Paper 1, Section I, $\mathbf{7 H}$

comment(a) Let $f_{i}: \mathbb{R}^{d} \rightarrow \mathbb{R}$ be a convex function for each $i=1, \ldots, m$. Show that

$x \mapsto \max _{i=1, \ldots, m} f_{i}(x) \quad \text { and } \quad x \mapsto \sum_{i=1}^{m} f_{i}(x)$

are both convex functions.

(b) Fix $c \in \mathbb{R}^{d}$. Show that if $f: \mathbb{R} \rightarrow \mathbb{R}$ is convex, then $g: \mathbb{R}^{d} \rightarrow \mathbb{R}$ given by $g(x)=f\left(c^{T} x\right)$ is convex.

(c) Fix vectors $a_{1}, \ldots, a_{n} \in \mathbb{R}^{d}$. Let $Q: \mathbb{R}^{d} \rightarrow \mathbb{R}$ be given by

$Q(\beta)=\sum_{i=1}^{n} \log \left(1+e^{a_{i}^{T} \beta}\right)+\sum_{j=1}^{d}\left|\beta_{j}\right|$

Show that $Q$ is convex. [You may use any result from the course provided you state it.]

Paper 2, Section I, H

commentFind the solution to the following Optimization problem using the simplex algorithm:

Write down the dual problem and give its solution.

$\begin{aligned} & \text { maximise } 3 x_{1}+6 x_{2}+4 x_{3} \\ & \text { subject to } 2 x_{1}+3 x_{2}+x_{3} \leqslant 7 \text {, } \\ & 4 x_{1}+2 x_{2}+2 x_{3} \leqslant 5, \\ & x_{1}+x_{2}+2 x_{3} \leqslant 2, \quad x_{1}, x_{2}, x_{3} \geqslant 0 . \end{aligned}$

Paper 3, Section II, H

commentExplain what is meant by a two-person zero-sum game with $m \times n$ payoff matrix $A$, and define what is meant by an optimal strategy for each player. What are the relationships between the optimal strategies and the value of the game?

Suppose now that

$A=\left(\begin{array}{cccc} 0 & 1 & 1 & -4 \\ -1 & 0 & 2 & 2 \\ -1 & -2 & 0 & 3 \\ 4 & -2 & -3 & 0 \end{array}\right)$

Show that if strategy $p=\left(p_{1}, p_{2}, p_{3}, p_{4}\right)^{T}$ is optimal for player I, it must also be optimal for player II. What is the value of the game in this case? Justify your answer.

Explain why we must have $(A p)_{i} \leqslant 0$ for all $i$. Hence or otherwise, find the optimal strategy $p$ and prove that it is unique.

Paper 4, Section II, H

comment(a) Consider the linear program

$\begin{aligned} P: \quad \text { maximise over } x \geqslant 0, & c^{T} x \\ \text { subject to } & A x=b \end{aligned}$

where $A \in \mathbb{R}^{m \times n}, c \in \mathbb{R}^{n}$ and $b \in \mathbb{R}^{m}$. What is meant by a basic feasible solution?

(b) Prove that if $P$ has a finite maximum, then there exists a solution that is a basic feasible solution.

(c) Now consider the optimization problem

$Q: \quad \text { maximise over } x \geqslant 0, \quad \frac{c^{T} x}{d^{T} x}$

subject to $A x=b$,

$d^{T} x>0,$

where matrix $A$ and vectors $c, b$ are as in the problem $P$, and $d \in \mathbb{R}^{n}$. Suppose there exists a solution $x^{*}$ to $Q$. Further consider the linear program

$\begin{aligned} R: \quad \text { maximise over } y \geqslant 0, t \geqslant 0, & c^{T} y \\ & A y=b t \\ & d^{T} y=1 \end{aligned}$

(i) Suppose $d_{i}>0$ for all $i=1, \ldots, n$. Show that the maximum of $R$ is finite and at least as large as that of $Q$.

(ii) Suppose, in addition to the condition in part (i), that the entries of $A$ are strictly positive. Show that the maximum of $R$ is equal to that of $Q$.

(iii) Let $\mathcal{B}$ be the set of basic feasible solutions of the linear program $P$. Assuming the conditions in parts (i) and (ii) above, show that

$\frac{c^{T} x^{*}}{d^{T} x^{*}}=\max _{x \in \mathcal{B}} \frac{c^{T} x}{d^{T} x}$

[Hint: Argue that if $(y, t)$ is in the set $\mathcal{A}$ of basic feasible solutions to $R$, then $y / t \in \mathcal{B} .]$

Paper 1, Section I, H

commentSolve the following Optimization problem using the simplex algorithm:

$\begin{array}{rr} \operatorname{maximise} & x_{1}+x_{2} \\ \text { subject to } & \left|x_{1}-2 x_{2}\right| \leqslant 2 \\ & 4 x_{1}+x_{2} \leqslant 4, \quad x_{1}, x_{2} \geqslant 0 \end{array}$

Suppose the constraints above are now replaced by $\left|x_{1}-2 x_{2}\right| \leqslant 2+\epsilon_{1}$ and $4 x_{1}+x_{2} \leqslant 4+\epsilon_{2}$. Give an expression for the maximum objective value that is valid for all sufficiently small non-zero $\epsilon_{1}$ and $\epsilon_{2}$.

Paper 2, Section II, H

commentState and prove the Lagrangian sufficiency theorem.

Solve, using the Lagrangian method, the optimization problem

$\begin{array}{ll} \operatorname{maximise} & x+y+2 a \sqrt{1+z} \\ \text { subject to } & x+\frac{1}{2} y^{2}+z=b \\ & x, z \geqslant 0 \end{array}$

where the constants $a$ and $b$ satisfy $a \geqslant 1$ and $b \geqslant 1 / 2$.

[You need not prove that your solution is unique.]

Paper 1, Section I, H

commentSuppose that $f$ is an infinitely differentiable function on $\mathbb{R}$. Assume that there exist constants $0<C_{1}, C_{2}<\infty$ so that $\left|f^{\prime \prime}(x)\right| \geqslant C_{1}$ and $\left|f^{\prime \prime \prime}(x)\right| \leqslant C_{2}$ for all $x \in \mathbb{R}$. Fix $x_{0} \in \mathbb{R}$ and for each $n \in \mathbb{N}$ set

$x_{n}=x_{n-1}-\frac{f^{\prime}\left(x_{n-1}\right)}{f^{\prime \prime}\left(x_{n-1}\right)} .$

Let $x^{*}$ be the unique value of $x$ where $f$ attains its minimum. Prove that

$\left|x^{*}-x_{n+1}\right| \leqslant \frac{C_{2}}{2 C_{1}}\left|x^{*}-x_{n}\right|^{2} \quad \text { for all } n \in \mathbb{N} .$

[Hint: Express $f^{\prime}\left(x^{*}\right)$ in terms of the Taylor series for $f^{\prime}$ at $x_{n}$ using the Lagrange form of the remainder: $f^{\prime}\left(x^{*}\right)=f^{\prime}\left(x_{n}\right)+f^{\prime \prime}\left(x_{n}\right)\left(x^{*}-x_{n}\right)+\frac{1}{2} f^{\prime \prime \prime}\left(y_{n}\right)\left(x^{*}-x_{n}\right)^{2}$ where $y_{n}$ is between $x_{n}$ and $\left.x^{*} .\right]$

Paper 2, Section I, H

commentState the Lagrange sufficiency theorem.

Find the maximum of $\log (x y z)$ over $x, y, z>0$ subject to the constraint

$x^{2}+y^{2}+z^{2}=1$

using Lagrange multipliers. Carefully justify why your solution is in fact the maximum.

Find the maximum of $\log (x y z)$ over $x, y, z>0$ subject to the constraint

$x^{2}+y^{2}+z^{2} \leqslant 1$

Paper 3, Section II, H

comment(a) Suppose that $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^{m}$, with $n \geqslant m$. What does it mean for $x \in \mathbb{R}^{n}$ to be a basic feasible solution of the equation $A x=b ?$

Assume that the $m$ rows of $A$ are linearly independent, every set of $m$ columns is linearly independent, and every basic solution has exactly $m$ non-zero entries. Prove that the extreme points of $\mathcal{X}(b)=\{x \geqslant 0: A x=b\}$ are the basic feasible solutions of $A x=b$. [Here, $x \geqslant 0$ means that each of the coordinates of $x$ are at least 0 .]

(b) Use the simplex method to solve the linear program

$\begin{array}{cl} \max & 4 x_{1}+3 x_{2}+7 x_{3} \\ \text { s.t. } & x_{1}+3 x_{2}+x_{3} \leqslant 14 \\ & 4 x_{1}+3 x_{2}+2 x_{3} \leqslant 5 \\ & -x_{1}+x_{2}-x_{3} \geqslant-2 \\ & x_{1}, x_{2}, x_{3} \geqslant 0 \end{array}$

Paper 4, Section II, H

comment(a) State and prove the max-flow min-cut theorem.

(b) (i) Apply the Ford-Fulkerson algorithm to find the maximum flow of the network illustrated below, where $S$ is the source and $T$ is the sink.

(ii) Verify the optimality of your solution using the max-flow min-cut theorem.

(iii) Is there a unique flow which attains the maximum? Explain your answer.

(c) Prove that the Ford-Fulkerson algorithm always terminates when the network is finite, the capacities are integers, and the algorithm is initialised where the initial flow is 0 across all edges. Prove also in this case that the flow across each edge is an integer.

Paper 1, Section I, 8H

commentWhat is meant by a transportation problem? Illustrate the transportation algorithm by solving the problem with three sources and three destinations described by the table

where the figures in the boxes denote transportation costs, the right-hand column denotes supplies, and the bottom row denotes requirements.

Paper 2, Section $I$, H

commentWhat does it mean to state that $f: \mathbb{R}^{n} \rightarrow \mathbb{R}$ is a convex function?

Suppose that $f, g: \mathbb{R}^{n} \rightarrow \mathbb{R}$ are convex functions, and for $b \in \mathbb{R}$ let

$\phi(b)=\inf \{f(x): g(x) \leqslant b\}$

Assuming $\phi(b)$ is finite for all $b \in \mathbb{R}$, prove that the function $\phi$ is convex.

Paper 3, Section II, 21H

commentState and prove the Lagrangian Sufficiency Theorem.

The manufacturers, $A$ and $B$, of two competing soap powders must plan how to allocate their advertising resources ( $X$ and $Y$ pounds respectively) among $n$ distinct geographical regions. If $x_{i} \geqslant 0$ and $y_{i} \geqslant 0$ denote, respectively, the resources allocated to area $i$ by $A$ and $B$ then the number of packets sold by $A$ and $B$ in area $i$ are

$\frac{x_{i} u_{i}}{x_{i}+y_{i}}, \quad \frac{y_{i} u_{i}}{x_{i}+y_{i}}$

respectively, where $u_{i}$ is the total market in area $i$, and $u_{1}, u_{2}, \ldots, u_{n}$ are known constants. The difference between the amount sold by $A$ and $B$ is then

$\sum_{i=1}^{n} \frac{x_{i}-y_{i}}{x_{i}+y_{i}} u_{i}$

$A$ seeks to maximize this quantity, while $B$ seeks to minimize it.

(i) If $A$ knows $B$ 's allocation, how should $A$ choose $x=\left(x_{1}, x_{2}, \ldots, x_{n}\right)$ ?

(ii) Determine the best strategies for $A$ and $B$ if each assumes the other will know its strategy and react optimally.

Paper 4, Section II, H

commentGiven a network with a source $A$, a sink $B$, and capacities on directed edges, define a cut. What is meant by the capacity of a cut? State the max-flow min-cut theorem. If the capacities of edges are integral, what can be said about the maximum flow?

Consider an $m \times n$ matrix $A$ in which each entry is either 0 or 1 . We say that a set of lines (rows or columns of the matrix) covers the matrix if each 1 belongs to some line of the set. We say that a set of 1 's is independent if no pair of 1 's of the set lie in the same line. Use the max-flow min-cut theorem to show that the maximal number of independent 1's equals the minimum number of lines that cover the matrix.

Paper 1, Section I, H

commentSolve the following linear programming problem using the simplex method:

$\begin{array}{r} \max \left(x_{1}+2 x_{2}+x_{3}\right) \\ \text { subject to } \quad x_{1}, x_{2}, x_{3} \geqslant 0 \\ x_{1}+x_{2}+2 x_{3} \leqslant 10 \\ 2 x_{1}+x_{2}+3 x_{3} \leqslant 15 \end{array}$

Suppose we now subtract $\Delta \in[0,10]$ from the right hand side of the last two constraints. Find the new optimal value.

Paper 2, Section I, H

commentConsider the following optimization problem

$\mathrm{P}: \quad \min f(x) \quad \text { subject to } \quad g(x)=b, x \in X .$

(a) Write down the Lagrangian for this problem. State the Lagrange sufficiency theorem.

(b) Formulate the dual problem. State and prove the weak duality property.

Paper 3, Section II, H

comment(a) Explain what is meant by a two-person zero-sum game with payoff matrix $A=\left(a_{i j}: 1 \leqslant i \leqslant m, 1 \leqslant j \leqslant n\right)$ and define what is an optimal strategy (also known as a maximin strategy) for each player.

(b) Suppose the payoff matrix $A$ is antisymmetric, i.e. $m=n$ and $a_{i j}=-a_{j i}$ for all $i, j$. What is the value of the game? Justify your answer.

(c) Consider the following two-person zero-sum game. Let $n \geqslant 3$. Both players simultaneously call out one of the numbers $\{1, \ldots, n\}$. If the numbers differ by one, the player with the higher number wins $£ 1$ from the other player. If the players' choices differ by 2 or more, the player with the higher number pays $£ 2$ to the other player. In the event of a tie, no money changes hands.

Write down the payoff matrix.

For the case when $n=3$ find the value of the game and an optimal strategy for each player.

Find the value of the game and an optimal strategy for each player for all $n$.

[You may use results from the course provided you state them clearly.]

Paper 4, Section II, H

comment(a) Let $G$ be a flow network with capacities $c_{i j}$ on the edges. Explain the maximum flow problem on this network defining all the notation you need.

(b) Describe the Ford-Fulkerson algorithm for finding a maximum flow and state the max-flow min-cut theorem.

(c) Apply the Ford-Fulkerson algorithm to find a maximum flow and a minimum cut of the following network:

(d) Suppose that we add $\varepsilon>0$ to each capacity of a flow network. Is it true that the maximum flow will always increase by $\varepsilon$ ? Justify your answer.

Paper 1, Section I, H

comment$A=\left(\begin{array}{rrr} 5 & -2 & -5 \\ -2 & 3 & 2 \\ -3 & 6 & 2 \\ 4 & -8 & -6 \end{array}\right)$

be the payoff of a two-person zero-sum game, where player I (randomly) picks a row to maximise the expected payoff and player II picks a column to minimise the expected payoff. Find each player's optimal strategy and the value of the game.

Paper 2, Section I, H

commentUse the simplex algorithm to find the optimal solution to the linear program:

$\operatorname{maximise} 3 x+5 y \text { subject to } \begin{aligned} 8 x+3 y+10 z & \leqslant 9, \quad x, y, z \geqslant 0 \\ 5 x+2 y+4 z & \leqslant 8 \\ 2 x+y+3 z & \leqslant 2 \end{aligned}$

Write down the dual problem and find its solution.

Paper 3, Section II, H

comment(a) State and prove the Lagrangian sufficiency theorem.

(b) Let $n \geqslant 1$ be a given constant, and consider the problem:

$\operatorname{minimise} \sum_{i=1}^{n}\left(2 y_{i}^{2}+x_{i}^{2}\right) \text { subject to } x_{i}=1+\sum_{k=1}^{i} y_{k} \text { for all } i=1, \ldots, n$

Find, with proof, constants $a, b, A, B$ such that the optimal solution is given by

$x_{i}=a 2^{i}+b 2^{-i} \text { and } y_{i}=A 2^{i}+B 2^{-i} \text {, for all } i=1, \ldots, n .$

Paper 4, Section II, H

comment(a) What is the maximal flow problem in a network? Explain the Ford-Fulkerson algorithm. Prove that this algorithm terminates if the initial flow is set to zero and all arc capacities are rational numbers.

(b) Let $A=\left(a_{i, j}\right)_{i, j}$ be an $n \times n$ matrix. We say that $A$ is doubly stochastic if $0 \leqslant a_{i, j} \leqslant 1$ for $i, j$ and

$\begin{aligned} &\sum_{i=1}^{n} a_{i, j}=1 \text { for all } j \\ &\sum_{j=1}^{n} a_{i, j}=1 \text { for all } i \end{aligned}$

We say that $A$ is a permutation matrix if $a_{i, j} \in\{0,1\}$ for all $i, j$ and

for all $j$ there exists a unique $i$ such that $a_{i, j}=1$,

for all $i$ there exists a unique $j$ such that $a_{i, j}=1$.

Let $\mathcal{C}$ be the set of all $n \times n$ doubly stochastic matrices. Show that a matrix $A$ is an extreme point of $\mathcal{C}$ if and only if $A$ is a permutation matrix.

Paper 1, Section I, H

comment(a) Consider a network with vertices in $V=\{1, \ldots, n\}$ and directed edges $(i, j)$ in $E \subseteq V \times V$. Suppose that 1 is the source and $n$ is the sink. Let $C_{i j}, 0<C_{i j}<\infty$, be the capacity of the edge from vertex $i$ to vertex $j$ for $(i, j) \in E$. Let a cut be a partition of $V=\{1, \ldots, n\}$ into $S$ and $V \backslash S$ with $1 \in S$ and $n \in V \backslash S$. Define the capacity of the cut $S$. Write down the maximum flow problem. Prove that the maximum flow is bounded above by the minimum cut capacity.

(b) Find the maximum flow from the source to the sink in the network below, where the directions and capacities of the edges are shown. Explain your reasoning.

Paper 2, Section I, H

commentDefine what it means to say that a set $S \subseteq \mathbb{R}^{n}$ is convex. What is meant by an extreme point of a convex set $S$ ?

Consider the set $S \subseteq \mathbb{R}^{2}$ given by

$S=\left\{\left(x_{1}, x_{2}\right): x_{1}+4 x_{2} \leqslant 30,3 x_{1}+7 x_{2} \leqslant 60, x_{1} \geqslant 0, x_{2} \geqslant 0\right\}$

Show that $S$ is convex, and give the coordinates of all extreme points of $S$.

For all possible choices of $c_{1}>0$ and $c_{2}>0$, find the maximum value of $c_{1} x_{1}+c_{2} x_{2}$ subject to $\left(x_{1}, x_{2}\right) \in S$.

Paper 3, Section II, H

commentConsider the linear programming problem $P$ :

$\text { minimise } c^{T} x \text { subject to } A x \geqslant b, x \geqslant 0,$

where $x$ and $c$ are in $\mathbb{R}^{n}, A$ is a real $m \times n$ matrix, $b$ is in $\mathbb{R}^{m}$ and ${ }^{T}$ denotes transpose. Derive the dual linear programming problem $D$. Show from first principles that the dual of $D$ is $P$.

Suppose that $c^{T}=(6,10,11), b^{T}=(1,1,3)$ and $A=\left(\begin{array}{lll}1 & 3 & 8 \\ 1 & 1 & 2 \\ 2 & 4 & 4\end{array}\right)$. Write down the dual $D$ and find the optimal solution of the dual using the simplex algorithm. Hence, or otherwise, find the optimal solution $x^{*}=\left(x_{1}^{*}, x_{2}^{*}, x_{3}^{*}\right)$ of $P$.

Suppose that $c$ is changed to $\tilde{c}=\left(6+\varepsilon_{1}, 10+\varepsilon_{2}, 11+\varepsilon_{3}\right)$. Give necessary and sufficient conditions for $x^{*}$ still to be the optimal solution of $P$. If $\varepsilon_{1}=\varepsilon_{2}=0$, find the range of values for $\varepsilon_{3}$ for which $x^{*}$ is still the optimal solution of $P$.

Paper 4, Section II, 20H

commentSuppose the recycling manager in a particular region is responsible for allocating all the recyclable waste that is collected in $n$ towns in the region to the $m$ recycling centres in the region. Town $i$ produces $s_{i}$ lorry loads of recyclable waste each day, and recycling centre $j$ needs to handle $d_{j}$ lorry loads of waste a day in order to be viable. Suppose that $\sum_{i} s_{i}=\sum_{j} d_{j}$. Suppose further that $c_{i j}$ is the cost of transporting a lorry load of waste from town $i$ to recycling centre $j$. The manager wishes to decide the number $x_{i j}$ of lorry loads of recyclable waste that should go from town $i$ to recycling centre $j$, $i=1, \ldots, n, j=1, \ldots, m$, in such a way that all the recyclable waste produced by each town is transported to recycling centres each day, and each recycling centre works exactly at the viable level each day. Use the Lagrangian sufficiency theorem, which you should quote carefully, to derive necessary and sufficient conditions for $\left(x_{i j}\right)$ to minimise the total cost under the above constraints.

Suppose that there are three recycling centres $A, B$ and $C$, needing 5,20 and 20 lorry loads of waste each day, respectively, and suppose there are three towns $a, b$ and $c$ producing 20,15 and 10 lorry loads of waste each day, respectively. The costs of transporting a lorry load of waste from town $a$ to recycling centres $A, B$ and $C$ are $£ 90, £ 100$ and $£ 100$, respectively. The corresponding costs for town $b$ are $£ 130, £ 140$ and $£ 100$, while for town $c$ they are $£ 110, £ 80$ and $£ 80$. Recycling centre $A$ has reported that it currently receives 5 lorry loads of waste per day from town $a$, and recycling centre $C$ has reported that it currently receives 10 lorry loads of waste per day from each of towns $b$ and c. Recycling centre $B$ has failed to report. What is the cost of the current arrangement for transporting waste from the towns to the recycling centres? Starting with the current arrangement as an initial solution, use the transportation algorithm (explaining each step carefully) in order to advise the recycling manager how many lorry loads of waste should go from each town to each of the recycling centres in order to minimise the cost. What is the minimum cost?

Paper 1, Section I, 8H

commentState and prove the Lagrangian sufficiency theorem.

Use the Lagrangian sufficiency theorem to find the minimum of $2 x_{1}^{2}+2 x_{2}^{2}+x_{3}^{2}$ subject to $x_{1}+x_{2}+x_{3}=1$ (where $x_{1}, x_{2}$ and $x_{3}$ are real).

Paper 2, Section I, H

commentExplain what is meant by a two-player zero-sum game with $m \times n$ pay-off matrix $P=\left(p_{i j}\right)$, and state the optimal strategies for each player.

Find these optimal strategies when

$P=\left(\begin{array}{rr} -4 & 2 \\ 2 & -4 \end{array}\right)$

Paper 3, Section II, H

commentUse the two-phase simplex method to maximise $2 x_{1}+x_{2}+x_{3}$ subject to the constraints

$x_{1}+x_{2} \geqslant 1, \quad x_{1}+x_{2}+2 x_{3} \leqslant 4, \quad x_{i} \geqslant 0 \text { for } i=1,2,3$

Derive the dual of this linear programming problem and find the optimal solution of the dual.

Paper 4, Section II, H

commentConsider a network with a single source and a single sink, where all the edge capacities are finite. Write down the maximum flow problem, and state the max-flow min-cut theorem.

Describe the Ford-Fulkerson algorithm. If all edge capacities are integers, explain why, starting from a suitable initial flow, the algorithm is guaranteed to end after a finite number of iterations.

The graph in the diagram below represents a one-way road network taking traffic from point $A$ to point $B$ via five roundabouts $R_{i}, i=1, \ldots, 5$. The capacity of each road is shown on the diagram in terms of vehicles per minute. Assuming that all roundabouts can deal with arbitrary amounts of flow of traffic, find the maximum flow of traffic (in vehicles per minute) through this network of roads. Show that this flow is indeed optimal.

After a heavy storm, roundabout $R_{2}$ is flooded and only able to deal with at most 20 vehicles per minute. Find a suitable new network for the situation after the storm. Apply the Ford-Fulkerson algorithm to the new network, starting with the zero flow and explaining each step, to determine the maximum flow and the associated flows on each road.

Paper 1, Section I, $8 \mathrm{H}$

commentState sufficient conditions for $p$ and $q$ to be optimal mixed strategies for the row and column players in a zero-sum game with payoff matrix $A$ and value $v$.

Rowena and Colin play a hide-and-seek game. Rowena hides in one of 3 locations, and then Colin searches them in some order. If he searches in order $i, j, k$ then his search cost is $c_{i}, c_{i}+c_{j}$ or $c_{i}+c_{j}+c_{k}$, depending upon whether Rowena hides in $i, j$ or $k$, respectively, and where $c_{1}, c_{2}, c_{3}$ are all positive. Rowena (Colin) wishes to maximize (minimize) the expected search cost.

Formulate the payoff matrix for this game.

Let $c=c_{1}+c_{2}+c_{3}$. Suppose that Colin starts his search in location $i$ with probability $c_{i} / c$, and then, if he does not find Rowena, he searches the remaining two locations in random order. What bound does this strategy place on the value of the game?

Guess Rowena's optimal hiding strategy, show that it is optimal and find the value of the game.

Paper 2, Section I, H

commentGiven a network with a source $A$, a sink $B$, and capacities on directed arcs, define what is meant by a minimum cut.

The $m$ streets and $n$ intersections of a town are represented by sets of edges $E$ and vertices $V$ of a connected graph. A city planner wishes to make all streets one-way while ensuring it possible to drive away from each intersection along at least $k$ different streets.

Use a theorem about min-cut and max-flow to prove that the city planner can achieve his goal provided that the following is true:

$d(U) \geqslant k|U| \text { for all } U \subseteq V,$

where $|U|$ is the size of $U$ and $d(U)$ is the number edges with at least one end in $U$. How could the planner find street directions that achieve his goal?

[Hint: Consider a network having nodes $A, B$, nodes $a_{1}, \ldots, a_{m}$ for the streets and nodes $b_{1}, \ldots, b_{n}$ for the intersections. There are directed arcs from $A$ to each and from each $b_{i}$ to $B$. From each $a_{i}$ there are two further arcs, directed towards $b_{j}$ and $b_{j^{\prime}}$ that correspond to endpoints of street $i .]$

Paper 3, Section II, H

commentUse the two phase method to find all optimal solutions to the problem

$\begin{aligned} \operatorname{maximize} 2 x_{1}+3 x_{2}+x_{3} \\ \text { subject to } x_{1}+x_{2}+x_{3} & \leqslant 40 \\ 2 x_{1}+x_{2}-x_{3} & \geqslant 10 \\ -x_{2}+x_{3} & \geqslant 10 \\ x_{1}, x_{2}, x_{3} & \geqslant 0 \end{aligned}$

Suppose that the values $(40,10,10)$ are perturbed to $(40,10,10)+\left(\epsilon_{1}, \epsilon_{2}, \epsilon_{3}\right)$. Find an expression for the change in the optimal value, which is valid for all sufficiently small values of $\epsilon_{1}, \epsilon_{2}, \epsilon_{3}$.

Suppose that $\left(\epsilon_{1}, \epsilon_{2}, \epsilon_{3}\right)=(\theta,-2 \theta, 0)$. For what values of $\theta$ is your expression valid?

Paper 4, Section II, 20H

commentGiven real numbers $a$ and $b$, consider the problem $\mathrm{P}$ of minimizing

$f(x)=a x_{11}+2 x_{12}+3 x_{13}+b x_{21}+4 x_{22}+x_{23}$

subject to $x_{i j} \geqslant 0$ and

$\begin{array}{r} x_{11}+x_{12}+x_{13}=5 \\ x_{21}+x_{22}+x_{23}=5 \\ x_{11}+x_{21}=3 \\ x_{12}+x_{22}=3 \\ x_{13}+x_{23}=4 \end{array}$

List all the basic feasible solutions, writing them as $2 \times 3$ matrices $\left(x_{i j}\right)$.

Let $f(x)=\sum_{i j} c_{i j} x_{i j}$. Suppose there exist $\lambda_{i}, \mu_{j}$ such that

$\lambda_{i}+\mu_{j} \leqslant c_{i j} \text { for all } i \in\{1,2\}, j \in\{1,2,3\}$

Prove that if $x$ and $x^{\prime}$ are both feasible for $\mathrm{P}$ and $\lambda_{i}+\mu_{j}=c_{i j}$ whenever $x_{i j}>0$, then $f(x) \leqslant f\left(x^{\prime}\right) .$

Let $x^{*}$ be the initial feasible solution that is obtained by formulating $\mathrm{P}$ as a transportation problem and using a greedy method that starts in the upper left of the matrix $\left(x_{i j}\right)$. Show that if $a+2 \leqslant b$ then $x^{*}$ minimizes $f$.

For what values of $a$ and $b$ is one step of the transportation algorithm sufficient to pivot from $x^{*}$ to a solution that maximizes $f$ ?

Paper 1, Section I, 8H

commentState the Lagrangian sufficiency theorem.

Use Lagrange multipliers to find the optimal values of $x_{1}$ and $x_{2}$ in the problem: maximize $x_{1}^{2}+x_{2} \quad$ subject to $\quad x_{1}^{2}+\frac{1}{2} x_{2}^{2} \leqslant b_{1}, \quad x_{1} \geqslant b_{2}$ and $x_{1}, x_{2} \geqslant 0$ for all values of $b_{1}, b_{2}$ such that $b_{1}-b_{2}^{2} \geqslant 0$.

Paper 2, Section I, H

commentConsider the two-player zero-sum game with payoff matrix

$A=\left(\begin{array}{rrr} 2 & 0 & -2 \\ 3 & 4 & 5 \\ 6 & 0 & 6 \end{array}\right)$

Express the problem of finding the column player's optimal strategy as a linear programming problem in which $x_{1}+x_{2}+x_{3}$ is to be maximized subject to some constraints.

Solve this problem using the simplex algorithm and find the optimal strategy for the column player.

Find also, from the final tableau you obtain, both the value of the game and the row player's optimal strategy.

Paper 3, Section II, 21H

commentFor given positive real numbers $\left(c_{i j}: i, j \in\{1,2,3\}\right)$, consider the linear program

$P: \operatorname{minimize} \sum_{i=1}^{3} \sum_{j=1}^{3} c_{i j} x_{i j},$

subject to $\sum_{i=1}^{3} x_{i j} \leqslant 1$ for all $j, \quad \sum_{j=1}^{3} x_{i j} \geqslant 1$ for all $i$,

and $x_{i j} \geqslant 0$ for all $i, j$.

(i) Consider the feasible solution $x$ in which $x_{11}=x_{12}=x_{22}=x_{23}=x_{31}=x_{33}=1 / 2$ and $x_{i j}=0$ otherwise. Write down two basic feasible solutions of $P$, one of which you can be sure is at least as good as $x$. Are either of these basic feasible solutions of $P$ degenerate?

(ii) Starting from a general definition of a Lagrangian dual problem show that the dual of $P$ can be written as

$D: \operatorname{maximize}_{\lambda_{i} \geqslant 0, \mu_{i} \geqslant 0} \sum_{i=1}^{3}\left(\lambda_{i}-\mu_{i}\right) \quad \text { subject to } \lambda_{i}-\mu_{j} \leqslant c_{i j} \text { for all } i, j .$

What happens to the optimal value of this problem if the constraints $\lambda_{i} \geqslant 0$ and $\mu_{i} \geqslant 0$ are removed?

Prove that $x_{11}=x_{22}=x_{33}=1$ is an optimal solution to $P$ if and only if there exist $\lambda_{1}, \lambda_{2}, \lambda_{3}$ such that

$\lambda_{i}-\lambda_{j} \leqslant c_{i j}-c_{j j}, \quad \text { for all } i, j$

[You may use any facts that you know from the general theory of linear programming provided that you state them.]

Paper 4, Section II, 20H

commentDescribe the Ford-Fulkerson algorithm.

State conditions under which the algorithm is guaranteed to terminate in a finite number of steps. Explain why it does so, and show that it finds a maximum flow. [You may assume that the value of a flow never exceeds the value of any cut.]

In a football league of $n$ teams the season is partly finished. Team $i$ has already won $w_{i}$ matches. Teams $i$ and $j$ are to meet in $m_{i j}$ further matches. Thus the total number of remaining matches is $M=\sum_{i<j} m_{i j}$. Assume there will be no drawn matches. We wish to determine whether it is possible for the outcomes of the remaining matches to occur in such a way that at the end of the season the numbers of wins by the teams are $\left(x_{1}, \ldots, x_{n}\right)$.

Invent a network flow problem in which the maximum flow from source to sink equals $M$ if and only if $\left(x_{1}, \ldots, x_{n}\right)$ is a feasible vector of final wins.

Illustrate your idea by answering the question of whether or not $x=(7,5,6,6)$ is a possible profile of total end-of-season wins when $n=4, w=(1,2,3,4)$, and $M=14$ with

$\left(m_{i j}\right)=\left(\begin{array}{cccc} - & 2 & 2 & 2 \\ 2 & - & 1 & 1 \\ 2 & 1 & - & 6 \\ 2 & 1 & 6 & - \end{array}\right)$

Paper 1, Section I, H

commentSuppose that $A x \leqslant b$ and $x \geqslant 0$ and $A^{T} y \geqslant c$ and $y \geqslant 0$ where $x$ and $c$ are $n$-dimensional column vectors, $y$ and $b$ are $m$-dimensional column vectors, and $A$ is an $m \times n$ matrix. Here, the vector inequalities are interpreted component-wise.

(i) Show that $c^{T} x \leqslant b^{T} y$.

(ii) Find the maximum value of

$\begin{aligned} 6 x_{1}+8 x_{2}+3 x_{3} \quad \text { subject to } & 2 x_{1}+4 x_{2}+x_{3} \leqslant 10 \\ & 3 x_{1}+4 x_{2}+3 x_{3} \leqslant 6 \\ & x_{1}, x_{2}, x_{3} \geqslant 0 \end{aligned}$

You should state any results from the course used in your solution.

Paper 2, Section I, H

commentLet $N=\{1, \ldots, n\}$ be the set of nodes of a network, where 1 is the source and $n$ is the $\operatorname{sink}$. Let $c_{i j}$ denote the capacity of the arc from node $i$ to node $j$.

(i) In the context of maximising the flow through this network, define the following terms: feasible flow, flow value, cut, cut capacity.

(ii) State and prove the max-flow min-cut theorem for network flows.

Paper 3, Section II, H

comment(i) What does it mean to say a set $C \subseteq \mathbb{R}^{n}$ is convex?

(ii) What does it mean to say $z$ is an extreme point of a convex set $C ?$

Let $A$ be an $m \times n$ matrix, where $n>m$. Let $b$ be an $m \times 1$ vector, and let

$C=\left\{x \in \mathbb{R}^{n}: A x=b, x \geqslant 0\right\}$

where the inequality is interpreted component-wise.

(iii) Show that $C$ is convex.

(iv) Let $z=\left(z_{1}, \ldots, z_{n}\right)^{T}$ be a point in $C$ with the property that at least $m+1$ indices $i$ are such that $z_{i}>0$. Show that $z$ is not an extreme point of $C$. [Hint: If $r>m$, then any set of $r$ vectors in $\mathbb{R}^{m}$ is linearly dependent.]

(v) Now suppose that every set of $m$ columns of $A$ is linearly independent. Let $z=\left(z_{1}, \ldots, z_{n}\right)^{T}$ be a point in $C$ with the property that at most $m$ indices $i$ are such that $z_{i}>0$. Show that $z$ is an extreme point of $C$.

Paper 4, Section II, H

commentA company must ship coal from four mines, labelled $A, B, C, D$, to supply three factories, labelled $a, b, c$. The per unit transport cost, the outputs of the mines, and the requirements of the factories are given below.

\begin{tabular}{c|c|c|c|c|c} & $A$ & $B$ & $C$ & $D$ & \ \hline$a$ & 12 & 3 & 5 & 2 & 34 \ \hline$b$ & 4 & 11 & 2 & 6 & 21 \ \hline$c$ & 3 & 9 & 7 & 4 & 23 \ \hline & 20 & 32 & 15 & 11 & \end{tabular}

For instance, mine $B$ can produce 32 units of coal, factory a requires 34 units of coal, and it costs 3 units of money to ship one unit of coal from $B$ to $a$. What is the minimal cost of transporting coal from the mines to the factories?

Now suppose increased efficiency allows factory $b$ to reduce its requirement to $20.8$ units of coal, and as a consequence, mine $B$ reduces its output to $31.8$ units. By how much does the transport cost decrease?

Paper 1, Section I, 8E

commentWhat is the maximal flow problem in a network?

Explain the Ford-Fulkerson algorithm. Why must this algorithm terminate if the initial flow is set to zero and all arc capacities are rational numbers?

Paper 2, Section I, E

commentConsider the function $\phi$ defined by

$\phi(b)=\inf \left\{x^{2}+y^{4}: x+2 y=b\right\}$

Use the Lagrangian sufficiency theorem to evaluate $\phi(3)$. Compute the derivative $\phi^{\prime}(3)$.

Paper 3 , Section II, E

commentLet $A$ be the $m \times n$ payoff matrix of a two-person, zero-sum game. What is Player I's optimization problem?

Write down a sufficient condition that a vector $p \in \mathbb{R}^{m}$ is an optimal mixed strategy for Player I in terms of the optimal mixed strategy of Player II and the value of the game. If $m=n$ and $A$ is an invertible, symmetric matrix such that $A^{-1} e \geqslant 0$, where $e=(1, \ldots, 1)^{T} \in \mathbb{R}^{m}$, show that the value of the game is $\left(e^{T} A^{-1} e\right)^{-1}$

Consider the following game: Players I and II each have three cards labelled 1,2 , and 3. Each player chooses one of her cards, independently of the other, and places it in the same envelope. If the sum of the numbers in the envelope is smaller than or equal to 4, then Player II pays Player I the sum (in $£$ ), and otherwise Player I pays Player II the sum. (For instance, if Player I chooses card 3 and Player II choose card 2, then Player I pays Player II £5.) What is the optimal strategy for each player?

Paper 4, Section II, E

commentA factory produces three types of sugar, types $X$, $Y$, and $Z$, from three types of syrup, labelled $A, B$, and C. The following table contains the number of litres of syrup necessary to make each kilogram of sugar.

\begin{tabular}{c|ccc} & $\mathrm{X}$ & $\mathrm{Y}$ & $\mathrm{Z}$ \ \hline $\mathrm{A}$ & 3 & 2 & 1 \ $\mathrm{~B}$ & 2 & 3 & 2 \ $\mathrm{C}$ & 4 & 1 & 2 \end{tabular}

For instance, one kilogram of type $\mathrm{X}$ sugar requires 3 litres of $\mathrm{A}, 2$ litres of $\mathrm{B}$, and 4 litres of C. The factory can sell each type of sugar for one pound per kilogram. Assume that the factory owner can use no more than 44 litres of $\mathrm{A}$ and 51 litres of $\mathrm{B}$, but is required by law to use at least 12 litres of C. If her goal is to maximize profit, how many kilograms of each type of sugar should the factory produce?

Paper 1, Section I, H

commentFind an optimal solution to the linear programming problem

$\max 3 x_{1}+2 x_{2}+2 x_{3}$

in $x \geqslant 0$ subject to

$\begin{gathered} 7 x_{1}+3 x_{2}+5 x_{3} \leqslant 44 \\ x_{1}+2 x_{2}+x_{3} \leqslant 10 \\ x_{1}+x_{2}+x_{3} \geqslant 8 \end{gathered}$

Paper 2, Section I, H

commentThe diagram shows a network of sewage treatment plants, shown as circles, connected by pipes. Some pipes (indicated by a line with an arrowhead at one end only) allow sewage to flow in one direction only, others (indicated by a line with an arrowhead at both ends) allow sewage to flow in either direction. The capacities of the pipes are shown. The system serves three towns, shown in the diagram as squares.

Each sewage treatment plant can treat a limited amount of sewage, indicated by the number in the circle, and this may not be exceeded for fear of environmental damage. Treated sewage is pumped into the sea, but at any treatment plant incoming untreated sewage may be immediately pumped to another plant for treatment there.

Find the maximum amount of sewage which can be handled by the system, and how this is assigned to each of the three towns.

Paper 3, Section II, H

commentFour factories supply stuff to four shops. The production capacities of the factories are $7,12,8$ and 9 units per week, and the requirements of the shops are 8 units per week each. If the costs of transporting a unit of stuff from factory $i$ to shop $j$ is the $(i, j)$ th element in the matrix

$\left(\begin{array}{cccc} 6 & 10 & 3 & 5 \\ 4 & 8 & 6 & 12 \\ 3 & 4 & 9 & 2 \\ 5 & 7 & 2 & 6 \end{array}\right)$

find a minimal-cost allocation of the outputs of the factories to the shops.

Suppose that the cost of producing one unit of stuff varies across the factories, being $3,2,4,5$ respectively. Explain how you would modify the original problem to minimise the total cost of production and of transportation, and find an optimal solution for the modified problem.

Paper 4, Section II, H

commentIn a pure exchange economy, there are $J$ agents, and $d$ goods. Agent $j$ initially holds an endowment $x_{j} \in \mathbb{R}^{d}$ of the $d$ different goods, $j=1, \ldots, J$. Agent $j$ has preferences given by a concave utility function $U_{j}: \mathbb{R}^{d} \rightarrow \mathbb{R}$ which is strictly increasing in each of its arguments, and is twice continuously differentiable. Thus agent $j$ prefers $y \in \mathbb{R}^{d}$ to $x \in \mathbb{R}^{d}$ if and only if $U_{j}(y) \geqslant U_{j}(x)$.

The agents meet and engage in mutually beneficial trades. Thus if agent $i$ holding $z_{i}$ meets agent $j$ holding $z_{j}$, then the amounts $z_{i}^{\prime}$ held by agent $i$ and $z_{j}^{\prime}$ held by agent $j$ after trading must satisfy $U_{i}\left(z_{i}^{\prime}\right) \geqslant U_{i}\left(z_{i}\right), U_{j}\left(z_{j}^{\prime}\right) \geqslant U_{j}\left(z_{j}\right)$, and $z_{i}^{\prime}+z_{j}^{\prime}=z_{i}+z_{j}$. Meeting and trading continues until, finally, agent $j$ holds $y_{j} \in \mathbb{R}^{d}$, where

$\sum_{j} x_{j}=\sum_{j} y_{j}$

and there are no further mutually beneficial trades available to any pair of agents. Prove that there must exist a vector $v \in \mathbb{R}^{d}$ and positive scalars $\lambda_{1}, \ldots, \lambda_{J}$ such that

$\nabla U_{j}\left(y_{j}\right)=\lambda_{j} v$

for all $j$. Show that for some positive $a_{1}, \ldots, a_{J}$ the final allocations $y_{j}$ are what would be achieved by a social planner, whose objective is to obtain

$\max \sum_{j} a_{j} U_{j}\left(y_{j}\right) \quad \text { subject to } \sum_{j} y_{j}=\sum_{j} x_{j}$

1.I.8H

commentState the Lagrangian Sufficiency Theorem for the maximization over $x$ of $f(x)$ subject to the constraint $g(x)=b$.

For each $p>0$, solve

$\max \sum_{i=1}^{d} x_{i}^{p} \quad \text { subject to } \sum_{i=1}^{d} x_{i}=1, \quad x_{i} \geqslant 0 .$

2.I.9H

commentGoods from three warehouses have to be delivered to five shops, the cost of transporting one unit of good from warehouse $i$ to shop $j$ being $c_{i j}$, where

$C=\left(\begin{array}{ccccc} 2 & 3 & 6 & 6 & 4 \\ 7 & 6 & 1 & 1 & 5 \\ 3 & 6 & 6 & 2 & 1 \end{array}\right)$

The requirements of the five shops are respectively $9,6,12,5$ and 10 units of the good, and each warehouse holds a stock of 15 units. Find a minimal-cost allocation of goods from warehouses to shops and its associated cost.

3.II.20H

commentUse the simplex algorithm to solve the problem

$\max x_{1}+2 x_{2}-6 x_{3}$

subject to $x_{1}, x_{2} \geqslant 0,\left|x_{3}\right| \leqslant 5$, and

$\begin{array}{r} x_{1}+x_{2}+x_{3} \leqslant 7 \\ 2 x_{2}+x_{3} \geqslant 1 \end{array}$

4.II.20H

comment(i) Suppose that $f: \mathbb{R}^{n} \rightarrow \mathbb{R}$, and $g: \mathbb{R}^{n} \rightarrow \mathbb{R}^{m}$ are continuously differentiable. Suppose that the problem

$\max f(x)$ subject to $g(x)=b$

is solved by a unique $\bar{x}=\bar{x}(b)$ for each $b \in \mathbb{R}^{m}$, and that there exists a unique $\lambda(b) \in \mathbb{R}^{m}$ such that

$\varphi(b) \equiv f(\bar{x}(b))=\sup _{x}\left\{f(x)+\lambda(b)^{T}(b-g(x))\right\}$

Assuming that $\bar{x}$ and $\lambda$ are continuously differentiable, prove that

$\frac{\partial \varphi}{\partial b_{i}}(b)=\lambda_{i}(b)$

(ii) The output of a firm is a function of the capital $K$ deployed, and the amount $L$ of labour employed, given by

$f(K, L)=K^{\alpha} L^{\beta}$

where $\alpha, \beta \in(0,1)$. The firm's manager has to optimize the output subject to the budget constraint

$K+w L=b,$

where $w>0$ is the wage rate and $b>0$ is the available budget. By casting the problem in Lagrangian form, find the optimal solution and verify the relation $(*)$.

$3 . \mathrm{II} . 20 \mathrm{C}$

commentState and prove the Lagrangian sufficiency theorem.

Solve the problem

$\begin{array}{ll} \text { maximize } & x_{1}+3 \ln \left(1+x_{2}\right) \\ \text { subject to } \quad & 2 x_{1}+3 x_{2} \leqslant c_{1} \\ & \ln \left(1+x_{1}\right) \geqslant c_{2}, \quad x_{1} \geqslant 0, x_{2} \geqslant 0 \end{array}$

where $c_{1}$ and $c_{2}$ are non-negative constants satisfying $c_{1}+2 \geqslant 2 e^{c_{2}}$.

1.I.8C

commentState and prove the max-flow min-cut theorem for network flows.

2.I.9C

commentConsider the game with payoff matrix

$\left(\begin{array}{lll} 2 & 5 & 4 \\ 3 & 2 & 2 \\ 2 & 1 & 3 \end{array}\right)$

where the $(i, j)$ entry is the payoff to the row player if the row player chooses row $i$ and the column player chooses column $j$.

Find the value of the game and the optimal strategies for each player.

4.II $20 \mathrm{C}$

commentConsider the linear programming problem

$\begin{aligned} \operatorname{minimize} \quad & 2 x_{1}-3 x_{2}-2 x_{3} \\ \text { subject to } \quad-& 2 x_{1}+2 x_{2}+4 x_{3} \leqslant 5 \\ & 4 x_{1}+2 x_{2}-5 x_{3} \leqslant 8 \\ & 5 x_{1}-4 x_{2}+\frac{1}{2} x_{3} \leqslant 5, \quad x_{i} \geqslant 0, \quad i=1,2,3 . \end{aligned}$

(i) After adding slack variables $z_{1}, z_{2}$ and $z_{3}$ and performing one iteration of the simplex algorithm, the following tableau is obtained.

\begin{tabular}{c|rrrrrr|c} & $x_{1}$ & $x_{2}$ & $x_{3}$ & $z_{1}$ & $z_{2}$ & $z_{3}$ & \ \hline$x_{2}$ & $-1$ & 1 & 2 & $1 / 2$ & 0 & 0 & $5 / 2$ \ $z_{2}$ & 6 & 0 & $-9$ & $-1$ & 1 & 0 & 3 \ $z_{3}$ & 1 & 0 & $17 / 2$ & 2 & 0 & 1 & 15 \ \hline Payoff & $-1$ & 0 & 4 & $3 / 2$ & 0 & 0 & $15 / 2$ \end{tabular}

Complete the solution of the problem.

(ii) Now suppose that the problem is amended so that the objective function becomes

$2 x_{1}-3 x_{2}-5 x_{3}$

Find the solution of this new problem.

(iii) Formulate the dual of the problem in (ii) and identify the optimal solution to the dual.

$2 . \mathrm{I} . 9 \mathrm{C} \quad$

commentConsider the maximal flow problem on a finite set $N$, with source $A$, sink $B$ and capacity constraints $c_{i j}$ for $i, j \in N$. Explain what is meant by a cut and by the capacity of a cut.

Show that the maximal flow value cannot exceed the minimal cut capacity.

Take $N=\{0,1,2,3,4\}^{2}$ and suppose that, for $i=\left(i_{1}, i_{2}\right)$ and $j=\left(j_{1}, j_{2}\right)$,

$c_{i j}=\max \left\{\left|i_{1}-i_{2}\right|,\left|j_{1}-j_{2}\right|\right\} \quad \text { if } \quad\left|i_{1}-j_{1}\right|+\left|i_{2}-j_{2}\right|=1,$

and $c_{i j}=0$ otherwise. Thus the node set is a square grid of 25 points, with positive flow capacity only between nearest neighbours, and where the capacity of an edge in the grid equals the larger of the distances of its two endpoints from the diagonal. Find a maximal flow from $(0,3)$ to $(3,0)$. Justify your answer.

1.I.8C

State the Lagrangian sufficiency theorem.

Let $p \in(1, \infty)$ and let $a_{1}, \ldots, a_{n} \in \mathbb{R}$. Maximize

$\sum_{i=1}^{n} a_{i} x_{i}$