|
Linear Complementarity Problem
In mathematical optimization theory, the linear complementarity problem (LCP) arises frequently in computational mechanics and encompasses the well-known quadratic programming as a special case. It was proposed by Cottle and Dantzig in 1968. Formulation Given a real matrix ''M'' and vector ''q'', the linear complementarity problem LCP(''q'', ''M'') seeks vectors ''z'' and ''w'' which satisfy the following constraints: * w, z \geqslant 0, (that is, each component of these two vectors is non-negative) * z^Tw = 0 or equivalently \sum\nolimits_i w_i z_i = 0. This is the complementarity condition, since it implies that, for all i, at most one of w_i and z_i can be positive. * w = Mz + q A sufficient condition for existence and uniqueness of a solution to this problem is that ''M'' be symmetric positive-definite. If ''M'' is such that has a solution for every ''q'', then ''M'' is a Q-matrix. If ''M'' is such that have a unique solution for every ''q'', then ''M'' is a P ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Optimization (mathematics)
Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criteria, 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. In the more general approach, an optimization problem consists of maxima and minima, maximizing or minimizing a Function of a real variable, real function by systematically choosing Argument of a function, input values from within an allowed set and computing the Value (mathematics), value of the function. The generalization of optimization theory and techniques to other formulations constitutes a large area of applied mathematics. Optimization problems Opti ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Interior Point Method
Interior-point methods (also referred to as barrier methods or IPMs) are algorithms for solving Linear programming, linear and nonlinear programming, non-linear convex optimization problems. IPMs combine two advantages of previously-known algorithms: * Theoretically, their run-time is Polynomial time, polynomial—in contrast to the simplex method, which has exponential run-time in the worst case. * Practically, they run as fast as the simplex method—in contrast to the ellipsoid method, which has polynomial run-time in theory but is very slow in practice. In contrast to the simplex method which traverses the ''boundary'' of the feasible region, and the ellipsoid method which bounds the feasible region from ''outside'', an IPM reaches a best solution by traversing the ''interior'' of the feasible region—hence the name. History An interior point method was discovered by Soviet mathematician I. I. Dikin in 1967. The method was reinvented in the U.S. in the mid-1980s. In 1984, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Siconos
SICONOS is an open source scientific software primarily targeted at modeling and simulating non-smooth dynamical systems (NSDS): * Mechanical systems (Rigid body or solid) with Unilateral contact and Coulomb friction as we find in Non-smooth mechanics, Contact dynamics or Granular material. * Switched Electrical Circuit such as Power converter, Rectifier, Phase-locked loop (PLL) or Analog-to-digital converter * Sliding mode control systems Other applications are found in Systems and Control (hybrid systems, differential inclusions, optimal control with state constraints), Optimization ( Complementarity problem and Variational inequality) Biology Gene regulatory network, Fluid Mechanics and Computer graphics, etc. Components The software is based on 3 main components * Siconos/Numerics (C API). Collection of low-level algorithms for solving basic Algebra and optimization problems arising in the simulation of nonsmooth dynamical systems ** Linear complementarity problem (LCP) ** ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Bimatrix Game
In game theory, a bimatrix game is a simultaneous game for two players in which each player has a finite number of possible actions. The name comes from the fact that the normal form of such a game can be described by two matrices - matrix A describing the payoffs of player 1 and matrix B describing the payoffs of player 2. Player 1 is often called the "row player" and player 2 the "column player". If player 1 has m possible actions and player 2 has n possible actions, then each of the two matrices has m rows by n columns. When the row player selects the i-th action and the column player selects the j-th action, the payoff to the row player is A ,j/math> and the payoff to the column player is B ,j/math>. The players can also play mixed strategies. A mixed strategy for the row player is a non-negative vector x of length m such that: \sum_^m x_i = 1. Similarly, a mixed strategy for the column player is a non-negative vector y of length n such that: \sum_^n y_j = 1. When the players ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Contact Dynamics
Contact dynamics deals with the motion of multibody systems subjected to unilateral contacts and friction. Such systems are omnipresent in many multibody dynamics applications. Consider for example * Contacts between wheels and ground in vehicle dynamics * Squealing of brakes due to friction induced oscillations * Motion of many particles, spheres which fall in a funnel, mixing processes (granular media) * Clockworks * Walking machines * Arbitrary machines with limit stops, friction. *Anatomic tissues (skin, iris/lens, eyelids/anterior ocular surface, joint cartilages, vascular endothelium/blood cells, muscles/tendons, et cetera) In the following it is discussed how such mechanical systems with unilateral contacts and friction can be modeled and how the time evolution of such systems can be obtained by numerical integration. In addition, some examples are given. Modeling The two main approaches for modeling mechanical systems with unilateral contacts and friction are the regulariz ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Physics Engine
A physics engine is computer software that provides an approximate simulation of certain physical systems, typically classical dynamics, including rigid body dynamics (including collision detection), soft body dynamics, and fluid dynamics. It is of use in the domains of computer graphics, video games and film ( CGI). Their main uses are in video games (typically as middleware), in which case the simulations are in real-time. The term is sometimes used more generally to describe any software system for simulating physical phenomena, such as high-performance scientific simulation. Description There are generally two classes of physics engines: real-time and high-precision. High-precision physics engines require more processing power to calculate very precise physics and are usually used by scientists and computer-animated movies. Real-time physics engines—as used in video games and other forms of interactive computing—use simplified calculations and decreased accura ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Oriented Matroid
An oriented matroid is a mathematical structure that abstracts the properties of directed graphs, vector arrangements over ordered fields, and hyperplane arrangements over ordered fields. In comparison, an ordinary (i.e., non-oriented) matroid abstracts the dependence properties that are common both to graphs, which are not necessarily ''directed'', and to arrangements of vectors over fields, which are not necessarily ''ordered''. All oriented matroids have an underlying matroid. Thus, results on ordinary matroids can be applied to oriented matroids. However, the converse is false; some matroids cannot become an oriented matroid by ''orienting'' an underlying structure (e.g., circuits or independent sets). The distinction between matroids and oriented matroids is discussed further below. Matroids are often useful in areas such as dimension theory and algorithms. Because of an oriented matroid's inclusion of additional details about the ''oriented'' nature of a structure, its ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Principal minor
In linear algebra, a minor of a matrix is the determinant of some smaller square matrix generated from by removing one or more of its rows and columns. Minors obtained by removing just one row and one column from square matrices (first minors) are required for calculating matrix cofactors, which are useful for computing both the determinant and inverse of square matrices. The requirement that the square matrix be smaller than the original matrix is often omitted in the definition. Definition and illustration First minors If is a square matrix, then the ''minor'' of the entry in the -th row and -th column (also called the ''minor'', or a ''first minor'') is the determinant of the submatrix formed by deleting the -th row and -th column. This number is often denoted . The ''cofactor'' is obtained by multiplying the minor by . To illustrate these definitions, consider the following matrix, \begin 1 & 4 & 7 \\ 3 & 0 & 5 \\ -1 & 9 & 11 \\ \end To compute the minor and the c ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Positive-definite Matrix
In mathematics, a symmetric matrix M with real entries is positive-definite if the real number \mathbf^\mathsf M \mathbf is positive for every nonzero real column vector \mathbf, where \mathbf^\mathsf is the row vector transpose of \mathbf. More generally, a Hermitian matrix (that is, a complex matrix equal to its conjugate transpose) is positive-definite if the real number \mathbf^* M \mathbf is positive for every nonzero complex column vector \mathbf, where \mathbf^* denotes the conjugate transpose of \mathbf. Positive semi-definite matrices are defined similarly, except that the scalars \mathbf^\mathsf M \mathbf and \mathbf^* M \mathbf are required to be positive ''or zero'' (that is, nonnegative). Negative-definite and negative semi-definite matrices are defined analogously. A matrix that is not positive semi-definite and not negative semi-definite is sometimes called ''indefinite''. Some authors use more general definitions of definiteness, permitting the matrices to be ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Criss-cross Algorithm
In optimization (mathematics), mathematical optimization, the criss-cross algorithm is any of a family of algorithms for linear programming. Variants of the criss-cross algorithm also solve more general problems with linear programming, linear inequality constraints and nonlinear programming, nonlinear optimization (mathematics), objective functions; there are criss-cross algorithms for linear-fractional programming problems, quadratic programming, quadratic-programming problems, and linear complementarity problems. Like the simplex algorithm of George Dantzig, George B. Dantzig, the criss-cross algorithm is not a time complexity, polynomial-time algorithm for linear programming. Both algorithms visit all 2''D'' corners of a (perturbed) unit cube, cube in dimension ''D'', the Klee–Minty cube (after Victor Klee and George J. Minty), in the worst-case complexity, worst case. However, when it is started at a random corner, the criss-cross algorithm Average-case com ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Active Set
In mathematical optimization, the active-set method is an algorithm used to identify the active constraints in a set of inequality constraints. The active constraints are then expressed as equality constraints, thereby transforming an inequality-constrained problem into a simpler equality-constrained subproblem. An optimization problem is defined using an objective function to minimize or maximize, and a set of constraints : g_1(x) \ge 0, \dots, g_k(x) \ge 0 that define the feasible region, that is, the set of all ''x'' to search for the optimal solution. Given a point x in the feasible region, a constraint : g_i(x) \ge 0 is called active at x_0 if g_i(x_0) = 0, and inactive at x_0 if g_i(x_0) > 0. Equality constraints are always active. The active set at x_0 is made up of those constraints g_i(x_0) that are active at the current point . The active set is particularly important in optimization theory, as it determines which constraints will influence the final result of o ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
