Contenido

Los problemas de optimización se expresan a menudo con una notación especial. A continuación se muestran algunos ejemplos.

Minimum and Maximum value of a function

Consider the following notation:

This denotes the minimum "Magnitude (mathematical)") value of the objective function, when x is selected from the set of real numbers. The minimum value in this case is and occurs for .

Similarly, the notation.

expresses the maximum value of the objective function 2x, where x is any real number. In this case, there is no such maximum, therefore there is no bounded optimal value.

Arguments for optimal entry

Consider the following expression:

or equivalently.

This represents the value (or values) of the argument "Argument (complex analysis)") of x in the interval "Interval (mathematics)") that minimize (or maximize) the objective function x + 1 (and not the minimum value that the objective function reaches for those values). In this case, the answer is x = -1, since x = 0 is not feasible, that is, it does not belong to the problem domain.

Similarly,

which equivalent to.

represents the pair (or pairs) (x,y) that minimize (or maximize) the value of the objective function xcos(y), with the added constraint that x lies in the interval [-5,5] (again, the minimum value of the function does not matter). In this case, the solutions are the pairs of the form (5, 2kπ) and (−5,(2k+1)π), where k runs through all the integers.

Arg min and arg max are sometimes written as argmin and argmax, meaning minimum argument and maximum argument.

Pierre de Fermat and Joseph Louis Lagrange found calculus-based formulas to identify optimal values, while Isaac Newton and Carl Friedrich Gauss proposed iterative methods to approximate the optimum. Historically, the term linear programming to refer to certain optimization problems is due to George B. Dantzig, although much of the theory had been introduced by Leonid Kantorovich in 1939. Dantzig published the Simplex Algorithm in 1947 and John von Neumann developed the theory of duality "Duality (mathematics)") in the same year.

The term programming in this context does not refer to computer programming. Rather, the term comes from the use of program by the United States military when referring to the training and logistics planning proposal, which was the problem studied by Dantzig at the time.

Other important researchers in the field of mathematical optimization were the following:

• - Convex programming studies the case in which the objective function is convex (minimization) or concave (maximization) and the set of constraints is convex. This can be seen as a particular case of nonlinear programming or as the generalization of linear or convex quadratic programming.

• Linear programming (LP): is a type of convex programming, in which the objective function f is linear and the set of constraints is specified using only linear equations and inequalities. This set is called a polyhedron or polytope if it is bounded.

• Conic programming: it is a general form of convex programming. PL, PCSO and PSD can all be viewed as conical programs with the appropriate cone type.

• Second-order cone programming (PCSO): It is a type of convex programming and includes certain types of quadratic programming problems.

• Semi-definite programming (PSD): is a subfield of convex optimization where the fundamental variables are semi-definite "Matrix (mathematics)" matrices. It is a generalization of linear programming and convex quadratic programming.

• Geometric programming: it is a technique by which the objective and inequality constraints expressed as polynomials and equality constraints as monomials can be transformed into a convex program.

• Programming with integers or Integer programming: studies linear programs in which some or all of the variables are forced to take integer values. This is non-convex and is generally much more complex than regular linear programming.

• - Quadratic programming: allows the objective function to have quadratic terms, while the feasible set can be specified with linear equations and inequalities. For specific forms of the quadratic term, this is a type of convex programming.

• - Fractional programming: studies the optimization of ratios of two nonlinear functions. The special class of concave fractional programs can be transformed to a convex optimization problem.

• - Nonlinear programming: studies the general case in which the objective function, or the constraints, or both, contain nonlinear parts. This may or may not be a convex program. In general, whether the program is convex affects the difficulty of solving.

• - Stochastic programming or Stochastic optimization: studies the case in which some of the constraints or parameters depend on random variables.

• - Robust programming: like stochastic programming, it is an attempt to capture uncertainty in the fundamental data of the optimization problem. This is done by using random variables, but instead, the problem is solved by taking into account inaccuracies in the input data.

• - Combinatorial optimization: is concerned with problems where the set of feasible solutions is discrete or can be reduced to one.

• - Infinite-dimensional optimization: studies the case where the set of feasible solutions is a subset of a space of infinite dimension, for example a space of functions.

