1

I am following Prof. Williams's description of the linear programming formulation [1] of the minimax problem:

Minimize: $\left( \underset{i}{\rm Maximum} \sum\limits_j a_{ij} x_j \right)$

subject to: conventional linear constraints.

Here, {$x_j$} are the decision variables and {$a_{ij}$} are constant coefficients. The above is recast into:

Minimize $z$

subject to $\displaystyle\sum_j a_{ij} x_j - z \le 0$ for all $i$

I get that the search will seek a $z$ that gets as close as possible to $\displaystyle\sum_i a_{ij} x_j$ because that is the explicit minimization expression. What causes $\sum\limits_i a_{ij} x_j$ to be maximized?

[1] Model Building in Mathematical Programming, H. Paul Williams (2013), ed.5, Section 3.2.3 (Minimax objectives), page 27: https://www.researchgate.net/profile/Fazel_Varasteh/post/Can_anybody_please_suggest_a_reference_for_modelling_cost_of_production/attachment/59d63615c49f478072ea3d2f/AS:273636437495809@1442251418466/download/Wiley Model Building in Mathematical Programming 5th (2013).[sharethefiles.com].pdf

RobPratt
  • 45,619
user2153235
  • 189
  • What are the variables here? I can't open your link, so it's best to provide as much context as possible. – Théophile Apr 28 '20 at 17:13
  • 1
    The idea is that the constraints enforce $z\ge \max_i {\sum_i a_{i,j} x_j}$ and the minimization objective avoids $z> \max_i {\sum_i a_{i,j} x_j}$. – RobPratt Apr 28 '20 at 19:38
  • @Théophile: I added the context and corrected summation index in the $z$ formulation$, but I'm not sure if it's any more informative. Out of curiosity, what happens when you try to access the URL for the PDF file? – user2153235 Apr 28 '20 at 21:40
  • Regarind the URL, it probably works for most people, but I have a number of sites blocked on my browser, including this one. – Théophile Apr 30 '20 at 16:45
  • Blocked ResearchGate? Now I'm curious.... – user2153235 May 01 '20 at 00:17
  • Sometimes I get grumpy and block sites when there are popups or long signup forms or whatnot. But just for you, I unblocked it. ;) So I looked at the link, and lo and behold, it mentions zero-sum games on the page you cited. It looks like game theory is outside the scope of your book, but it's a fascinating topic and should be easy for you to understand. "Games" in this context can represent actual games, or real political / economic situations. – Théophile May 01 '20 at 02:03
  • Actually, I remember. Every few years, when I'm not buried under bureaucracy, I do a temporary dive into bodies of knowledge. Payoff grids, individual benefit versus group benefit (I admit, I googled some concepts to review). Nice to know that the math in the book will eventually tie into those other concepts. – user2153235 May 01 '20 at 03:02

1 Answers1

1

The following mental picture helped me understand the effects in play. It may depend on how people think of things, but hopefully, it will save someone an afternoon of pondering.

Each $i$ in $\left( \underset{i}{\rm Maximum} \sum\limits_j a_{ij} x_j \right)$ enumerates an inner product between a row $i$ of array [$a_{ij}$] with the column vector [$x_j$] of decision variables

Then, $\left( \underset{i}{\rm Maximum} \sum\limits_j a_{ij} x_j \right)$ simply refers to the largest-valued inner product.

We want values of $x_j$ that yield the smallest possible $\left( \underset{i}{\rm Maximum} \sum\limits_j a_{ij} x_j \right)$.

In the reformulation using $z$, for each inner product enumerated $i$, $z$ is forced downward onto the inner product $\sum\limits_j a_{ij} x_j$ from above. While there are $|\{i\}|$ such constraints, the only one that matters is the one for which the inner product is largest. Since $z$ is made to be as small as possible, the values of $x_j$ will be found such that the largest inner product is minimized.

user2153235
  • 189
  • Yes, this is exactly right. The point is that in an LP, the objective function must be a linear combination of the variables. You'll see this setup when solving games: the $\sum_j{a_{ij}x_j}$ represent the row player's winnings on row $i$, and the column player wants to keep these as low as possible. Now that you've added context, your explanation here is a lot more relevant than mine; for posterity, I think you ought to make it the accepted answer! – Théophile Apr 30 '20 at 16:44
  • Thanks, Théophile. Can you link to the game that you're referring to? As for marking my reply as the answer, I thought it might be a conflict of interests, and I'm not an expert. With your advocacy, however, I will do that (but not upvote it). Thanks again. – user2153235 Apr 30 '20 at 21:26
  • Glad to help. By "game" I mean a two-player zero-sum game; in short, two players each make a choice, reveal it simultaneously, and then one pays the other $x$ points. Rock-paper-scissors is a classic example. If you write out all the payoffs in a matrix, you can find optimal strategies for both players using exactly the LP in your question. Here's a more comprehensive introduction: https://theory.stanford.edu/~tim/w16/l/l10.pdf – Théophile May 01 '20 at 01:49