in which i cover the linear programming component in [[00_Plan]] lecture05.pdf (stanford.edu)

objective function : the function we want to optimize feasible solution: an assignment of values that satisfies the inequalities

Primal¶

Geometric Interpretation¶

![[Pasted image 20221112115923.png]] Given the above LP, we can think of each constraint as a line that divides the cartesian plane into a feasible and unfeasible region.
Then the feasible region of all constraints is the overlapping feasible region.
![[Pasted image 20221112120245.png]] Note that the feasible region is has 4 edges! This is because we have exactly 4 constraints :)
Note however that it doesn't have to be that the region is bounded, and even the objective function can be unbounded! We can also have unbounded LPs (leading to strong vs weak duality?)

Standard form of LP¶

For an objective function $\text{maximize } c_1x_1 + c_2x_2, ... c_nx_n$, we can express it in standard form via $ ![[Pasted image 20221112120738.png]] Every variable in the objective is non-negative All other variables are subject to a $\leq$ constraint

where $c^T$ is the row vector of coefficients of the objective function
$x$ is a column vector of variables, such that $c^T x = c_1x_1, c_2x_2, ... c_nx_n$ (1xN matrix * Nx1 gives a dot product)

matrix multiplication is just the dot product of the rows of matrix 1 with the columns of matrix 2

$A$ is the $n \times m$ coefficient matrix for $n$ variables and $m$ constraints so each column $i$ corresponds to the coefficients for the $i$th constraint each row $j$ corresponds to all the constraints that the $j$th variable is involved in this becomes important to understand well when we're solving the dual $b$ is an $m \times 1$ vector for the scalar constraints in the primal
$Ax \leq b$ gives us $a_{1,1}x_1 + ... + a_{1,n}x_n \leq b_1$ and more generally $a_{m, 1}x_1 + ... + a_{m,n}x_n \leq b_m$ Entry $a_{i,j}$ is the coefficient for the $i$th variable in the $j$th coefficient

Converting to standard form¶

If we have the constraint $x \geq 12$, can convert to $-x \leq -12$ , $a_{i,j}=-1$ and $b_j = -12$ If we have an equality constraint $x = 12$ , we can just add two constraints $x \leq 12$ and $-x \leq -12$

Duality¶

lecture06.pdf (stanford.edu)

playing with constraints¶

first and foremost, observe that we can play with constraints however we'd like as long as we maintain equality.
We can scale each inequality such that $2a + 4b \leq 6c$ is equal to $a + 2b \leq 3c$
Given two constraints $a \leq b$ and $c \leq d$, we can make a third inequality that must be true $a + c \leq b + d$

Note that this inequality is less strict, since we can satisfy this third inequality while violating the other 2.

Given that we can scale them, we also have that $2a + 5c \leq 2b + 5d$ This is known as taking a linear combination of the constraints. The whole shebang about taking the dual is really just searching for a linear combination of constraints to convert them into an upper bound of the objective Any set of feasible solutions will also be feasible for the linear combination of constraints, but not every feasible solution for the linear combination is feasible for the separate constraints.

![[Pasted image 20221112123001.png]] If we take 1/2 the first constraint, 1/2 the third inequality, and add them all up, then for every feasible solution, we get that $x_1 + 2x_2 + 1.5x_3 + x_4 \leq 2.5$ In the objective we have $x_3$ not $1.5x_3$, so we now know the solution can be no larger than $2.5$. But we also note that this doesn't give the exact upper bound necessarily

Linear combinations¶

How do we find a good choice of scaling factors for the inequalities to minimize the upper bound (lower bound is tighter) We can introduce new scaling factors $y_1, y_2... y_m$ to scale each constraint's linear combination. Then the linear combination will yield an inequality like ![[Pasted image 20221112133510.png]]

which we can rewrite as ![[Pasted image 20221112133746.png]] This final formulation that we want to minimize $\sum_{i=1} b_iy_i$ makes a lot of sense because we're scaling each constraint with an upper bound of $b_i$ by $y_i$, so minimizing their sum will directly minimize the upper bound

The dual's constraints each addresses a different variable in the primal's objective: in order for the linear combination of constraints to provide an upper bound on the objective, it must be that for every variable $x_i$ in the objective, the linear combination of constraints is at least $c_i$ for example, our first example found a linear combination of constraints such that the feasible solution satisfies $x_1 + 2x_2 + 1.5x_3 + x_4 \leq 2.5$ The actual objective had $c_3$ = 1. So this solution provides an upper bound since 1.5 > 1

Relationship between primal and dual¶

Dimensions: $A_{i,j}$ is the coefficient for the $i$th constraint for the $j$th variable, so it's $m \times n$ $c_j$ is the coefficient for the $j$th var in the objective, so it's $n \times 1$ $b_i$ is the upper bound for the $i$th constraint, so it's $m \times 1$ $y_i$ is the coefficient for the $i$th constraint's linear combination, so it's $m \times 1$ ![[Pasted image 20221114144829.png|768]] ![[Pasted image 20221112133854.png]]

What if the primal is a minimization?¶

minimize $c^T y$ --> maximize $-c^Ty$ likewise, just change the $A^Ty \geq c$ constraints as needed

From this, we can prove that the dual of the dual is the primal.

Fact : The dual of the dual of a linear program is the LP Fact: If the primal and dual are both feasible, then $$ opt(\text{primal}) \leq opt(\text{dual}) $$

Weak Duality Theorem¶

If the primal is unbounded, then its dual is infeasible If the dual is unbounded, then its primal is infeasible If both are feasible, then $opt(\text{primal}) \leq opt(\text{dual})$

Strong Duality Theorem¶

If either the primal or dual is feasible and bounded, then so is the other, and $\(opt(primal) = opt(dual)$\) The following cases are possible:
- if one LP is feasible and bounded, so is the other - If one LP is unbounded, the other is infeasible - If one LP is infeasible, the other is either infeasible or unbounded

Solving tips¶

Figure out the values for $A$ first and foremost! ensure all constraints in the primal are written as $\leq b$ In general, explicitly write out the values for $c, b, A$

We may need to show that the dual is feasible (there is at least one solution? See pset 6 solutions)

Problem 2 in practice quiz: If the word problem is minimization, then we can work backwards, pretend the initial is the dual (in minimization form) and solve for its primal.

If we're trying to solve for the bound, remember that we must show that the objective of the dual is greater than the bound. If we know the exact bound, then we can work backwards and check for values which would let the objective satisfy the problem, instead of directly solving for it. Especially if the numbers don't cancel out such that a linear combination is tricky. ![[Pasted image 20221114161859.png|500]]from this dual, we see that we want the bound to be hn. we have the h, and we have n variables in the first term! so intuitively we see that it would be solved if we set $x_i$ to 1. ![[Pasted image 20221114161825.png|500]] Common theme i've found: if we find something like $W$ is stochastic (rows or columns sum to 1), then the summation $\sum_i W_{ij}x_i$ has nice convenient properties if we set $x_i$ to a constant.