• - Heuristics&action=edit&redlink=1 "Heuristics (computer science) (not yet written)") and Metaheuristics: make assumptions about the problem being optimized. Usually, heuristics do not guarantee that any optimal solution will be found. Heuristics are then used to find approximate solutions to many complicated optimization problems.

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

• - Disjunctive programming: used when at least one constraint can be satisfied but not all. This is of particular use in programming in a number of subfields. The techniques are primarily designed for optimization in dynamic contexts (i.e., decision making over time).

• - Calculation of variations: seeks to optimize a defined objective over many points over time, considering how the objective function changes if the change is small in the choice path. The optimal control technique is a generalization of this.

• - Dynamic programming studies the case in which the optimization strategy is based on dividing the problem into smaller subproblems. The equation that describes the relationship between these subproblems is called the Bellman equation.

• - Mathematical programming with equilibrium constraints is where the constraints include variable or complementary inequalities.

Feasibility of the problem

Problem solubility, also called problem feasibility, is the question of whether any feasible solution exists, regardless of its objective value. This can be considered the special case of mathematical optimization where the objective value is the same for every solution, and thus any solution is optimal.

Many optimization algorithms need to start from a feasible point. One way to obtain such a point is to relax the feasibility conditions using a slack variable; With enough slack, any starting point is feasible. Then, that slack variable is minimized until the slack is zero or negative.

Existence

The Weierstrass theorem states that a real and continuous function on a compact set reaches its maximum and minimum value. More generally, an inferior semi-continuous function on a compact set reaches its minimum; a superior semi-continuous function on a compact set reaches its maximum.

Necessary optimality conditions

One of Fermat's theorems ensures that the optima of unrestricted problems are found at stationary points, where the first derivative of the objective function is zero (or its null gradient). More generally, they can also be found at critical points where the first derivative or gradient of the objective function is not defined, or at the "Frontier (topology)" boundary of the choice set. An equation (or set of equations) indicating that the first derivative(s) is(are) equal to zero at an interior optimum is called a first-order condition or a set of first-order conditions.

The optima of problems with inequality constraints are instead found by the method of Lagrange multipliers. This method computes a system of inequalities called Karush–Kuhn–Tucker conditions or complementary slack conditions, which are then used to calculate the optimum.

Sufficient optimality conditions

While the first derivative test identifies points that may be extremes, this test does not distinguish whether a point is a minimum, a maximum, or neither. When the objective function is twice differentiable, these cases can be distinguished by studying the second derivative or the matrix of the second derivatives (called the Hessian matrix), in unrestricted problems, or the matrix of the second derivatives of the objective function and the restrictions called the bordered Hessian matrix, in restricted problems.

The conditions that distinguish maxima, or minima, from other stationary points are called second order conditions. If a solution candidate satisfies the first-order conditions and the second-order conditions as well, it is sufficient to establish, at least, local optimality.

Optimal sensitivity and continuity

The envelope theorem describes how the value of an optimal solution changes when an underlying parameter changes. The process that computes this change is called comparative statics.

Claude Berge's (1963) maximum theorem describes the continuity of an optimal solution as a function of underlying parameters.

Optimization calculations

For unrestricted problems with twice differentiable functions, some critical points "Critical point (mathematics)") can be found by detecting the points where the gradient of the objective function is zero (i.e., the stationary points). More generally, a zero subgradient certifies that a local minimum has been found for minimization problems with convex functions or other Lipschitz functions.

Furthermore, critical points can be classified using the definiteness of the Hessian matrix: if it is positive definite at a critical point, then the point is a local minimum; if it is negative definite, then the point is a local maximum; finally, if it is indefinite, then the point is some kind of saddle point.

Restricted problems can often be transformed into unrestricted problems with the help of Lagrange multipliers. Lagrangian relaxation can also provide approximate solutions to difficult constrained problems.

When the objective function is convex, then any local minimum will also be a global minimum. There are efficient numerical techniques to minimize convex functions, for example interior point methods.

Para resolver problemas, los investigadores pueden usar algoritmos que terminen en un número finito de pasos, o métodos iterativos que convergen a una solución (en alguna clase específica de problemas), o heurísticas que pueden proveer soluciones aproximadas a algunos problemas (aunque sus iteraciones no convergen necesariamente).

