Nonlinear Optimization

Iteration-complexity of a Jacobi-type non-Euclidean ADMM for multi-block linearly constrained nonconvex programs

  • Jefferson Gonçalves Melo
  • Renato D.C. Monteiro
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Nonsmooth Optimization Tags , , , ,

    This paper establishes the iteration-complexity of a Jacobi-type non-Euclidean proximal alternating direction method of multipliers (ADMM) for solving multi-block linearly constrained nonconvex programs. The subproblems of this ADMM variant can be solved in parallel and hence the method has great potential to solve large scale multi-block linearly constrained nonconvex programs. Moreover, our analysis allows the … Read more

    Extending the Scope of Robust Quadratic Optimization

  • Aharon Ben-Tal
  • Dick den Hertog
  • Ahmadreza Marandi
  • Bertrand Melenberg
    • Categories Quadratic Programming, Robust Optimization Tags , , ,

    We derive computationally tractable formulations of the robust counterparts of convex quadratic and conic quadratic constraints that are concave in matrix-valued uncertain parameters. We do this for a broad range of uncertainty sets. In particular, we show how to reformulate the support functions of uncertainty sets represented in terms of matrix norms and cones. Our … Read more

    Exact augmented Lagrangian functions for nonlinear semidefinite programming

  • Ellen H. Fukuda
  • Bruno F. Lourenço
    • Categories Constrained Nonlinear Optimization, Semi-definite Programming Tags , ,

    In this paper, we study augmented Lagrangian functions for nonlinear semidefinite programming (NSDP) problems with exactness properties. The term exact is used in the sense that the penalty parameter can be taken appropriately, so a single minimization of the augmented Lagrangian recovers a solution of the original problem. This leads to reformulations of NSDP problems … Read more

    An Investigation of Newton-Sketch and Subsampled Newton Methods

  • Albert S. Berahas
  • Raghu Bollapragada
  • Jorge Nocedal
    • Categories Convex Optimization, Nonlinear Optimization, Stochastic Programming Tags , , ,

    Sketching, a dimensionality reduction technique, has received much attention in the statistics community. In this paper, we study sketching in the context of Newton’s method for solving finite-sum optimization problems in which the number of variables and data points are both large. We study two forms of sketching that perform dimensionality reduction in data space: … Read more

    Polynomial Norms

  • Amir Ali Ahmadi
  • Etienne de Klerk
  • Georgina Hall
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization, Semi-definite Programming Tags , , ,

    In this paper, we study polynomial norms, i.e. norms that are the dth root of a degree-d homogeneous polynomial f. We first show that a necessary and sufficient condition for f^(1/d) to be a norm is for f to be strictly convex, or equivalently, convex and positive definite. Though not all norms come from dth … Read more

    A Primal-Dual Augmented Lagrangian Penalty-Interior-Point Filter Line Search Algorithm

  • Christof Büskens
  • Renke Kuhlmann
    • Categories Constrained Nonlinear Optimization Tags , , , ,

    Interior-point methods have been shown to be very efficient for large-scale nonlinear programming. The combination with penalty methods increases their robustness due to the regularization of the constraints caused by the penalty term. In this paper a primal-dual penalty-interior-point algorithm is proposed, that is based on an augmented Lagrangian approach with an l2-exact penalty function. … Read more

    Convergence and Complexity Analysis of a Levenberg-Marquardt Algorithm for Inverse Problems

  • Elhoucine Bergou
  • Youssef Diouane
  • Vyacheslav Kungurtsev
    • Categories Nonlinear Optimization, Unconstrained Optimization

    The Levenberg-Marquardt algorithm is one of the most popular algorithms for finding the solution of nonlinear least squares problems. Across different modified variations of the basic procedure, the algorithm enjoys global convergence, a competitive worst case iteration complexity rate, and a guaranteed rate of local convergence for both zero and nonzero small residual problems, under … Read more

    Stability and accuracy of Inexact Interior Point methods for convex quadratic programming

  • Benedetta Morini
  • Valeria Simoncini
    • Categories Nonlinear Optimization Tags , ,

    We consider primal-dual IP methods where the linear system arising at each iteration is formulated in the reduced (augmented) form and solved approximately. Focusing on the iterates close to a solution, we analyze the accuracy of the so-called inexact step, i.e., the step that solves the unreduced system, when combining the effects of both different … Read more

    A Derivative-Free and Ready-to-Use NLP Solver for Matlab or Octave

  • Florian Jarre
  • Felix Lieder
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization, Optimization Software and Modeling Systems Tags , ,

    This paper introduces a derivative-free and ready-to-use solver for nonlinear programs with nonlinear equality and inequality constraints (NLPs). Using finite differences and a sequential quadratic programming (SQP) approach, the algorithm aims at finding a local minimizer and no extra attempt is made to generate a globally optimal solution. Due to the use of finite differences, … Read more