Incremental quasi-subgradient methods for minimizing the sum of quasi-convex functions

Yaohua Hu, Carisa Kwok Wai Yu, Xiaoqi Yang

Research output: Journal article publicationJournal articleAcademic researchpeer-review

1 Citation (Scopus)

Abstract

The sum of ratios problem has a variety of important applications in economics and management science, but it is difficult to globally solve this problem. In this paper, we consider the minimization problem of the sum of a number of nondifferentiable quasi-convex component functions over a closed and convex set. The sum of quasi-convex component functions is not necessarily to be quasi-convex, and so, this study goes beyond quasi-convex optimization. Exploiting the structure of the sum-minimization problem, we propose a new incremental quasi-subgradient method for this problem and investigate its convergence properties to a global optimal value/solution when using the constant, diminishing or dynamic stepsize rules and under a homogeneous assumption and the Hölder condition. To economize on the computation cost of subgradients of a large number of component functions, we further propose a randomized incremental quasi-subgradient method, in which only one component function is randomly selected to construct the subgradient direction at each iteration. The convergence properties are obtained in terms of function values and iterates with probability 1. The proposed incremental quasi-subgradient methods are applied to solve the quasi-convex feasibility problem and the sum of ratios problem, as well as the multiple Cobb–Douglas productions efficiency problem, and the numerical results show that the proposed methods are efficient for solving the large-scale sum of ratios problem.

Original languageEnglish
Pages (from-to)1003-1028
Number of pages26
JournalJournal of Global Optimization
Volume75
Issue number4
DOIs
Publication statusPublished - 12 Aug 2019

Keywords

  • Incremental approach
  • Quasi-convex programming
  • Subgradient method
  • Sum of ratios problem
  • Sum-minimization problem

ASJC Scopus subject areas

  • Computer Science Applications
  • Management Science and Operations Research
  • Control and Optimization
  • Applied Mathematics

Cite this