augmenting flow is upper bounded by the residual capacity across all \(s-t\) cut.

No parallel arcs.

Doesn't contain a direction path with infinite capacity from source to node. (Makes sure that the problem is not unbounded)

All capacities are nonnegative integers.

The Network is Directed

Aug Path theorem

Undergraduate. Proof based. Take note that the converse is definitely not true. But if we assume cycle exists in the predecessor graph, then there has to be a negative cycle cost directed cycle on the original graph.

Key: Page 137, last 10 lines and keep reading. The invariant of the label correcting algorithm is the key.

The reduce costs of all arcs \((i, j)\) on the predecessor graph have to have a reduced cost that is less than zero.\(\forall (j, pred(j)): d(j) \ge d(i) + c_{i, j}\).

Undergraduarte, algorithm based.

Network flow integers theorem.

The capacity of the cut of any flow is less than or equal to the capacity of any cut in the network, in the context of maximum flow problem.

\(E_i\) is a typo – should be \(F_i\). Also, use the acyclic shortest path algorithm to solve (Topological Ordering Algorithm).

Reduced costs perspective of the shortest path optimal labels, such an interpretation exists due to the reduction from the shortest path to network flow.

• The distance is the dual variable.
• The shortest path label is the negative of the potential, the negative of the dual variables.
• The non-negative condition of the reduced costs comes from the simplex interpretation of the matter.

There is a linear programming interpretation via the network flow standard form and the reduction of shortest path to the network flow problem at the end of chapter 5.2.

Pairs of arcs changed into vertices for the lattice grid. Transform the problem into some type of shortest path. Find the solution of problem (using computer), then show that it's also optimal on the changed graph.

Optimality condition: \(0 \le c^{d}{i, j} = c{i, j} + d(i) - d(j)\)

Argue the transformation is correct.

The \(z(0)\) is the objective function whenever the potential for all the vertices are zero, hence it's the objective of the original problem. In this claim we prove that the difference between the problem with zero porential and the problem with some potential and a "reduced costs" is a constant away, and hence, solving the problem with the reduced costs is the same as solving the original.

Is this some type of primal dual algoithm that we are dong here...

The Original, dumb dumb Dijkstra Algorithm

label format (cost, flow, upper-bound).

• Decompose it into flow
• use theorem 3.8 to check whether the flow is an optimal solution to the minimum costs flow problem.

See page 63 for more information about potential functions and amortize complexity.

• The 3 operations happen in no particular order.
• The Big O notation indicates the number of time of an operations related to parameter m, n.
• It's is given that the potential function is bounded in such a way. It's saying that the operations are carried out for this and that way such that the potential function has this given bound on it.

Read this to compelemnt the lectures.

Given 2 feasible flow, \(x, x^\circ\), it's possible to construct \(x\) with at most m directed cycles on the residual graph \(G(x^\circ)\).

Properties of Reduced costs network. A reduced cost label is created via a potential label on the vertices of the graph. 1. The reduced costs on a path equals to the costs itself. 2. The sum of reduced costs along any path is the original cost minus the differences between the destination and the source.

It's like a line integer over a conservative field in physics you know, the value we get by subtracting the reduced costs over circle and path gives the differences in the potential. Just like a conservative field in physics.

Residual Network is a transform on the network given an existing feasible flow.

This exercise has been rerefenced due to it being heavily references throughout the text.

Trees of graphs: - A tree on n nodes contains exactly n - 1 node. - A tree has at least two leaf nodes - Every two nodes of a tree are connected by a unique path.

All Assumptions in chapter 4 applies here.

In the proof below, please observe that, the path \(P_2\) can cross with \(P_3\), therefore it said it's a \(P_2-P_3\) Directed Walk instead of a path, and then arising from here, it applies the none existence of negative directed cycle on the graph!

This is a direct applications of property 4.1.

Restate it in Clearer Mathematical Terms

Assuming that \(d(i)\) is the shortest path path length from a source node \(s\) to any other vertices: \(i\), let\(P\) denote the shortest s-i path then the following statements are equivalent: - a directed path P is a shortest path from a to k - \(d(j) = d(i) + c_{i, j}\; \forall (i, j)\in P\)