Optimization algorithms

• - George Dantzig's Simplex algorithm, designed for linear programming.

• - Extensions to the Simplex algorithm, designed for quadratic programming and linear-fractional programming.

• - Variants of the Simplex algorithm that are especially appropriate for network optimization.

• - Combinatorial algorithms.

Iterative methods

Iterative methods used to solve nonlinear programming problems differ depending on what they evaluate: Hessians, gradients, or just function values. While evaluating Hessians (H) and gradients (G) improves the speed of convergence, such evaluations increase the computational complexity (or computational cost) of each iteration. In some cases, the computational complexity may be excessively high.

An important criterion for optimizers is just the number of function evaluations required, as this is often in itself a large computational effort, usually much more effort than that of the optimizer itself, since it mostly has to operate on N variables. Derivatives provide detailed information for optimizers, but are even more expensive to compute, for example approximating the gradient takes at least N+1 function evaluations. For the approximation of the second derivatives (grouped in the Hessian matrix) the number of function evaluations is of order N². Newton's method requires second-order derivatives, so for each iteration the number of function calls is of order N², but for the simplest pure gradient optimizer it is of order N. However, gradient optimizers usually need more iterations than Newton's algorithm. Being better about the number of function calls depends on the problem itself.

• - Methods that evaluate Hessians (or approximate Hessians, using finite differences):

• Newton's method.

• Quadratic sequential programming: a Newton method based on restricted small-medium scale problems. Some versions can handle high-dimensional problems.

• - Methods that evaluate gradients or approximate gradients using finite differences (or even subgradients):

• Quasi-Newton methods: iterative methods for medium-large problems (example N<1000).

• Conjugate gradient methods: iterative methods for large problems. (In theory, these methods terminate in a finite number of steps with quadratic objective functions, but this finite termination is not observed in practice on finite-precision computers.)

• Interior Point Methods: This is a great class of methods for constrained optimization. Some interior point methods use only subgradient information, and others require evaluation of Hessians.

• Gradient descent (alternatively, steep descent or steep ascent): a slow method of theoretical and historical interest, which has been renewed to find approximate solutions to enormous problems.

• Subgradient method: an iterative method for locally large Lipschitz functions using generalized gradients.

• - Methods that evaluate only function values: if a problem is continuously differentiable, then the gradients can be approximated using finite differences, in which case a gradient-based method can be used.

• Interpolation methods.

• Pattern search methods, which have better convergence properties than the Nelder-Mead heuristic.

Generally, if the objective function is not a quadratic function, then many optimization methods use other methods to ensure that some subsequence of iterations converges to an optimal solution. The first popular method that guarantees convergence is based on linear searches, which optimizes a function in one dimension. A second and popularized method to ensure convergence uses trust regions. Both linear searches and confidence regions are used in modern nondifferentiable optimization methods. Usually a global optimizer is much slower than advanced local optimizers (e.g. BFGS), so often an efficient global optimizer can be built by starting the local optimizer from different starting points.

Heuristics

In addition to algorithms (finite completion) and iterative methods (convergent), there are heuristics that can provide approximate solutions to some optimization problems:

• - Differential evolution.

• - Differential search algorithm.

• - Dynamic Relaxation.

• - Genetic algorithms.

• - Climbing mountains.

• - Nelder-Mead: a popular heuristic for approximating minimization (without calls to gradients).

• - Particle swarm optimization.

• - Artificial optimization of the bee colony.

• - Multi-objective optimization.

• - Pareto efficiency.

• - Lagrange multipliers.

• - Bayesian optimization.

• - COIN-OR—Computational Infrastructure for Operations Research.

• - Decision Tree for Optimization Software Links to optimization source codes.

• - Global optimization Archived December 28, 2008 at the Wayback Machine.

• - Mathematical Programming Glossary.

• - Mathematical Programming Society.

• - NEOS Wikicurrently being replaced by theArchived August 22, 2002 at the Wayback Machine.

• - Optimization Online A repository for optimization e-prints.

• - Optimization Related Links.

• - Convex Optimization I EE364a: Course from Stanford University.

• - Convex Optimization – Boyd and Vandenberghe Book on Convex Optimization.

