Interior-point method

Common card · No. 382996

Interior-point methods (also referred to as barrier methods or IPMs) are algorithms for solving linear and non-linear convex optimization problems. IPMs combine two advantages of previously-known algorithms: Theoretically, their run-time is 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 active-set methods (such as 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.

Read on Wikipedia · Image Gjacquenot, CC BY-SA 4.0