We still assume all the assumptions 4.1, 4.2, 4.3, 4.4

next

Why in part (b), it says "that a (connected) graph". What is the significance of this particular condition here?

Because one example of an disconnected graph is 2 discrete cycle, which could both have odd length, and yet the graph is bipartitle

This assumption is not useful for part (a) of the proof.

Think back to the even cycle problem from 2.21 when judging this problem.

I think all of them are true.

For something that is very useful, please vists here, the wiki section with the definitions for everything.

An algorithm stated in long paragraph before this point. Applies for: 1. Direct Acyclic Graph Algorithm: Given a topological ordering of the graph we: - set \(d(s) = 0\) for source vertices and \(d(i) = \infty\) for all the other vertices. - for all \(i\) in topological order: - for all arcs coming out of \(i\) to \(j\), if \(d(j) > d(i) + c_{i, j}\) then we set \(d(j) = d(i) + c_{i, j}\), and setset the predecessor for \(j\) to \(i\).

All out going arcs from vertex i, state at the ver start of the chapter.

Assumptions required for labeling algorithms, and non-directed edges can be reduced to parallel double edges.

Optimal distance \(d(i)\) is given in advance.

None Unique.

This is HW1 * (a) Directed in tree are directed tree where all path goes from the leaf to the root. * (b) Directed out tree are directed tree where all the path goes from the root to the leaf. * (c) Fundamental cycle: Given a spanning tree, adding any edge will create a cycle on the tree, and that is a fundamental cycle. Take note that the cycle doesn't have to be directed, see page 26 for the definition of a cycle. * (d) Foundamental cut: Given a spanning tree, removing any edge will break the tree apart, forming 2 subset of vertices that is the cut.

Tree: Page 30

Justify your answers with a proof or a counterexample.

For just Fig. 4.15(b).

Draw the network at each stage with the distance update(s) identified, the permanently labeled node(s), the node chosen to be permanently labeled, and the current tree.

Do this one, it's useful for future lectures.

The proof is direct from the fact that a subset of \(\sup\) is smaller gonna be larger than the \(\sup\) of the super set.

Paculiar, I have no idea about the significant of this theorem and why it's stated here. How does this variation of the theorem even make inuitive sense?

This is direct because the characterization contractive mapping resemble the Lipschitz Continuity in real analysis.

Showing something is complete is actally harder than showing something is incomplete, because the trick of looking for an counter example sequence that punch a hole in the space is no useful.

consider the element sequence \(x = (1, 1/2,/3, 1/4, 1/5, 0, \cdots)\) all the way to infinity. Then another sequence that is the truncation of the sequence is in the set \(M\), and it converges to \(x\), but it's not in \(M\). This subspace is incomplete.

This is also not hard to invoke the Cauchy criterion.

Just use \(n, n > \tan(N)\) and exploit the fact that limit of \(\arctan\) is \(\pi/2\). The sequence \(x_n = n\) does the trick. This time we use the Cauchy criterion for the convergence.

theorem

yes. It's kinda obvious if you know \(\Vert \cdot\Vert_2\)

A direct application of the holder inequality, which is proved.

Check out these pathologies, they look quite fun.

homework

Definition of Compactness Remarks

Compactness is defined by the existence of converging subsequence of any sequences. The "close and boundedness" is only a characterizations of compactness when we have finite dimension Euclidean space.

See page 197 about the \(p_n(x^3)\).

This is a special case of the Newton's interpolation formula where \(x_1 = x_2 = x_3... =x_n\).

The famouse failure case of the Taylor series. A proof by indiction is use to show that derivative for \(f\), and then it's used to show that all derivative of \(f\) are zeros at the point \(x = 0\).

The slow convergence rate of the archtan at \(\pm 1\) is revealed here after all these years.

Matching polynomial's derivative and the function's derivative at one point x = a.

Exercises to do: A, B, C

How and why....

The closure and the openedness of a set is relative to the background topology defined, in this case, we defined the set \(X\) with the metric different compare to the previous instance.

Open and closedness of a subset in the metric space via epsilon ball topologies.

Theorem:

metric equivalences preserves sequential convergence and openedness of sets.

