Title: Part IB / Optimisation
Tags: Optimisation_Algorithms Convexity Lagrange_Multipliers Linear_Programming Maximum_Flow_Minimum_Cut Network_Flows Simplex_Method Game_Theory Linear_Programming_Duality Transport_Algorithm

Definition. The following definitions will be used.
i) Objective function:  the function we are minimising
ii) Decision variables:  the components of the vector \(\mathbf{x}\) which is input into the objective function
iii) Functional constraint: a constraint of the form \(h(\mathbf{x}) = \mathbf{b}\)
iv) Regional constrant: A constraint of the form \(\mathbf{x} \in \mathcal{X}\)
v) Feasible set: the set \(\mathcal{X}(\mathbf{x}) = \{ \mathbf{x}: \mathbf{x} \in \mathcal{X}, h(\mathbf{x}) = \mathbf{b} \}\) 
vi) Bounded problem: the minimum on the feasible set is bounded
vii) Optimal point:  a point which minimises the objective function

Q: Definition: A set \(S \subseteq \mathbb{R}^n \) is convex if for all \(\mathbf{x,y} \in S\), the line segment between the two points lies entirely inside S. In other words, [...]
A: \(\forall \lambda \in [0,1], \mathbf{x}(1 - \lambda) + \mathbf{y}(\lambda) \in S \)

Q: Definition. A function \(f : S \to \mathbb{R}\) is convex if [...]
A: - S is convex
- \(\forall \mathbf{x,y} \in S\), \[f((1-\lambda)\mathbf{x} + \lambda \mathbf{y}) \leq (1-\lambda)f(\mathbf{x}) + \lambda f(\mathbf{y})\]
Back Extra: Informally, for a convex function, if we take two inputs, the chord connecting their oututs lies above the function's curve.

