an interior-point method
Suppose the allowed region of a problem is a fenced yard, and the best point lies somewhere on or near a fence. Older methods (like simplex) walk along the fences themselves, corner to corner. An interior-point method does the opposite: it stays strictly INSIDE the yard, well away from every fence, and gradually lets itself drift toward the boundary as it homes in on the optimum — as if repelled by an invisible force field at the walls that slowly weakens.
The trick is a BARRIER function. To enforce inequality constraints g_i(x) <= 0, you add a term that blows up to +infinity as any constraint is approached — the classic choice is the logarithmic barrier -sum log(-g_i(x)), which is finite strictly inside the region and explodes at the boundary. You then minimize f(x) + t * (barrier) for a parameter t, which keeps the iterate strictly feasible (interior). Solving this for a sequence of SHRINKING barrier weights traces out the 'central path', and as the barrier weight goes to zero the solution approaches the true constrained optimum, which may lie on the boundary. Each subproblem is solved by Newton's method, so an interior-point method is essentially Newton steps following the central path, repeatedly tightening toward the KKT conditions.
Interior-point methods revolutionized optimization in the 1980s-90s: they solve linear programs in provably POLYNOMIAL time (unlike simplex, whose worst case is exponential), and they extend gracefully to quadratic programs, second-order cone programs, and semidefinite programs — the whole modern convex-optimization toolkit. For large structured problems they are often the method of choice, taking a small, nearly constant number of Newton iterations almost regardless of problem size. The honest trade-offs: each Newton step solves a linear system that can be costly for huge dense problems, they need a strictly feasible interior starting point, and unlike simplex they do not naturally return an exact vertex solution or warm-start cheaply when a problem is modified slightly. For many problems simplex and interior-point are complementary, not rivals.
To minimize over x >= 0 you add the barrier -t * log(x), which is gentle far from x = 0 but soars toward +infinity as x nears zero, keeping every iterate strictly positive. Shrinking t from 1 to 0.1 to 0.01 lets the iterate slide toward the boundary x = 0 along the central path, reaching the constrained optimum in a handful of Newton steps.
A barrier repels the iterate from the boundary, then is slowly relaxed.
Interior-point methods need a strictly feasible starting point and never touch the boundary exactly — they approach the optimal vertex without landing on it, so they don't return an exact basic/vertex solution the way simplex does and don't warm-start cheaply after a small problem change. Choose simplex or interior-point by the use case; they are complementary.