How to write dual form of $ \min \sum_{i=1}^{n} \mathbf{x}_i\mathbf{y}_i$ with $\sum_{i=1}^n \mathbf{y}_i = 1, \mathbf{y}_i \ge0$

Question

$$\begin{array}{ll} \text{minimize}_{\mathbf{y} \in \mathbb R^n} & \sum_{i=1}^{n} \mathbf{x}_i\mathbf{y}_i \\ \text{subject to} & \ \sum_{i=1}^n \mathbf{y}_i = 1, \mathbf{y}_i \ge0 \end{array}$$

Here $\mathbf{x}, \mathbf{y}$ are both column vector with size $n$ How to write the dual form of this linear programming?

Answer 1

The Lagrangian function of the primal problem

$$ \begin{align*} \min_{y \in \mathbb{R}^n}\; x^\top y \quad \text{s.t.} \quad \mathbb{1}^\top y = 1,\; y \geq 0 \end{align*} $$

is given by

$$ \begin{align*} L(y, \lambda, \mu) = x^\top y + \lambda (1-\mathbb{1}^\top y) - \mu^\top y = (x - \mathbb{1}\lambda - \mu)^\top y + \lambda. \end{align*} $$

The lagrangian dual problem reads

$$ \max_{\lambda \in \mathbb{R}, \mu \in \mathbb{R}^n } \inf_{y \in \mathbb{R}^n} L(y, \lambda, \mu) \quad \text{ s.t. } \quad \mu \geq 0. $$

We have

$$ \begin{align*} \inf_{y \in \mathbb{R}^n} L(y, \lambda, \mu) = \begin{cases} \lambda, \quad &{ x - \mathbb{1}\lambda - \mu = 0} \\ -\infty, \quad &\text{else} \end{cases} \end{align*} $$

and since $x - \mathbb{1}\lambda = \mu \geq 0$ iff $\mathbb{1}\lambda \leq x$, we have the dual problem

$$ \begin{align*} \max_{\lambda \in \mathbb{R}} \; \lambda \quad \text{s.t.} \quad \lambda \leq x_i \; \forall i = 1, \ldots, n \end{align*} $$