Nonlinear Optimization

A Branch-and-Bound based Algorithm for Nonconvex Multiobjective Optimization

  • Gabriele Eichfelder
  • Julia Niebling
    • Categories Global Optimization, Multi-Criteria Optimization, Nonlinear Optimization Tags , , , ,

    A new branch-and-bound based algorithm for smooth nonconvex multiobjective optimization problems with convex constraints is presented. The algorithm computes an $(\varepsilon,\delta)$-approximation of all globally optimal solutions. We introduce the algorithm which uses selection rules, discarding and termination tests. The discarding tests are the most important aspect, as they examine in different ways whether a box … Read more

    ADMM for Multiaffine Constrained Optimization

  • Frank E. Curtis
  • Wenbo Gao
  • Donald Goldfarb
    • Categories Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , , ,

    We propose an expansion of the scope of the alternating direction method of multipliers (ADMM). Specifically, we show that ADMM, when employed to solve problems with multiaffine constraints that satisfy certain easily verifiable assumptions, converges to the set of constrained stationary points if the penalty parameter in the augmented Lagrangian is sufficiently large. When the … Read more

    A Riemannian Conjugate Gradient Algorithm with Implicit Vector Transport for Optimization on the Stiefel Manifold

  • Hugo Lara
  • Harry Oviedo
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , ,

    In this paper, a reliable curvilinear search algorithm for solving optimization problems over the Stiefel manifold is presented. This method is inspired by the conjugate gradient method, with the purpose of obtain a new direction search that guarantees descent of the objective function in each iteration. The merit of this algorithm lies in the fact … Read more

    Algorithms and Convergence Results of Projection Methods for Inconsistent Feasibility Problems: A Review

  • Yair Censor
  • Maroun Zaknoon
    • Categories Convex Optimization, Nonlinear Optimization Tags , ,

    The convex feasibility problem (CFP) is to find a feasible point in the intersection of finitely many convex and closed sets. If the intersection is empty then the CFP is inconsistent and a feasible point does not exist. However, algorithmic research of inconsistent CFPs exists and is mainly focused on two directions. One is oriented … Read more

    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