TITLE: Approximation Algorithms for Difference of Convex (DC) Programming Problems
by Fahaar Mansoor Pirani, M.S. in Industrial Engineering
Advisor: Assistant Professor Firdevs Ulus
Date & Time: July 11, 2023 Tuesday at 10:30
Place: EA-409
ABSTRACT:
This thesis is concerned with Difference of Convex (DC) programming problems and approximation algorithms to solve them. There is an existing exact algorithm that solves DC programming problems if one component of the DC function is polyhedral convex. Motivated by this, first, we propose an algorithm (Algorithm 1) for generating an ϵ-polyhedral underestimator of a convex function g. The algorithm starts with a polyhedral underestimator of g and the epigraph of the current underestimator is intersected with a single halfspace in each iteration to obtain a better approximation. We prove the correctness and establish the convergence rate of Algorithm 1. We also propose a modified variant (Algorithm 2) in which multiple halfspaces are used to update the epigraph of current approximation in each iteration. In addition to its correctness, we prove that Algorithm 2 terminates after finitely many iterations. We show that after obtaining an ϵ-polyhedral underestimator of the first component of a DC function, the algorithm from the literature can be applied to compute an ϵ-solution of the DC programming problem.
We also propose an algorithm (Algorithm 3) for solving DC programming problems directly. In each iteration, Algorithm 3 updates the polyhedral underestimator of g locally while searching for an ϵ-solution of the DC programming problem directly. We prove that the algorithm stops after finitely many iterations and it returns an ϵ-solution to the DC programming problem. Moreover, the sequence {x_k }_({k ≥0}) outputted by Algorithm 3 converges to a global minimizer of the DC problem when ϵ is set to zero. The computational results, obtained using some test examples, show comparable performance of Algorithms 1, 2 and 3 with respect to two DC programming algorithms from the literature.
BIO
Fahaar Pirani received his B.S, and graduated with High Honors and valedictorian, from the Department of Industrial Engineering Bilkent University in June 2021. He is currently pursuing M.S. degree in the Department of Industrial Engineering and working with Prof Firdevs Ulus on designing polyhedral approximation algorithms to solve Difference of Convex (DC) Programming Problems, a sub-class of optimization problems in the realm of non-convex and global optimization. Alongside, his other research interests include Stochastic Processes and their applications in Financial Mathematics.