Mixed linear complementarity problem

Last updated

In mathematical optimization theory, the mixed linear complementarity problem, often abbreviated as MLCP or LMCP, is a generalization of the linear complementarity problem to include free variables.

Related Research Articles

Quadratic programming (QP) is the process of solving certain mathematical optimization problems involving quadratic functions. Specifically, one seeks to optimize a multivariate quadratic function subject to linear constraints on the variables. Quadratic programming is a type of nonlinear programming.

Linear programming Method to solve some optimization problems

Linear programming is a method to achieve the best outcome in a mathematical model whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming.

Mathematical optimization Study of mathematical algorithms for optimization problems

Mathematical optimization or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. 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.

Time complexity Estimate of time taken for running an algorithm

In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor.

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.

Interior-point method Algorithms for solving convex optimization problems

Interior-point methods are a certain class of algorithms that solve linear and nonlinear convex optimization problems.

In mathematics, a P-matrix is a complex square matrix with every principal minor > 0. A closely related class is that of -matrices, which are the closure of the class of P-matrices, with every principal minor 0.

The TOMLAB Optimization Environment is a modeling platform for solving applied optimization problems in MATLAB.

A complementarity problem is a type of mathematical optimization problem. It is the problem of optimizing a function of two vector variables subject to certain requirements (constraints) which include: that the inner product of the two vectors must equal zero, i.e. they are orthogonal. In particular for finite-dimensional real vector spaces this means that, if one has vectors X and Y with all nonnegative components, then for each pair of components xi and yi one of the pair must be zero, hence the name complementarity. e.g. X = (1, 0) and Y = (0, 2) are complementary, but X = (1, 1) and Y = (2, 0) are not. A complementarity problem is a special case of a variational inequality.

In mathematics, a unique sink orientation is an orientation of the edges of a polytope such that, in every face of the polytope, there is exactly one vertex for which all adjoining edges are oriented inward. If a polytope is given together with a linear objective function, and edges are oriented from vertices with smaller objective function values to vertices with larger objective values, the result is a unique sink orientation. Thus, unique sink orientations can be used to model linear programs as well as certain nonlinear programs such as the smallest circle problem.

In mathematical optimization, Lemke's algorithm is a procedure for solving linear complementarity problems, and more generally mixed linear complementarity problems. It is named after Carlton E. Lemke.

Paul Tseng Chinese-American mathematician

Paul Tseng was a Chinese-American and Canadian applied mathematician and a professor at the Department of Mathematics at the University of Washington, in Seattle, Washington. Tseng was recognized by his peers to be one of the leading optimization researchers of his generation. On August 13, 2009, Paul Tseng went missing while kayaking in the Yangtze River in the Yunnan province of China and is presumed dead.

In applied mathematics, a nonlinear complementarity problem (NCP) with respect to a mapping ƒ : Rn → Rn, denoted by NCPƒ, is to find a vector x ∈ Rn such that

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.

Siconos Open source scientific software for modeling non-smooth dynamical systems

SICONOS is an Open Source scientific software primarily targeted at modeling and simulating non-smooth dynamical systems (NSDS):

In the study of algorithms, an LP-type problem is an optimization problem that shares certain properties with low-dimensional linear programs and that may be solved by similar algorithms. LP-type problems include many important optimization problems that are not themselves linear programs, such as the problem of finding the smallest circle containing a given set of planar points. They may be solved by a combination of randomized algorithms in an amount of time that is linear in the number of elements defining the problem, and subexponential in the dimension of the problem.

Artelys Knitro is a commercial software package for solving large scale nonlinear mathematical optimization problems.

Algebraic modeling languages like AIMMS, AMPL, GAMS, MPL and others have been developed to facilitate the description of a problem in mathematical terms and to link the abstract formulation with data-management systems on the one hand and appropriate algorithms for solution on the other. Robust algorithms and modeling language interfaces have been developed for a large variety of mathematical programming problems such as linear programs (LPs), nonlinear programs (NPs), Mixed Integer Programs (MIPs), mixed complementarity programs (MCPs) and others. Researchers are constantly updating the types of problems and algorithms that they wish to use to model in specific domain applications.

Richard W. Cottle

Richard W. Cottle is an American mathematician. He was a professor of Management Science and Engineering at Stanford University, starting as an Acting Assistant Professor of Industrial Engineering in 1966 and retiring in 2005. He is notable for his work on mathematical programming/optimization, “Nonlinear programs”, the proposal of the linear complementarity problem, and the general field of operations research.

References