{
  "id": "1807.07563",
  "version": "v1",
  "published": "2018-07-19T17:59:37.000Z",
  "updated": "2018-07-19T17:59:37.000Z",
  "title": "A linear-time algorithm for generalized trust region problems",
  "authors": [
    "Rujun Jiang",
    "Duan Li"
  ],
  "categories": [
    "math.OC"
  ],
  "abstract": "In this paper, we provide the first provable linear-time (in the number of non-zero entries of the input) algorithm for approximately solving the generalized trust region subproblem (GTRS) of minimizing a quadratic function over a quadratic constraint under some regular conditions. Our algorithm is motivated by and extends a recent linear-time algorithm for the trust region subproblem by Hazan and Koren [Math. Program., 2016, 158(1-2): 363-381]. However, due to the non-convexity and non-compactness of the feasible region, such an extension is nontrivial. Our main contribution is to demonstrate that under some regular condition, the optimal solution is in a compact and convex set and lower and upper bounds of the optimal value can be computed in linear time. Using these properties, we develop a linear-time algorithm for the GTRS.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-07-19T17:59:37.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "generalized trust region problems",
      "linear-time algorithm",
      "regular condition",
      "generalized trust region subproblem",
      "linear time"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}