Quasi-convex feasibility problems: Subgradient methods and convergence rates

Yaohua Hu, Gongnong Li, Carisa Kwok Wai Yu, Tsz Leung Yip

Research output: Journal article publicationJournal articleAcademic researchpeer-review

Abstract

The feasibility problem is at the core of the modeling of many problems in various areas, and the quasi-convex function usually provides a precise representation of reality in many fields such as economics, finance and management science. In this paper, we consider the quasi-convex feasibility problem (QFP), that is to find a common point of a family of sublevel sets of quasi-convex functions, and propose a unified framework of subgradient methods for solving the QFP. This paper is contributed to establish the quantitative convergence theory, including the iteration complexity and the convergence rates, of subgradient methods with the constant/dynamic stepsize rules and several general control schemes, including the α-most violated constraints control, the s-intermittent control and the stochastic control. An interesting finding is disclosed by iteration complexity results that the stochastic control enjoys both advantages of low computational cost requirement and low iteration complexity. More importantly, we introduce a notion of Hölder-type error bound property for the QFP, and use it to establish the linear (or sublinear) convergence rates for subgradient methods to a feasible solution of the QFP. Preliminary numerical results to the multiple Cobb-Douglas productions efficiency problem indicate the powerful modeling capability of the QFP and show the high efficiency and stability of subgradient methods for solving the QFP.

Original languageEnglish
JournalEuropean Journal of Operational Research
DOIs
Publication statusAccepted/In press - 2021

Keywords

  • Convergence rate
  • Global optimization
  • Iteration complexity
  • Quasi-convex feasibility problem
  • Subgradient method

ASJC Scopus subject areas

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Cite this