Contenido

Los problemas de optimización se expresan a menudo con una notación especial. A continuación se muestran algunos ejemplos.

Minimum and Maximum value of a function

Consider the following notation:

This denotes the minimum "Magnitude (mathematical)") value of the objective function, when x is selected from the set of real numbers. The minimum value in this case is and occurs for .

Similarly, the notation.

expresses the maximum value of the objective function 2x, where x is any real number. In this case, there is no such maximum, therefore there is no bounded optimal value.

Arguments for optimal entry

Consider the following expression:

or equivalently.

This represents the value (or values) of the argument "Argument (complex analysis)") of x in the interval "Interval (mathematics)") that minimize (or maximize) the objective function x + 1 (and not the minimum value that the objective function reaches for those values). In this case, the answer is x = -1, since x = 0 is not feasible, that is, it does not belong to the problem domain.

Similarly,

which equivalent to.

represents the pair (or pairs) (x,y) that minimize (or maximize) the value of the objective function xcos(y), with the added constraint that x lies in the interval [-5,5] (again, the minimum value of the function does not matter). In this case, the solutions are the pairs of the form (5, 2kπ) and (−5,(2k+1)π), where k runs through all the integers.

Arg min and arg max are sometimes written as argmin and argmax, meaning minimum argument and maximum argument.

Pierre de Fermat and Joseph Louis Lagrange found calculus-based formulas to identify optimal values, while Isaac Newton and Carl Friedrich Gauss proposed iterative methods to approximate the optimum. Historically, the term linear programming to refer to certain optimization problems is due to George B. Dantzig, although much of the theory had been introduced by Leonid Kantorovich in 1939. Dantzig published the Simplex Algorithm in 1947 and John von Neumann developed the theory of duality "Duality (mathematics)") in the same year.

The term programming in this context does not refer to computer programming. Rather, the term comes from the use of program by the United States military when referring to the training and logistics planning proposal, which was the problem studied by Dantzig at the time.

Other important researchers in the field of mathematical optimization were the following:

• - Convex programming studies the case in which the objective function is convex (minimization) or concave (maximization) and the set of constraints is convex. This can be seen as a particular case of nonlinear programming or as the generalization of linear or convex quadratic programming.

• Linear programming (LP): is a type of convex programming, in which the objective function f is linear and the set of constraints is specified using only linear equations and inequalities. This set is called a polyhedron or polytope if it is bounded.

• Conic programming: it is a general form of convex programming. PL, PCSO and PSD can all be viewed as conical programs with the appropriate cone type.

• Second-order cone programming (PCSO): It is a type of convex programming and includes certain types of quadratic programming problems.

• Semi-definite programming (PSD): is a subfield of convex optimization where the fundamental variables are semi-definite "Matrix (mathematics)" matrices. It is a generalization of linear programming and convex quadratic programming.

• Geometric programming: it is a technique by which the objective and inequality constraints expressed as polynomials and equality constraints as monomials can be transformed into a convex program.

• Programming with integers or Integer programming: studies linear programs in which some or all of the variables are forced to take integer values. This is non-convex and is generally much more complex than regular linear programming.

• - Quadratic programming: allows the objective function to have quadratic terms, while the feasible set can be specified with linear equations and inequalities. For specific forms of the quadratic term, this is a type of convex programming.

• - Fractional programming: studies the optimization of ratios of two nonlinear functions. The special class of concave fractional programs can be transformed to a convex optimization problem.

• - Nonlinear programming: studies the general case in which the objective function, or the constraints, or both, contain nonlinear parts. This may or may not be a convex program. In general, whether the program is convex affects the difficulty of solving.

• - Stochastic programming or Stochastic optimization: studies the case in which some of the constraints or parameters depend on random variables.

• - Robust programming: like stochastic programming, it is an attempt to capture uncertainty in the fundamental data of the optimization problem. This is done by using random variables, but instead, the problem is solved by taking into account inaccuracies in the input data.

• - Combinatorial optimization: is concerned with problems where the set of feasible solutions is discrete or can be reduced to one.

• - Infinite-dimensional optimization: studies the case where the set of feasible solutions is a subset of a space of infinite dimension, for example a space of functions.

