Jump to content

Talk:Simplex algorithm

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Nealeyoung (talk | contribs) at 01:41, 29 April 2021 (→Reference needed for statement about Baire Category). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Template:Vital article

Unusual wording

My apologies but me not understand

"while having no polynomial time worst-case complexity implementation"... (last-but-one paragraph).

Is it possible to enhance this sentence? Thanks. Pfortuny 09:22, 19 Apr 2004 (UTC)

Last paragraph also speaks about

"much better computational complexity"

which for me sounds weird. Pfortuny 09:27, 19 Apr 2004 (UTC)

Associating to other method

To the anonymous editor from IP-address 4.250.xxx.xxx: I don't understand why you want to associate Dantzig's method to mathematical optimization and the other simplex method, with which you have apparently some experience, with computer programming. Surely both methods are part of mathematical optimization, since they both solve optimization problems. Similarly, both methods are part of computer programming, since they can be programmed on a computer. -- Jitse Niesen 18:38, 10 Jan 2005 (UTC)

I associate "Dantzig's method to mathematical optimization" with "the other simplex method" because the documentation I read in order to fulfill the customer's request for implementing the simplex method optimization was derived by computation scientists (not me, I just implemented their algorithms in 6809 assembly code) from what appears to my eyes as what you descibe as "Dantzig's method to mathematical optimization". As I did this around 1985, I no longer recall the exact materials I read. In any case, I'll make no reverts to the current article. Cheers from user 4.250.xxx.xxx

Transposes

In the Problem Input section, shouldn`t it be the transpose of -c, and not -c? Perhaps I am missing something, in which case I apologize. --Tomas

History section should be moved.

It should be moved above and made the first section after the lead for a more logical flow of the article. Hmanburg (talk) 14:00, 18 September 2020 (UTC)[reply]

I've decided to move it, do let me know incase it isn't appropriate. Hmanburg (talk) 14:00, 18 September 2020 (UTC)[reply]

Simplex overview verification

I am not sure of this mathematical statement in the overview.

"It can also be shown that, if an extreme point is not a maximum point of the objective function, then there is an edge containing the point so that the objective function is strictly increasing on the edge moving away from the point."

Since degeneracy can cause a stalling effect, it is possible to find a descent direction where the objective value is not increased, but is still a valid direction. Thus, I doubt the term "strictly", and I don't know how it would need to be phrased since it is only an overview of the algorithm. On another note, do we say that the objective value is increased, or objective function? Raphaelbwiki (talk) 22:33, 26 January 2021 (UTC)[reply]

Response: I believe the statement you've quoted is technically true, with the geometric interpretation of "extreme point" and "edge". That is, an extreme point is a point that is the intersection of the feasible region with some supporting hyperplane, and an edge is a line segment that is the intersection of the feasible region with some supporting hyperplane. On the other hand, if one interprets "extreme point" as a "basic feasible solution" (which is what the Simplex algorithm works with, rather than points per se), then you are right that there might not be an edge (in the sense of an exchange of two variables leading to a neighboring basic feasible solution) that strictly increases the objective function, even if the basic feasible solution is not a maximum of the objective (because of the degeneracy that you mention, by which many basic feasible solutions may all represent the same extreme point. Nealeyoung (talk) 01:30, 29 April 2021 (UTC)[reply]

Reference needed for statement about Baire Category

In this 2011 edit (https://en.wikipedia.org/w/index.php?title=Simplex_algorithm&type=revision&diff=420535791&oldid=420516031), user Kiefer.Wolfowitz ([1], not active as of April 2021) introduced the statement "Another approach to studying typical phenoma uses Baire category theory from general topology, and to show that (topologically) "most" matrices can be solved by the simplex algorithm in a polynomial number of steps." This statement has been questioned on cstheory.stackexchange.com here: https://cstheory.stackexchange.com/questions/48850/using-baire-category-to-analyze-the-efficiency-of-the-simplex-method , with no clarification as of April 2021. From a quick google scholar search, I don't find any research mentioning (much less explaining) anything about the Simplex algorithm and Baire Category theory (except a 2015 online article that appears to be plagiarized from the Wikipedia page). I suggest that either a suitable reference be found and added, or, if none can be found, that the statement be removed. Nealeyoung (talk) 01:36, 29 April 2021 (UTC)[reply]

Retrieved from "https://en.wikipedia.org/w/index.php?title=Talk:Simplex_algorithm&oldid=1020431172"