Talk:Optimization (mathematics)

From Wikipedia, the free encyclopedia

WikiProject Mathematics
Mathematics Portal
This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating: Start Class Top Priority  Field: Applied mathematics
One of the 500 most frequently viewed mathematics articles.
WikiProject Systems This article is within the scope of WikiProject Systems, which collaborates on articles about the idea of systems. If you would like to help, you can edit this article or visit the project page, where you can join the project and/or contribute to the discussion.
??? This article has not yet received a rating on the assessment scale. [FAQ]
??? This article has not yet received an importance rating within Systems.
Comments:

KaHa242 06:16, 31 Mar 2004 (UTC)

Contents

[edit] Global optimization

A more general question that came up: this page is about global optimization. I propose to merge Optimization (mathematics) and global optimization and store it in global optimization. The entry Optimization (mathematics) should be changed to give links to global optimization and local optimization and describe the difference (like NP-completness for most of the GO-problems, local optimization more or less a topic in numerics with standard algorithms like conjugate gradient etc...).

I strongly argue into this direction as optimization has to be distinguished according to the targets that one follows.

I disagree that this page is about global optimization, but I agree that they should be merged. I think that global optimization should redirect to here, and that there should be a section in this article on local vs global optimization, and what kind of algorithms find which or are likely to find which etc. moink 17:08, 31 Mar 2004 (UTC)
Well, the definition at the top of the page talks about finding x_m in the domain A, so that f(x_m)<=f(x) for every x in A. A local version would be "for every x_m there is a neighborhood U in which f(x_m)<=f(x) with x in U". That was my reasoning behind classifying the page to be about GO. KaHa242 08:12, 2 Apr 2004 (UTC)
You're right, the introduction is poor and should be fixed. moink 18:52, 2 Apr 2004 (UTC)

I disagree with many points of view expressed in this comment. Initially, a clear distinction between the concept of an optimization problem and the capabilities and limitations of available numerical methods to solve it must be made. An optimization problem and its optimal solution are defined precisely as in the beginning of the article. Rigorously, the criteria that defines a local optimal solution does not necessarily meet the requirements for it to be regarded as a optimal solution, although many numerical methods have the strong limitation of not being able to guarantee rigorous (or global) optimality and treat local solutions as de facto solutions to the problem. In other words, a local optimal solution is not necessarily the actual solution to the problem, but it’s the best we can get using common NLP and MINLP solvers. Global optimization, on the other hand, is a field of study that aims the development of deterministic algorithms that are capable of guaranteeing convergence in finite time to the actual optimal solution of a non-linear (and non-convex) problem. Therefore, Global Optimization defines a set of methodologies and algorithms designed to obtain a proven optimal solution to an optimization problem, and it is not, by any means, the definition of the problem at hand. --Jonnat 20:30, 17 March 2006 (UTC)

[edit] Mathematical programming

This article seems to be about mathematical programming, which is not the same as but one type of optimization. Am I right? Should it be moved to mathematical programming then? I mean: The Lagrange multiplier is not even mentioned. And the convex optimization section assumes that there exists a local minimum within the constraints. I am not an expert in this field so ... what do you think? --Rade

Mathematical Programming and Optimization are synonyms. However, the term optimization is sometimes viewed as having a broader sense that includes non-deterministic numerical procedures and alternative problem formulations such as genetic algorithms and tabu-search. --Jonnat 20:38, 17 March 2006 (UTC)

[edit] Argmin

Sorry to serious math people for any errors in my explanation of min, arg min, etc..

Perhaps one of you could also clarify for me what the subscript x in minx f(x) means. (I take this to mean, hopefully correctly, "What is the minimum value of f(x)?") Is it an indication that x is a variable, so you don't accidentally treat it as a constant? If so, when do you have to specify subscript x and when do you not?

--Ryguasu 04:22 Nov 6, 2002 (UTC)

It's in the context of argmin, argmax, then it's the value of x which minimizes f(X)

The last example of section 1 is not correct. Patrick 02:07 Dec 20, 2002 (UTC)


[edit] Book of Boyd and Vandenberghe

As far as I can see, the book of Boyd and Vandenberghe cannot be downloaded from the website, in contradiction to the recent edit. Did I perhaps miss the correct link? -- Jitse Niesen 12:22, 8 Nov 2004 (UTC)

No response, so I removed the link. -- Jitse Niesen 23:14, 23 Nov 2004 (UTC)

