2

Vectors $x, y \in \mathbb{R}^{n\times 1}$ satisfy $$ \forall_{i,j}\; x_i + y_j \leq a_{i,j} $$ where $a\in \mathbb{R}^{n\times n}$ is a given matrix. The question is to find the maximum value of $\sum_i x_i + \sum_j y_j$.

My idea

Suppose $t$ is a bijection defined on $\{1,..,n\}\mapsto \{1,..,n\}$, then we have $$ \sum_i x_i + \sum_j y_j \leq \sum_k a_{k\,t(k)} $$ which further introduce $$ \sum_i x_i + \sum_j y_j \leq \min_t \sum_k a_{k\,t(k)} $$

What's left is to prove that $\min_t \sum_k a_{k\,t(k)}$ can be reached. That is to say, prove there exist vectors $x, y$ such that $$ \begin{cases} x_i + y_j \leq a_{i,j},\;\;\forall_{i,j}\\ \sum_i x_i + \sum_j y_j = \min_t \sum_k a_{k\,t(k)} \end{cases} $$

useprxf
  • 485

2 Answers2

2

Your upper bound is good and corresponds to finding a min weight match over permutation matrices. Or you can prove a related upper bound directly:

Related (in fact, identical) upper bound

Let $P=(p_{ij})$ be a "doubly stochastic" $n \times n$ matrix so that \begin{align} \sum_{j=1}^n p_{ij} &= 1 \quad \forall i \in \{1, ..., n\} \\ \sum_{i=1}^n p_{ij} &=1 \quad \forall j \in \{1, ..., n\} \\ p_{ij} &\geq 0 \quad \forall i, j \end{align} Then if $(x_i), (y_j)$ are values that satisfy $x_i + y_j \leq a_{ij}$ for all $i,j \in \{1, ..., n\}$, then you can show (using methods similar to your existing upper bound) that: $$\sum_{i=1}^n x_i + \sum_{j=1}^n y_j \leq \sum_{ij} p_{ij} a_{ij} $$ So the best upper bound of this type is solved by the following linear program

\begin{align} \mbox{Minimize:} & \quad \sum_{ij} p_{ij}a_{ij} \\ \mbox{Subject to:} & \sum_{j=1}^n p_{ij} = 1 \quad \forall i \in \{1, ..., n\} \\ &\sum_{i=1}^n p_{ij} =1 \quad \forall j \in \{1, ..., n\} \\ &p_{ij} \geq 0 \quad \forall i, j \end{align} It turns out that this upper bound is identical to your upper bound of the min-weight match over the matrix $(a_{ij})$ because every doubly stochastic matrix $(p_{ij})$ can be expressed as a convex combination of permutation matrices (which is sometimes called the Birkhoff-von Neumann theorem), and so minimizing a linear function over doubly stochastic matrices can be reduced to minimizing the same function over permutation matrices (since permutation matrices are the "extreme points" of the set of doubly stochastic matrices).

Matching lower bound

Try using linear program duality to take the dual of the above linear program with $p_{ij}$ variables to convert to a linear program with dual variables $x_i,y_j$.

Michael
  • 23,905
  • In other words, swap the ordering of $\inf_{p\geq 0}[\cdot]$ and $\sup_{x,y \in \mathbb{R}^n} [\cdot]$ for the expression $$\left[\sum_{ij}p_{ij}a_{ij} +\sum_{i=1}^nx_i\left(1-\sum_{j=1}^n p_{ij}\right) +\sum_{j=1}^ny_j\left(1-\sum_{i=1}^n p_{ij}\right)\right]$$ [Alternatively, you could start with your linear program in $x_i,y_j$ variables and use duality on that to transform to dual variables $p_{ij}$]. – Michael Aug 20 '18 at 04:42
  • How do you construct the optimal $x,y$ according to $p_{ij}$? – useprxf Aug 20 '18 at 07:55
  • Your question says "That is to say, prove there exist vectors $x,y$ such that..." You can prove existence by completing the "matching lower bound" step in my above answer, which means you will need to construct the dual linear program (with $x,y$ variables as "Lagrange multipliers") from the linear program with $p_{ij}$ variables in my answer. The key step is swapping the ordering of $\inf$ and $\sup$ as in my above comment. Are you familiar with duality theory? It does not give us an answer for $(x,y)$ in terms of $p_{ij}$, rather, it tells us a new linear program to solve. – Michael Aug 20 '18 at 15:02
  • This seems to be a homework problem about duality. I don't see how it can be solved without duality theory or saddle point theory. The type of linear program duality I am referring to is in equations (13)-(14) in these notes: https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=3&ved=2ahUKEwiK7YHd7_vcAhUPWa0KHRuYCnMQFjACegQIABAC&url=http%3A%2F%2Fweb.mit.edu%2F15.053%2Fwww%2FAMP-Chapter-04.pdf&usg=AOvVaw2ca3zfM8SvZTYusmYmFYC5 – Michael Aug 20 '18 at 15:19
  • Genius, now I got it. It's actually a programming problem. I tried to find a determinitic and discretic approach to construct the optimal $(x,y)$ but failed. You method indeed proves the existence of the optimal $(x,y)$. – useprxf Aug 20 '18 at 16:18
