Optimization and Control (math.OC)

Abstract: In appropriate frameworks, automatic differentiation is transparent to the user at the cost of being a significant computational burden when the number of operations is large. For iterative algorithms, implicit differentiation alleviates this issue but requires custom implementation of Jacobian evaluation. In this paper, we study one-step differentiation, also known as Jacobian-free backpropagation, a method as easy as automatic differentiation and as performant as implicit differentiation for fast algorithms (e.g., superlinear optimization methods). We provide a complete theoretical approximation analysis with specific examples (Newton's method, gradient descent) along with its consequences in bilevel optimization. Several numerical examples illustrate the well-foundness of the one-step estimator.

Abstract: In this paper we extend the previously introduced class of boundary port-Hamiltonian systems to boundary control systems where the variational derivative of the Hamiltonian functional is replaced by a pair of reciprocal differential operators. In physical systems modelling, these differential operators naturally represent the constitutive relations associated with the implicitly defined energy of the system and obey Maxwell's reciprocity conditions. On top of the boundary variables associated with the Stokes-Dirac structure, this leads to additional boundary port variables and to the new notion of a Stokes-Lagrange subspace. This extended class of boundary port-Hamiltonian systems is illustrated by a number of examples in the modelling of elastic rods with local and non-local elasticity relations. Finally it shown how a Hamiltonian functional on an extended state space can be associated with the Stokes-Lagrange subspace, and how this leads to an energy balance equation involving the boundary variables of the Stokes-Dirac structure as well as of the Stokes-Lagrange subspace.

Abstract: We consider two formulations for distributed optimization wherein $N$ agents in a generic connected network solve a problem of common interest: distributed personalized optimization and consensus optimization. A new method termed DINAS (Distributed Inexact Newton method with Adaptive Stepsize) is proposed. DINAS employs large adaptively computed step-sizes, requires a reduced global parameters knowledge with respect to existing alternatives, and can operate without any local Hessian inverse calculations nor Hessian communications. When solving personalized distributed learning formulations, DINAS achieves quadratic convergence with respect to computational cost and linear convergence with respect to communication cost, the latter rate being independent of the local functions condition numbers or of the network topology. When solving consensus optimization problems, DINAS is shown to converge to the global solution. Extensive numerical experiments demonstrate significant improvements of DINAS over existing alternatives. As a result of independent interest, we provide for the first time convergence analysis of the Newton method with the adaptive Polyak's step-size when the Newton direction is computed inexactly in centralized environment.

Abstract: This paper investigates the column generation (CG) for solving cutting stock problems (CSP). Traditional CG method, which repeatedly solves a restricted master problem (RMP), often suffers from two critical issues in practice -- the loss of solution quality introduced by linear relaxation of both feasible domain and objective and the high time cost of last iterations close to convergence. We empirically find that the first issue is common in ordinary CSPs with linear cutting constraints, while the second issue is especially severe in CSPs with nonlinear cutting constraints that are often generated by approximating chance constraints. We propose an alternative approach, ensembles of multiple column generation processes. In particular, we present two methods -- \mc (multi-column) which return multiple feasible columns in each RMP iteration, and \mt (multi-path) which restarts the RMP iterations from different initialized column sets once the iteration time exceeds a given time limit. The ideas behind are same: leverage the multiple column generation pathes to compensate the loss induced by relaxation, and add earlier sub-optimal columns to accelerate convergence of RMP iterations. Besides, we give theoretical analysis on performance improvement guarantees. Experiments on cutting stock problems demonstrate that compared to traditional CG, our method achieves significant run-time reduction on CSPs with nonlinear constraints, and dramatically improves the ratio of solve-to-optimal on CSPs with linear constraints.

Abstract: We introduce a new workflow for unconstrained optimization whereby objective functions are mapped onto a physical domain to more easily design algorithms that are robust to hyperparameters and achieve fast convergence rates. Specifically, we represent optimization problems as an equivalent circuit that are then solved solely as nonlinear circuits using robust solution methods. The equivalent circuit models the trajectory of component-wise scaled gradient flow problem as the transient response of the circuit for which the steady-state coincides with a critical point of the objective function. The equivalent circuit model leverages circuit domain knowledge to methodically design new optimization algorithms that would likely not be developed without a physical model. We incorporate circuit knowledge into optimization methods by 1) enhancing the underlying circuit model for fast numerical analysis, 2) controlling the optimization trajectory by designing the nonlinear circuit components, and 3) solving for step sizes using well-known methods from the circuit simulation. We first establish the necessary conditions that the controls must fulfill for convergence. We show that existing descent algorithms can be re-derived as special cases of this approach and derive new optimization algorithms that are developed with insights from a circuit-based model. The new algorithms can be designed to be robust to hyperparameters, achieve convergence rates comparable or faster than state of the art methods, and are applicable to optimizing a variety of both convex and nonconvex problems.

Abstract: The subgradient method is one of the most fundamental algorithmic schemes for nonsmooth optimization. The existing complexity and convergence results for this algorithm are mainly derived for Lipschitz continuous objective functions. In this work, we first extend the typical complexity results for the subgradient method to convex and weakly convex minimization without assuming Lipschitz continuity. Specifically, we establish $\mathcal{O}(1/\sqrt{T})$ bound in terms of the suboptimality gap ``$f(x) - f^*$'' for convex case and $\mathcal{O}(1/{T}^{1/4})$ bound in terms of the gradient of the Moreau envelope function for weakly convex case. Furthermore, we provide convergence results for non-Lipschitz convex and weakly convex objective functions using proper diminishing rules on the step sizes. In particular, when $f$ is convex, we show $\mathcal{O}(\log(k)/\sqrt{k})$ rate of convergence in terms of the suboptimality gap. With an additional quadratic growth condition, the rate is improved to $\mathcal{O}(1/k)$ in terms of the squared distance to the optimal solution set. When $f$ is weakly convex, asymptotic convergence is derived. The central idea is that the dynamics of properly chosen step sizes rule fully controls the movement of the subgradient method, which leads to boundedness of the iterates, and then a trajectory-based analysis can be conducted to establish the desired results. To further illustrate the wide applicability of our framework, we extend the complexity results to the truncated subgradient, the stochastic subgradient, the incremental subgradient, and the proximal subgradient methods for non-Lipschitz functions.