Optimization and Control (math.OC)

Abstract: Bilevel optimization has become a powerful tool in a wide variety of machine learning problems. However, the current nonconvex bilevel optimization considers an offline dataset and static functions, which may not work well in emerging online applications with streaming data and time-varying functions. In this work, we study online bilevel optimization (OBO) where the functions can be time-varying and the agent continuously updates the decisions with online streaming data. To deal with the function variations and the unavailability of the true hypergradients in OBO, we propose a single-loop online bilevel optimizer with window averaging (SOBOW), which updates the outer-level decision based on a window average of the most recent hypergradient estimations stored in the memory. Compared to existing algorithms, SOBOW is computationally efficient and does not need to know previous functions. To handle the unique technical difficulties rooted in single-loop update and function variations for OBO, we develop a novel analytical technique that disentangles the complex couplings between decision variables, and carefully controls the hypergradient estimation error. We show that SOBOW can achieve a sublinear bilevel local regret under mild conditions. Extensive experiments across multiple domains corroborate the effectiveness of SOBOW.

Abstract: Increased flexibility in job shops leads to more complexity in decision-making for shop floor engineers. Partial Flexible Job Shop Scheduling (PFJSS) is a subset of Job shop problems and has substantial application in the real world. Priority Dispatching Rules (PDRs) are simple and easy to implement for making quick decisions in real-time. The present study proposes a novel method of integrating Multi-Criteria Decision Making (MCDM) methods and the Discrete Event Simulation (DES) Model to define job priorities in large-scale problems involving multiple criteria. DES approach is employed to model the PFJSS to evaluate Makespan, Flow Time, and Tardiness-based measures considering static and dynamic job arrivals. The proposed approach is implemented in a benchmark problem and large-scale PFJSS. The integration of MCDM methods and simulation models offers the flexibility to choose the parameters that need to govern the ranking of jobs. The solution given by the proposed methods is tested with the best-performing Composite Dispatching Rules (CDR), combining several PDR, which are available in the literature. Proposed MCDM approaches perform well for Makespan, Flow Time, and Tardiness-based measures for large-scale real-world problems. The proposed methodology integrated with the DES model is easy to implement in a real-time shop floor environment.

Abstract: A Line Replaceable Unit (LRU) is a collection of connected parts in a system that is replaced when any part of the LRU fails. Companies use LRUs as a mechanism to reduce downtime of systems following a failure. The design of LRUs determines how fast a replacement is performed, so a smart design reduces replacement and downtime cost. A firm must purchase/repair a LRU upon failure, and large LRUs are more expensive to purchase/repair. Hence, a firm seeks to design LRUs such that the average costs per time unit are minimized. We formalize this problem in a new model that captures how parts in a system are connected, and how they are disassembled from the system. Our model optimizes the design of LRUs such that the replacement (and downtime) costs and LRU purchase/repair costs are minimized. We present a set partitioning formulation for which we prove a rare result: the optimal solution is integer, despite a non--integral feasible polyhedron. Secondly, we formulate our problem as a binary linear program. The paper concludes by numerically comparing the computation times of both formulations and illustrates the effects of various parameters on the model's outcome.

Abstract: We present a method for the approximate propagation of mean and covariance of a probability distribution through ordinary differential equations (ODE) with discontinous right-hand side. For piecewise affine systems, a normalization of the propagated probability distribution at every time step allows us to analytically compute the expectation integrals of the mean and covariance dynamics while explicitly taking into account the discontinuity. This leads to a natural smoothing of the discontinuity such that for relevant levels of uncertainty the resulting ODE can be integrated directly with standard schemes and it is neither necessary to prespecify the switching sequence nor to use a switch detection method. We then show how this result can be employed in the more general case of piecewise smooth functions based on a structure preserving linearization scheme. The resulting dynamics can be straightforwardly used within standard formulations of stochastic optimal control problems with chance constraints.

Abstract: We propose a numerical algorithm for computing approximately optimal solutions of the matching for teams problem. Our algorithm is efficient for problems involving a large number of agent categories and allows for the measures describing the agent types to be non-discrete. Specifically, we parametrize the so-called transfer functions and develop a parametric version of the dual formulation. Our algorithm tackles this parametric formulation and produces feasible and approximately optimal solutions for the primal and dual formulations of the matching for teams problem. These solutions also yield upper and lower bounds for the optimal value, and the difference between the upper and lower bounds provides a direct sub-optimality estimate of the computed solutions. Moreover, we are able to control a theoretical upper bound on the sub-optimality to be arbitrarily close to 0 under mild conditions. We subsequently prove that the approximate primal and dual solutions converge when the sub-optimality goes to 0 and their limits constitute a true matching equilibrium. Thus, the outputs of our algorithm are regarded as an approximate matching equilibrium. We also analyze the theoretical computational complexity of our parametric formulation as well as the sparsity of the resulting approximate matching equilibrium. Through numerical experiments, we showcase that the proposed algorithm can produce high-quality approximate matching equilibria and is applicable to versatile settings, including a high-dimensional setting involving 100 agent categories.