2 Metric is equivalent if they one can be bounded by the other one with just a constant.

This is important when we are talking about many different type of metrics all at the same time. And we would also have a way of categorizing them.

A convergence sequence is a Cauchy sequence under a certain metric.

My interpretation of the matter:

Let \(M\subseteq X\) be dense then for any element in \(M\), it's neighborhood has to contain some element of \(X\) then the subset is dense.

It might be saying that with certain norms, we don't have separable spaces, and that would create the illusion of convergence under this particular subspace but it migh actually be converging from other alternative metrics?

sequential continuity of a mapping in the metric space.

Proof Summarized in brain dead layman's terms: * Ignoring the trivial case where $x\in M \cap \bar M$, we choose some $x$ to be the accumulation point of \(M\). * Since accumulation point, we can open epsilon shrinkage region with singleton isoluation to define a sequence. * Such a sequence will always be in \(M\) by the epsilon ball definition of \(x\in \bar M\). * The sequence will converge by the singleton isolation shrinkage epsilon ball.

For an accumulation point in a subset \(M\) of space \(X\), any epsilon balls with central isolation has ifninitely many points and there is a sequence in such epsilon ball such that it converges to the singularity but never really being on the singularity.

Singularity: \(x_0\) as described in the proof.

Theorem 13

The equivalence of the sequential closedness of a set and the epsilon ball closedness of a set.

accumation point defined without the sequences and their covergence. This definition is cloest to the closure of the set.

This proof establishes a spcial kind of sequences containing only ones and zeros. The set is a countably infinite subset of \(l^\infty\), but we showed a way to separable all the elements with open balls such that none of them are overlapping.

By doing this, we showed that the closure of the subet \(S\) is not going to be the space itself, hence the space doesn't contain a dense subset, hence it's not separable.

Characterization of a limit point of a set via a limit that occurs inside of the set.

This definition is different compare to some literatures where a limit point \(x\) is a point if a sequence \(x_n\in A\) have \(\lim_{n\rightarrow \infty} x_n = x\). What distinguishes it here is the claim that "Other than X".

A briefer way of defining it is: The point \(x\) is not isolated in if wrt to the set \(A\).

floyd warshall algorithm

The algorithm describes a way to construct a graph with potential and non-negatie arcs. The original graph cannot contain any negative cycles.

The reduce arc length/cost, will be non negative when an optimal distance from a source node is given.

The analog situation should provide intuitions for a primal dual realizations of the LP programming problem solved via some of the algorithms that we are going to develope next???

1. All arcs are intergers.
2. Directed path exists from a source vertex s to every other node.
3. No directed cycle with a total of negative costs are involved.
4. The network is directed. Exactly the same as the 4 assumptions in chapter 4 of the textbook.

By re-rearranging the optimality conditions for the shortest paths between vertices.

By the property of reduced cost

This is a function that is convex but not continous at one point in 2D. It's a case of a support function of a set.

Figure 2.28

closed directed walk: A walk that starts and end on the same vertex.

• Walk has odd number of arcs => It contains an odd directed cycle in it.
• Walk has even number of arcs => It contains an even direct cycle in it?

What does it mean to have a walk containing "n" number of arcs? If the arcs repeats in the graph, do we need to count it again?

If \(d\) is the max degree of vertices in a tree, then the tree contains at least \(d\) many vertices with degree 1.

To consider the problem, we consider the worse case where he number of degree one vertices equals to the maximum degree of the tree.

I don't understand the hint and an inductive argumet works for me.

Do this one.

Proof by contradiction is the simplest way to go I think.

Read this to complement the lectures about tree searches on a graph.

The key is that a cycle is a path that doesn't walk over the same arc more than once.

Take note that, if arc \((i, j)\) belongs to a cycle in \(G\), it doesn't say anything about whether \(G\) is connected or not. If it's not connected, then removing an arc is still connected. Therefore I think this question is assuming that the graph is connected when proving it in both directions.

Circulation problem is where the mass balance on the vertices are always zero, but this problem is an assignment problem, not circulation. 1. We are minimizing the resource commitment. If a car is used for a shift, it can be used again for another shift, but that will count towards the objective as an extra commitment. 2. When we assign a police car, it can come frome the reserve of a precinct, OR, a previous shift of the day. 3. The mass balance constraints resembles circulation because we are not destroying police cars.

