M.Sc Thesis
M.Sc Student Pemov Ella The 2-Coordinate Descent Method for Solving Simplex-Type Constrained Problems with Application to SVM Training Department of Industrial Engineering and Management Professor Amir Beck

Abstract

In this work, we interested to find the solution of the problem of finding the minimum of f(x), a convex function constrained by aTx=b, x0.  Two well known problems that have the above form are Support Vector machine (SVM) in the linearly separable case and the Chebyshev center problem.

We propose a two coordinate descent method, where in each iteration, at the beginning, we choose one coordinate and the second coordinate is chosen with respect to the first chosen coordinate. We show the convergence rate of the proposed method. Several numerical experiments were made in order to compare the suggested method to the existing block coordinate methods.  The numerical experiments show that in most of the cases, the suggested method improved the results of the existing methods.