|
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-matrix ... [...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 criterion, from some set of available alternatives. It is generally divided into two subfields: discrete optimization and continuous optimization. Optimization problems of sorts 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 maximizing or minimizing a real function by systematically choosing input values from within an allowed set and computing the value of the function. The generalization of optimization theory and techniques to other formulations constitutes a large area of applied mathematics. More generally, optimization includes finding "best available" values of some objective function given a define ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Interior Point Method
Interior-point methods (also referred to as barrier methods or IPMs) are a certain class of algorithms that solve linear and nonlinear convex optimization problems. An interior point method was discovered by Soviet mathematician I. I. Dikin in 1967 and reinvented in the U.S. in the mid-1980s. In 1984, Narendra Karmarkar developed a method for linear programming called Karmarkar's algorithm, which runs in provably polynomial time and is also very efficient in practice. It enabled solutions of linear programming problems that were beyond the capabilities of the simplex method. Contrary to the simplex method, it reaches a best solution by traversing the interior of the feasible region. The method can be generalized to convex programming based on a self-concordant barrier function used to encode the convex set. Any convex optimization problem can be transformed into minimizing (or maximizing) a linear function over a convex set by converting to the epigraph form. The idea of encodi ... [...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 regulari ... [...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, such as rigid body dynamics (including collision detection), soft body dynamics, and fluid dynamics, 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 accuracy to compute in time for the game to respon ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Oriented Matroid
An oriented matroid is a mathematics, mathematical mathematical structure, structure that abstracts the properties of directed graphs, Vector space, vector arrangements over ordered fields, and Arrangement of hyperplanes, hyperplane arrangements over ordered fields. In comparison, an ordinary (i.e., non-oriented) matroid abstracts the linear independence, dependence properties that are common both to Graph (discrete mathematics), graphs, which are not necessarily ''directed'', and to arrangements of vectors over field (mathematics), 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 conversion (logic), 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 usefu ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Principal minor
In linear algebra, a minor of a matrix A is the determinant of some smaller square matrix, cut down from A 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 in turn are useful for computing both the determinant and inverse of square matrices. Definition and illustration First minors If A is a square matrix, then the ''minor'' of the entry in the ''i''th row and ''j''th column (also called the (''i'', ''j'') ''minor'', or a ''first minor'') is the determinant of the submatrix formed by deleting the ''i''th row and ''j''th column. This number is often denoted ''M''''i,j''. The (''i'', ''j'') ''cofactor'' is obtained by multiplying the minor by (-1)^. To illustrate these definitions, consider the following 3 by 3 matrix, :\begin 1 & 4 & 7 \\ 3 & 0 & 5 \\ -1 & 9 & 11 \\ \end To compute the minor ''M''2,3 and the cofactor ''C''2,3, we fin ... [...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 z^\textsfMz is positive for every nonzero real column vector z, where z^\textsf is the transpose of More generally, a Hermitian matrix (that is, a complex matrix equal to its conjugate transpose) is positive-definite if the real number z^* Mz is positive for every nonzero complex column vector z, where z^* denotes the conjugate transpose of z. Positive semi-definite matrices are defined similarly, except that the scalars z^\textsfMz and z^* Mz 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. A matrix is thus positive-definite if and only if it is the matrix of a positive-definite quadratic form or Hermitian form. In other words, a matrix is positive-definite if and only if it defines a ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Criss-cross Algorithm
In 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 inequality constraints and nonlinear objective functions; there are criss-cross algorithms for linear-fractional programming problems, quadratic-programming problems, and linear complementarity problems. Like the simplex algorithm of George B. Dantzig, the criss-cross algorithm is not a polynomial-time algorithm for linear programming. Both algorithms visit all 2''D'' corners of a (perturbed) cube in dimension ''D'', the Klee–Minty cube (after Victor Klee and George J. Minty), in the worst case. However, when it is started at a random corner, the criss-cross algorithm on average visits only ''D'' additional corners.The simplex algorithm takes on average ''D'' steps for a cube. : Thus, for the three-dimensional cube, the algorithm visits all 8 c ... [...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 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 optim ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