Residual Network and feasible flow.

non-isomorphic: Not the same tree by re-arranging the vertices, permuting the vertices, (but the arcs still stick to the same vertex).

This actually gives a better formulations of the LP, because we now have \(Mx = b\) where \(M\) is the adjacency matrix, and, \(x \ge \mathbf 0\), which is a cone. More importantly, whenever we have \(b\) to be integers vector, the system is unimodular I think.

If we have a positive lower bound for the undirected edge, and a negative costs, then after transforming it, the problem is now unbounded I think.

This should be \(b_j\).

Given a flow, we decompose it into a cycle of flows, or paths of flows.

*

(i, j)?

Convex proper function are locally Lipschitz in its relative interior.

Ignore isolated point yeah.

This is a much more general definitions than the usual sense of point wise continuity because it's applicable to general topological spaces, IF, the 'neighbourhood' can be defined differently.

The Proof has 2 parts. We want to prove the equality between the proposed set and the closure of the positive quadrant. It's a 2 direction proof. Let \(\text{int}(\mathbb R_+^n)\) be the closure, let \(\mathbb R_{++}^n\) be the proposed set.

• The first part proves \(\mathbb R_{++}^n\subseteq \text{int}(\mathbb R_+^n)\)
• The second part prove the other direction using a prove by contradiction.

In L2 sequence space, this shit, the positive quadrant is like a freaking singleton that is quite dope if you think about it.

here, we are showing that any element outside of the set is definitely not the interior of the set, by showing that it's not fitting the definition of the interior, this is necessarily because we are proving the EQUALITY between the claimed set and the interior definition of the set.

The interior of the positive quadrant of the finite dimensional Euclidean space exists and it's non-empty.

By the specific choice of \(r = \min{x_1, x_2, \cdots, x_n}\), we guaranteed the inclusions of the ball inside of the set \(\mathbb R_+^n\circ\). Therefore, we have proved that the set we claim is indeed open, and it's also a subset of \(\mathbb R_+^n\), however, is this open set the largest there is?

That is what the second part of the contradictory proof is addressing.

\(x_i \le 0\) might be better here for the contradiction?

Divides both side by the big ass positive sum.

Where did we used the fact that \(p\ge 1\) in the following proofs????

Its used to determine that the beta we get is indeed, a maximizer, in fact, it used a weaker condition that \(p> 0\), instead of the stronger one. The Fenchel's Young Inequality is, using a weaker conditions than the Holder's inequality for the quantity \(p, q\).

And it's used again in the Minkowski's inequality proof, the first line.

You see, the function \(x^p\) is monotone for any choice of \(p\) that is nonegativ. So that where \((\cdot)^{1/p}\) is not affecting the inequality for sure. It has to be about splitting the sum and the convexitywhen \(p > 1\).

Triangular inequality is broke.

Conjugate pair conditions encodes a constrained optimization problem and we seek to find the maximum term of \(\alpha\beta - q^{-1}\beta^{q}\) or, vice versa due to the symmetry of the argument.

Fill this in.

Exercises proves that the Cantor Set is a totally disconnected set.

Woah! Remember that the cantor set is also closed, and it's nowhere dense too. Immediately recall that, a bounded real sequence must has a converged subsequence (Bozano Weierstrass). Observe that the converse of this fact is genralized into the definition of compactness in a general topological space.

This is kinda dope if you think about it.

Definition of a Nowhere dense set.

A set is separated if can be written as the disjoint union of 2 sets.

Perfect set: Closed and with no isolated points.

The Cantor set would be a perfect set.

read this please. [Not yet done], for more, see Volterra's Function

Every sequence of numbers from the set is going to be bounded and it will converge to a point in the set. To show that part, we need to show that \(x\in E_1\cap E_2\cap\cdots\), which is in the sequence of monotone sets.

This theorem is important!

Definition of compact set!

If a sequence in \(K\), a subset of real has a converging subsequence (A cluster point from that set), then the set \(K\) would be a closed set.

Yes

No.

Every point in \(B\) is isolated.