Q: Theorem. First-order conditions for convexity. A differentiable function \(f : \mathbb{R}^n \to \mathbb{R}\) is convex if and only if \[\forall \mathbf{x,y} \in \mathbb{R}^n, f(\mathbf{y}) \geq f(\mathbf{x}) + (\mathbf{y} - \mathbf{x}) \cdot \nabla f(\mathbf{x})\]
A: First prove convexity implies first-order condition by rearranging the definition of convexity.
Then for a general case define \(g(\lambda) = f((1-\lambda) \mathbf{x} + \lambda \mathbf{y})\). Since f is convex, so is g.
Therefore using the first-order case, \(g(1) \geq g(0) + g'(0)(1-0) \implies f(\mathbf{y}) \geq f(\mathbf{x}) + \nabla f(\mathbf{x}) \cdot (\mathbf{y} - \mathbf{x})\).
To prove the converse first define \(\mathbf{x}_{\lambda} = (1-\lambda)\mathbf{x} - \lambda \mathbf{y}\). Now use the first order condition on \(f(\mathbf{x}), f(\mathbf{y})\) and multiply by \(1- \lambda\) and \(\lambda\) to get the convexity condition.

Q: Defintion. An \(n \times n\) matrix A is position semidefinite if [...] If A is positive semidefinite, we write \(A \geq 0\).
A: for all \(\mathbf{x} \in \mathbb{R}^n\), we have \(\mathbf{x}^T A \mathbf{x} \geq 0\). Equivalently, all eigenvalues of A are non-negative.

Q: Theorem. Second-order conditions for convexity. A twice-differentiable function \(f : \mathbb{R}^n \to \mathbb{R}\) is convex if \(\nabla^2 f(\mathbf{x}) \geq 0\) at all \(\mathbf{x}\). The converse also holds, but is not proven in this course.
A: Use the taylor expansion of f, with \(\mathbf{z} = (1-\lambda)\mathbf{x} + \lambda \mathbf{y}\) for some \(\lambda \in [0,1]\),  to get \[f(\mathbf{y}) = f(\mathbf{x}) + \nabla f(\mathbf{x})^T (\mathbf{y - x}) + \frac{1}{2}(\mathbf{y-x})^T \nabla^2 f(\mathbf{z})(\mathbf{y-x})\]Since the rightmost term is positive, we get the first-order conditions, which imply convexity.

Q: Definition. A continuously differentiable function \(f: \mathbb{R}^n \to \mathbb{R}\) is \(\beta\)-smooth if \(\nabla f\) is a \(\beta\)-Lipschitz function: [...]
A: \[|| \nabla f(\mathbf{x}) - \nabla f(\mathbf{y})|| \leq \beta || \mathbf{x-y}||\]
Back Extra: Further if f is twice differentiable then this smoothness is equivalent to \[\nabla^2 f(\mathbf{x}) \leq \beta I\]
So all eigenvalues of the Hessian have \(\lambda \leq \beta\)

Q: Definition. The linear approximation to f at \(\mathbf{x}\) is [...]
A: \[f(\mathbf{x}) + \nabla f(\mathbf{x})^T(\mathbf{y-x})\]

Q: Claim. If f is \(\beta\)-smooth, then \[f(\mathbf{y}) \leq f(\mathbf{x}) + \nabla f(\mathbf{x})^T (\mathbf{y-x}) + \frac{\beta}{2}||\mathbf{y-x}||^2\]
A: By Taylor's Theorem and using the fact that \(\nabla^2 f(\mathbf{x}) \leq \beta I\) due to it being \(\beta\)-smooth.

Q: Corollary. If we move by a step size of \(\frac{1}{\beta}\), we will descend by at least \(\frac{1}{2\beta} ||\nabla f(\mathbf{x})||^2\). \[f \left (\mathbf{x} - \frac{1}{\beta} \nabla f(\mathbf{x}) \right ) \leq f(\mathbf{x}) - \frac{1}{2\beta}||\nabla f(\mathbf{x})||^2\]
A: Consider \(f(\mathbf{x}) + \nabla f(\mathbf{x})^T (\mathbf{y - x}) + \frac{\beta}{2} ||\mathbf{y-x}||^2\) as a function of \(\mathbf{y}\) and minimise it.

Q: Claim. Improved first order condition. \[f(\mathbf{y}) \geq f(\mathbf{x}) + \nabla f(\mathbf{x})^T (\mathbf{y-x}) + \frac{1}{2\beta} || \nabla f(\mathbf{x}) - \nabla f(\mathbf{y})||^2\]
A: For any \(\bf z\) we can bound in the following way, \(f(\mathbf{x}) + \nabla f(\mathbf{x})^T(\mathbf{z-x}) \leq f(\mathbf{z}) \leq f(\mathbf{y}) + \nabla f(\mathbf{y})^T (\mathbf{z-y}) + \frac{\beta}{2} ||\mathbf{z-y}||^2\).
Then rearrange to get \(f(\mathbf{x}) - f(\mathbf{y})\) on its own and minimise \(\mathbf{z}\) and substitute back in.

Q: Definition. A function \(f : \mathbb{R}^n \to \mathbb{R}\) is called \(\alpha\)-strongly convex if [...]
A: \[f(\mathbf{y}) \geq f(\mathbf{x}) + \nabla f(\mathbf{x})^T(\mathbf{y-x}) + \frac{\alpha}{2} ||\mathbf{y-x}||^2\]
Back Extra: Now if f is twice differentiable, then \[\nabla^2 f(\mathbf{x}) \geq \alpha I\]

Q: Claim. Let f be \(\alpha\)-strongly convex. Let \(p*\) be the optimal cost; i.e. the minimum value of f. Then for any \(\mathbf{x}\) we have \[p* \geq f(\mathbf{x}) - \frac{1}{2\alpha}||\nabla f(\mathbf{x})||^2\]
A: Use the strong convexity assumption - \(f(\mathbf{y})\geq f(\mathbf{x}) + \nabla f(\mathbf{x})^T(\mathbf{y-x}) + \frac{\alpha}{2}|\mathbf{y-x}||^2\) - and take the minimum over \(\bf y\) on both sides and plug it back in to the equation.

Q: Claim. Let \(\bf x^*\) be the minimising value, then \[||\mathbf{x - x^*}|| \leq \frac{2}{\alpha} ||\nabla f (\mathbf{x})||\]So if a function is strongly convex, we can find a region in which we know the global maximum lies.
A: Use Cauchy-Schwarz on the strong convexity condition and then use the fact that \(f(\mathbf{x^*}) \leq f(\mathbf{x})\) to reach the conclusion.

Q: Theorem. Gradient descent with step size \(\frac{1}{\beta}\) satisfies \[f(\mathbf{x_T}) - f(\mathbf{x^*}) \leq \left ( 1 - \frac{\alpha}{\beta} \right )^T (f(\mathbf{x_0}) - f(\mathbf{x^*}))\]given that f is \(\beta\)-smooth and \(\alpha\)-strongly convex
A: \(f(\mathbf{x}_{t+1}) - f(\mathbf{x^*}) \leq f(\mathbf{x_t}) - f(\mathbf{x^*}) - \frac{1}{2\beta}||\nabla f(\mathbf{x}_t)||^2 \leq f(\mathbf{x_t}) - f(\mathbf{x^*}) - \frac{\alpha}{\beta}(f(\mathbf{x}_t) - f(\mathbf{x^*}))\)
The result follows from induction.
First inequality due to \(\beta\)-smoothness, second due to \(\alpha\)-strong convexity.

Q: Definition. Gradient Descent and Newton's Method. How do we iterate in each?
A: Gradient descent: \(\mathbf{x}_{t+1} = \mathbf{x}_t - \eta_t \nabla f(\mathbf{x}_t)\)
Newton's method: \(\mathbf{x}_{t+1} = \mathbf{x}_t - (\nabla^2 f(\mathbf{x}))^{-1}\nabla f(\mathbf{x}_t)\)
Newton's method comes frmo minimising the right hand side of a second-order approximation.

Q: Theorem. Lagrange Sufficiency. Let \(x^*\) be feasible. Suppose there exists \(\lambda^* \in \mathbb{R}^m\) such that \[L(x^*, \lambda^*) \leq L(x, \lambda^*)\] for all \(x \in X\), then \(x^*\) is optimal for minimising f subject to conditions.
A: For any feasible x and any \(\lambda\) we have \[L(x,\lambda) = f(x) + \lambda^T (b - g(x)) = f(x)\] since \(g(x) = b\). So if \(x^*\) is feasible \[f(x^*) = L(x^*, \lambda^*) \leq L(x, \lambda^*) = f(x)\] for all feasible x

Q: Theorem. Weak Duality Theorem. If \(\mathbf{x} \in \mathcal{X}(\mathbf{b})\) and \(\lambda \in \Lambda\), then \(f(\mathbf{x}) \geq g(\lambda)\), where \(g(\lambda) = \inf_{\mathbf{x} \in \mathcal{X}} L(\mathbf{x}, \lambda)\), in particular, \[\inf_{\mathbf{x} \in \mathcal{X}(\mathbf{b})} f(\mathbf{x}) \geq \sup_{\lambda \in \Lambda} g(\lambda)\]
A: \(\inf_{\mathbf{x} \in \mathcal{X}(\mathbf{b})} f(\mathbf{x}) = \inf_{\mathbf{x} \in \mathcal{X}(\mathbf{b})} f(\mathbf{x}) - \lambda^T(h(\mathbf{x}) - \mathbf{b}) \geq \inf_{\mathbf{x} \in \mathcal{X}} f(\mathbf{x}) - \lambda^T(h(\mathbf{x}) - \mathbf{b}) = \inf_{\mathbf{x} \in \mathcal{X}} L(\mathbf{x}, \lambda) = g(\lambda)\)
Using this property, if it is hard to find the optimal cost we can attempt to maximise \(g(\lambda)\).

Q: Definition. A function \(\phi : \mathbb{R}^m \to \mathbb{R}\) is said to have a supporting hyperplane at a point \(\mathbf{b}\) if [...]
A: there exists \(\mathbf{\lambda} \in \mathbb{R}^m\) such that for all \(\mathbf{c} \in \mathbb{R}^m\), \[\phi(\mathbf{c}) \geq \phi(\mathbf{b}) + \mathbf{\lambda}^T (\mathbf{c - b})\]

Q: Definition. Value Function. We define a function \(\phi : \mathbb{R}^m \to \mathbb{R}\) associated with the primal problem by[...]
A: \[\phi(\mathbf{c}) = \inf_{\mathbf{x} \in \mathcal{X}(\mathbf{c})} f(\mathbf{x})\]
Back Extra: This function can be thought of as the optimal cost of a family of optimisation problems with different functional constraint values \(\mathbf{c}\).

Q: Theorem. Strong Duality Theorem. Strong duality holds if and only if the value function \(\phi\) has a supporting hyperplane at \(\mathbf{b}\).
A: First show that a supporting hyperplane implies strong duality. We have \(\mathbf{\lambda}\) such that \[\phi(\mathbf{c}) \geq \phi(\mathbf{b}) + \mathbf{\lambda}^T (\mathbf{c-b})\]Then, we have \[g(\mathbf{\lambda}) = \inf_{\mathbf{x} \in \mathcal{X}} f(\mathbf{x}) - \mathbf{\lambda}^T(h(\mathbf{x}) - \mathbf{b}) = \inf_c \inf_{\mathbf{x} \in \mathcal{X}} f(\mathbf{x}) - \mathbf{\lambda}^T (h(\mathbf{x}) - \mathbf{c}) - \mathbf{\lambda}^T(\mathbf{c-b}) = \inf_c \phi(\mathbf{c}) - \mathbf{\lambda}^T(\mathbf{c-b}) \geq \phi(\mathbf{b})\]The third equality comes comes from the middle term vanishing due to the fact we are extremising.
By weak duality we have the reverse inequality also so \(g(\lambda) = \phi(\mathbf{b})\) and strong duality holds.
If strong duality holds then we can manipulate the exptression for \(g(\lambda)\) and use weak duality to show such a supporting hyperplane exists.

Q: Theorem. If \(\phi\) is differentiable at \(\mathbf{b}\) and has a supporting hyperplane given by \(\lambda\), then \[\lambda = \nabla \phi(\mathbf{b})\]
A: Let \(\mathbf{a} = (a_1, a_2, \dots, a_m)\) be an arbitrary vector. Then from the supporting hyperplane condition, for some small \(\delta > 0\) we have \[\frac{\phi(\mathbf{b} + \delta \mathbf{a})}{\delta} \geq \lambda^T \mathbf{a}\]Since \(\phi\) is differentiable we can take the limit to get \(\nabla \phi(\mathbf{b}) \cdot \mathbf{a} \geq \lambda^T \mathbf{a}\). But \(\mathbf{a}\) was arbitrary and this can only hold if \(\lambda = \nabla \phi(\mathbf{b})\) as required.
This comes from the shadow price interpretation of Lagrange multipliers, where a suppliers offers some small extra quantity of supplies and we want to figure out how much these supplies are worth.

Q: Definition. A point \(\mathbf{x}\) in a convex set C is an extreme point if [...]
A: it cannot be written as a convex combination of two distinct points in C; that is, \[(1-\delta) \mathbf{y} + \delta \mathbf{z}\] for \(\delta \in (0,1)\) and \(\mathbf{y \neq z}\)
Back Extra: So, convex functions on convex sets are maximised at extreme points.

Q: Definition. Consider a linear problem in standard form, \(\text{minimise}_{\mathbf{x} \in \mathbb{R}^n} \mathbf{c^T x} \text{ subject to } A\mathbf{x} = \mathbf{b}, \mathbf{x} \geq 0\), where \(A \in \mathbb{R}^{m \times n}, \mathbf{x} \in \mathbb{R^n}, \mathbf{b} \in \mathbb{R}^m\).A vector \(\mathbf{x}\) is said to be a basic solution if [...] It is called a basic feasible solutions if also [...]
A: it satisfies \(A\mathbf{x} = \mathbf{b}\) and \(\mathbf{x}\) has at most m non-zero entries.; all nonzero entries are positive, since it lies in the feasible set.

Q: Theorem. \(\mathbf{x}\) is an extreme point of the set \(\{ \mathbf{x} : A\mathbf{x} = \mathbf{b}, \mathbf{x} \geq 0\}\) if and only if \(\mathbf{x}\) is a basic feasible solution.
A: First show that basic feasible implies extreme point.
Assume \(\mathbf{x} = (1-\delta)\mathbf{y} + \delta \mathbf{z}\). So \(\mathbf{y}, \mathbf{z}\) must be 0 in the same places as \(\mathbf{x}\), and also \(A\mathbf{y} = A\mathbf{z} = \mathbf{b}\) so we can show that the vector with all non-zero elements are the same for all 3 and therefore all of \(\mathbf{x}, \mathbf{y}, \mathbf{z}\) are the same.
Now for extreme implies basic feasible.
If it is not a basic feasible solution, then it has an amount of nonzero indices greater than m, then since the rank of A is only m, the columns \(A_{i_1}, \dots, A_{i_r}\) a linearly dependent set. Hence, we can find some weights, not all of which are zero, which give zero when multiplied by the columns. So we can make a vector \(\mathbf{w}\) such that \(A\mathbf{w} = 0\), but now \(\mathbf{x} \pm \epsilon \mathbf{w}\) are in the feasible set if we choose a small enough \(\epsilon\), so \(\mathbf{x}\) is not an extreme point as it is the midpoint of these two.

Q: Theorem. If a linear pgoram is bounded and feasible, then strong duality holds.
A: This is true as the value function is convex.

Q: Theorem. Fundamental Theorem of Linear Programming. Let \(\mathbf{x}, \mathbf{p}\) be feasible solutions to the primal and dual programs respectively. Then \(\mathbf{x}, \mathbf{p}\) are optimal for these programs if and only if
 - \(p_i(\mathbf{a}_i^T \mathbf{x} - b_i) = 0\) for all i
- \((c_j - \mathbf{p}^T \mathbf{A}_j)x_j = 0\) for all j
A: First define \(u_i = p_i(\mathbf{a}^T \mathbf{x} - b_i)\) and \(v_j = (c_j - \mathbf{p}^T \mathbf{A}_j)x_j\). Observe that if \(\mathbf{x}, \mathbf{p}\) are feasible, then \(u_i \geq 0\) for all i, and \(v_j \geq 0\) for all j.
\(\sum u_i + \sum v_j = \mathbf{c^T x - p^T b}\) which is the difference between the two objective functions in the primal and the dual. So it is greater than or equal to 0. So if complementary slackness holds, then \(u_i = 0\) and \(v_j = 0\) for all i,j. So \(\mathbf{c^T x = p^T b}\) and therefore the solutions are optimal by weak duality.
Conversely suppose they are optimal, by strong duality \(\mathbf{c^T x = p^T b}\), so from the sum above and since all \(u_i, v_j\) are non-negative, they must all be 0. Equivalently, complementary slackness holds.

Q: Definition. Let \(P = \{\mathbf{x} : A\mathbf{x} = \mathbf{b}, \mathbf{x} \geq 0\}\) be the feasible set of a problem in standard form. Further, let \(\mathbf{x} \in P\). A vector \(\mathbf{d} \in \mathbb{R}^n\) is called a feasible direction if [...]
A: there exists \(\theta > 0\) such that \(\mathbf{x} + \theta \mathbf{d} \in P\).

Q: Theorem. Let \(\mathbf{x}\) be a basic feasible solution associated with a basis matrix B and let \(\mathbf{\overline{c}}\) be the vector of reduced costs. Then \(\mathbf{x}\) is optimal if and only if \(\mathbf{\overline{c}} \geq 0\).
A: The optimality conditions are primal feasibility, dual feasibility and complementary slackness.
If \(\mathbf{x}\) is a basic feasible solution, we can substitute this into the complementary slackness equation and pick \(\bf \lambda\) such that it holds. Then for dual feasibility to hold we need the vector of reduced costs - \(\mathbf{\overline{c}} = \mathbf{c} - A^T(B^T)^{-1} \mathbf{c_b}\) - to be non-negative.
If this has any negative elements, we can move in the jth direction and decrease cost as going from \(\mathbf{x} \mapsto \mathbf{x} + \theta \mathbf{d}\) we get \(\mathbf{c^T(x + \theta d)} = \mathbf{c^T x} + \theta \overline{c_j}\).

Q: Result. Simplex Method. How do we run the simplex method?
A: Choose a j such that \(\overline{c_j} < 0\), let \(\mathbf{u} = - B^{-1}A_j\).
If \(\mathbf{u} \leq 0\), then the cost is \(- \infty\) so terminate.
Let \(\theta^* = \min \frac{x_{B(i)}}{u_i}\) and choose l to be the index which gives the minimal value.
Let \(\mathbf{x} = \mathbf{x} - \theta^* \mathbf{u}\).
Repeated until \(\mathbf{\overline{c}} \geq 0\).

Q: Definition. Zero-sum two person game. This is a scenario in which two players denoted P1 and P2 have different action they can take. P1 has m possible actions and P2 has n possible actions such that [...]
A: if P1 plays move i and P2 plays more j, then P1 wins \(a_{ij} \) and P2 loses this same amount. P1 chooses a row, P2 chooses a column, and the intersection is the outcome of the game.
Back Extra: So P1 wants to maximise \(\min_{j \in \{1, \dots , m\}} a_{ij}\) and P2 wants to minimise \(\max_{i \in \{1,\dots,n\}} a_{ij}\).

Q: Theorem. A strategy \(\mathbf{p}\) is optimal for P1 if there exist \(\mathbf{q}, v\) such that
-(primal feasibility) \(A^T \mathbf{p} \geq v \mathbf{e}, \mathbf{e}^T \mathbf{p} = 1, \mathbf{p} \geq 0\);
-(dual feasibility) \(A\mathbf{q} \leq v\mathbf{e}, \mathbf{e}^T \mathbf{q} = 1, \mathbf{q} \geq 0\);
-(complementary slackness)\(v = \mathbf{p}^T A \mathbf{q}\)
A: \((\mathbf{p},v)\) and \((\mathbf{q}, w)\) are optimal if \[(A\mathbf{q} - w\mathbf{e})^T \mathbf{p} = 0; \mathbf{q}^T(A^T \mathbf{p} -v\mathbf{e}) = 0\] which gives \[v = w = \mathbf{p}^T A \mathbf{q}\]

Q: Definition. Given a graph \(G = (V,E)\) on n vertices, we associate to every \((i,j) \in E\) the number \(x_{ij}\) which represents [...] The collection x of \(x_{ij}\) is called the flow, the flow is affected by
i) A vector \(\mathbf{b} \in \mathbb{R}^n\), where \(b_i\) is the [...]
ii) The cost matrix \(c \in \mathbb{R}^{n \times m}\), which gives the cost per unit of flow on \((i,j) \in E\)
iii) The lower bound matrix \(\underline{M}\) and upper bound matrix \(\overline{M}\) , give the upper and lower bounds on \(x_{ij}\), so we have \(\underline{m}_{ij} \leq x_{ij} \leq \overline{m}_{ij}\).
A: the flow of a quantity from vertex i to vertex j.; amount of flow entering vertex i from outside the graph. If \(B_i > 0\) then vertex i is a source, if it is negative it is a sink.