Abstract: We present a branch-and-cut-and-price framework to solve Cutting Stock Problems with strong relaxations using Set Covering (Partition) Formulations, which are solved by column generation. We propose an extended Ryan-Foster branching scheme for non-binary models, a pricing algorithm that converges in a few iterations, and a variable selection algorithm based on branching history. These strategies are combined with subset-row cuts and custom primal heuristics to create a framework that overcomes the current state-of-the-art for the following problems: Cutting Stock, Skiving Stock, Ordered Open-End Bin Packing, Class-Constrained Bin Packing, and Identical Parallel Machines Scheduling with Minimum Makespan. Additionally, a new challenging benchmark for Cutting Stock is introduced.

Abstract: In the undetermined linear system $\bm{b}=\mathcal{A}(\bm{X})+\bm{s}$, vector $\bm{b}$ and operator $\mathcal{A}$ are the known measurements and $\bm{s}$ is the unknown noise. In this paper, we investigate sufficient conditions for exactly reconstructing desired matrix $\bm{X}$ being low-rank or approximately low-rank. We use the difference of nuclear norm and Frobenius norm ($L_{*-F}$) as a surrogate for rank function and establish a new nonconvex relaxation of such low rank matrix recovery, called the $L_{*-F}$ minimization, in order to approximate the rank function closer. For such nonconvex and nonsmooth constrained $L_{*-F}$ minimization problems, based on whether the noise level is $0$, we give the upper bound estimation of the recovery error respectively. Particularly, in the noise-free case, one sufficient condition for exact recovery is presented. If linear operator $\mathcal{A}$ satisfies the restricted isometry property with $\delta_{4r}<\frac{\sqrt{2r}-1}{\sqrt{2r}-1+\sqrt{2}(\sqrt{2r}+1)}$, then $r$-\textbf{rank} matrix $\bm{X}$ can be exactly recovered without other assumptions. In addition, we also take insights into the regularized $L_{*-F}$ minimization model since such regularized model is more widely used in algorithm design. We provide the recovery error estimation of this regularized $L_{*-F}$ minimization model via RIP tool. To our knowledge, this is the first result on exact reconstruction of low rank matrix via regularized $L_{*-F}$ minimization.

Abstract: Stochastic sequential quadratic optimization (SQP) methods for solving continuous optimization problems with nonlinear equality constraints have attracted attention recently, such as for solving large-scale data-fitting problems subject to nonconvex constraints. However, for a recently proposed subclass of such methods that is built on the popular stochastic-gradient methodology from the unconstrained setting, convergence guarantees have been limited to the asymptotic convergence of the expected value of a stationarity measure to zero. This is in contrast to the unconstrained setting in which almost-sure convergence guarantees (of the gradient of the objective to zero) can be proved for stochastic-gradient-based methods. In this paper, new almost-sure convergence guarantees for the primal iterates, Lagrange multipliers, and stationarity measures generated by a stochastic SQP algorithm in this subclass of methods are proved. It is shown that the error in the Lagrange multipliers can be bounded by the distance of the primal iterate to a primal stationary point plus the error in the latest stochastic gradient estimate. It is further shown that, subject to certain assumptions, this latter error can be made to vanish by employing a running average of the Lagrange multipliers that are computed during the run of the algorithm. The results of numerical experiments are provided to demonstrate the proved theoretical guarantees.

Abstract: This paper considers a risk-sensitive optimal control problem for a field-mediated interconnection of a quantum plant with a coherent (measurement-free) quantum controller. The plant and the controller are multimode open quantum harmonic oscillators governed by linear quantum stochastic differential equations, which are coupled to each other and driven by multichannel quantum Wiener processes modelling the external bosonic fields. The control objective is to internally stabilize the closed-loop system and minimize the infinite-horizon asymptotic growth rate of a quadratic-exponential functional which penalizes the plant variables and the controller output. We obtain first-order necessary conditions of optimality for this problem by computing the partial Frechet derivatives of the cost functional with respect to the energy and coupling matrices of the controller in frequency domain and state space. An infinitesimal equivalence between the risk-sensitive and weighted coherent quantum LQG control problems is also established. In addition to variational methods, we employ spectral factorizations and infinite cascades of auxiliary classical systems. Their truncations are applicable to numerical optimization algorithms (such as the gradient descent) for coherent quantum risk-sensitive feedback synthesis.