Traduzione by GIUSEPPE TURTURIELLO, volontario di English Gratis. Il testo originale è tratto da una pagina del sito inglese di Wikipedia ed è disponibile nel rispetto della licenza Creative Commons Attribution 2.5
photo credit: mag3737

Optimization (mathematics)
Ottimizzazione matematica

In mathematics, the term optimization, or mathematical programming, refers to the study of problems in which one seeks to minimize or maximize a real function by systematically choosing the values of real or integer variables from within an allowed set.
In matematica il termine ottimizzazione, o programmazione matematica, si riferisce allo studio dei problemi nei quali si cerca di minimizzare o massimizzare una funzione di variabile reale scegliendo ordinatamente i valori della variabile reale o intera all’interno dell’insieme di definizione.

Overview
Panoramica

An optimization problem can be represented in the following way

Given: a function f : A R from some set A to the real numbers

Sought: an element x₀ in A such that f(x₀) <= f(x) for all x in A (“minimization”) or such that f(x₀) >= f(x) for all x in A (“maximization”).

Un problema di ottimizzazione può essere rappresentato nel modo seguente

Data: una funzione f: A R da qualche insieme A ai numeri reali

Sia: x ₀ un elemento in A tale che f (x ₀₎ <= f (x) per ogni x in A ( “minimizzazione”) o tale che f (x ₀) >= f(x) per ogni x in A ( ” massimizzazione “).

Such a formulation is called an optimization problem or a mathematical programming problem (a term not directly related to computer programming , but still in use for example in linear programming – see History below).
Una tale formulazione è detta problema di ottimizzazione o problema di programmazione matematica (termine non direttamente correlato alla programmazione software, ma ancora in uso per esempio nella programmazione lineare – vedi Storia di seguito).

Many real-world and theoretical problems may be modeled in this general framework. Problems formulated using this technique in the fields of physics and computer vision may refer to the technique as energy minimization, speaking of the value of the function f as representing the energy of the system being modeled .
Molti problemi concreti e teorici possono essere modellati in questo quadro generale. Problemi formulati utilizzando questa tecnica nei campi della fisica e della visione al computer possono far riferimento alla tecnica della minimizzazione dell’energia, parlando del valore della funzione f come rappresentante l’energia del sistema modellato.

Typically, A is some subset of the Euclidean space Rⁿ, often specified by a set of constraints, equalities or inequalities that the members of A have to satisfy. The domain A of f is called the search space , while the elements of A are called candidate solutions or feasible solutions .
In genere, A è un particolare sottoinsieme dello spazio euclideo Rⁿ, spesso specificato da un insieme di vincoli, uguaglianze o disuguaglianze che i membri di A devono soddisfare. Il dominio A di f è detto lo spazio di ricerca, mentre gli elementi di A sono detti soluzioni candidate o soluzioni ammissibili.

The function f is called an objective function , or cost function . A feasible solution that minimizes (or maximizes, if that is the goal) the objective function is called an optimal solution .
La funzione f è detta funzione obiettivo, o funzione costo. Una soluzione ammissibile che minimizza (o massimizza, se questo è lo scopo) la funzione obiettivo è detta soluzione ottimale.

Generally, when the feasible region or the objective function of the problem does not present convexity , there may be several local minima and maxima, where a local minimum x^* is defined as a point for which there exists some ? > 0 so that for all x such that

the expression

In genere, quando la regione ammissibile o la funzione obiettivo del problema non presentano convessità, ci possono essere più minimi e massimi locali, dove un minimo locale x^* è definito come un punto per il quale esiste qualche ?> 0 tale che per ogni x scelto in modo che

l’espressione

holds; that is to say, on some region around x^* all of the function values are greater than or equal to the value at that point. Local maxima are defined similarly.
sia valida; cioè, in alcune regioni dell’intorno di x^* tutti i valori della funzione sono maggiori del o uguali al valore in quel punto. I massimi locali sono definiti in modo simile.

A large number of algorithms proposed for solving non-convex problems – including the majority of commercially available solvers – are not capable of making a distinction between local optimal solutions and rigorous optimal solutions, and will treat the former as actual solutions to the original problem. The branch of applied mathematics and numerical analysis that is concerned with the development of deterministic algorithms that are capable of guaranteeing convergence in finite time to the actual optimal solution of a non-convex problem is called global optimization .
Un gran numero di algoritmi proposti per la soluzione dei problemi non convessi – tra cui la maggior parte dei risolutori disponibili in commercio – non sono in grado di fare una distinzione tra soluzione di ottimo locale e soluzione di ottimo rigorosa, e tratteranno la prima come l’effettiva soluzione al problema originale. Il ramo della matematica applicata e dell’analisi numerica che riguarda lo sviluppo di algoritmi deterministici che sono in grado di garantire la convergenza in un tempo finito per la reale soluzione ottimale di un problema non-convesso è detta ottimizzazione globale.

The first optimization technique, which is known as steepest descent, goes back to Gauss. Historically, the first term to be introduced was linear programming , which was invented by George Dantzig in the 1940s.
La prima tecnica di ottimizzazione, che è nota come di più ripida discesa, risale a Gauss. Storicamente, il primo termine a essere introdotto è stato di programmazione lineare, che fu inventato da George Dantzig nel 1940.

The term programming in this context does not refer to computer programming (although computers are nowadays used extensively to solve mathematical problems).
Il termine di programmazione in questo contesto non si riferisce alla programmazione di computer (anche se i computer sono oggi ampiamente utilizzati per risolvere problemi matematici).

Instead, the term comes from the use of program by the United States military to refer to proposed training and logistics schedules, which were the problems that Dantzig was studying at the time.
Invece, il termine deriva dall’uso di programma da parte dei militari degli Stati Uniti per riferirsi a proposte di formazione e schedulazioni logistiche, che sono stati i problemi che Dantzig stava studiando a quel tempo.

(Additionally, later on, the use of the term “programming” was apparently important for receiving government funding, as it was associated with high-technology research areas that were considered important.)
(Inoltre, in seguito, l’uso del termine “programmazione” è stato effettivamente importante per la ricezione di finanziamenti governativi, come è stato associato con aree di ricerca ad alta tecnologia che erano considerate importanti.)

Optimization problems are often expressed with special notation. Here are some examples:

I problemi di ottimizzazione sono spesso espressi con notazione speciale. Ecco alcuni esempi:

This asks for the minimum value for the objective function x ² + 1, where x ranges over the real numbers R . The minimum value in this case is 1, occurring at x = 0.
Questo chiede il valore minimo per la funzione obiettivo x² + 1, dove x varia nell’insieme dei numeri reali R. Il valore minimo in questo caso è 1, per x = 0.

This asks for the maximum value for the objective function 2 x , where x ranges over the reals. In this case, there is no such maximum as the objective function is unbounded, so the answer is “infinity ” or “undefined”.

Questo chiede il valore massimo per la funzione obiettivo 2 x, dove x varia nei reali. In questo caso, non esiste tale massimo in quanto la funzione obiettivo è illimitata, per cui la risposta è “infinito” o “indefinito”.

This asks for the value (or values) of x in the interval (??, ?1] that minimizes (or minimize) the objective function x ² + 1 (the actual minimum value of that function does not matter). In this case, the answer is x = ?1.

Questo chiede il valore (o i valori) di x nell’intervallo (- ?, -1] che minimizza (o minimizzano) la funzione obiettivo x² + 1 (l’effettivo minimo di tale funzione non conta). In questo caso, la risposta è x = -1.

This asks for the ( x , y ) pair, or pairs, that maximizes (or maximize) the value of the objective function x cos( y ), with the added constraint that x lies in the interval [?5, 5] (again, the actual maximum value of the expression does not matter). In this case, the solutions are the pairs of the form (5, 2 ? k ) and (?5, (2 k + 1)?), where k ranges over all integers .

Questo chiede la coppia, o le coppie, (x, y) che massimizza (o massimizzano) il valore della funzione obiettivo x cos(y), con l’ulteriore vincolo che x vari nell’intervallo [-5, 5] ( ancora una volta, l’effettivo valore massimo dell’espressione non conta). In questo caso, le soluzioni sono le coppie di forma (5, 2 ? k) e (-5, (2 k + 1) ?), dove k spazia su tutti gli interi.

· Linear programming studies the case in which the objective function f is linear and the set A is specified using only linear equalities and inequalities.
· La Programmazione lineare studia il caso in cui la funzione obiettivo f è lineare e l’insieme A è definito usando solo uguaglianze e disuguaglianze lineari.

· Such a set is called a polyhedron or a polytope if it is bounded .
· Tale insieme è detto poliedro o politopo se è limitato.

· Integer programming studies linear programs in which some or all variables are constrained to take on integer values.
· La programmazione intera studia problemi lineari in cui alcune o tutte le variabili sono vincolate ad assumere valori interi.

· Quadratic programming allows the objective function to have quadratic terms, while the set A must be specified with linear equalities and inequalities.
· La Programmazione quadratica permette alla funzione obiettivo di avere termini quadratici, mentre l’insieme A è definito con uguaglianze e disuguaglianze lineari.

· Nonlinear programming studies the general case in which the objective function or the constraints or both contain nonlinear parts.
· La programmazione non lineare studia il caso generale in cui la funzione obiettivo o i vincoli o entrambe contengono parti non lineari.

· Convex programming studies the case when the objective function is convex and the constraints, if any, form a convex set.
· La programmazione convessa studia il caso in cui la funzione obiettivo è convessa e i vincoli, se del caso, formano un insieme convesso.

· This can be viewed as a particular case of nonlinear programming or as generalization of linear or convex quadratic programming.
· Questo può essere visto come un caso particolare di programmazione non lineare o come una generalizzazione della programmazione quadratica lineare o convessa.

· Semidefinite programming (SDP) is a subfield of convex optimization where the underlying variables are semidefinite matrices.
· La programmazione semidefinita (SDP) è un sottocampo della ottimizzazione convessa dove le variabili di base sono matrici semidefinite.

· It is generalization of linear and convex quadratic programming.
· Si tratta di generalizzazione della programmazione quadratica lineare e convessa.

· Stochastic programming studies the case in which some of the constraints or parameters depend on random variables.
· La programmazione stocastica studia il caso in cui alcuni dei vincoli o parametri dipendono da variabili casuali.

· Robust programming is, as stochastic programming, an attempt to capture uncertainty in the data underlying the optimization problem.
· La programmazione robusta è, come programmazione stocastica, un tentativo di catturare l’incertezza nei dati sottostante al problema di ottimizzazione.

· This is not done through the use of random variables, but instead, the problem is solved taking into account inaccuracies in the input data.
· Ciò non avviene attraverso l’uso di variabili casuali, ma invece, il problema è risolto tenendo conto delle imprecisioni dei dati di input.

· Combinatorial optimization is concerned with problems where the set of feasible solutions is discrete or can be reduced to a discrete one.
· L’ottimizzazione combinatoria si occupa dei problemi in cui l’insieme di soluzioni ammissibili è discreto o può essere ridotto ad un discreto.

· Infinite-dimensional optimization studies the case when the set of feasible solutions is a subset of an infinite-dimensional space, such as a space of functions.
· L’ottimizzazione a infinite dimensioni studia il caso in cui l’insieme di soluzioni ammissibili è un sottoinsieme di uno spazio infinito-dimensionale, come ad esempio uno spazio di funzioni.

· Heuristic algorithms

• Metaheuristics

· Algoritmi euristici

• Meta-euristiche

· Constraint satisfaction studies the case in which the objective function f is constant (this is used in artificial intelligence , particularly in automated reasoning ).

• Constraint programming.

· Il soddisfacimento dei vincoli studia di caso in cui la funzione obiettivo f è costante (questo è usato in intelligenza artificiale, in particolare nel ragionamento automatico).

o Programmazione vincolata.

· Disjunctive programming used where at least one constraint must be satisfied but not all. Of particular use in scheduling.
· La programmazione disgiunta è utilizzata dove almeno un vincolo deve essere soddisfatto, ma non tutti. Di particolare impiego nella schedulazione.

· Trajectory optimization is the speciality of optimizing trajectories for air and space vehicles.
· L’ottimizzazione delle traiettorie è la specialità che ottimizza traiettorie per veicoli aerei e spaziali.

In a number of subfields, the techniques are designed primarily for optimization in dynamic contexts (that is, decision making over time):
In un certo numero di sottocampi, le tecniche sono progettate principalmente per l’ottimizzazione in contesti dinamici (cioè, nel processo decisionale nel tempo):

· Calculus of variations seeks to optimize an objective defined over many points in time, by considering how the objective function changes if there is a small change in the choice path.
· Il Calcolo delle variazioni cerca di ottimizzare un obiettivo definito su molti punti nel tempo, considerando come la funzione obiettivo cambia se c’è un piccolo cambiamento nella scelta del percorso.

· Optimal control theory is a generalization of the calculus of variations.
· La teoria del controllo ottimale è una generalizzazione del calcolo delle variazioni.

· Dynamic programming studies the case in which the optimization strategy is based on splitting the problem into smaller subproblems.
· La programmazione dinamica studia il caso in cui la strategia di ottimizzazione si basa sulla suddivisione del problema in sottoproblemi più piccoli.

· The equation that relates these subproblems is called the Bellman equation .
· L’equazione che riguarda questi sottoproblemi è detta equazione di Bellman.

For twice-differentiable functions, unconstrained problems can be solved by finding the points where the gradient of the objective function is zero (that is, the stationary points) and using the Hessian matrix to classify the type of each point.
Per funzioni due volte-differenziabili, i problemi non vincolati possono essere risolti trovando i punti dove il gradiente della funzione obiettivo è nullo (ovvero, il punto di stazionarietà) e usando la matrice Hessiana per classificare il tipo di ciascun punto.

If the Hessian is positive definite, the point is a local minimum, if negative definite, a local maximum, and if indefinite it is some kind of saddle point.
Se la Hessiana è definita positiva, il punto è un minimo locale, se definita negativa, un massimo locale, e se è indeterminata una sorta di punto sella.

However, existence of derivatives is not always assumed and many methods were devised for specific situations.
Tuttavia, l’esistenza delle derivate non è sempre scontata e molti metodi sono stati concepiti per situazioni specifiche.

The basic classes of methods, based on smoothness of the objective function, are:

· Combinatorial methods
· Derivative-free methods
· First order methods
· Second-order methods

Le classi base dei metodi, basate su una funzione obiettivo liscia, sono:

• metodi combinatori
• metodi senza derivate
• metodi del primo ordine
• metodi del secondo ordine

Actual methods falling somewhere among the categories above include:

· Gradient descent aka steepest descent or steepest ascent
· Nelder-Mead method aka the Amoeba method
· Subgradient method – similar to gradient method in case there are no gradients
· Simplex method
· Ellipsoid method
· Bundle methods
· Newton’s method
· Quasi-Newton methods
· Interior point methods
· Conjugate gradient method
· Line search – a technique for one dimensional optimization, usually used as a subroutine for other, more general techniques.

I metodi reali che rientrano in qualche punto tra le categorie di cui sopra comprendono:

• Gradiente di discesa alias di più ripida discesa o più ripida salita
• Il metodo di Nelder-Mead alias il metodo Amoeba
• metodo subgradient – simile al metodo del gradiente nel caso in cui non vi sono gradienti
• metodo del simplesso
• metodo dell’ellissoide
• metodi bundle
• metodo di Newton
• metodo quasi-Newtoniani
• metodi del punto interno
• metodo del gradiente coniugato
• ricerca lineare – una tecnica per l’ottimizzazione uno-dimensionale, di solito usata come una subroutine per altre, più generali tecniche.

Should the objective function be convex over the region of interest, then any local minimum will also be a global minimum. There exist robust, fast numerical techniques for optimizing twice differentiable convex functions.
La funzione obiettivo dovrebbe essere convessa sopra la regione di interesse, allora ogni minimo locale sarà anche un minimo globale. Esistono robuste, veloci tecniche numeriche per l’ottimizzazione delle funzioni convesse due volte differenziabili.

Constrained problems can often be transformed into unconstrained problems with the help of Lagrange multipliers .
I problemi vincolati possono spesso essere trasformati in problemi non vincolati con l’aiuto dei moltiplicatori di Lagrange.

Here are a few other popular methods:

• Hill climbing
• Simulated annealing
• Quantum annealing
• Tabu search
• Beam search
• Genetic algorithms
• Ant colony optimization
• Evolution strategy
• Stochastic tunneling
• Differential evolution
• Particle swarm optimization
• Harmony search
• Bees algorithm

Ecco alcuni altri metodi popolari:

• Hill climbing
• Simulated annealing
• Annealing quantistica
• Tabu search
• ricerca Beam
• Algoritmi genetici
• ottimizzazione Ant colony
• Strategia evolutiva
• tunneling stocastico
• evoluzione differenziale
• ottimizzazione a sciame di particelle
• ricerca armonica
• algoritmo bees

Problems in rigid body dynamics (in particular articulated rigid body dynamics) often require mathematical programming techniques, since you can view rigid body dynamics as attempting to solve an ordinary differential equation on a constraint manifold; the constraints are various nonlinear geometric constraints such as “these two points must always coincide”, “this surface must not penetrate any other”, or “this point must always lie somewhere on this curve”.
I problemi nella dinamica del corpo rigido (in particolare dinamica del corpo rigido articolato) spesso richiedono tecniche di programmazione matematica, poiché può essere vista come il tentativo di risolvere un’equazione differenziale ordinaria su una varietà vincolata; i vincoli sono geometrici non lineari vari come ad esempio “questi due punti devono sempre coincidere”,” questa superficie non deve intersecare nessun altra”, o” questo punto deve sempre giacere da qualche parte su questa curva”.

Also, the problem of computing contact forces can be done by solving a linear complementarity problem , which can also be viewed as a QP (quadratic programming problem).
Inoltre, il problema del calcolo delle forze di contatto può essere effettuato mediante la soluzione di un problema di complementarità lineare, che può anche essere visto come un PQ (problema di programmazione quadratica).

Many design problems can also be expressed as optimization programs. This application is called design optimization. One recent and growing subset of this field is multidisciplinary design optimization , which, while useful in many problems, has in particular been applied to aerospace engineering problems.
Molti problemi di progettazione possono anche essere espressi come programmi di ottimizzazione. Questa applicazione è detta ottimizzazione del progetto. Un recente e crescente sottoinsieme di questo settore è l’ottimizzazione multidisciplinare del progetto, che, pur utile in molti problemi, è stato in particolare applicato a problemi di ingegneria aerospaziale.

Mainstream economics also relies heavily on mathematical programming. An often studied problem in microeconomics, the utility maximization problem , and its dual problem the Expenditure minimization problem , are economic optimization problems. Consumers and firms are assumed to maximize their utility / profit .
L’economia mainstream si basa anche fondamentalmente sulla programmazione matematica. Un problema spesso studiato in microeconomia, il problema di massimizzazione dell’utilità, e il suo problema duale della minimizzazione della spesa, sono problemi di ottimizzazione economica. Si assume che consumatori e aziende massimizzino la loro utilità / profitto.

Also, agents are most frequently assumed to be risk-averse thereby wishing to minimize whatever risk they might be exposed to. Asset prices are also explained using optimization though the underlying theory is more complicated than simple utility or profit optimization. Trade theory also uses optimization to explain trade patterns between nations.
Inoltre, si assume che gli agenti siano più frequentemente avversi al rischio quindi che desiderino minimizzare qualsiasi rischio cui potrebbero essere esposti. I prezzi di asset sono spiegati anche con l’ottimizzazione sebbene la teoria sottostante sia più complicata di quella dell’utilità semplice o dell’ottimizzazione del profitto. La teoria del commercio utilizza inoltre l’ottimizzazione per spiegare le correnti di scambio tra le nazioni.

Another field that uses optimization techniques extensively is operations research.
Un altro settore che utilizza estensivamente tecniche di ottimizzazione è la ricerca operativa.