Search

Trust-region algorithms can be applied to very abstract optimization problems because they do not require a specific direction of descent or anti-gradient. This has lead to recent interest in them, in particular in the area of integer optimal control problems, where the infinite-dimensional problem formulations do not assume vector space structure. We analyze a trust-region algorithm in the abstract setting of a compact metric space, a setting in which integer optimal control problems with total variation regularization can be formulated in. Our analysis allows to avoid a reset of the trust-region radius upon acceptance of the iterates when proving convergence to stationary points. This reset has been present in previous analyses of trust-region algorithms for integer optimal control problems. Our computational benchmark shows that the runtime can be considerably improved when avoiding this reset, which is now theoretically justified.

Total variation integer optimal control problems admit solutions and necessary optimality conditions via geometric variational analysis. In spite of the existence of said solutions, algorithms which solve the discretized objective suffer from high numerical cost associated with the combinatorial nature of integer programming. Hence, such methods are often limited to small- and medium-sized problems. We propose a globally convergent, coordinate descent-inspired algorithm that allows tractable subproblem solutions restricted to a partition of the domain. Our decomposition method solves relatively small trust-region subproblems that modify the control variable on a subdomain only. Given sufficient subdomain overlap, we prove that first-order optimality is equivalent to first-order optimality per subdomain. We additionally show that sufficient decrease is achieved on a single subdomain by way of a trust region subproblem solver. We utilize this to prove convergence of our algorithm, which operates via greedy patch selection. Finally, our method demonstrates the capacity to accelerate large PDE-constrained integer control problems.

McCormick envelopes are a standard tool for deriving convex relaxations of optimization problems that involve polynomial terms. Such McCormick relaxations provide lower bounds, for example, in branch-and-bound procedures for mixed-integer nonlinear programs but have not gained much attention in PDE-constrained optimization so far. This lack of attention may be due to the distributed nature of such problems, which on the one hand leads to infinitely many linear constraints (generally state constraints that may be difficult to handle) in addition to the state equation for a pointwise formulation of the McCormick envelopes and renders bound-tightening procedures that successively improve the resulting convex relaxations computationally intractable. We analyze McCormick envelopes for a problem class that is governed by a semilinear PDE involving a bilinearity and integrality constraints. We approximate the nonlinearity by averaging the involved terms over the cells of a partition of the computational domain on which the PDE is defined. This yields convex relaxations that underestimate the original problem up to an a priori error estimate that depends on the mesh size of the discretization. These approximate McCormick relaxations can be improved by means of an optimization-based bound-tightening procedure. We show that their minimizers converge to minimizers to a limit problem with a pointwise formulation of the McCormick envelopes when driving the mesh size to zero. We provide a computational example, for which we certify all of our imposed assumptions. The results point to both the potential of the methodology and the gaps in the research that need to be closed.

Motivated by many applications, optimal control problems with integer controls have recently received a significant attention. Some state-of-the-art work uses perimeter-regularization to derive stationarity conditions and trust-region algorithms. However, the discretization is difficult in this case because the perimeter is concentrated on a set of dimension $d - 1$ for a domain of dimension $d$. This article proposes a potential way to overcome this challenge by using the fractional nonlocal perimeter with fractional exponent $0<\alpha<1$. In this way, the boundary integrals in the perimeter regularization are replaced by volume integrals. Besides establishing some non-trivial properties associated with this perimeter, a $\Gamma$-convergence result is derived. This result establishes convergence of minimizers of fractional perimeter-regularized problem, to the standard one, as the exponent $\alpha$ tends to 1. In addition, the stationarity results are derived and algorithmic convergence analysis is carried out for $\alpha \in (0.5,1)$ under an additional assumption on the gradient of the reduced objective. The theoretical results are supplemented by a preliminary computational experiment. We observe that the isotropy of the total variation may be approximated by means of the fractional perimeter functional.

We analyze integer linear programs which we obtain after discretizing two-dimensional subproblems arising from a trust-region algorithm for mixed integer optimal control problems with total variation regularization. We discuss NP-hardness of the discretized problems and the connection to graph-based problems. We show that the underlying polyhedron exhibits structural restrictions in its vertices with regards to which variables can attain fractional values at the same time. Based on this property, we derive cutting planes by employing a relation to shortest-path and minimum bisection problems. We propose a branching rule and a primal heuristic which improves previously found feasible points. We validate the proposed tools with a numerical benchmark in a standard integer programming solver. We observe a significant speedup for medium-sized problems. Our results give hints for scaling towards larger instances in the future.