• - Heuristics&action=edit&redlink=1 "Heuristics (computer science) (not yet written)") and Metaheuristics: make assumptions about the problem being optimized. Usually, heuristics do not guarantee that any optimal solution will be found. Heuristics are then used to find approximate solutions to many complicated optimization problems.

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

• - Disjunctive programming: used when at least one constraint can be satisfied but not all. This is of particular use in programming in a number of subfields. The techniques are primarily designed for optimization in dynamic contexts (i.e., decision making over time).

• - Calculation of variations: seeks to optimize a defined objective over many points over time, considering how the objective function changes if the change is small in the choice path. The optimal control technique is a generalization of this.

• - Dynamic programming studies the case in which the optimization strategy is based on dividing the problem into smaller subproblems. The equation that describes the relationship between these subproblems is called the Bellman equation.

• - Mathematical programming with equilibrium constraints is where the constraints include variable or complementary inequalities.

Feasibility of the problem

Problem solubility, also called problem feasibility, is the question of whether any feasible solution exists, regardless of its objective value. This can be considered the special case of mathematical optimization where the objective value is the same for every solution, and thus any solution is optimal.

Many optimization algorithms need to start from a feasible point. One way to obtain such a point is to relax the feasibility conditions using a slack variable; With enough slack, any starting point is feasible. Then, that slack variable is minimized until the slack is zero or negative.

Existence

The Weierstrass theorem states that a real and continuous function on a compact set reaches its maximum and minimum value. More generally, an inferior semi-continuous function on a compact set reaches its minimum; a superior semi-continuous function on a compact set reaches its maximum.

Necessary optimality conditions

One of Fermat's theorems ensures that the optima of unrestricted problems are found at stationary points, where the first derivative of the objective function is zero (or its null gradient). More generally, they can also be found at critical points where the first derivative or gradient of the objective function is not defined, or at the "Frontier (topology)" boundary of the choice set. An equation (or set of equations) indicating that the first derivative(s) is(are) equal to zero at an interior optimum is called a first-order condition or a set of first-order conditions.

The optima of problems with inequality constraints are instead found by the method of Lagrange multipliers. This method computes a system of inequalities called Karush–Kuhn–Tucker conditions or complementary slack conditions, which are then used to calculate the optimum.

Sufficient optimality conditions

While the first derivative test identifies points that may be extremes, this test does not distinguish whether a point is a minimum, a maximum, or neither. When the objective function is twice differentiable, these cases can be distinguished by studying the second derivative or the matrix of the second derivatives (called the Hessian matrix), in unrestricted problems, or the matrix of the second derivatives of the objective function and the restrictions called the bordered Hessian matrix, in restricted problems.

The conditions that distinguish maxima, or minima, from other stationary points are called second order conditions. If a solution candidate satisfies the first-order conditions and the second-order conditions as well, it is sufficient to establish, at least, local optimality.

Optimal sensitivity and continuity

The envelope theorem describes how the value of an optimal solution changes when an underlying parameter changes. The process that computes this change is called comparative statics.

Claude Berge's (1963) maximum theorem describes the continuity of an optimal solution as a function of underlying parameters.

Optimization calculations

For unrestricted problems with twice differentiable functions, some critical points "Critical point (mathematics)") can be found by detecting the points where the gradient of the objective function is zero (i.e., the stationary points). More generally, a zero subgradient certifies that a local minimum has been found for minimization problems with convex functions or other Lipschitz functions.

Furthermore, critical points can be classified using the definiteness of the Hessian matrix: if it is positive definite at a critical point, then the point is a local minimum; if it is negative definite, then the point is a local maximum; finally, if it is indefinite, then the point is some kind of saddle point.

Restricted problems can often be transformed into unrestricted problems with the help of Lagrange multipliers. Lagrangian relaxation can also provide approximate solutions to difficult constrained problems.

When the objective function is convex, then any local minimum will also be a global minimum. There are efficient numerical techniques to minimize convex functions, for example interior point methods.

Para resolver problemas, los investigadores pueden usar algoritmos que terminen en un número finito de pasos, o métodos iterativos que convergen a una solución (en alguna clase específica de problemas), o heurísticas que pueden proveer soluciones aproximadas a algunos problemas (aunque sus iteraciones no convergen necesariamente).