The book can be downloaded from (http://www.stanford.edu/~boyd/bv_cvxbook.pdf ). Right ?

Correct, so I added the book again to the article. -- Jitse Niesen 13:38, 26 Nov 2004 (UTC)


[edit] Combinatorial optimization

User:Artur adib wrote:

In mathematics, the term optimization typically refers to the study of ...

I would say not typically, but all the time. So the word typically is reduntant.

(When the set A contains a finite number of elements, the problem falls in the domain of combinatorial optimization.)

OK, you do have a point. But you see, to include all the special cases would make the definition way too long. For example, I specialize in infinite dimensional optimization, when the domain of the objective function is a space of functions, or a space of shapes. But you see, if we add your special case, and my special case, what becomes is a mess. So, for the sake of clarity, and at the expence of being the most general, I deleted your sentence. There is still that link at the bottom about combinatorial optimization you put. You can also add it in the Major subfields section, several paragraphs below the definition of optimization. But I would suggest that we keep the definition of optimization simple. I would be very interested in hearing what you think about this. Thanks! --Oleg Alexandrov 23:01, 18 Dec 2004 (UTC)


[edit] Notations and other alterations

I would suggest major modifications on the notations section of the article. Specially, I suggest the replacement of the entire section containing all the illustrative examples by a more rigorous exposition of general instances of mathematical programming problems. From the mathematical representation of the general problem, most “subfields” specified in the next section can be derived from the specification of simple characteristics of the functions in the general model, such as linearity or convexity.

Moreover, the remaining sections also require major alterations. The information under the “techniques” section only regards methods for solving non-linear programming problems. The criteria for a local minimum to be also a global one is not only the convexity of the objective function, but also of the feasible region. The other popular methods linkified are considered heuristic methods and are commonly regarded as a separate from deterministic optimization procedures.--Jonnat 21:38, 17 March 2006 (UTC)

This is a nice article, and rather proeminent, so whatever you want to do has to be done slowly, and with discussion. :)
I like the existing "Notation" section. I think you suggest replacing it with something more complicated, and as such, I would think harder to understand for the general public. I would like to see more details on what you want to do before you get down to big rewrites. Could you write in here your version of the "Notation" section? Would be nice to see. Oleg Alexandrov (talk) 02:00, 18 March 2006 (UTC)
I completely agree that any major changes should be thoroughly discussed. And I appreciate the suggestion of posting major changes in the discussion prior to a modification of the article. I am new to Wikipedia and still getting used with the dynamics of the site :)
However, I do believe that the article should be consistently reviewed. I believe that it should present the Mathematical Programming problem in a way that is closer to the ones that acknowledged textbooks in the field use. But primarily, I think that the information contained in the article should be concise. If methods for solving nonlinear programming problems are described, so must be methods for solving LPs and IPs. And a clear distinction between proven finite-time methods and heuristics should be made.
Your point about the understanding the general public is crucial, and I admit that I have little idea about who is Wikipedia’s public. I would really appreciate if you could share some insights in that mater. All I can do now, however, is base this analysis in myself, as a Wikipedia user. I use Wikipedia differently when I’m looking for mathematical theories or general information. In the latter case, I’d rather find a simplified article that would give me some basic definitions to start understanding a topic, whereas in the former case, I like to see more rigorous articles that could give me a more complete understanding of the topic and give me some pointers to further study. I don’t know if I’m off the scope of the site, but please tell me if so. --Jonnat 15:40, 20 March 2006 (UTC)
As often, when Oleg says that an article is "nice", I think it is merely a good start.
The public depends on the article under consideration. This article is probably also read by people that do not know much mathematics. So I think a good idea is to start at the most basic level possible. However, mathematicians will also read the article so it's okay to get technical later. The important thing is to increase the difficulty slowly throughout the article (see Wikipedia:Manual of Style (mathematics) and Wikipedia:Make technical articles accessible for more discussion on this). Regarding textbooks, think of a text book used by non-maths (e.g., economics) students.
This makes me a bit anxious to support your changes to the notation section, though I'm not quite sure what you want. I think a nice outline for the article is to start with an informal defition (what is optimization?), then examples / applications (including notation) and then a discussion of the subfields (LP, IP, QP, etc.). The subfields should be treated in a few paragraphs (what is a linear problem? what are the main techniques for solving them?), with references to articles linear programming for details (see Wikipedia:Summary style).
I agree that the article, as it stands currently, gives an undue stress on nonlinear problems, and especially heuristic algorithms for them.
The question of the level at which an article should address its readers is one of the most difficult questions on Wikipedia and often generates a lot of discussion, so feel free to disagree. But you're most certainly not off-scope for the site. There are some highly technical articles around here.
Finally, welcome! I look forward to your future contributions. -- Jitse Niesen (talk) 23:56, 20 March 2006 (UTC)
Thank you for the insights. The linked pages were very useful. --Jonnat 22:15, 21 March 2006 (UTC)