Q: Definition. The minimum cost flow is the linear program [...]
A: \[\text{minimise } \sum_{(i,j) \in E} c_{ij}x_{ij}\] \[\text{subject to } \underline{m}_{ij} \leq x_{ij} \leq \overline{m}_{ij}, b_i + \sum_{(i,j) \in E} x_{ji} = \sum_{(i,j) \in E} x_{ij}\]
Back Extra: The second constraint is the conservation of flow. We need \(\sum b_i = 0\) as none of the vertices have any storage capacity.

Q: Theorem. If for some feasible x we have dual varialbes \(\lambda \in \mathbb{R}^n\)(for suppliers) and \(\mu \in \mathbb{R}^m\)(for consumers), such that:
i)\(\lambda_i + \mu_j \leq c_{ij}\)
ii) \((c_{ij} - (\lambda_i + \mu_j))x_{ij} = 0\)
then x is an optimal solution
A: The Lagrangian of the transport problem is \[L(x,\lambda,\mu) = \sum_{i} \sum_j c_{ij}x_{ij} - \sum_i \lambda_i \left(\sum_j x_{ij} - s_i \right ) - \sum_j \mu_j \left ( \sum_i x_{ij} - d_j \right ) = \sum_i \sum_j (c_{ij} - \lambda_i - \mu_j)x_{ij} + \sum_i \lambda_i s_i + \sum_j \mu_j d_j\]\((\lambda, \mu)\) is dual feasible if \(\lambda_i + \mu_j \leq c_{ij}\) for all i,j. We have primal feasiblity, dual feasibility and complementary slackness, so optimality holds.