\({\pm 1}\).

Density of \(\mathbb R\) in \(\mathbb Q\).

\(\mathbb Q\), the set of rational is dense in \(\mathbb R\).

An isolated point is a point in \(A\), a subset of real where there exists an \(\epsilon\) region such that no other point from the set \(A\) is in that epsilon region.

Refers to: Def 3.2.6

Ok.

For a full coverage of the convergence of the classical Weierstrass's Function, consult: Berkley's lecture notes

For a specific choice of \(a, b\) that results in non-differentiability, consider reaing 8.4.9 of this book.

A search on Wiki reveals that \(ab > 1 + (3/2)\pi\) with \(a\in (0, 1)\), \(b\) being a odd integer. This doesn't have a format the fits the Weierstrass's M-Test.

First annotations to test on things.

Fejer Monotone but the sequence set also have a limit point in C.

Plase observe that \(x\in C\) is arbitrary, and this monotonicity holds true for all \(x\in C\), and \(C\) can be wacky sets of all kinds.

Under the assumption that we don't have strict monotonicity, and assuming that \(C\) is a singleton, then it's possible that a trajectory of \(x_n\) circulates that sington, it would be Fejer Mono, but it won't converge to anything. \(\vert x_n\vert\) won't converge to anything.

Thomea's Function:

• It's pointwise continuous for all irrational number
• It has a removable singularity at all rational number.
• It has a limit on everypoint but discontinuous on a dense set.

Cluster Point!

Observe the conition \(a_n \in A, a_n \neq x\) inside the subspace of euclidean space. Every point where it has an epsilon ball around it and it's not in the subset \(A\) is not a cluster point, but it can be a limit point!

Basically, cluster points excludes isolated limit points.

A subset of \(\mathbb R^n\) is compact if and only if it is closed and bounded.

Limit Point! Which is not a cluster point!

Read This! It illustrates an instance of Weierstrass's function that diverges.

Weierstrass's proof generalized for all values of \(a, b\) such that this is not differentiable everywhere, here we are only looking at the case where \(a = 1/2, b = 10\). A special case of Weierstrass's original argument.

This converges too slowly compare to how the denominator is going to converge for the sequence.

Wonderful.

It suffice to assume that the number we are taking the derivative of is in between \((-10, 10)\) because, this is true because the term with the longest period is \((\cos(10 \pi x))\), which has a period of \(2/10 = 0.2\). We can even assume \(x_0 = 0\) because the cosine function are just copies of the function on interval \((-\pi, \pi)\), upside down and repeats.

The format we assumes covers a much larger range that the interval yeah.

Finding an out tree that no directed cycle exists on the out-tree. * Choose the vertex with only out-arcs. Remove that vertex. * If there is no such a vertex, then terminates. * else repeats. * If there arevertices left, then a direct cycle is inside the remaining graph, else, the order of removing the vertices gives us a topological ordering for the graph.

The definition of an admissible arc is changed, not the direction of the arc. A reverse search generates an in-tree instead of an out-tree.

Reversing the direction of the arcs and then run an forward algorithm is not the same as reverse search.

Using a stack, and pop the tail of the list to choose the admissible arcs.

• The order of visinting each node in the tree, are consecutively ordered for all the descendents of a given vertext.

It choses any random vertices in the list and then update the arcs on the graph, and it filles in the predecessor and the order of discovery for each of the vertices.

The goal is to generate an out tree on the graph based on the starting vertex.

• In the test, it would be great to select the arcs that points to the vertex that is labeled with the smallest number from all.

A quque is used, we always choose from the head of the list to update the arcs. It means visiting the parent vertices on the tree before visiting the children vertices on the BFS tree.

• It gives the shortest path (In terms lf the number of vertices) to go to each of the leaf nodes in the graph.

\(h_1\) is proper convex but in augmented real, but \(h_2\) is real-valued and convex.

We may assume that both \(h_1, h_2\) are proper, then we can negate the condition that one of them is real-valued.

This is an important type of set convergence!

An approach of taking derivative directly is not used, since without the uniform convergence of the derivative, one cannot proceed and take the derivative of the series of functions.