Below are the discussed suggestions. The next section would replace the current sections of “notations” and “major subfields”. --Jonnat 16:32, 18 April 2006 (UTC)


[edit] General formulation and notations

Optimization problems in finite dimension can assume the following general form

\min\limits_{x,y}\;\; Z = f(x,y)
\mbox{subject to: }\
h(x,y) = a\
g(x,y) \leq b
x^{L} \leq x \leq x^{U}, x \in \Re^{n}
y \in \{0,1\}^{p}

Where f is a scalar function of the continuous variables x and of the discrete variables y, h is a q-dimension vector function representing equality constraints, g is a m-dimension vector function representing inequality constraints and xL and xU are lower and upper bounds on the x variable, respectively. Generally, the inequality constraints do not necessarily need to formulated with an upper limit to their value (≤), but this formulation constitutes a general formalism once any constraints in the form of a lower bound (≥) can be easily converted to an upper bound. Rigorously, a problem containing only the inequality constraints would, by itself, be a general representation of a mathematical programming problem, once the bounds on the variables can be immediately represented by this form and equality constraints can be represented by the association of two simultaneous constraints having the same upper and lower bounds.

Optimization problems are divided into distinct classes, according to characteristics of the functions and variables that compose them. In the case in which all the functions that belong to the model are linear functions and the set of discrete variables is empty (q = 0), the problem belongs to the class of Linear Programming (LP) problems. If, conversely, any of the functions in the problem present non-linearity and it’s variables are still all in a continuous space, the problem belongs to the class of Non-Linear Programming (NLP) problems. The special case in which the objective function of a continuous problem contains quadratic and bilinear terms and the entire set of constraints is composed of linear functions is regarded as Quadratic Programming (QP). Finally, if the problem contains discrete variables (q > 0), it belongs to the classes of Mixed Integer Linear Problems (MILP), if it is composed of linear functions, and Mixed Integer Non-Linear Problems (MINLP), otherwise.

[edit] logical programming

I always thought that logical programming is a special case of mathematical programming (where the search is for a model that satisfies a given theory), but the page on logical programming is written from a different viewpoint, like it is just another programming paradigm. I wonder if I am correct, maybe the log. progr. page could be improved by people here. Samohyl Jan 16:58, 14 June 2006 (UTC)

[edit] How about a much shorter introduction

  • The concepts of Maxima_and_minima have been nicely described in the article about Maxima_and_minima, but the description the the present article is a little vague. Perhaps it is better to provide a very short description and a link.
  • The description of convexity is important, but it should be put in a subsection rather than in the introduction of the article.


I do agree convexity should be placed in another section. Xerenio (talk) 18:51, 23 May 2008 (UTC)

[edit] Shorter introduction, promote discussion of applications, history

I support the comments above about placing the more technical content later in the article, and therefore propose a short introduction quickly followed by an expanded section on Uses. The ones given at the moment seem relatively specialized. It's important to mention that optimization lies at the heart of traditional (neo-classical) economics, and works out the consequences of a major hypothesis about human behaviour (i.e. that people make optimizing choices). One should also mention its role in statistical estimation – least-squares methods, maximum likelihood.

After Uses, History would be relatively non-technical and a good rationale for the more technical content that follows. Indeed, the history would provide a good way to organize the technical content.

One also needs to mention, or link to, extreme-value functions and duality theory.

[[User:Rwb001 16:07, 16 October 2006 (UTC)]]

I absolutely agree. Of all concepts used in mainstream economics this is the most fundamental and the article should mention it. I am going to add a short paragraph on it, then we can on that together. MartinDK 17:29, 8 November 2006 (UTC)

[edit] unrelated to computer programming

hi. AFAIK mathematical programming is completely unrelated to computer programming, however the article is a bit ambiguous with regard to this. I've not changed since i'm not truly sure... Jabbba (talk) 21:27, 3 February 2008 (UTC)