1. Time: 2:00 - 4:00pm, November 4th (Saturday), 2023.
2. Venue: Rooms reserved. We will announce the exam room and seating No. for each student later.
3. A closed-book, closed-notes examination. You are allowed to bring one-page two-sided A4 cheat sheet. Cheat sheet written using iPad and then printing it is fine. (Though printing is allowed, preparing the cheat sheet by yourself is a good review practice). No other things will be allowed, especially calculators.

## MAT3007: Midterm Exam (SF302)

### Lecture 2: Formulating Optimization Problems

Formulating Inseparable SVM (sample):

### Lecture 3: Linear Optimization

Standard Form of the Inseparable SVM:

Standard Form for Absolute Value:

### Lecture 4: The Geometry of Linear Optimization

**Extreme Point**: Let $P$ be a polyhedron. A point $x \in P$ is said to be an extreme point of $P$ if we can not find two vectors $y, z \in P$ with $y, z \neq x$ and a scalar $\lambda \in [0, 1]$, such that $x = \lambda y + (1 - \lambda) z$.
Usually we assume $A$ (an $m \times n$ matrix with $m < n$) has linearly independent rows. If it is not satisfied then either: there is redundant constraints (can remove) or the constraints are not consistent (no feasible solution).

### Lecture 5: Simplex Method

Degeneracy if basic variable(s) is zero, stucks the algo

### Lecture 6: Simplex Method (Tableau)

Two-phase simplex method (to get initial BFS):

Phase 1: solve auxiliary problem.
- In constraint:
- If found $\geq$, then $-s_i$ and $+a_i$.
- If found $\leq$, then $+s_i$ and $+a_i$.
- If found $=$, then $+a_i$.
- Tableu's objective row is $-\sum$ (of columns)
- Perform simplex method.
- Compute $\bar{c}^T = c^T - c_B^T A_B^{-1} A$.

Phase 2: solve problem
- Tableu's objective row is $\bar{c}^T$.
- Solve and get $x$.

Bland's: keep choosing smallest index $\Rightarrow$ no loop.

### Lecture 7: Dual Theory

dual of dual is primal equivalence 👀

### Lecture 8: Dual Theory (cont'd)

**Weak Duality**: If $x$ is feasible to the primal and $y$ is feasible to the dual, then $b^Ty \leq c^Tx$.
Consequently, if $c^Tx = b^Ty$, then $x$ and $y$ must be optimal solutions to the primal and dual.
**Strong Duality**: If a linear program has a finite optimal solution, so does its dual, and the optimal values of the primal and dual are equal.
**Complementary Conditions**: Let $x$ and $y$ be feasible points to the primal and dual problems, respectively. Then $x$ and $y$ are optimal if and only if: $y_i \cdot (a_i^Tx - b_i) = 0, \forall i$ and $x_j \cdot (A_j^Ty - c_j) = 0, \forall j$,

### Lecture 9: Dual Theory (cont'd)
**Alternative Systems**: either one of the following two statements is true: there exists $y$ such that $A^Ty \leq c$ or there exists $x$ such that $Ax = 0, x \geq 0, c^Tx < 0$.

### Lecture 10: Sensitivity Analysis

What happened after changing the $i$-th constraint of $b$? **(NO MINUS SIGN AT ALL!)**

- As long as $x_B + \lambda A_B^{-1}e_i \geq 0$ (local sensitivity) holds, $\texttt{ans}(b + \Delta b) = \texttt{ans}(b) + {y^*}^T \Delta b$

What happened after changing the $j$-th variable of $c$? ($e_j$ contains minus sign is the problem is maximization).
- If $j \in B$, as long as $r_N^T - \lambda e_j^T A_B^{-1} A_N \geq 0$ (local sensitivity) holds, $\texttt{ans}(c + \Delta c) = \texttt{ans}(c) + {\Delta c}^T x_B^*$
- If $j \in N$, as long as $r_N^T + \lambda e_j \geq 0$ (local sensitivity) holds, $\texttt{ans}(c + \Delta c) = \texttt{ans}(c) + {\Delta c}^T x_B^*$

What happened after changing $A$?
- If the change happens in non-basic column ($j$-th variable for example, $j \notin B$), then the optimal solution is still feasible. Simply recompute $\bar{c}_j$; if non-negative, use original solution; otherwise, update tableau for $j$-th column and continue.
- If the change happens in basic column. Fked off. Recompute everything.

Adding a **variable**? Check the reduced cost. If non-negative, use original solution; otherwise, update tableau and continue.
Adding a **constraint**? If original solution still satisfy, we use it. Otherwise, convert into dual problem and use simplex tableu to solve.

### Lecture 11: Interior Point Methods

- Maintain both primal feasibility and dual feasibility during iteration and seek pairs that satisfy complementary conditions.
- How? Relax the $A^Ty \leq c$ to be $A^Ty + s = c, s \geq 0$.
- $\mathcal{O}(n^{3.5})$ (polynomial efficiency), high rank (maximum possible non-zeros)