Nonlinear Optimization

Cubic Regularization Method based on Mixed Factorizations for Unconstrained Minimization

  • Ernesto G. Birgin
  • José Mario Martínez
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , ,

    Newton’s method for unconstrained optimization, subject to proper regularization or special trust-region procedures, finds first-order stationary points with precision $\varepsilon$ employing, at most, $O(\varepsilon^{-3/2})$ functional and derivative evaluations. However, the computer work per iteration of the best-known implementations may need several factorizations per iteration or may use rather expensive matrix decompositions. In this paper, we … Read more

    Concise Complexity Analyses for Trust-Region Methods

  • Frank E. Curtis
  • Daniel P. Robinson
  • Zachary Lubberts
    • Categories Unconstrained Optimization Tags , , , , , ,

    Concise complexity analyses are presented for simple trust region algorithms for solving unconstrained optimization problems. In contrast to a traditional trust region algorithm, the algorithms considered in this paper require certain control over the choice of trust region radius after any successful iteration. The analyses highlight the essential algorithm components required to obtain certain complexity … Read more

    Local attractors of newton-type methods for constrained equations and complementarity problems with nonisolated solutions

  • Andreas Fischer
  • Alexey F. Izmailov
  • Mikhail V. Solodov
    • Categories Complementarity and Variational Inequalities, Nonlinear Systems and Least-Squares

    For constrained equations with nonisolated solutions, we show that if the equation mapping is 2-regular at a given solution with respect to a direction in the null space of the Jacobian, and this direction is interior feasible, then there is an associated domain of starting points from which a family of Newton-type methods is well-de ned … Read more

    Combinatorial Integral Approximation Decompositions for Mixed-Integer Optimal Control

  • Sebastian Sager
  • Tobias Weber
  • Clemens Zeile
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Systems governed by Differential Equations Optimization Tags , , , , ,

    Solving mixed-integer nonlinear programs (MINLPs) is hard in theory and practice. Decomposing the nonlinear and the integer part seems promising from a computational point of view. In general, however, no bounds on the objective value gap can be guaranteed and iterative procedures with potentially many subproblems are necessary. The situation is different for mixed-integer optimal … Read more

    A Progressive Batching L-BFGS Method for Machine Learning

  • Raghu Bollapragada
  • Jorge Nocedal
  • Hao-Jun Shi
  • Ping Tak Peter Tang
  • Dheevatsa Mudigere
    • Categories Convex Optimization, Nonlinear Optimization, Stochastic Programming Tags , , ,

    The standard L-BFGS method relies on gradient approximations that are not dominated by noise, so that search directions are descent directions, the line search is reliable, and quasi-Newton updating yields useful quadratic models of the objective function. All of this appears to call for a full batch approach, but since small batch sizes give rise … Read more

    Extensions of Yuan’s Lemma to fourth-order tensor system with applications

  • Qingzhi Yang
  • Yuning Yang
  • Yang Zhou
    • Categories Constrained Nonlinear Optimization, Semi-definite Programming

    Yuan’s lemma is a basic proposition on homogeneous quadratic function system. In this paper, we extend Yuan’s lemma to 4th-order tensor system. We first give two gen- eralized definitions of positive semidefinite of 4th-order tensor, and based on them, two extensions of Yuan’s lemma are proposed. We illustrate the difference between our ex- tensions and … Read more

    On classes of set optimization problems which are reducible to vector optimization problems and its impact on numerical test instances

  • Gabriele Eichfelder
  • Tobias Gerlach
    • Categories Multi-Criteria Optimization, Nonlinear Optimization Tags , , , ,

    Set optimization with the set approach has recently gained increasing interest due to its practical relevance. In this problem class one studies optimization problems with a set-valued objective map and defines optimality based on a direct comparison of the images of the objective function, which are sets here. Meanwhile, in the literature a wide range … Read more

    Optimal linearized symmetric ADMM for separable convex programming

  • Jianchao Bai
  • Chang Xiaokai
  • Liu Sanyang
    • Categories Constrained Nonlinear Optimization

    Due to its wide applications and simple implementations, the Alternating Direction Method of Multipliers (ADMM) has been extensively investigated by researchers from different areas. In this paper, we focus on a linearized symmetric ADMM (LSADMM) for solving the multi- block separable convex minimization model. This LSADMM partitions the data into two group variables and updates … Read more

    Exact Semidefinite Formulations for a Class of (Random and Non-Random) Nonconvex Quadratic Programs

  • Samuel Burer
  • Yinyu Ye
    • Categories Global Optimization Theory, Quadratic Programming, Semi-definite Programming Tags , ,

    We study a class of quadratically constrained quadratic programs (QCQPs), called {\em diagonal QCQPs\/}, which contain no off-diagonal terms $x_j x_k$ for $j \ne k$, and we provide a sufficient condition on the problem data guaranteeing that the basic Shor semidefinite relaxation is exact. Our condition complements and refines those already present in the literature … Read more

    Combinatorial Integral Approximation for Mixed-Integer PDE-Constrained Optimization Problems

  • Mirko Hahn
  • Sebastian Sager
    • Categories (Mixed) Integer Nonlinear Programming, Optimization of Systems modeled by PDEs, Systems governed by Differential Equations Optimization Tags , , ,

    We apply the basic principles underlying combinatorial integral approximation methods for mixed-integer optimal control with ordinary differential equations in general, and the sum-up rounding algorithm specifically, to optimization problems with partial differential equation (PDE) constraints. By doing so, we identify two possible generalizations that are applicable to problems involving PDE constraints with mesh-dependent integer variables, … Read more