Math 525: Linear Optimization

Taken at UW Madison during Summer 2026. The textbook used was Introduction to Linear Optimization by Dimitris Bertsimas and John. N Tsitsiklis

What is the definition of a General Linear Programming (LP) problem

Really all you need to remember is the constraints (Video 1)

What is a feasible solution

A feasible solution is a vector x satisfying all the constraints (Video 1)

What is the feasible set

The feasible set is the set of all feasible solutions (Video 1)

What is the cost of a feasible solution x

c’x where c is the cost function (Video 1)

What is the optimal cost

The value of c’x (Video 1)

What mathematical operations do you need to do to convert a general linear programming problem to the more simple form

Make sure all your constraints are greater than inequalities (Video 1)

What is the definition of equivalence of linear programming problems

(Video 1)

What is the lemma associated with equivalence of linear programming problems

(Video 1)

What is the definition of Piecewise Linear Convex Functions. What is the “main” example for this

The main example is the absolute value function, f(x) = |x| = max{x,-x} (Video 3)

Consider the family of parallel lines shown in the image, where a₁ and a₂ are fixed (don’t change) and b is not fixed. What does the vector (a₁,a₂) tell you.

It always points in the direction where b increases. So if you want to maximize the objective function, you go in the direction of that vector. If you want to minimize the objective function, go in the opposite direction of that vector (Video 4)