OPTEC - K.U.Leuven Center of Excellence: Optimization in Engineering

"Iterative facet dividing algorithm for optimization of Lagrange multipliers with logarithmic complexity"
Speaker: Amir Forouzan, Department of Electrical Engineering, ESAT-SCD/SISTA (promoter: Prof. Marc Moonen)
Discussant: Carlo Savorgnan

Lagrange dual optimization technique is widely used in constraint optimization. Using this technique, the problem can be solved in two nested levels, namely, the lower and higher levels, where a dual function should be calculated in the lower level and the Lagrange multipliers should be optimized in the higher level. The computational complexity is equal to the computational complexity of calculating the dual function times the number of iterations required for finding the optimal value of the Lagrange multipliers. Therefore, reducing the number of iterations required by the higher level has a considerable effect on the total computational complexity of the solution. In this talk, we propose a new zero-order algorithm called iterative facet dividing algorithm (IFDA) for optimizing the Lagrange multipliers. The computational complexity of IFDA is O(n log(1/epsilon)), where n is the total number of utility and constraint functions and epsilon is the desired precision. This is much faster than several widely used algorithms such as the gradient method and Nesterov’s optimal gradient scheme. Additionally, the proposed algorithm provides much flexibility in solving large separable problems which will be discussed in this talk.