Here

It means presenting it to implict form instead of the parametric form.

maximal element of a partial order.

A maximal element is, of the set \(M\), not the set \(W\).

Upper bound of a subset of a partially ordered set.

Observe that an upper bound is not necessarily from the subet \(W\subseteq M\), of the partial order.

Useful for abstract vector spaces Banach Hahn.

A sequence of linear operator such that, pointwise the value of the linear operators are bounded is enough for the norm of the operator to be bounded for the limit of the sequence of linear operators.

Every Bounded linear functionals on C[a, b] is Riemann Integrals.

Strong convergence, equivalences and converse.

weak convergences and its lemmas.

Bounded Linear Functional Theorems in Banach Space.

Hahn Banach Theorem in normed vector spaces

weak convergence in a normed space

Strong convergence in a normed space

The space of polynomials is not a complete space.

The canonical mapping properly defined

Definiton of Adjoint operator in Normed spaces (Not Hilbert!!!)

Representing vector norm using linear functional from the dual spaces.

Example for looking for the dual space of \(l^p\) sequence space.

The example that finite Euclidean space is a self-normed space.

Sequence \(\Vert x_n - c\Vert\) bounded, monotone, and for all \(c \in C\). The real sequence is bounded above and monotone decreasing, limit exists in norm for all \(c\in C\).

Consequence of Fejer Monotonicity

Integral of the limit of uniform converging function is the same as the integral of the lmit. Pay attention to conditions: 1. Closed and bounded interval \([a, b]\). 2. Sequence of CONTINUOUS functions. 3. Of course, converges uniformly.

open set, closed complement and vice versa. In finite Euclidean space.

in \(\mathbb R^n\), intersections/union of open subets are still open.

Union andintersection preserves closedness of sets, in \(\mathbb R^n\).

Complexity of the Floyd warshall Algorithm.

1. Convert the tree structure to a flow.
2. compute the potential and the reduced costs.
3. Select an arc to pivot, keeping the strong feasibility of the tree when changing the arcs on the tree!

Strong feasibility of the tree is at pg 421

strong feasible spanning tree solution definition.

pg: 417

the incidence matrix of a spanning tree graph can be, lower triangular.

The starting node is, the first element from thread. First node from the in-order tree traversal.

for arc (i, j), the frist index is the tail.

Do (a) - (c)

(a): No negative cycle, then flow optimal, we might need the reduced costs positive optimaity conditions?

out of kilter algorithm

Out of Kilter Algorithm

(9.11) is literally the dual LP formulation of the min cost flow problem onthe network.

This is the other way of the proof for theorem 9.4 listed earlier in the chapter.

Expression (9.8) is at page 310 for the complementary slackness conditions, expression (9.7) is page 309, thorem 9.3.

Some flow is optimal, if and only if, there is some potential, where, the reduced costs for the potential satisfies the complementary slackness conditions for the duality of the linear program of the min cos flow problem.

We actually didn't show that the cases that proved below are mutually exclusive cases!

Draw the residual graph G(x) with appropriate arc costs and the updated Residual.

The dual spaces theorem

The dual space of \(l^1\) is \(l^\infty\).

This is probably very important due to the fact that, both field is complete, and they are equipped with norm. And of course, the reals and the complex are technically also a vector field with dim = 1.

The total orderness property is probably important for vector fields in functional analysis.

It's just augmenting the domain of the linear operators to a set which the domain is a subset of.

I don't think we ever defined the concept of linear indepence for a set of linear functionals.

It's inner product.

A linear functional such that: 1. Subadditive. 2. Positive Homoegeneous.

Dual of the dual is just the original space.

The space and the dual space is having the same dimension.

first mention of dual space in this textbook?

It's an example of theorem 2.7-9. A linear operator has boundedness and continuity being an equivalent conditions.

Very similar to the definition of a linear mapping between 2 normed space.

Linear functonal maps from a vector space to the real space.

For a bounded linear operator \(T\), we have: 1. a sequence converge in the domain of T will converge in the image of T after applying the linear transformation 2. The null space of the operator is a closed linear subspace.

