Nonlinear Optimization

Approximation Properties of Sum-Up Rounding in the Presence of Vanishing Constraints

  • Christian Kirches
  • Felix Lenders
  • Paul Manns
    • Categories (Mixed) Integer Nonlinear Programming, Approximation Algorithms, Systems governed by Differential Equations Optimization Tags , ,

    Approximation algorithms like sum-up rounding that allow to compute integer-valued approximations of the continuous controls in a weak$^*$ sense have attracted interest recently. They allow to approximate (optimal) feasible solutions of continuous relaxations of mixed-integer control problems (MIOCPs) with integer controls arbitrarily close. To this end, they use compactness properties of the underlying state equation, … Read more

    Complexity of gradient descent for multiobjective optimization

  • Jörg Fliege
  • A. Ismael F. Vaz
  • Luis Nunes Vicente
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , , ,

    A number of first-order methods have been proposed for smooth multiobjective optimization for which some form of convergence to first order criticality has been proved. Such convergence is global in the sense of being independent of the starting point. In this paper we analyze the rate of convergence of gradient descent for smooth unconstrained multiobjective … Read more

    Block Coordinate Proximal Gradient Method for Nonconvex Optimization Problems: Convergence Analysis

  • Xiangfeng Wang
  • Xiao-Ming Yuan
  • Shangzhi Zeng
  • Jin Zhang
  • Jinchuan Zhou
    • Categories Nonlinear Optimization, Nonsmooth Optimization Tags , ,

    We propose a block coordinate proximal gradient method for a composite minimization problem with two nonconvex function components in the objective while only one of them is assumed to be differentiable. Under some per-block Lipschitz-like conditions based on Bregman distance, but without the global Lipschitz continuity of the gradient of the differentiable function, we prove … Read more

    A Merit Function Approach for Evolution Strategies

  • Youssef Diouane
    • Categories Constrained Nonlinear Optimization Tags , , ,

    In this paper, we extend a class of globally convergent evolution strategies to handle general constrained optimization problems. The proposed framework handles relaxable constraints using a merit function approach combined with a specific restoration procedure. The unrelaxable constraints in our framework, when present, are treated either by using the extreme barrier function or through a … Read more

    Derivative-Free Superiorization With Component-Wise Perturbations

  • Yair Censor
  • Howard Heaton
  • Reinhard W. Schulte
    • Categories Biomedical Applications, Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , , , ,

    Superiorization reduces, not necessarily minimizes, the value of a target function while seeking constraints-compatibility. This is done by taking a solely feasibility-seeking algorithm, analyzing its perturbations resilience, and proactively perturbing its iterates accordingly to steer them toward a feasible point with reduced value of the target function. When the perturbation steps are computationally efficient, this … Read more

    Improving the Flexibility and Robustness of Model-Based Derivative-Free Optimization Solvers

  • Coralia Cartis
  • Jan Fiala
  • Benjamin Marteau
  • Lindon Roberts
    • Categories Nonlinear Optimization Tags , , , , ,

    We present DFO-LS, a software package for derivative-free optimization (DFO) for nonlinear Least-Squares (LS) problems, with optional bound constraints. Inspired by the Gauss-Newton method, DFO-LS constructs simplified linear regression models for the residuals. DFO-LS allows flexible initialization for expensive problems, whereby it can begin making progress from as few as two objective evaluations. Numerical results … Read more

    Derivative-Free Optimization of Noisy Functions via Quasi-Newton Methods

  • Albert S. Berahas
  • Richard H. Byrd
  • Jorge Nocedal
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , ,

    This paper presents a finite difference quasi-Newton method for the minimization of noisy functions. The method takes advantage of the scalability and power of BFGS updating, and employs an adaptive procedure for choosing the differencing interval h based on the noise estimation techniques of Hamming (2012) and Moré and Wild (2011). This noise estimation procedure … Read more

    A Dynamic Penalty Parameter Updating Strategy for Matrix-Free Sequential Quadratic Optimization

  • James V. Burke
  • Frank E. Curtis
  • Jiashan Wang
  • Hao Wang
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , , ,

    This paper focuses on the design of sequential quadratic optimization (commonly known as SQP) methods for solving large-scale nonlinear optimization problems. The most computationally demanding aspect of such an approach is the computation of the search direction during each iteration, for which we consider the use of matrix-free methods. In particular, we develop a method … Read more

    On the Complexity of Testing Attainment of the Optimal Value in Nonlinear Optimization

  • Amir Ali Ahmadi
  • Jeffrey Zhang
    • Categories Global Optimization Theory, Nonlinear Optimization, Semi-definite Programming Tags , , , , ,

    We prove that unless P=NP, there exists no polynomial time (or even pseudo-polynomial time) algorithm that can test whether the optimal value of a nonlinear optimization problem where the objective and constraints are given by low-degree polynomials is attained. If the degrees of these polynomials are fixed, our results along with previously-known “Frank-Wolfe type” theorems … Read more

    Solving Quadratic Programs to High Precision using Scaled Iterative Refinement

  • Ambros Gleixner
  • Sebastian Sager
  • Tobias Weber
    • Categories Quadratic Programming Tags , , ,

    Quadratic optimization problems (QPs) are ubiquitous, and solution algorithms have matured to a reliable technology. However, the precision of solutions is usually limited due to the underlying floating-point operations. This may cause inconveniences when solutions are used for rigorous reasoning. We contribute on three levels to overcome this issue. First, we present a novel refinement … Read more