generalized eigenvalue problem

Solving Large Scale Cubic Regularization by a Generalized Eigenvalue Problem

  • Felix Lieder
    • Categories Nonlinear Optimization, Optimization Software and Modeling Systems, Unconstrained Optimization Tags , ,

    Cubic Regularization methods have several favorable properties. In particular under mild assumptions, they are globally convergent towards critical points with second order necessary conditions satisfied. Their adoption among practitioners, however, does not yet match the strong theoretical results. One of the reasons for this discrepancy may be additional implementation complexity needed to solve the occurring … Read more

    On local non-global minimizers of quadratic optimization problem with a single quadratic constraint

  • Maziar Salahi
  • Akram Taati
    • Categories Global Optimization, Nonlinear Optimization Tags , , ,

    In this paper, we consider the nonconvex quadratic optimization problem with a single quadratic constraint. First we give a theoretical characterization of the local non-global minimizers. Then we extend the recent characterization of the global minimizer via a generalized eigenvalue problem to the local non-global minimizers. Finally, we use these results to derive an efficient … Read more

    A conjugate gradient-based algorithm for large-scale quadratic programming problem with one quadratic constraint

  • Maziar Salahi
  • Akram Taati
    • Categories Global Optimization, Quadratic Programming Tags , ,

    In this paper, we consider the nonconvex quadratically constrained quadratic programming (QCQP) with one quadratic constraint. By employing the conjugate gradient method, an efficient algorithm is proposed to solve QCQP that exploits the sparsity of the involved matrices and solves the problem via solving a sequence of positive definite system of linear equations after identifying … Read more

    Distributionally robust optimization with polynomial densities: theory, models and algorithms

  • Etienne de Klerk
  • Daniel Kuhn
  • Krzysztof Postek
    • Categories Robust Optimization, Semi-definite Programming Tags , , ,

    In distributionally robust optimization the probability distribution of the uncertain problem parameters is itself uncertain, and a fictitious adversary, e.g., nature, chooses the worst distribution from within a known ambiguity set. A common shortcoming of most existing distributionally robust optimization models is that their ambiguity sets contain pathological discrete distribution that give nature too much … Read more

    Improved convergence rates for Lasserre-type hierarchies of upper bounds for box-constrained polynomial optimization

  • Etienne de Klerk
  • Monique Laurent
  • Roxana Hess
    • Categories Semi-definite Programming Tags , , , , ,

    We consider the problem of minimizing a given $n$-variate polynomial $f$ over the hypercube $[-1,1]^n$. An idea introduced by Lasserre, is to find a probability distribution on $[-1,1]^n$ with polynomial density function $h$ (of given degree $r$) that minimizes the expectation $\int_{[-1,1]^n} f(x)h(x)d\mu(x)$, where $d\mu(x)$ is a fixed, finite Borel measure supported on $[-1,1]^n$. It … Read more

    Local Nonglobal Minima for Solving Large Scale Extended Trust Region Subproblems

  • Maziar Salahi
  • Henry Wolkowicz
  • Akram Taati
    • Categories Constrained Nonlinear Optimization, Global Optimization, Optimization Software and Modeling Systems Tags , , ,

    We study large scale extended trust region subproblems (eTRS) i.e., the minimization of a general quadratic function subject to a norm constraint, known as the trust region subproblem (TRS) but with an additional linear inequality constraint. It is well known that strong duality holds for the TRS and that there are efficient algorithms for solving … Read more