We introduce discretizations of infinite-dimensional optimization problems with total variation regularization and integrality constraints on the optimization variables. We advance the discretization of the dual formulation of the total variation term with Raviart--Thomas functions which is known from literature for certain convex problems. Since we have an integrality constraint, the previous analysis from Caillaud and Chambolle [10] does not hold anymore. Even weaker $\Gamma$-convergence results do not hold anymore because the recovery sequences generally need to attain non-integer values to recover the total variation of the limit function. We solve this issue by introducing a discretization of the input functions on an embedded, finer mesh. A superlinear coupling of the mesh sizes implies an averaging on the coarser mesh of the Raviart--Thomas ansatz, which enables to recover the total variation of integer-valued limit functions with integer-valued discretized input functions. Moreover, we are able to estimate the discretized total variation of the recovery sequence by the total variation of its limit and an error depending on the mesh size ratio. For the discretized optimization problems, we additionally add a constraint that vanishes in the limit and enforces compactness of the sequence of minimizers, which yields their convergence to a minimizer of the original problem. This constraint contains a degree of freedom whose admissible range is determined. Its choice may have a strong impact on the solutions in practice as we demonstrate with an example from imaging., Comment: 22 pages, 3 figures

The SCIP Optimization Suite provides a collection of software packages for mathematical optimization, centered around the constraint integer programming (CIP) framework SCIP. This report discusses the enhancements and extensions included in the SCIP Optimization Suite 9.0. The updates in SCIP 9.0 include improved symmetry handling, additions and improvements of nonlinear handlers and primal heuristics, a new cut generator and two new cut selection schemes, a new branching rule, a new LP interface, and several bug fixes. The SCIP Optimization Suite 9.0 also features new Rust and C++ interfaces for SCIP, new Python interface for SoPlex, along with enhancements to existing interfaces. The SCIP Optimization Suite 9.0 also includes new and improved features in the LP solver SoPlex, the presolving library PaPILO, the parallel framework UG, the decomposition framework GCG, and the SCIP extension SCIP-SDP. These additions and enhancements have resulted in an overall performance improvement of SCIP in terms of solving time, number of nodes in the branch-and-bound tree, as well as the reliability of the solver., Comment: The release report of the SCIP Optimization Suite version 9.0

We consider optimal control problems that have binary-valued control input functions and a perimeter regularization. We develop and analyze a trust-region algorithm that solves a sequence of subproblems in which the regularization term and the binarity constraint are relaxed by a non-convex energy functional. We show how the parameter that controls the distinctiveness of the resulting phase field can be coupled to the trust-region radius updates and be driven to zero over the course of the iterations in order to obtain convergence to stationary points of the limit problem under suitable regularity assumptions. Finally, we highlight and discuss the assumptions and restrictions of our approach and provide the first computational results for a motivating application in the field of control of acoustic waves in dissipative media.

The combinatorial integral approximation (CIA) is a solution technique for integer optimal control problems. In order to regularize the solutions produced by CIA, one can minimize switching costs in one of its algorithmic steps. This leads to combinatorial optimization problems, which are called switching cost aware rounding problems (SCARP). They can be solved efficiently on one-dimensional domains but no efficient solution algorithms have been found so far for multi-dimensional domains. The CIA problem formulation depends on a discretization grid. We propose to reduce the number of variables and thus improve the computational tractability of SCARP by means of a non-uniform grid refinement strategy. We prove that the grid refinement preserves the approximation properties of the combinatorial integral approximation. Computational results are offered to show that the proposed approach is able to achieve, within a prescribed time limit, smaller duality gaps that does the uniform approach. For several large instances, a dual bound could only be obtained through adaptivity.

Gradient-based methods have been highly successful for solving a variety of both unconstrained and constrained nonlinear optimization problems. In real-world applications, such as optimal control or machine learning, the necessary function and derivative information may be corrupted by noise, however. Sun and Nocedal have recently proposed a remedy for smooth unconstrained problems by means of a stabilization of the acceptance criterion for computed iterates, which leads to convergence of the iterates of a trust-region method to a region of criticality, Sun and Nocedal (2022). We extend their analysis to the successive linear programming algorithm, Byrd et al. (2023a,2023b), for unconstrained optimization problems with objectives that can be characterized as the composition of a polyhedral function with a smooth function, where the latter and its gradient may be corrupted by noise. This gives the flexibility to cover, for example, (sub)problems arising image reconstruction or constrained optimization algorithms. We provide computational examples that illustrate the findings and point to possible strategies for practical determination of the stabilization parameter that balances the size of the critical region with a relaxation of the acceptance criterion (or descent property) of the algorithm.

We consider optimal control problems with integer-valued controls and a total variation regularization penalty in the objective on domains of dimension two or higher. The penalty yields that the feasible set is sequentially closed in the weak-$^*$ and closed in the strict topology in the space of functions of bounded variation. In turn, we derive first-order optimality conditions of the optimal control problem as well as trust-region subproblems with partially linearized model functions using local variations of the level sets of the feasible control functions. We also prove that a recently proposed function space trust-region algorithm -- sequential linear integer programming -- produces sequences of iterates whose limits are first-order optimal points., Comment: 25 pages

