Combinatorial optimizationCombinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combinatorial optimization problems are the travelling salesman problem ("TSP"), the minimum spanning tree problem ("MST"), and the knapsack problem. In many such problems, such as the ones previously mentioned, exhaustive search is not tractable, and so specialized algorithms that quickly rule out large parts of the search space or approximation algorithms must be resorted to instead.
Optimization problemIn mathematics, computer science and economics, an optimization problem is the problem of finding the best solution from all feasible solutions. Optimization problems can be divided into two categories, depending on whether the variables are continuous or discrete: An optimization problem with discrete variables is known as a discrete optimization, in which an object such as an integer, permutation or graph must be found from a countable set.
Mathematical optimizationMathematical optimization (alternatively spelled optimisation) or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfields: discrete optimization and continuous optimization. Optimization problems arise in all quantitative disciplines from computer science and engineering to operations research and economics, and the development of solution methods has been of interest in mathematics for centuries.
Elasticity (physics)In physics and materials science, elasticity is the ability of a body to resist a distorting influence and to return to its original size and shape when that influence or force is removed. Solid objects will deform when adequate loads are applied to them; if the material is elastic, the object will return to its initial shape and size after removal. This is in contrast to plasticity, in which the object fails to do so and instead remains in its deformed state. The physical reasons for elastic behavior can be quite different for different materials.
Convex optimizationConvex optimization is a subfield of mathematical optimization that studies the problem of minimizing convex functions over convex sets (or, equivalently, maximizing concave functions over convex sets). Many classes of convex optimization problems admit polynomial-time algorithms, whereas mathematical optimization is in general NP-hard.
Elastic energyElastic energy is the mechanical potential energy stored in the configuration of a material or physical system as it is subjected to elastic deformation by work performed upon it. Elastic energy occurs when objects are impermanently compressed, stretched or generally deformed in any manner. Elasticity theory primarily develops formalisms for the mechanics of solid bodies and materials. (Note however, the work done by a stretched rubber band is not an example of elastic energy. It is an example of entropic elasticity.
Lagrangian mechanicsIn physics, Lagrangian mechanics is a formulation of classical mechanics founded on the stationary-action principle (also known as the principle of least action). It was introduced by the Italian-French mathematician and astronomer Joseph-Louis Lagrange in his 1788 work, Mécanique analytique. Lagrangian mechanics describes a mechanical system as a pair consisting of a configuration space and a smooth function within that space called a Lagrangian. For many systems, where and are the kinetic and potential energy of the system, respectively.
Constrained optimizationIn mathematical optimization, constrained optimization (in some contexts called constraint optimization) is the process of optimizing an objective function with respect to some variables in the presence of constraints on those variables. The objective function is either a cost function or energy function, which is to be minimized, or a reward function or utility function, which is to be maximized.
Duality (optimization)In mathematical optimization theory, duality or the duality principle is the principle that optimization problems may be viewed from either of two perspectives, the primal problem or the dual problem. If the primal is a minimization problem then the dual is a maximization problem (and vice versa). Any feasible solution to the primal (minimization) problem is at least as large as any feasible solution to the dual (maximization) problem.
Symplectic vector spaceIn mathematics, a symplectic vector space is a vector space V over a field F (for example the real numbers R) equipped with a symplectic bilinear form. A symplectic bilinear form is a mapping ω : V × V → F that is Bilinear Linear in each argument separately; Alternating ω(v, v) = 0 holds for all v ∈ V; and Non-degenerate ω(u, v) = 0 for all v ∈ V implies that u = 0. If the underlying field has characteristic not 2, alternation is equivalent to skew-symmetry. If the characteristic is 2, the skew-symmetry is implied by, but does not imply alternation.
Canonical transformationIn Hamiltonian mechanics, a canonical transformation is a change of canonical coordinates (q, p, t) → (Q, P, t) that preserves the form of Hamilton's equations. This is sometimes known as form invariance. It need not preserve the form of the Hamiltonian itself. Canonical transformations are useful in their own right, and also form the basis for the Hamilton–Jacobi equations (a useful method for calculating conserved quantities) and Liouville's theorem (itself the basis for classical statistical mechanics).
Symplectic geometrySymplectic geometry is a branch of differential geometry and differential topology that studies symplectic manifolds; that is, differentiable manifolds equipped with a closed, nondegenerate 2-form. Symplectic geometry has its origins in the Hamiltonian formulation of classical mechanics where the phase space of certain classical systems takes on the structure of a symplectic manifold. The term "symplectic", introduced by Weyl, is a calque of "complex"; previously, the "symplectic group" had been called the "line complex group".
Joseph-Louis LagrangeJoseph-Louis Lagrange (born Giuseppe Luigi Lagrangia or Giuseppe Ludovico De la Grange Tournier; 25 January 1736 – 10 April 1813), also reported as Giuseppe Luigi Lagrange or Lagrangia, was an Italian mathematician, physicist and astronomer, later naturalized French. He made significant contributions to the fields of analysis, number theory, and both classical and celestial mechanics.
Symplectic manifoldIn differential geometry, a subject of mathematics, a symplectic manifold is a smooth manifold, , equipped with a closed nondegenerate differential 2-form , called the symplectic form. The study of symplectic manifolds is called symplectic geometry or symplectic topology. Symplectic manifolds arise naturally in abstract formulations of classical mechanics and analytical mechanics as the cotangent bundles of manifolds.
Symplectic matrixIn mathematics, a symplectic matrix is a matrix with real entries that satisfies the condition where denotes the transpose of and is a fixed nonsingular, skew-symmetric matrix. This definition can be extended to matrices with entries in other fields, such as the complex numbers, finite fields, p-adic numbers, and function fields. Typically is chosen to be the block matrix where is the identity matrix. The matrix has determinant and its inverse is .
Symplectic groupIn mathematics, the name symplectic group can refer to two different, but closely related, collections of mathematical groups, denoted Sp(2n, F) and Sp(n) for positive integer n and field F (usually C or R). The latter is called the compact symplectic group and is also denoted by . Many authors prefer slightly different notations, usually differing by factors of 2. The notation used here is consistent with the size of the most common matrices which represent the groups.
Linear elasticityLinear elasticity is a mathematical model of how solid objects deform and become internally stressed due to prescribed loading conditions. It is a simplification of the more general nonlinear theory of elasticity and a branch of continuum mechanics. The fundamental "linearizing" assumptions of linear elasticity are: infinitesimal strains or "small" deformations (or strains) and linear relationships between the components of stress and strain. In addition linear elasticity is valid only for stress states that do not produce yielding.
Tautological one-formIn mathematics, the tautological one-form is a special 1-form defined on the cotangent bundle of a manifold In physics, it is used to create a correspondence between the velocity of a point in a mechanical system and its momentum, thus providing a bridge between Lagrangian mechanics and Hamiltonian mechanics (on the manifold ). The exterior derivative of this form defines a symplectic form giving the structure of a symplectic manifold. The tautological one-form plays an important role in relating the formalism of Hamiltonian mechanics and Lagrangian mechanics.
Semidefinite programmingSemidefinite programming (SDP) is a subfield of convex optimization concerned with the optimization of a linear objective function (a user-specified function that the user wants to minimize or maximize) over the intersection of the cone of positive semidefinite matrices with an affine space, i.e., a spectrahedron. Semidefinite programming is a relatively new field of optimization which is of growing interest for several reasons. Many practical problems in operations research and combinatorial optimization can be modeled or approximated as semidefinite programming problems.
Poisson manifoldIn differential geometry, a field in mathematics, a Poisson manifold is a smooth manifold endowed with a Poisson structure. The notion of Poisson manifold generalises that of symplectic manifold, which in turn generalises the phase space from Hamiltonian mechanics. A Poisson structure (or Poisson bracket) on a smooth manifold is a functionon the vector space of smooth functions on , making it into a Lie algebra subject to a Leibniz rule (also known as a Poisson algebra).
