Chapter 4 Linear Programs

Here are some famous LPs:

4.1 Piecewise linear minimization

\[\begin{align} \tag{4.1} \text{minimize}& & \max _{i=1,\dots,m}(a_i^Tx+b_i) \end{align}\] is equivalent to the LP \[\begin{align} \tag{4.2} \text{minimize}& & t & & \\ \text{subject to} & & a_i^Tx+b_i \leq t & , & i=1,\dots,m. \end{align}\]

Note that PWL can approximate any function, so this can be very useful!

4.2 Chebyshev center of a polyhedron

The Chebyshev center of a polyhedron \[\begin{equation} \tag{4.3} \mathcal P = \{ x|a_i^Tx < b_i \} \end{equation}\] is defined to be the center of a maximum sphere \[\begin{equation} \tag{4.4} \mathcal B = \{ x_c + u | \| u \|_2 \leq r \} \end{equation}\] inside the polyhedron (note this can be multiple such points).

Furthermore, \(a_i^Tx \leq b_i\) for all \(x \in \mathcal B\) if and only if \[\begin{equation} \tag{4.5} \sup\{ a_i^T (x_c + u) | \| u \|_2 \leq r\} = a_i^T x_c + r \| a_i \|_2 \leq b_i \end{equation}\]

This is actually an LP: \[\begin{align} \tag{4.6} \text{maximize}& & r & & \\ \text{subject to} & & a_i^Tx_c + \|a_i\|_2 r \leq b_i, & & i=1,\dots,m \end{align}\]