The proof make a special kind of construction. It takes a point in \(Z\) but not \(Y\) , and then it find the cloest point in \(Y\) to approxiamte such a vector. Then, the unit vector of, the closest approximation point to the point being approximated can generate a unitary vector that satisfies the conditions we talked about.

If a vector is bounded, and we put this vector into the linear operator, then the output vector from the space would be bounded by the norm too.

Let T be a linear mapping between 2 normed space, then:

1. T is continous if and only if it's bounded.
2. T is continous at a single point then it's continous.

Norm of the linear combinations of vectors are, larger than the sum of absolute value of all the scalar weight, by a strictly positive constant. Only for finite dimensional spaces.

\( \Vert \alpha_1 + \cdots + \alpha_n\Vert \ge c(|\alpha_1| + \cdots + |\alpha_n|) \)

Linear operator, and bounded linear operators are equivalent when the vector space is finite dimensional.

operator norm is actually a type of norm. Linear operators as homomorphism between the vector spaces are indeed a vector space itself. See here.

The properties of the operator norm basically interits the properties from the normed vector space. This is direct from the definition. However, these results are only for the bounded linear operators.

(1) Inverse exists is equivalen to having only \(\vec 0\) for the null space of the operator. (2) When the inverse exists, then it's a linear operator. (3) if dim of T is finite dimensional, then dim of range and domain is the same for T.

1. Range is a vector space.
2. If the dim of the range is less than infinitely, then the dim of the range is \(\le\) dim of the domain.

Zero vector being the identity of the linear operator is not direct from the axiom, but rather, the property of the real field.

Take note that, if we treat the norm as a type of metric, then the conditions for equivalent norm is strictly stronger than the conditions needed for metric, which is stated in convergence of sequences.

A finite dimensional spaces/subspaces have equivalence between compactness and Closed and Bounded. In this case, we infinite dimensions. Then there is some closed and bounded spaces that is not compact.

That was my first thought that is all.

From 11, we have: 1. Norm implies convex norm ball.

Hence the contra positive of the statement will state that, if the norm ball is not convex, then it's not a norm.

Unit Ball in a Normed space is convex

I just discovered that the subspaces in vector spaces are very different compare to metric spaces.

1. A subspace of a metric space just have to be a metric space.
2. A subspace of a vector space will still have to retain the vector space structure. But if it's viewed as a metric space, this doesn't have to be the case.

Also take note that this is talking about any spaces of dimensions.

Continuous mapping preserves compactness in finite dimensional spaces.

Compact Closed unit ball in a normed spaces would mean that we have finite dimension.

Riesz's Lemma, preparing for a theorem about the norm ball in finite dimensional spaces.

compactness is euivalent to closed and boundedness in finite dimensional spaces.

extreme value theorem. A continuous function attains some type of minimum and maximum over an compact set in its domain.

Monotone Subsequence Theorem for real Sequences.

index n1 is larger than the indices for all the dominating terms in the sequence.

A Necessary conditions for a function to he differentiable at a point.

The existence of a minimizer for functions.

7.3 1(a)

7.4, 1(a).

7.3 3(a)

7.3 1(a)

L has lower: [ [-2.1067], [3.0672, 1.1977]], U has upper: [[1.012, -2.132, 3.104], [-0.3955, -0.4737, -8.9391]]

The cute formula, generalized version.

In a finite dimensional space, every norm is Equivalent

Every finite dimensional Banach space is closed.

Every finite dimension subspace of the normed space is complete, so are their subspace.

Alternative explanations from Walfram Math world: here.

In brief, you can use an isometry map from a banach space to another subspace in a different Banach space such that it's dense.

Similar to 1.4-7

Math Stack Exchange

"from the stronger reasoning, we have:", it basically means: "implied" and not "equivalent. "

Classical example, and this feels like uniform convergence of functions, similar principles.

no negative cycles optimal solutions min cost flow theorem

Undergraduate based.

We have to consider it recursively to find a flormula for the number of saturating and nonsaturating pushes/relabel.

Ordered by distancer label and then the lexcicographic order of the nodes label.

Why is this \(2m\) what the fuck dude.

Ok, check: here for more information.

This is an unstated claim where, the proof comes before this paragraph.

gradute based, proof.

Observe that: A minimum flow will require some lowerbound, or else this is trivial because zero flow will always be an optimal solution.

