Help understand equivalence of two optimization problems The problem is the circled part. I don't fully understand why they are equivalent. In their notation, two vectors ${\bf x} \ge {\bf y}$ means every component of $\bf x$ is larger or equal to the corresponding component of vector $\bf y$.



My attempt and more explanation (might contain error): 
By my understanding, $\bf x$ here should be treated as fixed. The first optimization is varying ${\bf a}_i$, and the second optimization is varying ${\bf p}_i$. 
I think the two optimizations are equivalent in the sense that $\max_{{\bf a}_i} {\bf a}_i^T{\bf x} =\min_{{\bf p}_i} {\bf p}^T_i{\bf d}_i$.
It is easy to see ${\bf D}_i{\bf a}_i \le {\bf d}_i$ is equivalent to ${\bf p}_i^T{\bf D}_i{\bf a}_i \le {\bf p}_i^T{\bf d}_i, \forall {\bf p}_i \ge {\bf 0}$. Now if there exists ${\bf p}_i$ s.t. ${\bf p}_i^T{\bf D}_i = {\bf x}^T$, then we have
$${{\bf{x}}^T}{{\bf{a}}_i} = {\bf{p}}_i^T{{\bf{D}}_i}{{\bf{a}}_i} \leqslant {\bf{p}}_i^T{{\bf{d}}_i},\forall {{\bf{p}}_i} \geqslant {\bf{0}},{{\bf{p}_i}^T}{{\bf{D}}_i} = {\bf{x}}_i^T$$
Thus the maximum value of ${{\bf{x}}^T}{{\bf{a}}_i}$ is at most $\inf \{ {\bf{p}}_i^T{{\bf{d}}_i}:{{\bf{p}}_i} \geqslant {\bf{0}},{{\bf{p}}_i^T}{{\bf{d}}_i} = {\bf{x}}_i^T\} $. Here comes the question: First,

The equivalence in the circled part of the screen shot means 
$$\max \{ {{\bf{x}}^T}{{\bf{a}}_i}:{\bf{p}}_i^T{{\bf{D}}_i}{{\bf{a}}_i} \leqslant {\bf{p}}_i^T{{\bf{d}}_i},\forall {{\bf{p}}_i} \geqslant {\bf{0}}\}  = \inf \{ {\bf{p}}_i^T{{\bf{d}}_i}:{{\bf{p}}_i} \geqslant {\bf{0}},{{\bf{x}}^T}{{\bf{a}}_i} = {\bf{p}}_i^T\} $$
but I can only arrive at "$\le$" rather tahn $=$ from above discussion.
  $$\max \{ {{\bf{x}}^T}{{\bf{a}}_i}:{\bf{p}}_i^T{{\bf{D}}_i}{{\bf{a}}_i} \leqslant {\bf{p}}_i^T{{\bf{d}}_i},\forall {{\bf{p}}_i} \geqslant {\bf{0}}\}  \leqslant \inf \{ {\bf{p}}_i^T{{\bf{d}}_i}:{{\bf{p}}_i} \geqslant {\bf{0}},{{\bf{x}}^T}{{\bf{a}}_i} = {\bf{p}}_i^T\} $$
I am not able to see the full equivalence.

Secondly, 

What happens if there does not exist ${\bf p}_i$ s.t. ${\bf p}_i^T{\bf D}_i = {\bf x}^T$?


Paper: https://faculty.fuqua.duke.edu/~dbbrown/bio/papers/bertsimas_brown_caramanis_11.pdf
 A: I am very sure this example 4.2.1 is exactly what you ask for.
This is from the book "convex optimization theory" written by the author of the paper you link in the question.

A: I'll give a basic understanding of duality - more information can be found in a linear programming text, usually a course taken at an introductory level by sophomore and junior math/industrial engineering/management science students, or even as a first graduate course.
Consider the linear program
\begin{align*}
\max \ & c^T x \\
\text{subject to } & Ax \leq b \\
& x \geq 0
\end{align*}
where $A$ is an $m \times n$ matrix and $c$ is a vector in $\mathbb{R}^n$ defining costs. To write the dual, we consider the dual variable $u \in \mathbb{R}^m$. The dual is as follows:
\begin{align*}
\min \ & b^T u \\
\text{subject to } & A^T u \geq c \\
& u \geq 0
\end{align*}
What changed? This maximization problem became a minimization problem, the coefficient matrix $A$ has been replaced by its transpose, and the vectors $b$ and $c$ swapped positions. Notice that this is the "standard" form - inequalities of the type $ w \leq z$ correspond to a maximization problem and $w \geq z $ a minimization problem. Ensure that the constraints match this form before writing the dual - otherwise use the fact that $ w \leq z \implies -w \geq -z$.
To handle equality constraints, use also that $w = z \implies w \leq z \ \wedge \ w \geq z$.
