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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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)[reply]

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.