We need to convert the problem to an max flow, with/without the lower bound. 2 Applications of the maxflow probably means that we need a lower bound yes.

2 relabeling is required to saturate one arc once.

algorithm

I think that, the set of active nodes can never contains the same \(j\) such that \(j'\) is also an active node.

Undergraduaet based.

Show the distance labels and excesses at each step. Verify you have the maximum flow by exhibiting an appropriate cut.

There is double arcs on here again what the hell.

Undergraduate based, algorithm.

Show your residual Δ network after each augmentation. Verify you have the maximum flow by exhibiting an appropriate cut.

Why is there a double arc for the graph 7.21(b)? Is it a lower bound for the flow on the network?

Upper bound for the distance label of the preflow push algorithm

dipath connection for all nodes in the graph.

A node is active in the preflow push algorithm when its excess is strictly positive, during the operations of the preflow push algorithm.

This is just using the inductive hypothesis. The indecutive hypothesis hold for all the neighbours of the curren node \(i\), after the delection of the arcs, the neigboring vertices decreased, therefore, valid distance label condition still holds.

The shortest augmenting path matains a correct distance label for all the vertices during the iterations. By valid, we mean that there exists some way such that \(d(j) = d(i) + 1\), where \((i, j)\in A\), for all \(i\in N\).

A reduced cost is generated from a potential assignment on the vertices of the graph.

This is the definition of a reduced costs with potential on the nodes.

Applying the flow decomposition theorem from before, we decompose any flows into a sum of cycles flow and paths flows.

\((i, j)\) is an admissible arc when \(d(j) = d(i) + 1\), whre \(d\) is the distance label from the algorithm, and \(r_{i, j} > 0\).

The complexity of the memeroized shortest aug path max flow.

Not quite Dinic, Not quite Edmonds Karp. It's something in between.

graduate base, proof, see page 195 for theorem 6.11

Undergraduate based:

Using the shortest augmenting path algorithm, solve the maximum flow problem give in Figure 6.22(b). Describe the augmenting paths at each iteration as well as any advances and/or retreats and the distance labels at each iteration. Verify you have the maximum flow by exhibiting an appropriate cut.

In brief, run the Dinic's algorithm for this graph.

Feasibility search for the max flow problem with lower bound constraint.

Didn't mention what happen to the \(s, t\) vertices for the mass balance constraints.

Undergraduate based. (a) F, (b) F. (c) F, (d) F, (e) T, (f) F.

\(x_{i, j}= 0 \dot\vee x_{j, i} = 0\)

shortest path complexity proof is actually around here.

Dijkstra's interpretation from the generic labeling algorithm.

The complexity of the FIFO label correcting algorithms.

Not Bellmand ford, but it's an generic version of the FIFO it looks like.

this is the key that helps to improve the labeling algorithm and develope the idea of FIFO.

The BFS for max flow with retreat.

The proof uses the algorithm.

We implicitly assume that the flow is positive due to how the algorithm works.

Circulation property. Why is it not along a \(m\) many closed walks?

This is only true from the view of the flow decomposition algorithm and not the LP.

Hypothesis (1) holds for set \(s\cup {i}\).

Potential function and its application in Amortized Complexity.

Detecting the negative cycles using Floyd Warshall Algorithm.

Big Omega definition

Definition of Big Theta.

Big O definition

Graudate based.

Undergraduate, modeling based:

Make sure to prove the transformation works after describing it by proving a correspondence between flows of the multiple source/sink problem and the single source/sink problem.

arc disjont s-t path.

A small generalization of the maximum flow problem where lower capacity constraints are introduced for all the arcs.

undergraduate, hw description:

Find the longest path in the residual network by inspection. (Note: finding the longest path in a network is NP-complete unless the network is acyclic.)

Labeling Algorithm Page 184

This is a NECESSARY CONDITIONS for feasibility of the circulation problem.

positive flow path is part of the definition of an augmenting paths!

Subsequence of a Cauchy sequence as the same limit as the mother sequence.

By the statemet hypothesis.

The limit of sequences in \(c_{0, 0}\) that is not in the set \(l^\infty\) completes it by taking the closure of it.

\(c_0\) is the set of all sequences that converges to \(0\) in norm \(\Vert \cdot\Vert_\infty\).

It's about the maximum of partially order sets:

It states that a partially ordered set containing upper bounds for every chain (that is, every totally ordered subset) necessarily contains at least one maximal element.

Warning, property of metric space, not Banach Space specific.

This is not directly from the definition of complete metric, it's from the fact that a convergence sequence is Cauchy for the same metric!

By \(y\) being in the closure of \(Y\).

WTF, absolute convergence, the convergene on the norm of some sequences of elements from the vector spaces doesn't imply that the sequence itself is going to a limit in the space.

Relevant discussion: here, Please think and read carefully about them yes.

Some norm on a vector space, but the vector space might be complete, or incomplete.

Banach Space yes.

Why Cauchy when we already know that the sequence of the function is just the heaviside function at \(x = 1/2\)?????

Because convering to some limit in the spaces never meant that the metric of the sequence can be Cauchy. The metric. To show that it's incomplete, we need to start with the \(d(x, y)\) metric first, and then show that the convergence of the sequence of piecwise linear function converges in metric and then show that the limit is not in the space. Just showing thta it's not in the space is not entirely valid. But we sure can make use of the fact that a converging sequence in metric should also be Cauchy yes.

Subgradient sum rules

Normal cone of the non smooth level plot of a function.

Graduate base, proof. Description:

Gives a proof if the answer is yes or a no.

We would need an arc that goes over $O(n^2)$ many pairs of paths for all the possible path, and we need to firstly show that the previous algorithm 5.40 is not going to work anymore and, if would have no choice to look over almost all the possible path to figure out the optimal path for the pertrubed costs!

Graduate based, proof. Description:

Use the answers from 4.20 to help.

Graduate based, proof. Description:

The state requires that \(s\neq t\) to be true.

By length, the question probably mean the total cost of the directed path.

(a) I think this is just a direct application of the characterization of shortest path conditions, \(d(i, j) = d(i, k) + d(k, j) \; \forall i, j \in N\). (b) I have a feeling that this is a similar proof compare to the Floyd Warshall algorithm as discussed before.

Undergraduate homework question. Description from the assignment sheet:

Order the nodes 1,...,7, and order the arcs with tail node i, A(i), increasing by their head nodes. See next page for the algorithm.

The graph is at the same page. The FIFO Label-Correcting algorithm is exactly the same as Moore Bellman Ford Algorithm. Labels at the end should be: [0, -5, 15, -5, -10]

undergraduated based. Problem description:

Consider the LP formulation of the shortest path problem given on page 94 of the text. Show that shortest path problem LP is unbounded for any feasible network that has a negative cycle.

Undergraduate, description:

Solve the all-pairs shortest path problem using the Floyd-Warshall algorithm to the network given in Fig. 4.15(a). Show the distance matrix for each iteration. To make the matrix more readable, relabel the nodes a,b, ..., f for 1,2,... ,6, and z for node 0.

What the heck is this "z for node 0" under the homework discription, no such node exists in the graph, nor is thre additional nodes for the FW algorithm.

\((i, j)\in A\iff (j, i)\in A\). We allow for arcs with zero capacity. For all single direction arc, the opposite direction arc on the graph is having a capacity of zero.

I think this is essentially a residual graph on the zero flow, which is trivially feasible. Residual graph on the network is covered in the later part of the chapter (pg177).

complexity of the max flow labeling algorithm.

Min cut capacity and the cardinality of maximum number of arc disjoint path from source to destination.

It's proving by showing the existence of a basis that contains infinitely many elements in it.

Recall that function is an element from an vector space and the inner product of the space is the integrals of stuff.

I think it's unique also for zero vector since the set of vector is linear independent?

Also observe that the Hamel basis seems to be finite.

I am guessing that orthogonality is the key. Shcuader Basis is an orthogonal basis and Hamel basis is not...? Also observe that Hamel basis seems to be finite.

Probably by strong convexity and the fact that the function is differentiable on its entire.

Max Monotone Operator related, related to the Surjectivity of the operator or something.

Strong Monotonicity of the gradient/subgradient operator when the function is strongly convex.