Nonlinear Optimization

Substantiation of the Backpropagation Technique via the Hamilton-Pontryagin Formalism for Training Nonconvex Nonsmooth Neural Networks

  • Vladimir I. Norkin
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization, Stochastic Programming Tags , , , , ,

    The paper observes the similarity between the stochastic optimal control of discrete dynamical systems and the training multilayer neural networks. It focuses on contemporary deep networks with nonconvex nonsmooth loss and activation functions. In the paper, the machine learning problems are treated as nonconvex nonsmooth stochastic optimization problems. As a model of nonsmooth nonconvex dependences, … Read more

    On the Convergence to Stationary Points of Deterministic and Randomized Feasible Descent Directions Methods

  • Amir Beck
  • Nadav Hallak
    • Categories Constrained Nonlinear Optimization Tags , ,

    This paper studies the class of nonsmooth nonconvex problems in which the difference between a continuously differentiable function and a convex nonsmooth function is minimized over linear constraints. Our goal is to attain a point satisfying the stationarity necessary optimality condition, defined as the lack of feasible descent directions. Although elementary in smooth optimization, this … Read more

    Finding Second-Order Stationary Points in Constrained Minimization: A Feasible Direction Approach

  • Nadav Hallak
  • Marc Teboulle
    • Categories Constrained Nonlinear Optimization Tags , ,

    This paper introduces a method for computing points satisfying the second-order necessary optimality conditions in constrained nonconvex minimization. The method comprises two independent steps corresponding to the first and second order conditions. The first-order step is a generic closed map algorithm which can be chosen from a variety of first-order algorithms, making it The second-order … Read more

    A relaxed interior point method for low-rank semidefinite programming problems with applications to matrix completion

  • Stefania Bellavia
  • Jacek Gondzio
  • Margherita Porcelli
    • Categories Nonlinear Systems and Least-Squares, Semi-definite Programming Tags , , ,

    A new relaxed variant of interior point method for low-rank semidefinite programming problems is proposed in this paper. The method is a step outside of the usual interior point framework. In anticipation to converging to a low-rank primal solution, a special nearly low-rank form of all primal iterates is imposed. To accommodate such a (restrictive) … Read more

    Mixed-Integer Optimal Control under Minimum Dwell Time Constraints

  • Nicolò Robuschi
  • Sebastian Sager
  • Clemens Zeile
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Systems governed by Differential Equations Optimization Tags , , , , ,

    Tailored mixed-integer optimal control policies for real-world applications usually have to avoid very short successive changes of the active integer control. Minimum dwell time constraints express this requirement and can be included into the combinatorial integral approximation decomposition, which solves mixed-integer optimal control problems by solving one continuous nonlinear program and one mixed-integer linear program. … Read more

    An algorithm for optimization with disjoint linear constraints and its application for predicting rain

  • Tijana Janjic
  • Philippe L. Toint
  • Yvonne Ruckstuhl
    • Categories Basic Sciences Applications, Quadratic Programming Tags ,

    A specialized algorithm for quadratic optimization (QO, or, formerly, QP) with disjoint linear constraints is presented. In the considered class of problems, a subset of variables are subject to linear equality constraints, while variables in a different subset are constrained to remain in a convex set. The proposed algorithm exploits the structure by combining steps … Read more

    An Average Curvature Accelerated Composite Gradient Method for Nonconvex Smooth Composite Optimization Problems

  • Jiaming Liang
  • Renato D.C. Monteiro
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , ,

    This paper presents an accelerated composite gradient (ACG) variant, referred to as the AC-ACG method, for solving nonconvex smooth composite minimization problems. As opposed to well-known ACG variants that are either based on a known Lipschitz gradient constant or a sequence of maximum observed curvatures, the current one is based on a sequence of average … Read more

    Tight compact extended relaxations for nonconvex quadratic programming problems with box constraints

  • Sven de Vries
  • Bernd Perscheid
    • Categories (Mixed) Integer Nonlinear Programming, Graphs and Matroids, Quadratic Programming Tags ,

    Cutting planes from the Boolean Quadric Polytope (BQP) can be used to reduce the optimality gap of the NP-hard nonconvex quadratic program with box constraints (BoxQP). It is known that all cuts of the Chvátal-Gomory closure of the BQP are A-odd cycle inequalities. We obtain a compact extended relaxation of all A-odd cycle inequalities, which … Read more

    Simultaneous iterative solutions for the trust-region and minimum eigenvalue subproblem

  • Ioannis G. Akrotirianakis
  • Joshua D. Griffin
  • Melanie Gratton
  • Seyedalireza Yektamaram
  • Wenwen Zhou
    • Categories Nonlinear Optimization

    Given the inability to foresee all possible scenarios, it is justified to desire an efficient trust-region subproblem solver capable of delivering any desired level of accuracy on demand; that is, the accuracy obtainable for a given trust-region subproblem should not be partially dependent on the problem itself. Current state-of-the-art iterative eigensolvers all fall into the … Read more

    Derivative-Free Superiorization: Principle and Algorithm

  • Yair Censor
  • Elias Salomão Helou
  • Edgar Garduño
  • Gabor T. Herman
    • Categories Basic Sciences Applications, Constrained Nonlinear Optimization, Convex and Nonsmooth Optimization

    The superiorization methodology is intended to work with input data of constrained minimization problems, that is, a target function and a set of constraints. However, it is based on an antipodal way of thinking to what leads to constrained minimization methods. Instead of adapting unconstrained minimization algorithms to handling constraints, it adapts feasibility-seeking algorithms to … Read more