HSC welcomes all external visitors to this site, especially students and members of the academic community. Please use the comments box at the bottom of each page to record any comments or suggestions for improvement.

For a more exhaustive treatment of this subject, we have a pdf tutorial available here

Introduction

Interior point methods are one of a set of techniques for convex optimization. As opposed to other techniques such as the Lagrangian and Simplex algorithms, they offer significant performance improvements in many cases. For engineering applications, the most attractive feature of this technique is that the algorithm is iterative and each iteration provides a feasible and improved solution than the previous.

Problem description.

The standard convex programing problem can be defined as

.

If the objective function g() and inequality constraints f_i are linear, then this becomes a linear programming problem. Note that the matrix A and the vector \vec{b} are fixed inputs to the problem.

In the absence of the inequality constraints, solutions to this problem are relatively simple. They consist of finding a point x_0 where the hyperplane Ax+b and the objective function g() are mutually tangent; this yields the solution(the high contact principle). However, the inequality constraints make the problem complex. For one, the possible solutions have to be taken from the set S, as shown in Attach:ipm_2.png Δ. Secondly, the high contact condition may not even hold for the feasible set.

Formulation

Interior Point methods start by finding a feasible point, i.e a a point x_0, which, while not optimal, is within the feasible set. Starting from this, it move to points x_1, x_2 etc. with each point being an improvement on the previous one. At each step, the algorithm must find the direction in which to move, and the size of the step. The first is called a direction vector, and the second is called a step length.

To find the direction of movement, the interior point algorithm must take into account both the gradient of the objective function and the constraints. The idea is to combine these two into a single objective function, which can then be minimized. Different algorithms handle this differently, as is shown below.

Karmarkar's Algorithm for Linear Programing

Karmarkar's linear programming algorithm works by transforming the solution space, rather than the current point. If we take the distance to the edge of the solution space to be v = b - Ax, then by scaling b and A appropriately, we can keep the value of v equal to [1]. In this case, x will be equidistant from all the boundaries of the constraint space.

Note that the constraint Ax < b and DAx < Db are equivalent, as long as D is a diagonal vector of positive elements. i.e. if x satisfies the first constraint, it will satisfy the second constraint and vice-versa.

There are many ways to implement the transmutation of the solution space; the simplest technique shown above is called affine scaling. In coptgsl we have provided an implementation of the simple Karmarkar's algorithm with affine scaling.

Primal Dual Algorithms

The key point of primal dual algorithms is that they don't directly try to optimize the objective function. Instead, they try to minimize the difference between the primal and the dual solutions. The objective function is substituted by a potential function which incorporates both the duality gap and the constraints in the form of log-barrier functions. By strong duality theory, it can be shown that if a convex optimization problem has a feasible solution, the primal and the dual solutions match at the feasible point. Primal dual potential reduction algorithms exhibit very fast convergence and good robustness. In coptgsl, we have used a primal dual potential reduction algorithm to solve both the Socp and the SDP? problems.

Comments

Add Comment
Email address(will be kept hidden)
Enter code: