Template talk:Optimization algorithms

Welcome!

Constrained nonlinear optimization

Most of the nonlinear topics include only unconstrained methods. It would be good to have a group for constrained optimization: Sequential unconstrained minimization techniques (SUMT), sequential quadratic programming, augmented Lagrangian methods, Proximal point methods; Successive linear programming (like MS Excel's solver), Gradient projection methods (Lancelot), Michael Saunders's MINOS; Filter methods (Fletcher), etc. Kiefer.Wolfowitz (talk) 23:17, 8 November 2010 (UTC)

Heuristics

Previously, there were 3 lines of heuristics, out of proportion to the treatment of heuristics in optimization textbooks and surveys. There were two other problems, imho.

First, many of the heuristics that were listed have severe problems with notability, just to be listed in Wikipedia, and some have problems with single-purpose accounts (often anonymous IPs) being the main and nearly sole author: such editing is often associated with conflicts of interest, especially self-promotion. I removed all the heuristics with such problems with notability (with even having a WP article).

Second, many of the remaining heuristics were perhaps notable enough to have a Wikidia article, although the concerns with self-promotion and COI remain with a few of them (which seem to share the same editors). However, regardless of their merits as heuristics, many of those heuristics are not described in optimization textbooks and so fail notability to be in the footer for computational optimization. I removed the heuristics that are not discussed by optimization textbooks from this optimization footer.

(It might be useful to create a heuristic footer with them, because they do share a lot of commonalities.)

Finally, I think that my edits are consensus in optimization, because our optimization articles ignore the heuristics that I deleted, which makes it really weird to devote the header to them. I did ask for second opinions at the Wikiprojects in computer science, mathematics, and systems (operations research).

Sincerely, Kiefer.Wolfowitz (talk) 11:03, 30 November 2010 (UTC)

I don't think branch and bound belongs in the heuristics category as it is/can be complete, unlike the other algorithms in that category. I'd put it in a category on integer linear programming or search algorithms. —Ruud 19:34, 30 November 2010 (UTC)

Agreed, because the WP article is about branch-and-bound in integer programming. (There are also branch-and-branch methods in global optimization.) Most of this template concerns continuous optimization. It might be worthwhile to consider either moving the name to "continuous optimization methods" or to create at least one line about combinatorial optimization. Kiefer.Wolfowitz (talk) 22:51, 30 November 2010 (UTC)

I have noticed this template popping up on pages for optimization methods lately. I don't quite see its purpose since the categories already have comprehensive lists of optimizers. Nevertheless, wikipedia is a group effort so it is not for me to dictate whether it should be here or not. I was, however, curious about the choice of which optimizers were included and studying this discussion page as well as the history of changes I see that someone has removed e.g. CMA-ES, particle swarm optimization and differential evolution claiming they are not notable. This is clearly a fallacy. PSO and DE have been used and cited thousands of times (see e.g. google scholar), and CMA-ES is considered by many researchers to be amongst the very best (meta-)heuristics in existence today. It is a bit annoying that people take it upon themselves to make large edits/deletions in areas where they have no expertise. Just yesterday I had to save local unimodal sampling from deletion because an editor with no expertise had tagged it for deletion.

Optimering (talk) 06:46, 14 December 2010 (UTC)

To me, the method looks like junk and it certainly is a terrible article that stinks of self-promotion, since it is based on some engineer's dissertation (closely linked to Luus, whoever that is). Such methods have been studied, particularly in Russian-language literature, and the article has no referencs to the Paulakus family (originally from Lithuania and one whose Carnegie-Mellon dissertation was published by Kluwer), etc. Bless Pedersen and Luus and bless their luck if this "method" works on their problems, but this is far from the state of the art, even in the 1960s.  Kiefer.Wolfowitz  (Discussion) 23:02, 20 February 2011 (UTC)

It's fine that the mentioned "metaheuristic" (sic., "heuristic) topics have their own articles, because they seem to be notable. However, the optimization footer is very selective, and features topics that are found in optimization textbooks. As I suggested before, it would be a good project for you or others to create one (optimization) heuristics footer: Using the three rows that were in the optimization template! Kiefer.Wolfowitz (talk) 12:09, 14 December 2010 (UTC)

In my opinion it is not a good selection criteria whether something has been published in a textbook. Textbooks are usually slow to incorporate the state of the art. Besides, the mentioned optimizers (PSO, DE, CMA-ES) have actually been the topic of numerous textbooks, handbooks, etc. I haven't seen any papers using Rosenbrock optimizers. Golden section search is only for 1-dimensional unimodal functions, etc. etc. So it is a strange selection we have here. I also don't see the relevance of linking to e.g. combinatorial optimizers from pages on real-valued optimization, and vice versa. I suppose I could make a template/footer dedicated to (meta-)heuristics, but I still don't see the purpose. Most articles have 'see also' sections for closely related optimizers and there are wiki categories for broadly related optimizers. Why do we need this template? I think we should instead consider deleting this template altogether? Optimering (talk) 12:41, 14 December 2010 (UTC)

Six hours ago, you suggested restoring the three lines of (meta)heuristics. Within an hour of my reply, you suggest deleting the whole template. This seems to be an unconstructive conclusion.

on WP, "See also" sections are for articles that are not linked in the main article. A footer might be better than a list of see also articles, including much besides (meta)heuristics.

I agree that the some items on the function-evaluation line have little value, and wouldn't object to your deleting weak items. I would suggest that you keep "Powell's interpolation method" (and consider adding line search there and for the Wolfe conditions for the gradient-line). Kiefer.Wolfowitz (talk) 13:18, 14 December 2010 (UTC)

Actually, in my first posting I wrote "I don't quite see its purpose since the categories already have comprehensive lists of optimizers." I never suggested restoring all the (meta-)heuristics but a couple of them are certainly justified for inclusion; if the navbox is to exist at all. So my postings above are consistent and my overall vote is still that the navbox be deleted for the reasons I have listed above. I hope my opinion doesn't appear offensive. Optimering (talk) 15:23, 14 December 2010 (UTC)

Well, can you live with restoring whatever you think are the most important meta-heuristics, subject to the constraint that they fit on one line (not exceeding the length of the longest existing line)?

Before deleting this box, please ask for new opinions on Wiki Math and Wiki Systems projects. (I think it's useful to have the SQP article listed, which was new to me, etc. I suspect that this footer serves a modest purpose, as do many other footers, and footers seem to be particularly prone to disagreements!)

Of course, your opinion is well stated, and well argued, so it should not offend anybody. Best regards, Kiefer.Wolfowitz (talk) 23:30, 14 December 2010 (UTC)

I have looked at how these templates are used on Wikipedia and have thought about how they could be used with optimization methods. There are many problems in this, paramount is that the categorization of optimizers is very difficult as some belong to more categories, e.g. should we categorize according to search-space domains (real-valued, integers, combinatorial, etc.), single-dimensional / multi-dimensional, constrained / un-constrained, heuristic / gradient / hessian, multi-agent / single-agent, etc. For example, genetic algorithm can be used on a wide range of domains and problems. I have experimented with a navbox but because of the categorization difficulty I cannot seem to make a good and concise one (or multiple navboxes that can be combined.) As the existing navbox has many confusions I would again like to propose that we remove it and instead expand the use of categories and make better introductions and 'see-also' sections that cross-link articles where needed. I have already done this for a number of articles and others should feel free to participate in the effort where they have expertise. Optimering (talk) 09:03, 11 February 2011 (UTC)

I agree with many of your comments. The line on one-dimensional optimization may contain vestigial items, leftovers from textbooks of the 1970s (and before).

I would suggest looking at a great book on optimization, and following the outline. therein: Michel Minoux's book has a new (French) edition. Jeremy Shapiro's book from the early 1980s attempted to provide an overview of optimization, also. I suppose that Rardin's Optimization in OR textbook tries to cover many important topics, and could be useful.

A decision to delete this box needs more input from others, because few monitor template pages. If you want to delete this infobox, then please post requests for comment at the relevant WikiProject talk pages.

I would argue for moderation. Many editors prefer info-boxes over "see-also" sections, to reduce time for initial editing and especially maintenance, to reduce memory-demands in the original page, and because infobox categorizations help while long lists repel. It does seem valuable for WP to have one infobox on optimization, which is a recognized discipline at the intersection of mathematics, computer science, business administration, industrial engineering, statistics, etc. Look at the economics infobox and see that it contains topics that are of interest to different groups, too.

Your work on cross-linking and categorizing articles sounds very valuable, even if the infobox is kept. (Adding a lot of "see also" material may be less useful.)  Kiefer.Wolfowitz  (talk) 10:30, 11 February 2011 (UTC)

I see your points and I might reverse myself. Could we try and split this navbox into several navboxes? Strict categorization might be difficult and some methods might have to be listed in more than one navbox (e.g. genetic algorithm). Could we try and build these navboxes right on this talk-page? I'm a bit preoccupied at the moment but will contribute as time permits. A suggestion would be navboxes for: optimization of real-valued functions, combinatorial problems, (non-)linear programming, etc. Optimering (talk) 09:09, 17 February 2011 (UTC)

Hi Optimering!

This navbox serves its purpose. There is a cross-disciplinary field of optimization, whose computational interests are faithfully represented by this navbox. The navbox reflects the content of the books of Shapiro and Minoux (and the textbook of Rardin), for example---the subset of topics covered in Roger Fletcher's book is also covered. These references are well-regarded by those with interests more in applied combinatorial optimization and operations research, such as Thomas Magnanti, for example. Given the stable consensus of the optimization community, I see no reason to split up this box, which only provides the most important topics.

As I have suggested many times, you are welcome to develop a navbox about your interests in (meta)heuristics: You apparently are a titan of meta-heuristics to whom other world-leaders might refer, according to your recent discussion at AFD. Indulge your interests and use your knowledge!

It does seem that meta-heuristics has a lot of articles, some of which seem to have conflict-of-interest and self-promotion concerns; could you try to weed the worst COI-problems from such articles?

Other navboxes could be developed for e.g. combinatorial optimization. The main problem is a lack of articles, not a lack of navboxes. Indeed, integer programming is a stub and the optimization article is only at Start class.

Thanks,  Kiefer.Wolfowitz  (Discussion) 12:34, 17 February 2011 (UTC)

I have now made some changes to this navbox. I've tried to order from general to specific, and from most to least popular/relevant. As I've said previously, strict separation of categories is difficult here. I have not made changes to (non-)linear programming and convex optimization (yet), but some weeding and ordering should probably be done there as well. Please feel free to revise these as well as my other changes. The navbox ought to give a quick overview of the main optimization methods, regardless of how textbooks, survey papers, etc. may be structured. The Wiki categories might need some attention as well. A suggestion would be to merge 'optimization algorithms' into 'optimization methods'. The category 'heuristic algorithm' is a paradox, a computational method is either a heuristic or an algorithm (see e.g. the dictionary definition of these terms.) Optimering (talk) 10:20, 19 February 2011 (UTC)

Computer scientists would reject your proposal to merge algorithms and iterative methods. Knuth's Art of Computer Programming begins by distinguishing algorithms from methods (from heuristics, I believe; otherwise, look at Papadimitriou and Steiglitz).

Perhaps the category "heuristic algorithms" could be moved to "computing heuristics"? Non-computational heuristics are studied in psychology and behavioral organization theory, etc., e.g. by Herb Simon and James March, sometimes under the pragmatic rubric of the abductive mode of inquiry, following Charles Sanders Peirce. Sincerely,  Kiefer.Wolfowitz  (Discussion) 15:44, 20 February 2011 (UTC)

Self-promotion concerns

Optimering, I have reversed your latest edit, which is your latest edit promoting (meta)heuristics.

I would ask you to consider whether your edits over the last year are uncomfortably close to the description of "single-purpose account", in your case championing "metaheuristics". Your own description of your status (in a recent AFD discussion) raises concerns about conflict of interest, particularly self promotion.

Your description of metaheuristics as being (in optimization) more popular or important than the other algorithms is false, but in any event would be Original Research, contradicting the place of heuristics in optimization theory (important, but often at the last chapters of optimization textbooks). In the SIAM, ACM, and Mathematical Programming (Optimization) Society journals, heuristics have an important, perhaps essential, but still small role.

I would suggest that you read Phil Wolfe's 1973 "universal algorithm for optimization" published anonymously in Mathematical Programming: You will note that "anonymous"'s article lacks a complexity/convergence analysis and computational testing against other leading approaches. Wolfe intended his article as satire, although some emulate the article ....

Sincerely,  Kiefer.Wolfowitz  (Discussion) 15:11, 19 February 2011 (UTC)

Your removal of "integer programming" and "approximation algorithm" and your your adding "ant-colony optimization" were not the best methods of establishing your good-faith bonafides. Do you think that you will have any support at the WikiProject Computer Science for such tendentious editing? Why don't you ask for a second opinion on its talk page, about the relative importance of approximation algorithms and pissant heuristics....  Kiefer.Wolfowitz  (Discussion) 15:17, 19 February 2011 (UTC)

I strongly resent your accusations. You are really out of line here. I was trying to help in response to our previous dialogue and I was merely following the ordering that was already established in the navbox. I also politely asked others to 'please revise' if they disagreed with my edits. In fact, it appears that You have a strong bias Against heuristics using derogatory nicknames such as 'pissant heuristics' etc., and you are seemingly also basing your knowledge on textbooks on only certain types of optimization. I try to be fair and balanced in the edits I make, e.g. you will see that I have on several occasions cited strong criticism of metaheuristics. The navbox category 'methods calling functions' is actually what metaheuristics are and this follows general-to-specific ordering as gradient- and hessian-based optimizers follow. Some call metaheuristics for 'derivative free' or 'direct search' methods instead, but what they do is they 'call functions' and do not use gradients or hessians. 'Metaheuristics' is a more widely accepted term and it is what is being used on Wikipedia rather than 'direct search' etc. 'Methods calling functions' seems like a computer programmer's description. I removed the methods listed such as golden section search because they are special purpose methods and we can only list a limited number so they should be the most general and popular. This navbox is a complete mess and I tried to take a step towards cleaning it up. Since you exercise aggressive ownership tendencies over it I will now consider removing it from some of the articles on which it has been posted, because it really only serves the purpose of confusing people. I hope this does not start an edit-war which is in no way my intention or desire. It is because of cases like this that it is so difficult to recruit experts to edit Wikipedia articles. Maybe my suggestion for splitting it into several navboxes was not such a bad idea after all? Optimering (talk) 10:05, 23 February 2011 (UTC)

Combinatorial optimization algorithms

I created a subgrouping for combinatorial optimization algorithms. I was tempted to include mathematical structures important in combinatorial optimization (networks, graphs, matroids, greedoids, etc.) but then this template would not have been focused on algorithms. I did try to include the principal combinatorial algorithms presented in optimization and CS algorithm textbooks. Kiefer.Wolfowitz (talk) 11:43, 2 December 2010 (UTC)

Computational statistics

I removed the line on statistical methods. Like the minor heuristics that were removed earlier, the statistical methods are rarely discussed in optimization textbooks (although they are discussed in statistical textbooks, e.g. in system identification). Kiefer.Wolfowitz (talk) 11:46, 2 December 2010 (UTC)

User Optimering, Metaheuristics, and Template:Optimization algorithms

I posted the following on the talk page at "algorithm". Please respond there.  Kiefer.Wolfowitz  (Discussion) 15:50, 19 February 2011 (UTC)

Please view the promotion of (meta)heuristics by editor Optimering over the last year, including his edit at the Template:Optimization algorithms, where he removed approximation algorithm and added ant colony optimization from the section on combinatorial optimization. He also removed the Gauss-Newton and Levenberg-Marquardt articles from the gradient-related section; these are the most used methods in all of optimization, according to Lemaréchal, Gilbert, Bonnans, and Sagazstibal (sic) and science citation index counts.

"Optimering" has already had one "heads-up" at the COI noticeboard. He has been warned about OR and self promotion (at risk of blocking) at his self-titled discussion "Block_threat_to_expert_contributor" at the administrators' noticeboard. and has boasted about his own standing in the world of metaheurstics at AFD.

Currently this template seems heavily biased towards continuous/mathematical optimization. E.g. why doesn't the section on combinatorial algorithms mention Ford–Fulkerson or any algorithms for finding a minimum spanning tree? There are only some very generic "algorithmic design techniques". I think splitting this template into several more detailed ones, together with a higher level overview, would be a good idea.

Also, insinuating an editor is acting out of a conflict of interest (without providing any concrete evidence) at various places, while you're have a minor content dispute with him doesn't seem like a very honourable thing to do. —Ruud 17:34, 19 February 2011 (UTC)

E.g. why shouldn't this template simply list the optimization (mathematics)#Major subfields and each have a more detailed navigation box on their own? —Ruud 17:41, 19 February 2011 (UTC)

Dear Ruud, you continue to make a number of useful comments.

Regarding continuous/discrete imbalance, I plead plurally. First, arguing from authority: Continuous optimization (particularly convex & variational analysis) has a starring (and perhaps leading) role in even discrete optimization, according to Papadimitriou, Minoux, Magnanti, Lovasz, etc. Second, on my innocence: Checking the history, you can see that I expanded the combinatorial optimization row, earlier (perhaps even initiating it?).

Please be bold and expand the combinatorial optimization section, perhaps splitting it into a graph/network algorithm section and an an non-graphic combinatorial optimization section. You mentioned some important graph algorithms above.

The template is for optimization algorithms. Your suggestion sounds appropriate for a template on optimization theory. A year ago, I made some similar comments, suggeting some topics that I thought might belong in a more (theoretical) template---"foundations of optimization": Order & lattice theory, topological/metric completeness, inf-compactness (Weierstrass), extrema and fixed-points and zeros, matroids, oriented matroids, greedoids, etc. Good luck on making an optimization theory template!

(I might make a convex analysis template, following a suggestion by Geometry Guy (reviewing Shapley-Folkman lemma.)

Perhaps I lost patience prematurely yesterday. However, if you look at this page over the last 6 months, you can see that I have spent a lot of time harvesting, rinsing, peeling, and chopping carrots. Yesterday, I judged that my attempts (coupled with those of other editors, only a fraction of whom were linked) in working with Optimering had few results, and that further carrot-preparation would be enabling behavior, rather than helpful.

Of course, my judgment of the optimization-algorithmic standing of Optimering's metaheuristics may be wrong, also.

Sincerely,  Kiefer.Wolfowitz  (Discussion) 13:55, 20 February 2011 (UTC)

Dear Ruud, I don't believe it be helpful to document here the similarities between the Pedersen thesis and the articles that Optimering has started. Compare them for yourself. WP:AGF may force us to conclude that Pedersen's thesis found an innocent fan in Optimering, but some statement of concern about an appearance of a possible COI may be warranted.  Kiefer.Wolfowitz  (Discussion) 19:29, 22 February 2011 (UTC) (weakened last phrase to "appearance of a possible" COI, 22:13, 22 February 2011 (UTC))

I've seen quite a few researchers cite their own work on Wikipedia, sometimes justified, sometimes not. The article on particle swarm optimization, significantly revised by Optimering, seems to be neutrally written, so I don't think the potential conflict of interest has materialized into an actual conflict of interests. So far, I've seen no concrete evidence Optimering is not editing in good faith. In the case of this specific template, I could imagine that in its current form, some people might not find it a useful addition to an article such as simulated annealing. Cheers, —Ruud 20:46, 22 February 2011 (UTC)

I don't really want to participate in this discussion any further, but just want to voice my support for Ruud's suggestion for an overall navbox listing the major subfields of optimization, and then multiple navboxes detailing those. That would probably also defuse this heated debate which seems to have become a war between classes of optimizers. Optimering (talk) 10:51, 23 February 2011 (UTC)

I have now made navboxes following Ruud's idea, which I like, please see simulated annealing and particle swarm optimization for examples on how to apply them. These initial navboxes are just to get the ball rolling and other editors are naturally invited to make changes and additions as I note on Template_talk:Major_subfields_of_optimization. Kiefer.Wolfowitz, I regret that we got into this debacle and hope you agree that Ruud's idea with multiple navboxes is a good one, and that you will contribute with new and specialized navboxes for the optimizer categories where you have expertise. Cheers, Optimering (talk) 12:21, 23 February 2011 (UTC)

These all seem to be good nav-boxes, which should be useful. I would suggest using the simple "heuristics", as is usual in optimization and computer science, rather than the sesquipedalian "metaheuristics". Please make an announcement at the computer science and systems wikiprojects.  Kiefer.Wolfowitz  (Discussion) 17:41, 23 February 2011 (UTC)

Combinatorial Optimization

• Graph theory
  • Shortest path
  • Spanning tree
    • Minimum spanning tree
    • Minimum cost spanning tree
  • Flow network
    • Maximum flow problem
    • Minimum-cost flow problem

belowstyle

I would like to remove the belowstyle line so the style is consistent per wp:deviations. Any objections? Frietjes (talk) 16:30, 24 June 2011 (UTC)

Sounds good if you preserve the content. Thanks for asking! Cheers,  Kiefer.Wolfowitz 17:10, 24 June 2011 (UTC)

Classification of ellipsoid method

Please see this discussion item on the Linear Programming talk page (adding here for extra visibility). Alexeicolin (talk) —Preceding undated comment added 02:51, 10 January 2013 (UTC)