Zhou, Song2024-04-052024-04-052023-08Zhou_cornellgrad_0058F_13923http://dissertations.umi.com/cornellgrad:13923https://hdl.handle.net/1813/114824142 pagesThis work comprises two parts. Part I focuses on the convex feasibility problem (finding or approximating a point in the intersection of finitely many closed convex sets). We avoid the need for orthogonal projections by using radial projections, introduced by Renegar. The main requirement is that an interior point is known in each of the sets considered. By developing Renegar’s theory, we obtain a family of radial projection-based algorithms for the convex feasibility problem which recover the linear convergence rates of orthogonal projection-based methods. Through studying different assumptions on the emptiness of the interior of the intersection set in the convex feasibility problem, we also exhibit how radial projections can be applied to solve constrained optimization problems when certain conditions are met.Part II can be seen as an application of the theory of radial projections developed in Part I. Here, we revisit the notion of maximal-margin classifiers, from around 2000, but now from a general perspective – the intersections of generic closed convex cones, not just half-spaces (i.e., the perceptron). This requires extending concepts and establishing more general theory of the margin function, which is achieved by applying and refining the results in Part I in the conic case. Even more interestingly, we are led to the first Õ(1/ε) first-order method for approximating, within relative error ε, the margin-maximizer of the intersection cone. Previous results, only in the case of the perceptron, were O(1/ε²), making our result a notable improvement even in the most basic of cases.enConvex Feasibility ProblemFirst-Order MethodLinear RegularityMargin MaximizationPerceptronRadial Projectiondissertation or thesishttps://doi.org/10.7298/w6h4-0r65