Taking the derivative on the partial sum of the series is also a challenge, because the terms are changing depending on what vaue for the index \(n\) is given for the trig functions.

Here, I have to point out the this condition is artificially made for the convenience on the proof of the theorem, and additionally, we don't know whether this is strictly necessarly, there might exists weaker conditions for parameter \(a, b\) such that the non-differentiability of Weierstrass's Function still persists for the function over the real.

Again, what the fuck this is.

Unnecessary but ok.

Not Sure How. It might be using the summation of geometric series. How is \(a^n\) handled. Mutiply the \(a\) in and then use the geometric summations, and then we should get the inequality.

• Factored out \((-1)^{\alpha_m}\) on the numerator.
• Substituted the definition of \(y_m - x_0\).

Not sure what this mean.

Use \(b_mx_0 = x_m + \alpha_m\).

Using the fact that \(b_n\) is chosen to be an odd integers.

Using the fact that \(\alpha_m\) is an integer, and this has a period of \(2/b^n\).

\(b_m\) cancels out.

Divides the next inclusion bothsides by \(b^m\), then it's moving the point \(x_0\) by a full period using \(\almpha_m\) to the interval \((-1/(2b^m), 1/(2b^m)]\).

The sequence, \(x_m\) is compressed to the quarter period left and right around the origin for the function \(\cos(b^m\pi x)\).

Weierstrass sumee is having a period of \(2/b^n\), it's scaled by a number \(a\in (0, 1)\), notice that the range of \(\cos\) is \([-1, 1]\), by Weierstrass's M-Test we are cool.

Not only that, it's also uniform continuous, every \(f_n\) is uniformly continous, therefore, the resulting limiting function is very much uniform continuous.

At here, sum is splitted into 2, one from \(0\rightarrow m-1\) inclusive, while the other one goes from \(m\) to infinity.

Recall \(a_n \in (0, 1)\).

Relavent discussion on math stack exchange.

Why not just directly take the derivative on the partial sum of the functions and then show that it's diverging? Why are we precisely using the definition on each of the terms in the sum?

Web link

Interesting. It's easy to see that it's not Lipz, but how is it Holder Continuous with \(a < 1\)?

Another thing that relates the construction process of the Weiestrass function is the fact that the limit of a sequence of differentiable function can be non-differentiable, regardless of the fact that the type of convergence is uniform.

In brief: Uniform continuity doesn't preserve differentiability.

And it would also means that the space of differentiable function is incomplete.

Under convexity assumption, a basic cone (The projection based cone) is equivalent to the regular tangent cone.

A basic normal cone is equivalent to the outter set limit of the regular normal cone centered at \(x\) as \(x \rightarrow \bar x\) in \(\Omega\).

The regular normal cone refines the definition of classical convex normal cone, and when we do things at a set that is locally nonconvex, we will get empty set as the normal cone instead of a "cone" that is nonconvex.

Such a definition is consistent with Dimitri's and Jame Burkes definition of normal cone I think.

This is the limit of a set value mapping. It's fundamentally related the limit of a set. See wiki link for more about the limit of a set.

In hour conext, the \(\lim\sup\) here is the infinite tail end union of sets.

In brief, an normal cone of a set is the outter set limit of all the cone generated by the set \(\text{cone}(x - \Pi(x; \Omega))\) as \(x\rightarrow \bar x\).

Immeidately observe that whenever \(\bar x\) exists in the interior of the set \(\Omega\), the norm cone going to be the set \({\mathbf 0}\).

Uniform convergence of \(f_n\) killed it for both \(x_0, x\) in RHS of the inequality.

Continuity of \(f_n\).

This is the key of uniform convergence for a sequence of function, the parameter \(n\) we used here, is fixed for all \(x\), or using a more advanced way of phrasing is that, \(\vert f_n - f\vert\le \epsilon\). With this, this problem becomes exactly the same as the convergence of a sequence of the norm of the function.

The way of parameterizing the parameter in the statement is just beautiful.

Related to semidefinite programming, this equality constraints specifically comes from a semi-definite cone.

Relevant resources: https://www.princeton.edu/~aaa/Public/Presentations/IOS16_deKlerk.pdf

Reduction to a standard representations of graphs that is suitable for network flow problems.