Interior-point method

An optimization algorithm that approaches an optimum through the interior of a feasible region, often using barrier functions or primal-dual equations to avoid crossing its boundary.

Logarithmic barrier method: An optimization method that adds a logarithmic penalty near inequality boundaries to keep iterates inside the feasible region. Its barrier term is a classic mechanism for steering interior-point iterates away from constraints.
Convex optimization: Optimization of a convex objective over a convex feasible set, where local minima are global minima. The strongest general guarantees for interior-point algorithms are established in convex optimization.
Simplex algorithm: A linear-programming algorithm that moves between vertices of the feasible polytope. Unlike interior-point methods, it follows the boundary from one vertex to another.
Second-order cone programming: Optimization of a linear objective over affine constraints and second-order cone constraints. Primal-dual interior-point algorithms handle its cone constraints through structured Newton systems.
Narendra Karmarkar: An Indian mathematician who introduced a polynomial-time interior-point algorithm for linear programming in 1984. His algorithm brought interior-point methods to prominence as a polynomial-time alternative to simplex.
Primal-dual method: An algorithmic approach that updates primal variables and dual variables together to solve constrained optimization problems. Primal-dual interior-point algorithms advance both sides of the optimality conditions in one iteration.
Linear programming: Optimization of a linear objective subject to linear equality and inequality constraints. Interior-point methods became a major alternative to the simplex method for linear programs.
Projected gradient method: An iterative optimization method that takes a gradient step and projects the result onto the feasible set. Projection enforces feasibility directly, whereas interior-point methods typically encode boundaries with barriers or equations.
Semidefinite programming: Optimization with constraints requiring symmetric matrix variables to be positive semidefinite. Interior-point methods made many semidefinite programs computationally tractable.
Karmarkar's algorithm: A 1984 projective algorithm for linear programming with a polynomial-time complexity bound. It was the landmark interior-point method that sparked renewed research into the approach.

Linked from 9 pages