Back to search

Cornell University

RADIAL PROJECTIONS, CONVEX FEASIBILITY PROBLEMS AND MARGIN MAXIMIZATION

Abstract

dc:description.abstract

This 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.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Operations Research and Information Engineering
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Operations Research and Information Engineering
Grantor
Cornell University
Year dc:date.issued
2023

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Zhou, Song
Chair dc:contributor.chair
  • Renegar, James
Committee members dc:contributor.committeemember
  • Lewis, Adrian
  • Davis, Damek

Subjects

dc:subject × 6

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Dc Identifier Bibid
16219231
Dc Identifier Other
ProQuest Submission ID: 13923
ProQuest Publication ID: 30630914

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Zhou, Song. RADIAL PROJECTIONS, CONVEX FEASIBILITY PROBLEMS AND MARGIN MAXIMIZATION. Doctor of Philosophy thesis, Cornell University, 2023. https://hdl.handle.net/1813/114824