Math317Fa26 Lec08 BasicFeasibleOptimal

Overview

Steven Miller connects linear algebra to linear programming by defining a basic feasible solution as a feasible x with linearly independent columns corresponding to its nonzero entries. He shows that there are finitely many such candidates, proves that any feasible system has a basic feasible solution using a minimum-support descent argument, and states the parallel result that an existing optimum has a basic optimal representative.

Key takeaways

A basic feasible solution satisfies x ≥ 0 and Ax = b, with the columns of A indexed by nonzero entries of x linearly independent.
For an n-by-m constraint matrix, no basic support needs more than min(n,m) columns, giving at most Σₖ₌₁^min(n,m) C(m,k) candidate supports.
If A has independent columns, AᵀA is invertible even when A is rectangular, and for b in A's column space the unique solution is x = (AᵀA)⁻¹Aᵀb.
Every feasible linear system has a basic feasible solution: a feasible point with minimum nonzero support cannot have dependent support columns, because dependence permits a nonnegative-preserving move that removes a component.
An optimal solution, when one exists, has a basic optimal representative, so optimization can focus on basic feasible candidates rather than every point in the feasible region.

Chapters

0:00 Linear Independence and the Column-Space Meaning of Ax

Linear independence means the only combination α₁v₁ + … + αₖvₖ = 0 has every coefficient equal to zero.
In n-dimensional space, more than n vectors must be dependent; fewer than or equal to n are generically independent.
Writing A as columns a₁ through aₙ gives Ax = x₁a₁ + … + xₙaₙ, so Ax lies in A's column space.

5:00 Basic Feasible Solutions Select Independent Nonzero Columns

A feasible solution satisfies x ≥ 0 and Ax = b; a basic feasible solution adds independence of the columns paired with nonzero x entries.
Columns corresponding to zero entries do not contribute to Ax, so the basic condition only concerns the nonzero support.
Miller motivates the restriction by the diet problem, where an optimum can be found at a vertex rather than by checking infinitely many feasible points.

7:30 Why Linear Programming Searches Basic Feasible Candidates

A basic optimal solution is an optimal solution that is also basic feasible, meaning it has minimum cost among basic feasible candidates.
The goal is to replace an infinite feasible region with a finite set of candidates that can be searched systematically.
If multiple points on an optimal line segment share the same cost, an endpoint vertex is sufficient as an optimal representative.

11:00 Independent Columns and the Invertible Gram Matrix AᵀA

A matrix with three independent columns may be rectangular, such as an R-by-3 matrix, and therefore not itself invertible.
For an R-by-3 matrix A with independent columns, AᵀA is a 3-by-3 invertible matrix.
When b lies in A's column space, the unique coefficient vector can be recovered as x = (AᵀA)⁻¹Aᵀb.

16:00 Linear Systems Have Zero, One, or Infinitely Many Solutions

A linear system Ax = b has zero, one, or infinitely many solutions, never exactly two.
If x₁ and x₂ both solve Ax = b, then every combination t x₁ + (1 − t)x₂ also solves it.
Independent columns yield at most one coefficient vector, while dependent columns can create non-uniqueness.

20:00 Counting Basic Feasible Solutions with Column Subsets

For an n-by-m matrix, at most min(n,m) columns can be linearly independent.
An upper bound on candidate supports is the finite sum of binomial counts, Σₖ₌₁^min(n,m) C(m,k).
Each independent column subset determines at most one coefficient vector for Ax = b, establishing finiteness, though Miller cautions that a finite count can still be computationally enormous.

27:00 Descent Proof Technique Illustrated by √2 Irrationality

Miller proves √2 irrational by assuming √2 = p/q with relatively prime integers p and q.
From 2q² = p², p² even implies p is even; substituting p = 2a then shows q is even too.
Having both p and q divisible by 2 contradicts gcd(p,q) = 1, illustrating descent through a contradiction to a minimal or reduced solution.

32:00 Every Feasible Linear Program Has a Basic Feasible Solution

Choose a feasible x with the fewest nonzero entries; if its corresponding columns are independent, it is already basic feasible.
If those columns are dependent, a nontrivial relation lets one column be expressed using the others and creates a direction that preserves Ax = b.
Rescale the dependence direction and choose a sufficiently small feasible step so x remains nonnegative while at least one component becomes zero.
The resulting solution has fewer nonzero entries, contradicting the minimum-support choice; therefore the chosen solution must be basic feasible.

45:00 Basic Optimal Solutions and Further Descent Examples

Miller states that if an optimal solution exists, a basic optimal solution exists, and challenges students to adapt the minimum-support proof.
He recommends attempting the proof before consulting the textbook to test whether the descent argument is understood.
The closing examples include geometric irrationality arguments for √2 and √3, plus triangular numbers such as 1, 3, 6, 10, and 15.

Transcript excerpt

0:00 Math 317 operations research. This is lecture eight. So we're going to be talking about basic feasible and basic optimal solutions. There is a natural question that should be asked that I'm deliberately not going to ask initially. So we're going to finally start to use some of the results from linear algebra and see why they could be useful. So just a little bit of review on definitions. linearly independent. Nonzero vectors are linearly independent if the only way a linear combination of them alpha 1 v1 plus dot do alpha k vk equals z is that if each of the alphas equals z. You normally work in you know n dimensional real space. The vectors are integral of real numbers. They could be other spaces as well. You might look at function spaces and then you have to ask what does it

0:47 mean to talk about linear combinations of functions and then what other notions can be generalized? We can talk about vectors being perpendicular. Can you talk about functions being perpendicular? Did you guys have conversations like this in linear algebra? Okay. So you used the integral as a way to get a generalization of the dot product. Excellent. Perfect. And so you've seen stuff like this with Taylor series of functions where we would expand a function in terms of the basis 1x x x^2 x cubed. There are other bases you can use. If your function is periodic, you want to use ss and cosiness. And so depending on what symmetries, what behavior your system has, you choose a different basis. Again, this is one of the big themes of linear algebra. Choose whatever basis makes the calculations as nice as possible. Okay. If the vectors are not

1:34 linearly independent in a shaka, they're said to be linearly dependent.

This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.

In this course

Related notes

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Steven Miller.