{
  "id": "2205.01774",
  "version": "v1",
  "published": "2022-05-03T20:51:33.000Z",
  "updated": "2022-05-03T20:51:33.000Z",
  "title": "Efficient Algorithms for Minimizing Compositions of Convex Functions and Random Functions and Its Applications in Network Revenue Management",
  "authors": [
    "Xin Chen",
    "Niao He",
    "Yifan Hu",
    "Zikun Ye"
  ],
  "categories": [
    "math.OC"
  ],
  "abstract": "In this paper, we study a class of nonconvex stochastic optimization in the form of $\\min_{x\\in\\mathcal{X}} F(x):=\\mathbb{E}_\\xi [f(\\phi(x,\\xi))]$, where the objective function $F$ is a composition of a convex function $f$ and a random function $\\phi$. Leveraging an (implicit) convex reformulation via a variable transformation $u=\\mathbb{E}[\\phi(x,\\xi)]$, we develop stochastic gradient-based algorithms and establish their sample and gradient complexities for achieving an $\\epsilon$-global optimal solution. Interestingly, our proposed Mirror Stochastic Gradient (MSG) method operates only in the original $x$-space using gradient estimators of the original nonconvex objective $F$ and achieves $\\tilde{\\mathcal{O}}(\\epsilon^{-2})$ sample and gradient complexities, which matches the lower bounds for solving stochastic convex optimization problems. Under booking limits control, we formulate the air-cargo network revenue management (NRM) problem with random two-dimensional capacity, random consumption, and routing flexibility as a special case of the stochastic nonconvex optimization, where the random function $\\phi(x,\\xi)=x\\wedge\\xi$, i.e., the random demand $\\xi$ truncates the booking limit decision $x$. Extensive numerical experiments demonstrate the superior performance of our proposed MSG algorithm for booking limit control with higher revenue and lower computation cost than state-of-the-art bid-price-based control policies, especially when the variance of random capacity is large. KEYWORDS: stochastic nonconvex optimization, hidden convexity, air-cargo network revenue management, gradient-based algorithms",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-05-03T20:51:33.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "random function",
      "convex function",
      "stochastic convex optimization problems",
      "air-cargo network revenue management",
      "efficient algorithms"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}