Nonlinear Optimization

An Inertial Block Majorization Minimization Framework for Nonsmooth Nonconvex Optimization

  • Nicolas Gillis
  • Le Thi Khanh Hien
  • Duy Nhat Phan
    • Categories Constrained Nonlinear Optimization Tags , , , , ,

    In this paper, we introduce TITAN, a novel inerTial block majorIzation minimization framework for non-smooth non-convex opTimizAtioN problems. TITAN is a block coordinate method (BCM) that embeds inertial force to each majorization-minimization step of the block updates. The inertial force is obtained via an extrapolation operator that subsumes heavy-ball and Nesterov-type accelerations for block proximal … Read more

    A Noise-Tolerant Quasi-Newton Method for Unconstrained Optimization

  • Richard H. Byrd
  • Jorge Nocedal
  • Hao-Jun Shi
  • Yuchen Xie
    • Categories Unconstrained Optimization Tags , , ,

    This paper describes an extension of the BFGS and L-BFGS methods for the minimization of a nonlinear function subject to errors. This work is motivated by applications that contain computational noise, employ low-precision arithmetic, or are subject to statistical noise. The classical BFGS and L-BFGS methods can fail in such circumstances because the updating procedure … Read more

    Tight bounds on the maximal perimeter and the maximal width of convex small polygons

  • Christian Bingane
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Quadratic Programming Tags , , , , ,

    A small polygon is a polygon of unit diameter. The maximal perimeter and the maximal width of a convex small polygon with $n=2^s$ vertices are not known when $s \ge 4$. In this paper, we construct a family of convex small $n$-gons, $n=2^s$ and $s\ge 3$, and show that the perimeters and the widths obtained … Read more

    Optimization with Least Constraint Violation

  • Yu-Hong Dai
  • Liwei Zhang
    • Categories Nonlinear Optimization Tags , , , ,

    Study about theory and algorithms for constrained optimization usually assumes that the feasible region of the optimization problem is nonempty. However, there are many important practical optimization problems whose feasible regions are not known to be nonempty or not, and optimizers of the objective function with the least constraint violation prefer to be found. A … Read more

    Optimizing hypergraph-based polynomials modeling job-occupancy in queueing with redundancy scheduling

  • Daniel Brosch
  • Monique Laurent
  • Andries Steenkamp
    • Categories Constrained Nonlinear Optimization Tags , , ,

    We investigate two classes of multivariate polynomials with variables indexed by the edges of a uniform hypergraph and coefficients depending on certain patterns of union of edges. These polynomials arise naturally to model job-occupancy in some queuing problems with redundancy scheduling policy. The question, posed by Cardinaels, Borstand van Leeuwaarden (arXiv:2005.14566, 2020), is to decide … Read more

    A family of optimal weighted conjugate-gradient-type methods for strictly convex quadratic minimization

  • Roberto Andreani
  • Harry Oviedo
  • Marcos Raydan
    • Categories Unconstrained Optimization Tags , , , ,

    We introduce a family of weighted conjugate-gradient-type methods, for strictly convex quadratic functions, whose parameters are determined by a minimization model based on a convex combination of the objective function and its gradient norm. This family includes the classical linear conjugate gradient method and the recently published delayed weighted gradient method as the extreme cases … Read more

    Strengthened SDP Relaxation for an Extended Trust Region Subproblem with an Application to Optimal Power Flow

  • Samuel Burer
  • Anders Eltved
    • Categories Quadratic Programming, Semi-definite Programming Tags ,

    We study an extended trust region subproblem minimizing a nonconvex function over the hollow ball $r \le \|x\| \le R$ intersected with a full-dimensional second order cone (SOC) constraint of the form $\|x – c\| \le b^T x – a$. In particular, we present a class of valid cuts that improve existing semidefinite programming (SDP) … Read more

    Global optimality in minimum compliance topology optimization of frames and shells by moment-sum-of-squares hierarchy

  • Didier Henrion
  • Martin Kružík
  • Marek Tyburec
  • Jan Zeman
    • Categories Civil and Environmental Engineering, Constrained Nonlinear Optimization, Semi-definite Programming Tags , , , , ,

    The design of minimum-compliance bending-resistant structures with continuous cross-section parameters is a challenging task because of its inherent non-convexity. Our contribution develops a strategy that facilitates computing all guaranteed globally optimal solutions for frame and shell structures under multiple load cases and self-weight. To this purpose, we exploit the fact that the stiffness matrix is … Read more

    Mixed-Projection Conic Optimization: A New Paradigm for Modeling Rank Constraints

  • Dimitris Bertsimas
  • Ryan Cory-Wright
  • Jean Pauphilet
    • Categories Cutting Plane Approaches, Linear, Cone and Semidefinite Programming, Nonlinear Optimization Tags , ,

    We propose a framework for modeling and solving low-rank optimization problems to certifiable optimality. We introduce symmetric projection matrices that satisfy $Y^2 = Y$, the matrix analog of binary variables that satisfy $z^2 = z$, to model rank constraints. By leveraging regularization and strong duality, we prove that this modeling paradigm yields tractable convex optimization … Read more

    A structured modified Newton approach for solving systems of nonlinear equations arising in interior-point methods for quadratic programming

  • David Ek
  • Anders Forsgren
    • Categories Quadratic Programming Tags , , , ,

    The focus in this work is interior-point methods for quadratic optimization problems with linear inequality constraints where the system of nonlinear equations that arise are solved with Newton-like methods. In particular, the concern is the system of linear equations to be solved at each iteration. Newton systems give high quality solutions but there is an … Read more