Interior-point method
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 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 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.
History
An interior point method was discovered by Soviet mathematician I. I. Dikin in 1967.[1] The method was reinvented in the U.S. in the mid-1980s. In 1984, Narendra Karmarkar developed a method for linear programming called Karmarkar's algorithm,[2] which runs in provably polynomial time ( operations on L-bit numbers, where n is the number of variables and constants), and is also very efficient in practice. Karmarkar's paper created a surge of interest in interior point methods. Two years later, James Renegar invented the first path-following interior-point method, with run-time . The method was later extended from linear to convex optimization problems, based on a
Any convex optimization problem can be transformed into minimizing (or maximizing) a
Yurii Nesterov and Arkadi Nemirovski came up with a special class of such barriers that can be used to encode any convex set. They guarantee that the number of iterations of the algorithm is bounded by a polynomial in the dimension and accuracy of the solution.[5][3]
The class of primal-dual path-following interior-point methods is considered the most successful. Mehrotra's predictor–corrector algorithm provides the basis for most implementations of this class of methods.[6]
Definitions
We are given a
f(x_t) - f* ≤ ε
gi(x_t) ≤ ε for i in 1,...,m,
x in G,
where f* is the optimal solution. A solver is called polynomial if the total number of arithmetic operations in the first T steps is at most
poly(problem-size) * log(V/ε),
where V is some data-dependent constant, e.g., the difference between the largest and smallest value in the feasible set. In other words, V/ε is the "relative accuracy" of the solution - the accuracy w.r.t. the largest coefficient. log(V/ε) represents the number of "accuracy digits". Therefore, a solver is 'polynomial' if each additional digit of accuracy requires a number of operations that is polynomial in the problem size.
Types
Types of interior point methods include:
- Potential reduction methods: Karmarkar's algorithmwas the first one.
- Path-following methods: the algorithms of James Renegar[7] and Clovis Gonzaga[8] were the first ones.
- Primal-dual methods.
Path-following methods
Idea
Given a convex optimization program (P) with constraints, we can convert it to an unconstrained program by adding a barrier function. Specifically, let b be a smooth convex function, defined in the interior of the feasible region G, such that for any sequence {xj in interior(G)} whose limit is on the boundary of G: . We also assume that b is non-degenerate, that is: is positive definite for all x in interior(G). Now, consider the family of programs:
(Pt) minimize t * f(x) + b(x)
Technically the program is restricted, since b is defined only in the interior of G. But practically, it is possible to solve it as an unconstrained program, since any solver trying to minimize the function will not approach the boundary, where b approaches infinity. Therefore, (Pt) has a unique solution - denote it by x*(t). The function x* is a continuous function of t, which is called the central path. All limit points of x*, as t approaches infinity, are optimal solutions of the original program (P).
A path-following method is a method of tracking the function x* along a certain increasing sequence t1,t2,..., that is: computing a good-enough approximation xi to the point x*(ti), such that the difference xi - x*(ti) approaches 0 as i approaches infinity; then the sequence xi approaches the optimal solution of (P). This requires to specify three things:
- The barrier function b(x).
- A policy for determining the penalty parameters ti.
- The unconstrained-optimization solver used to solve (Pi) and find xi, such as Newton's method. Note that we can use each xi as a starting-point for solving the next problem (Pi+1).
The main challenge in proving that the method is polytime is that, as the penalty parameter grows, the solution gets near the boundary, and the function becomes steeper. The run-time of solvers such as Newton's method becomes longer, and it is hard to prove that the total runtime is polynomial.
Renegar[7] and Gonzaga[8] proved that a specific instance of a path-following method is polytime:
- The constraints (and the objective) are linear functions;
- The barrier function is logarithmic: b(x) := - sumj log(-gj(x)).
- The penalty parameter t is updated geometrically, that is, , where μ is a constant (they took , where m is the number of inequality constraints);
- The solver is Newton's method, and a single step of Newton is done for each single step in t.
They proved that, in this case, the difference xi - x*(ti) remains at most 0.01, and f(xi) - f* is at most 2*m/ti. Thus, the solution accuracy is proportional to 1/ti, so to add a single accuracy-digit, it is suffiicent to multiply ti by 2 (or any other constant factor), which requires O(sqrt(m)) Newton steps. Since each Newton step takes O(m n2) operations, the total complexity is O(m3/2 n2) operations for accuracy digit.
Details
We are given a convex optimization problem (P) in "standard form":
minimize cTx s.t. x in G,
where G is convex and closed. We can also assume that G is bounded (we can easily make it bounded by adding a constraint |x|≤R for some sufficiently large R).[3]: Sec.4
To use the interior-point method, we need a
For every t>0, we define the penalized objective ft(x) := cTx + b(x). We define the path of minimizers by: x*(t) := arg min ft(x). We apporimate this path along an increasing sequence ti. The sequence is initialized by a certain non-trivial two-phase initialization procedure. Then, it is updated according to the following rule: .
For each ti, we find an approximate minimum of fti, denoted by xi. The approximate minimum is chosen to satisfy the following "closeness condition" (where L is the path tolerance):
.
To find xi+1, we start with xi and apply the
Convergence and complexity
The convergence rate of the method is given by the following formula, for every i:[3]: Prop.4.4.1
Taking , the number of Newton steps required to go from xi to xi+1 is at most a fixed number, that depends only on r and L. In particular, the total number of Newton steps required to find an ε-approximate solution (i.e., finding x in G such that cTx - c* ≤ ε) is at most:[3]: Thm.4.4.1
where the constant factor O(1) depends only on r and L. The number of Newton steps required for the two-step initialization procedure is at most:[3]: Thm.4.5.1
where the constant factor O(1) depends only on r and L, and , and is some point in the interior of G. Overall, the overall Newton complexity of finding an ε-approximate solution is at most
, where V is some problem-dependent constant: .
Each Newton step takes O(n3) arithmetic operations.
Initialization: phase-I methods
To initialize the path-following methods, we need a point in the relative interior of the feasible region G. In other words: if G is defined by the inequalities gi(x) ≤ 0, then we need some x for which gi(x) < 0 for all i in 1,...,m. If we do not have such a point, we need to find one using a so-called phase I method.[4]: 11.4 A simple phase-I method is to solve the following convex program:
- If s*<0, then we know that x* is an interior point of the original problem and can go on to "phase II", which is solving the original problem.
- If s*>0, then we know that the original program is infeasible - the feasible region is empty.
- If s*=0 and it is attained by some solution x*, then the problem is feasible but has no interior point; if it is not attained, then the problem is infeasible.
For this program it is easy to get an interior point: we can take arbitrarily x=0, and take s to be any number larger than max(f1(0),...,fm(0)). Therefore, it can be solved using interior-point methods. However, the run-time is proportional to log(1/s*). As s* comes near 0, it becomes harder and harder to find an exact solution to the phase-I problem, and thus harder to decide whether the original problem is feasible.
Practical considerations
The theoretic guarantees assume that the penalty parameter is increased at the rate , so the worst-case number of required Newton steps is . In theory, if μ is larger (e.g. 2 or more), then the worst-case number of required Newton steps is in . However, in practice, larger μ leads to a much faster convergence. These methods are called long-step methods.[3]: Sec.4.6 In practice, if μ is between 3 and 100, then the program converges within 20-40 Newton steps, regardless of the number of constraints (though the runtime of each Newton step of course grows with the number of constraints). The exact value of μ within this range has little effect on the performane.[4]: chpt.11
Potential-reduction methods
For potential-reduction methods, the problem is presented in the conic form:[3]: Sec.5
minimize cTx s.t. x in {b+L} ᚢ K,
where b is a vector in Rn, L is a linear subspace in Rn (so b+L is an affine plane), and K is a closed pointed convex cone with a nonempty interior. Every convex program can be converted to the conic form. To use the potential-reduction method (specifically, the extension of Karmarkar's algorithm to convex programming), we need the following assumptions:[3]: Sec.6
- A. The feasible set {b+L} ᚢ K is bounded, and intersects the interior of the cone K.
- B. We are given in advance a strictly-feasible solution x^, that is, a feasible solution in the interior of K.
- C. We know in advance the optimal objective value, c*, of the problem.
- D. We are given an M-logarithmically-homogeneous self-concordant barrierF for the cone K.
Assumptions A, B and D are needed in most interior-point methods. Assumption C is specific to Karmarkar's approach; it can be alleviated by using a "sliding objective value". It is possible to further reduce the program to the Karmarkar format:
minimize sTx s.t. x in M ᚢ K and eTx = 1
where M is a linear subspace of in Rn, and the optimal objective value is 0. The method is based on the following scalar potential function:
v(x) = F(x) + M ln (sTx)
where F is the M-self-concordant barrier for the feasible cone. It is possible to prove that, when x is strictly feasible and v(x) is very small (- very negative), x is approximately-optimal. The idea of the potential-reduction method is to modify x such that the potential at each iteration drops by at least a fixed constant X (specifically, X=1/3-ln(4/3)). This implies that, after i iterations, the difference between objective value and the optimal objective value is at most V * exp(-i X / M), where V is a data-dependent constant. Therefore, the number of Newton steps required for an ε-approximate solution is at most .
Note that in path-following methods the expression is rather than M, which is better in theory. But in practice, Karmarkar's method allows taking much larger steps towards the goal, so it may converge much faster than the theoretical guarantees.
Primal-dual methods
The primal-dual method's idea is easy to demonstrate for constrained
For simplicity, consider the following nonlinear optimization problem with inequality constraints:This inequality-constrained optimization problem is solved by converting it into an unconstrained objective function whose minimum we hope to find efficiently. Specifically, the logarithmic barrier function associated with (1) is
Here is a small positive scalar, sometimes called the "barrier parameter". As converges to zero the minimum of should converge to a solution of (1).
The gradient of a differentiable function is denoted . The gradient of the barrier function is
In addition to the original ("primal") variable we introduce a Lagrange multiplier-inspired dual variable
Equation (4) is sometimes called the "perturbed complementarity" condition, for its resemblance to "complementary slackness" in
We try to find those for which the gradient of the barrier function is zero.
Substituting from (4) into (3), we get an equation for the gradient:
The intuition behind (5) is that the gradient of should lie in the subspace spanned by the constraints' gradients. The "perturbed complementarity" with small (4) can be understood as the condition that the solution should either lie near the boundary , or that the projection of the gradient on the constraint component normal should be almost zero.
Let be the search direction for iteratively updating . Applying
where is the Hessian matrix of , is a diagonal matrix of , and is the diagonal matrix of .
Because of (1), (4) the condition
should be enforced at each step. This can be done by choosing appropriate :
Types of Convex Programs Solvable via Interior-Point Methods
Here are some special cases of convex programs that can be solved efficiently by interior-point methods.[3]: Sec.10
Linear programs
Consider a linear program of the form:
Quadratically constrained quadratic programs
Given a quadratically constrained quadratic program of the form:
Lp norm approximation
Consider a problem of the form
Geometric programs
Consider the problem
There is a self-concordant barrier with parameter 2k+m. The path-following method has Newton complexity O(mk2+k3+n3) and total complexity O((k+m)1/2[mk2+k3+n3]).
Semidefinite programs
Interior point methods can be used to solve semidefinite programs.[3]: Sec.11
See also
- Affine scaling
- Augmented Lagrangian method
- Chambolle-Pock algorithm
- Karush–Kuhn–Tucker conditions
- Penalty method
References
- ^ Dikin, I.I. (1967). "Iterative solution of problems of linear and quadratic programming". Dokl. Akad. Nauk SSSR. 174 (1): 747–748.
- ISBN 0-89791-133-4. Archived from the original(PDF) on 28 December 2013.
- ^ a b c d e f g h i j k l m Arkadi Nemirovsky (2004). Interior point polynomial-time methods in convex programming.
- ^ MR 2061575.
- MR 2115066.
- .
- ^ ISSN 1436-4646.
- ^ ISBN 978-1-4613-9617-8, retrieved 22 November 2023
- doi:10.1137/0802028.
- ISBN 978-0-89871-382-4.
- Bonnans, J. Frédéric; Gilbert, J. Charles; MR 2265882.
- Nocedal, Jorge; Stephen Wright (1999). Numerical Optimization. New York, NY: Springer. ISBN 978-0-387-98793-4.
- Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Section 10.11. Linear Programming: Interior-Point Methods". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.