Mathematical optimization
Mathematical optimization (also spelled optimisation, and historically called mathematical programming) is the branch of applied mathematics and operations research concerned with selecting a best element, according to some criterion, from a set of available alternatives.[1] In its standard form, an optimization problem seeks values of one or more decision variables that minimize or maximize a scalar objective function while satisfying a collection of constraints that together delimit a feasible region; a point that lies in this region and attains the best objective value is an optimal solution.[2] The field supplies both the modeling language used to state such problems and the algorithms used to solve them, and it underlies decision problems across engineering, economics, machine learning, and workforce planning.[1]
Formal statement
A general optimization problem is written as minimizing an objective function over a decision vector subject to inequality constraints and equality constraints .[1] Because maximizing is equivalent to minimizing , minimization is taken as the canonical form without loss of generality.[2] The set of points satisfying every constraint is the feasible region; a problem whose feasible region is empty is called infeasible, while one whose objective can be improved without bound is called unbounded.[2]
A distinction is drawn between a global optimum, which is best over the entire feasible region, and a local optimum, which is best only within some neighborhood.[2] Optimality conditions characterize candidate solutions: for constrained differentiable problems, the Karush–Kuhn–Tucker (KKT) conditions generalize the method of Lagrange multipliers and, together with constraint qualifications, provide necessary conditions for a point to be optimal.[1]
Convex versus non-convex problems
A central dividing line in the field is whether a problem is convex. A problem is convex when its objective is a convex function and its feasible region is a convex set; for such problems every local optimum is also a global optimum, which makes them tractable both in theory and in practice.[1] Convex problems admit efficient interior-point and other polynomial-time methods and enjoy a well-developed duality theory that yields certificates of optimality.[1] By contrast, non-convex problems may possess many local optima that are not globally optimal, and finding a global optimum is in general computationally hard; practical algorithms often return only locally optimal or approximate solutions.[2]
Problem classes
Optimization problems are commonly grouped by the structure of their objective and constraints.[2]
Linear programming
In linear programming (LP) the objective and all constraints are linear functions of the decision variables, so the feasible region is a convex polyhedron.[3] The simplex method, introduced by George Dantzig, moves along the vertices of this polyhedron and remains among the most widely used algorithms for LP; interior-point methods traverse the interior of the feasible region instead.[3] Karmarkar's projective interior-point algorithm established that linear programs can be solved in polynomial time by a practical method, running in a bounded number of arithmetic operations in the problem size.[4]
Nonlinear programming
Nonlinear programming (NLP) covers problems in which the objective or some constraint is a nonlinear function.[2] Solution methods include gradient descent, Newton and quasi-Newton methods such as BFGS, and, for constrained problems, sequential quadratic programming and interior-point methods.[2] These methods typically guarantee convergence only to a point satisfying first-order optimality conditions rather than to a global optimum, except when additional structure such as convexity is present.[2]
Integer and combinatorial optimization
When some or all decision variables are restricted to integer values, the problem is an integer program (or mixed-integer program when only some variables are integer); such problems capture indivisible or logical decisions and are generally NP-hard.[5] Standard exact approaches include branch-and-bound, cutting-plane methods, and their combination in branch-and-cut, which rely on solving continuous relaxations to bound the integer optimum.[5]
Duality
Associated with a given ("primal") optimization problem is a dual problem, constructed from the Lagrangian, whose optimal value bounds that of the primal.[1] Weak duality states that the dual objective is always a bound on the primal optimum, and for convex problems satisfying a constraint qualification strong duality holds, meaning the two optimal values coincide; the resulting dual solution serves as a certificate that a primal solution is optimal.[1]
Applications in workforce management
Mathematical optimization provides the general frame for workforce management problems in contact centers, where staffing and scheduling are posed as the minimization of labor cost subject to service-level and coverage constraints. In a typical formulation the decision variables represent the number of agents assigned to each shift or interval, the objective is total staffing cost, and constraints require that forecast demand and a target service level be met in every interval. Because shift and headcount decisions are indivisible, these are naturally modeled as integer or mixed-integer programs, a class for which relaxation-based methods such as branch-and-bound are standard.[5] The nonlinear relationship between staffing and service level supplied by queueing analysis can be incorporated as constraints, linking optimization to the broader operations-research toolkit.[2]
See also
- Stochastic optimization
- Portfolio optimization
- Pareto efficiency
- Scalarization
- Hyperparameter optimization
- Monte Carlo method
References
- ↑ 1.0 1.1 1.2 1.3 1.4 1.5 1.6 1.7 Boyd, S., Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press. ISBN 978-0-521-83378-3.
- ↑ 2.00 2.01 2.02 2.03 2.04 2.05 2.06 2.07 2.08 2.09 Nocedal, J., Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer Series in Operations Research and Financial Engineering. Springer. ISBN 978-0-387-30303-1.
- ↑ 3.0 3.1 Bertsimas, D., Tsitsiklis, J. N. (1997). Introduction to Linear Optimization. Athena Scientific. ISBN 978-1-886529-19-9.
- ↑ Karmarkar, N. (1984). "A new polynomial-time algorithm for linear programming". Combinatorica 4 (4), 373–395. doi:10.1007/BF02579150.
- ↑ 5.0 5.1 5.2 Nemhauser, G. L., Wolsey, L. A. (1988). Integer and Combinatorial Optimization. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley. ISBN 978-0-471-82819-8.
