Karmarkar’s polynomial-time linear optimization with projective transformations
Prologue
In operations research, linear programming methods are employed to achieve the best possible outcome in a defined mathematical model, whose requirements are represented by linear relationships. In this regard, the very first algorithm that comes to mind for maximizing or minimizing the value of a linear objective function under a set of linear constraints, is probably the famous Simplex method, developed by George Dantzig in 1947. During the post-war era, when efficient resource allocation was crucial, it is safe to say that Dantzig’s innovation brought an immense breakthrough in optimization, and paved the way for further improvements in logistics, finance and engineering.
To remind you, let me first discuss the general structure of Dantzig’s approach. The Simplex method starts at a feasible corner point of the polytope (defined by the constraints) and moves along the edges of the polytope to find the optimal vertex where the objective function attains its maximum or minimum value, depending on what we search for. If our objective function represents the profit for our bakery, odds are high that we are trying to maximize its value; and in contrast, if the objective function models the combined CPU and network load throughout a computing cluster, most probably we are searching for its optimum lowest value. Regardless of that, the key concept here is that the optimal solution to our linear programming problem lies at one of the vertices of the polytope, formed by the constraints. Graphical solution/visualization for Simplex is indeed intuitive, and algebraically, what Simplex does is to organize the information of constraints into a tableau and use pivotal operations (similar to Gaussian elimination), to navigate from one vertex of the feasible region to another, focusing on improving the objective function’s value with each move, until no further improvements can be made.
Simplex is extremely significant for a number of reasons. Firstly, it is widely applicable, since it can be readily tailored to different businesses and their own issues within their respective fields. Second, it is strong, visually intuitive, and simple to grasp. Most notably, the simplex algorithm’s creation sparked more optimisation research, which produced new techniques and algorithms that could tackle increasingly difficult problems — including non-linear ones.
Great, but where does the simplex fall short? Although the simplex approach has been the foundation for handling linear programming issues, there are a number of drawbacks that become apparent when applying it in certain situations, especially when dealing with large-scale, intricate computing jobs that are typical in computer engineering.
The most prominent theoretical problem of the simplex algorithm is its worst-case exponential time complexity. In spite of the fact that it performs efficiently on average, specific instances exist where it requires an exhausting number of iterations to reach the optimal solution. This behavior is best exemplified by Klee-Minty cubes, a type of problem designed to force the simplex algorithm into checking almost every vertex before arriving at the optimal solution. Therefore, it can be argued that for problems involving thousands of variables and constraints, as we often encounter in network topology design, cluster management or other areas of computer engineering, this would mean a serious disadvantage.
Another concern with the simplex algorithm is cycling, a phenomenon where the algorithm might revisit the same set of basic feasible solutions indefinitely without making progress towards the optimum (as a side note, methods like Bland’s rule aim to prevent this issue, but they bring their own costs).
In practical applications, such limitations of the simplex algorithm become apparent when dealing with large-scale linear programming tasks, typical in industrial and scientific computing, mainly due to the storage requirements for maintaining a large tableau, and the computational overhead in each pivot operation.
Finally, from distributed systems perspective, it is worth noting that the simplex algorithm’s structure generally necessitates the load of constraints into memory, making it trickier to adapt for problems that naturally disperse across several processing units in a distributed system.
Therefore, scrutinizing all these sparked interest in alternative optimization techniques that can offer better performance and scalability.
Revolutionary approach of Narendra Karmarkar: interior-point methods
The world of optimization was significantly transformed with the introduction of a novel algorithm in 1984 when Narendra Karmarkar published his interior-point method as an alternative to Simplex. This meant a total change of perspective from the boundary-based approach (which traverse vertices one by one) of the simplex to a more direct manner that also navigates within the interior of the feasible region. Interior-point methods, unlike the simplex algorithm, do not rely on moving along the edges of the feasible region defined by the constraints. Instead, they can start from a point within the interior of the feasible region and move towards the optimum solution by traversing through the interior area. This approach can be visualized as a path-finding mission inside a multidimensional shape, and here, we seek the point that maximizes/minimizes the objective function, without ever necessarily touching the boundaries until the optimum is reached.
This represents a whole new philosophy, and the maths behind the scenes is deep, as Karmarkar’s algorithm specifically employs a projective transformation of the feasible region. The algorithm iteratively projects the feasible region into a lower-dimensional space, solves the problem in this transformed space, and then maps the solution back to the original space… Barrier functions are also associated with the interior point approach. Here, the idea is to apply a penalization to make sure that the algorithm moves toward the optimal solution without getting trapped on the boundary constraints. By the way, (I’ve found similarities in my mind with how simulated annealing algorithm manages the “temperature” while navigating inside the space), aggressiveness of the barrier function itself can change over the time as well.
We prove that given a polytope P and a strictly interior point, E, there is a projective transformation of the space that maps P to P’. The algorithm consists of repeated application of such projective transformations each followed by optimization over an inscribed sphere to create a sequence of points which converges to the optimal solution in polynomial-time. [Karmarkar, N. (1984). A New Polynomial-Time Algorithm for Linear Programming. AT&T Bell Laboratories.]
Logarithmic barrier functions
Barrier functions can be seen as mathematical constructs used in interior-point methods to maintain the search within the feasible region of an optimization problem. What they do is to basically “penalize” solutions that approach the boundaries of the feasible region. The penalty increases exponentially as the solution approaches any constraint boundary, effectively creating a “barrier” that discourages boundary approaches. A common form of barrier function used in linear programming is the logarithmic barrier function. For a constraint in the form of g(x) <= 0, a barrier term −𝜇 * log(−𝑔(𝑥)) is added to the objective function, where μ is a positive parameter (barrier parameter) that controls the influence of the barrier.
The term log(−𝑔(𝑥)) is only defined when 𝑔(𝑥)<0, i.e., strictly within the feasible region. As 𝑔(𝑥) approaches zero (means that we move towards the boundary of the feasible region), the logarithm approaches infinity, therefore significantly increasing the penalty.
Advantages of the interior-point methods
One of Karmarkar’s method’s primary advantages is its polynomial time complexity, which drastically improves upon the worst-case exponential time complexity of the simplex algorithm. Additionally, interior-point approaches are naturally suited to parallel processing. Unlike the simplex algorithm, which only analyses one vertex at a time, the computations in each iteration of an interior-point method can be divided across several processors. This property is very noteworthy today, given the high regard for parallel processing capabilities. Moreover, it should definitely be noted that Karmarkar’s idea opened the door to a new era of optimization techniques. It inspired the development of several other interior-point methods, each improving or adapting Karmarkar’s original concept to different types of optimization problems.
Further enhancements in modern operations research
Since Karmarkar’s pioneering invention of interior-point techniques in 1984, both linear and nonlinear optimisation has been constantly innovated. In the final part of my article, I believe it is beneficial to quickly discuss two enhancement ideas that are based on the aforementioned notions. Again, a brilliant idea to support the basic interior-point approach, predictor-corrector methods (they also have various applications for ordinary differential equations and numerical methods), allow for more accurate steps towards the solution by anticipating future corrections. This method significantly reduces the number of iterations needed to reach convergence, enhancing computational efficiency. Also, primal-dual interior point methods are widely regarded as some of the most effective for solving large-scale linear and nonlinear programming problems. In these methods, we progress towards the optimal solution by iteratively updating both the primal and the dual variables. This is done using a system of equations that aims to reduce the duality gap (i.e. the difference between the values of the objective function of the primal and dual problems), therefore converging to an optimal solution where both the primal and dual conditions are satisfied.
Closing remarks
I clearly observe that linear optimization is an astoundingly beneficial field of research, and the intersection of deep learning with operations research can provide fruitful outcomes. Can’t we discover innovative ways to integrate neural networks into existing optimization methods, aiming to enhance the convergence abilities, for example? Just thinking out loud. Additionally, from the hardware perspective, I believe there is still plenty of room for building the bridge between the multi-core distributed computing environments and the industrial-scale operations research problems. May these be the subject of a future article.
Thank you for reading. Feel free to discuss and contribute!
Anılcan Erciyes
Research Engineer,
Vehicular Networks & Intelligent Transportation Research Laboratory, Istanbul.