This paper is concerned with an optimization problem that is constrained by the Kantorovich optimal transportation problem. This bilevel optimization problem can be reformulated as a mathematical problem with complementarity constraints in the space of regular Borel measures. Because of the non-smoothness induced by the complementarity relations, problems of this type are frequently regularized. Here we apply a quadratic regularization of the Kantorovich problem. As the title indicates, this is the second part in a series of three papers. While the existence of optimal solutions to both the bilevel Kantorovich problem and its regularized counterpart were shown in the first part, this paper deals with the (weak-*) convergence of solutions to the regularized bilevel problem to solutions of the original bilevel Kantorovich problem., Comment: 21 pages, 0 figures

We revisit a class of integer optimal control problems for which a trust-region method has been proposed and analyzed in arXiv:2106.13453v3 [math.OC]. While the algorithm proposed in arXiv:2106.13453v3 [math.OC] successfully solves the class of optimization problems under consideration, its convergence analysis requires restrictive regularity assumptions. There are many examples of integer optimal control problems involving partial differential equations where these regularity assumptions are not satisfied. In this article we provide a way to bypass the restrictive regularity assumptions by introducing an additional partial regularization of the control inputs by means of mollification and proving a $\Gamma$-convergence-type result when the support parameter of the mollification is driven to zero. We highlight the applicability of this theory in the case of fluid flows through deformable porous media equations that arise in biomechanics. We show that the regularity assumptions are violated in the case of poro-visco-elastic systems, and thus one needs to use the regularization of the control input introduced in this article. Associated numerical results show that while the homotopy can help to find better objective values and points of lower instationarity, the practical performance of the algorithm without the input regularization may be on par with the homotopy.

We consider a class of integer linear programs (IPs) that arise as discretizations of trust-region subproblems of a trust-region algorithm for the solution of control problems, where the control input is an integer-valued function on a one-dimensional domain and is regularized with a total variation term in the objective, which may be interpreted as a penalization of switching costs between different control modes. We prove that solving an instance of the considered problem class is equivalent to solving a resource constrained shortest path problem (RCSPP) on a layered directed acyclic graph. This structural finding yields an algorithmic solution approach based on topological sorting and corresponding run time complexities that are quadratic in the number of discretization intervals of the underlying control problem, the main quantifier for the size of a problem instance. We also consider the solution of the RCSPP with an $A^*$ algorithm. Specifically, the analysis of a Lagrangian relaxation yields a consistent heuristic function for the $A^*$ algorithm and a preprocessing procedure, which can be employed to accelerate the $A^*$ algorithm for the RCSPP without losing optimality of the computed solution. We generate IP instances by executing the trust-region algorithm on several integer optimal control problems. The numerical results show that the accelerated $A^*$ algorithm and topological sorting outperform a general purpose IP solver significantly. Moreover, the accelerated $A^*$ algorithm is able to outperform topological sorting for larger problem instances., Comment: 25 pages, 6 figures

Recent work has focused on data-driven learning of the evolution of unknown systems via deep neural networks (DNNs), with the goal of conducting long time prediction of the evolution of the unknown system. Training a DNN with low generalization error is a particularly important task in this case as error is accumulated over time. Because of the inherent randomness in DNN training, chiefly in stochastic optimization, there is uncertainty in the resulting prediction, and therefore in the generalization error. Hence, the generalization error can be viewed as a random variable with some probability distribution. Well-trained DNNs, particularly those with many hyperparameters, typically result in probability distributions for generalization error with low bias but high variance. High variance causes variability and unpredictably in the results of a trained DNN. This paper presents a computational technique which decreases the variance of the generalization error, thereby improving the reliability of the DNN model to generalize consistently. In the proposed ensemble averaging method, multiple models are independently trained and model predictions are averaged at each time step. A mathematical foundation for the method is presented, including results regarding the distribution of the local truncation error. In addition, three time-dependent differential equation problems are considered as numerical examples, demonstrating the effectiveness of the method to decrease variance of DNN predictions generally.

Binary trust-region steepest descent (BTR) and combinatorial integral approximation (CIA) are two recently investigated approaches for the solution of optimization problems with distributed binary-/discrete-valued variables (control functions). We show improved convergence results for BTR by imposing a compactness assumption that is similar to the convergence theory of CIA. As a corollary we conclude that BTR also constitutes a descent algorithm on the continuous relaxation and its iterates converge weakly-$^*$ to stationary points of the latter. We provide computational results that validate our findings. In addition, we observe a regularizing effect of BTR, which we explore by means of a hybridization of CIA and BTR.

We discuss several topics related to polylogarithms with focus on dilogarithms. The topics are: a generating function with harmonic numbers coming from Ramanujan, extending the dilogarithm to complex numbers beyond the unit disk, and relating polylogarithms to Bernoulli polynomials and to solitons. Several improvements and corrections are made to existing representations.