Nonlinear Optimization

Properly optimal elements in vector optimization with variable ordering structures

  • Gabriele Eichfelder
  • Refail Kasimbeyli
    • Categories Multi-Criteria Optimization, Nonlinear Optimization Tags , , ,

    In this paper, proper optimality concepts in vector optimization with variable ordering structures are introduced for the first time and characterization results via scalarizations are given. New type of scalarizing functionals are presented and their properties are discussed. The scalarization approach suggested in the paper does not require convexity and boundedness conditions. CitationPreprint of the … Read more

    On the evaluation complexity of constrained nonlinear least-squares and general constrained nonlinear optimization using second-order methods

  • Coralia Cartis
  • Nicholas I. M. Gould
  • Philippe L. Toint
    • Categories Bound-constrained Optimization, Constrained Nonlinear Optimization, Nonlinear Systems and Least-Squares Tags , ,

    When solving the general smooth nonlinear optimization problem involving equality and/or inequality constraints, an approximate first-order critical point of accuracy $\epsilon$ can be obtained by a second-order method using cubic regularization in at most $O(\epsilon^{-3/2})$ problem-functions evaluations, the same order bound as in the unconstrained case. This result is obtained by first showing that the … Read more

    A Perturbed Sums of Squares Theorem for Polynomial Optimization and its Applications

  • Masakazu Muramatsu
  • Levent Tunçel
  • Hayato Waki
    • Categories Convex Optimization, Quadratic Programming, Semi-definite Programming

    We consider a property of positive polynomials on a compact set with a small perturbation. When applied to a Polynomial Optimization Problem (POP), the property implies that the optimal value of the corresponding SemiDefinite Programming (SDP) relaxation with sufficiently large relaxation order is bounded from below by $(f^¥ast – ¥epsilon)$ and from above by $f^¥ast … Read more

    Optimal scaling of the ADMM algorithm for distributed quadratic programming

  • Euhanna Ghadimi
  • Mikael Johansson
  • Henrik Sandberg
  • Iman Shames
  • André Teixeira
    • Categories Network Optimization, Quadratic Programming Tags ,

    This paper presents optimal scaling of the alternating directions method of multipliers (ADMM) algorithm for a class of distributed quadratic programming problems. The scaling corresponds to the ADMM step-size and relaxation parameter, as well as the edge-weights of the underlying communication graph. We optimize these parameters to yield the smallest convergence factor of the algorithm. … Read more

    Worst-case evaluation complexity of non-monotone gradient-related algorithms for unconstrained optimization

  • Coralia Cartis
  • Phillipe Sampaio
  • Philippe L. Toint
    • Categories Nonlinear Systems and Least-Squares, Unconstrained Optimization Tags , ,

    The worst-case evaluation complexity of finding an approximate first-order critical point using gradient-related non-monotone methods for smooth nonconvex and unconstrained problems is investigated. The analysis covers a practical linesearch implementation of these popular methods, allowing for an unknown number of evaluations of the objective function (and its gradient) per iteration. It is shown that this … Read more

    Trace-Penalty Minimization for Large-scale Eigenspace Computation

  • Xin Liu
  • Zaiwen Wen
  • Yin Zhang
  • Chao Yang
    • Categories Basic Sciences Applications, Constrained Nonlinear Optimization, Parallel Algorithms Tags , ,

    The Rayleigh-Ritz (RR) procedure, including orthogonalization, constitutes a major bottleneck in computing relatively high dimensional eigenspaces of large sparse matrices. Although operations involved in RR steps can be parallelized to a certain level, their parallel scalability, which is limited by some inherent sequential steps, is lower than dense matrix-matrix multiplications. The primary motivation of this … Read more

    Embedded Online Optimization for Model Predictive Control at Megahertz Rates

  • George A. Constantinides
  • Paul J. Goulart
  • Eric C. Kerrigan
  • Stefan Richter
  • Juan L. Jerez
  • Manfred Morari
    • Categories Parallel Algorithms, Quadratic Programming Tags , ,

    Faster, cheaper, and more power efficient optimization solvers than those currently offered by general-purpose solutions are required for extending the use of model predictive control (MPC) to resource-constrained embedded platforms. We propose several custom computational architectures for different first-order optimization methods that can handle linear-quadratic MPC problems with input, input-rate, and soft state constraints. We … Read more

    The Trust Region Subproblem with Non-Intersecting Linear Constraints

  • Samuel Burer
  • Boshi Yang
    • Categories Linear, Cone and Semidefinite Programming, Quadratic Programming, Second-Order Cone Programming Tags , , ,

    This paper studies an extended trust region subproblem (eTRS)in which the trust region intersects the unit ball with m linear inequality constraints. When m=0, m=1, or m=2 and the linear constraints are parallel, it is known that the eTRS optimal value equals the optimal value of a particular convex relaxation, which is solvable in polynomial … Read more

    A class of derivative-free nonmonotone optimization algorithms employing coordinate rotations and gradient approximations

  • Luigi Grippo
  • Francesco Rinaldi
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , ,

    In this paper we study a class of derivative-free unconstrained minimization algorithms employing nonmonotone inexact linesearch techniques along a set of suitable search directions. In particular, we define globally convergent nonmonotone versions of some well-known derivative-free methods and we propose a new algorithm combining coordinate rotations with approximate simplex gradients. Through extensive numerical experimentation, we … Read more

    A generalization of the Lowner-John’s ellipsoid theorem

  • Jean-Bernard Lasserre
    • Categories Convex Optimization, Nonlinear Optimization, Semi-definite Programming

    We address the following generalization $P$ of the Lowner-John’s ellipsoid problem. Given a (non necessarily convex) compact set $K\subset R^n$ and an even integer $d, find an homogeneous polynomial $g$ of degree $d$ such that $K\subset G:=\{x:g(x)\leq1\}$ and $G$ has minimum volume among all such sets. We show that $P$ is a convex optimization problem … Read more