Optimization algorithms

• - George Dantzig's Simplex algorithm, designed for linear programming.

• - Extensions to the Simplex algorithm, designed for quadratic programming and linear-fractional programming.

• - Variants of the Simplex algorithm that are especially appropriate for network optimization.

• - Combinatorial algorithms.

Iterative methods

Iterative methods used to solve nonlinear programming problems differ depending on what they evaluate: Hessians, gradients, or just function values. While evaluating Hessians (H) and gradients (G) improves the speed of convergence, such evaluations increase the computational complexity (or computational cost) of each iteration. In some cases, the computational complexity may be excessively high.

An important criterion for optimizers is just the number of function evaluations required, as this is often in itself a large computational effort, usually much more effort than that of the optimizer itself, since it mostly has to operate on N variables. Derivatives provide detailed information for optimizers, but are even more expensive to compute, for example approximating the gradient takes at least N+1 function evaluations. For the approximation of the second derivatives (grouped in the Hessian matrix) the number of function evaluations is of order N². Newton's method requires second-order derivatives, so for each iteration the number of function calls is of order N², but for the simplest pure gradient optimizer it is of order N. However, gradient optimizers usually need more iterations than Newton's algorithm. Being better about the number of function calls depends on the problem itself.

• - Methods that evaluate Hessians (or approximate Hessians, using finite differences):

• Newton's method.

• Quadratic sequential programming: a Newton method based on restricted small-medium scale problems. Some versions can handle high-dimensional problems.

• - Methods that evaluate gradients or approximate gradients using finite differences (or even subgradients):

• Quasi-Newton methods: iterative methods for medium-large problems (example N<1000).

• Conjugate gradient methods: iterative methods for large problems. (In theory, these methods terminate in a finite number of steps with quadratic objective functions, but this finite termination is not observed in practice on finite-precision computers.)

• Interior Point Methods: This is a great class of methods for constrained optimization. Some interior point methods use only subgradient information, and others require evaluation of Hessians.

• Gradient descent (alternatively, steep descent or steep ascent): a slow method of theoretical and historical interest, which has been renewed to find approximate solutions to enormous problems.

• Subgradient method: an iterative method for locally large Lipschitz functions using generalized gradients.

• - Methods that evaluate only function values: if a problem is continuously differentiable, then the gradients can be approximated using finite differences, in which case a gradient-based method can be used.

• Interpolation methods.

• Pattern search methods, which have better convergence properties than the Nelder-Mead heuristic.

Generally, if the objective function is not a quadratic function, then many optimization methods use other methods to ensure that some subsequence of iterations converges to an optimal solution. The first popular method that guarantees convergence is based on linear searches, which optimizes a function in one dimension. A second and popularized method to ensure convergence uses trust regions. Both linear searches and confidence regions are used in modern nondifferentiable optimization methods. Usually a global optimizer is much slower than advanced local optimizers (e.g. BFGS), so often an efficient global optimizer can be built by starting the local optimizer from different starting points.

Heuristics

In addition to algorithms (finite completion) and iterative methods (convergent), there are heuristics that can provide approximate solutions to some optimization problems:

• - Differential evolution.

• - Differential search algorithm.

• - Dynamic Relaxation.

• - Genetic algorithms.

• - Climbing mountains.

• - Nelder-Mead: a popular heuristic for approximating minimization (without calls to gradients).

• - Particle swarm optimization.

• - Artificial optimization of the bee colony.

• - Multi-objective optimization.

• - Pareto efficiency.

• - Lagrange multipliers.

• - Bayesian optimization.

• - COIN-OR—Computational Infrastructure for Operations Research.

• - Decision Tree for Optimization Software Links to optimization source codes.

• - Global optimization Archived December 28, 2008 at the Wayback Machine.

• - Mathematical Programming Glossary.

• - Mathematical Programming Society.

• - NEOS Wikicurrently being replaced by theArchived August 22, 2002 at the Wayback Machine.

• - Optimization Online A repository for optimization e-prints.

• - Optimization Related Links.

• - Convex Optimization I EE364a: Course from Stanford University.

• - Convex Optimization – Boyd and Vandenberghe Book on Convex Optimization.