Q: Theorem. When constructing a basic feasible solution using the transport tableaux, the set of edges with strictly positive flow form a connected graph with no cycles. In particlar, this graph is[...] This allows us to always construct a system of equations as above.
A: a spanning tree T with exactly m+n-1 edges.
Back Extra: No proof is given.

Q: Definition. A cut of a graph \(G = (V,E)\) is a partition of its vertices into two sets \((S, V \setminus S).\) The capacity of a cut is given by [...]
A: \[C(s) = \sum_{\{(i,j) \in E : i \in S, j \in V \setminus S\} } c_{ij} \]

Q: Theorem. For any feasible flow x with value \(\delta\), then for any cut \((S, V \setminus S)\) such that \(1 \in S, n \in V \setminus S\), we have \[\delta \leq C(s)\]
A: For any sets \(X,Y \subseteq V\), define \[f_x(X,Y) = \sum_{\{(i,j) \in E : i \in X, j \in Y\}} x_{ij}\]We have \[\delta = \sum_{i \in S} \left ( \sum_{\{j : (i,j) \in E\}} x_{ij} - \sum_{\{j:(j,i) \in E\}} x_{ji}\right )\]Therefore, \[\delta = f_x(S,V) - f_x(V,S) = f_x(S,S) + f_x(S, V \setminus S) - f_x(S,S) - f_x(V \setminus S, S) = f_x(S,V\setminus S) - f_x(V \setminus S, S) \leq f_x(S , V \setminus S) \leq C(S)\]

Q: Theorem. Let \(\delta^*\) be the value of the maximum flow. Then we have \[\delta^* = \min \{ C(S) : 1 \in S, n \in V \setminus S\}\]So the maximum flow is equal to the cut of smallest capacity.
A: Define an augmenting path to be one from the source to the sink in which more flow could be added, so each forward edge has remaining capacity and reverse edges have some flow. An optimal flow cannot have an augmenting path. Now suppose x is optimal, define a cut \[S = \{1\} \cup \{ i :\exists \text{ an augmenting path} 1 \to i \}\]Therefore \(n \in V \setminus S\), as there is no augmenting path from 1 to n. Then, \[\delta^* = f_x(S, V\setminus S) - f_x(V \setminus S, S)\]But we can show \(f_x(V \setminus S, S) = 0\), so \[\delta^* = f_x(S, V \setminus S) = C(S)\]