1

Since this seems to not be a homework, it may be useful to have the following "appendix" to my answer (although this may also be a spoiler to the do-it-yourself flavor of my prior answer). I give this because some treatments of duality theory assume a particular structure that is not convenient for this problem.

You have the (primal) LP: \begin{align} \mbox{Minimize:} &\quad -\left(\sum_{i=1}^n x_i + \sum_{i=1}^n y_i\right) \\ \mbox{Subject to:} &\quad x_i + y_j \leq a_{ij} \quad \forall i,j \in \{1, ..., n\} \end{align} The optimal objective value is the same as: \begin{align} &\inf_{x,y\in \mathbb{R}^n} \sup_{p\geq 0}\left[-\left(\sum_{i=1}^n x_i + \sum_{j=1}^n y_j\right) + \sum_{ij}p_{ij}\left(x_i+y_j-a_{ij}\right) \right]\\ &\overset{(a)}{=}\inf_{x,y\in \mathbb{R}^n}\sup_{p\geq 0}\left[-\sum_{ij}p_{ij}a_{ij} + \sum_{i=1}^nx_i\left(-1+\sum_{j=1}^np_{ij}\right)+\sum_{j=1}^ny_j\left(-1+\sum_{i=1}^np_{ij}\right) \right]\\ &\overset{(b)}{=}\sup_{p\geq 0}\inf_{x,y\in \mathbb{R}^n} \left[-\sum_{ij}p_{ij}a_{ij} + \sum_{i=1}^nx_i\left(-1+\sum_{j=1}^np_{ij}\right)+\sum_{j=1}^ny_j\left(-1+\sum_{i=1}^np_{ij}\right) \right]\\ \end{align} where (a) follows by switching the summation order; (b) follows by switching the order of $\inf$ and $\sup$ which can be justified in this case by saddle point theory. The last problem has optimal value the same as that of the (dual) LP: \begin{align} \mbox{Maximize:} & \quad -\sum_{ij} p_{ij} a_{ij} \\ \mbox{Subject to:} & \quad \sum_{j=1}^n p_{ij} = 1 \quad \forall i \in \{1, ..., n\} \\ & \quad \sum_{i=1}^n p_{ij} = 1 \quad \forall j \in \{1, ..., n\} \\ &\quad p_{ij} \geq 0 \quad \forall i,j \in \{1, ..., n\} \end{align}

Why is the primal problem equivalent to the following "2-player game"? $$\inf_{x,y\in \mathbb{R}^n} \sup_{p\geq 0}\underbrace{\left[-\left(\sum_{i=1}^n x_i + \sum_{j=1}^n y_j\right) + \sum_{ij}p_{ij}\left(x_i+y_j-a_{ij}\right) \right]}_{L(x,y,p)}$$ The reason is that player 1 wants to choose $x,y\in\mathbb{R}^n$ to minimize $\sup_{p\geq 0}L(x,y,p)$. If it chooses in a way that violates the constraint $x_i+y_j\leq a_{ij}$ for at least one $(i,j)$ pair, then player 2 can "win" by choosing $p_{ij}\rightarrow \infty$ for that same $(i,j)$ pair, making $L(x,y,p)\rightarrow\infty$. So player 1 must choose $x,y$ to satisfy $x_i + y_j \leq a_{ij}$ for all $(i,j)$. Player 1 can further optimize its choice of $x,y$ as long as these constraints are satisfied, which corresponds to the primal LP.

Since $L(x,y,p)$ is linear in $(x,y)$ for fixed $p$, and linear in $p$ for fixed $(x,y)$, saddle point theory ensures we can switch the $\inf$ and $\sup$ ordering as we did above.

Michael
  • 23,905