\begin{align} \min_{x}\ &c^{\top} x \\ s.t.\ &Ax \leq b \\ & x \geq 0 \end{align}

• linear objective function
• linear constraints

single our inequality forms a half-space; the entire feasible set is denoted by a series of linear functions—-these linear equalities are each CONVEX. The resulting feasible set, then, is ALSO convex—-meaning any line within the set remains within the set. So, any local minimum is a global minimum.

3 cases of design points

1. points on the interior of feasible set is always non-optimal, because we can always move along \(c\) gradient
2. points on the faces could be optimal IFF the face is perpendicular to \(c\), the gradient of our objective function—but you can always slide along the face, making there be infinite solutions if its on a face (because \(c\) doesn’t change along that face)
3. points on vertex could be optimal
4. unclosed feasible set—possibly unbounded solution

linear program equality form

\begin{align} \min_{x}\ &c^{\top} x \\ s.t.\ &Ax = b \\ & x \geq 0 \end{align}

Linear Dependence Lemma is AFAIK one of the more important results of elementary linear algebra.

statement

Suppose \(v_1, \dots v_{m}\) is an linearly dependent list in \(V\); then \(\exists j \in \{1, 2, \dots m\}\) such that…

1. \(v_{j} \in span(v_1, \dots, v_{j-1})\)
2. the span of the list constructed by removing \(v_{j}\) from \(v_1, \dots v_{m}\) equals the span of \(v_1, \dots v_{m}\) itself

intuition: “in a linearly dependent list of vectors, one of the vectors is in the span of the previous ones, and we can throw it out without changing the span.”

A linear map to numbers. Its very powerful because any linear functional can be represented as an inner product using Riesz Representation Theorem

constituents

• vector space \(V\)
• a linear map \(\varphi \in \mathcal{L}(V, \mathbb{F})\)

requirements

\(\varphi\) is called a linear functional on \(V\) if \(\varphi: V \to \mathbb{F}\). That is, it maps elements of \(V\) to scalars. For instance, every inner product is a Linear Map to scalars and hence a linear functional.

additional information

Riesz Representation Theorem

Suppose \(V\) is finite-dimensional, and \(\varphi\) is a linear functional on \(V\); then, there exists an unique \(u \in V\) such that:

Suppose you have continuous random variables \(X,Y\), you can use one to seed the value and the other to change the Gaussian distribution:

\begin{equation} p(x\mid y) = \mathcal{N}(x \mid my + b, \sigma^{2}) \end{equation}

A linearly independent list is a list of vectors such that there is one unique choice of scalars to be able to construct each member of their span.

Based on the same technique as in the proof that a sum of subsets is a direct sum IFF there is only one way to write \(0\), we can show that in a linearly independent list, there is (IFF) only one way to write the zero vector as a linear combination of that list of vectors —namely, the trivial representation of taking each vector to \(0\). In fact, we will actually use that as the formal definition of linear independence.