Optimization and Control (math.OC)

Abstract: The number of new cancer cases is expected to increase by about 50% in the next 20 years, and the need for chemotherapy treatments will increase accordingly. Chemotherapy treatments are usually performed in outpatient cancer centers where patients affected by different types of tumors are treated. The treatment delivery must be carefully planned to optimize the use of limited resources, such as drugs, medical and nursing staff, consultation and exam rooms, and chairs and beds for the drug infusion. Planning and scheduling chemotherapy treatments involve different problems at different decision levels. In this work, we focus on the patient chemotherapy multi-appointment planning and scheduling problem at an operational level, namely the problem of determining the day and starting time of the oncologist visit and drug infusion for a set of patients to be scheduled along a short-term planning horizon. We use a per-pathology paradigm, where the days of the week in which patients can be treated, depending on their pathology, are known. We consider different metrics and formulate the problem as a multi-objective optimization problem tackled by sequentially solving three problems in a lexicographic multi-objective fashion. The ultimate aim is to minimize the patient's discomfort. The problems turn out to be computationally challenging, thus we propose bounds and ad-hoc approaches, exploiting alternative problem formulations, decomposition, and $k$-opt search. The approaches are tested on real data from an Italian outpatient cancer center and outperform state-of-the-art solvers.

Abstract: In this paper, we carry out the analysis of the semismooth Newton method for bilinear control problems related to semilinear elliptic PDEs. We prove existence, uniqueness and regularity for the solution of the state equation, as well as differentiability properties of the control to state mapping. Then, first and second order optimality conditions are obtained. Finally, we prove the superlinear convergence of the semismooth Newton method to local solutions satisfying no-gap second order sufficient optimality conditions as well as a strict complementarity condition.

Abstract: We study an online mixed discrete and continuous optimization problem where a decision maker interacts with an unknown environment for a number of $T$ rounds. At each round, the decision maker needs to first jointly choose a discrete and a continuous actions and then receives a reward associated with the chosen actions. The goal for the decision maker is to maximize the accumulative reward after $T$ rounds. We propose algorithms to solve the online mixed discrete and continuous optimization problem and prove that the algorithms yield sublinear regret in $T$. We show that a wide range of applications in practice fit into the framework of the online mixed discrete and continuous optimization problem, and apply the proposed algorithms to solve these applications with regret guarantees. We validate our theoretical results with numerical experiments.

Abstract: Tulipa Energy Model aims to optimise the investment and operation of the electricity market, considering its coupling with other sectors, such as hydrogen and heat, that can also be electrified. The problem is analysed from the perspective of a central planner who determines the expansion plan that is most beneficial for the system as a whole, either by maximising social welfare or by minimising total costs. The formulation provides a general description of the objective function and constraints in the optimisation model based on the concept of energy assets representing any element in the model. The model uses subsets and specific methods to determine the constraints that apply to a particular technology or network, allowing more flexibility in the code to consider new technologies and constraints with different levels of detail in the future.

Abstract: Several recent works address the impact of inexact oracles in the convergence analysis of modern first-order optimization techniques, e.g. Bregman Proximal Gradient and Prox-Linear methods as well as their accelerated variants, extending their field of applicability. In this paper, we consider situations where the oracle's inexactness can be chosen upon demand, more precision coming at a computational price counterpart. Our main motivations arise from oracles requiring the solving of auxiliary subproblems or the inexact computation of involved quantities, e.g. a mini-batch stochastic gradient as a full-gradient estimate. We propose optimal inexactness schedules according to presumed oracle cost models and patterns of worst-case guarantees, covering among others convergence results of the aforementioned methods under the presence of inexactness. Specifically, we detail how to choose the level of inexactness at each iteration to obtain the best trade-off between convergence and computational investments. Furthermore, we highlight the benefits one can expect by tuning those oracles' quality instead of keeping it constant throughout. Finally, we provide extensive numerical experiments that support the practical interest of our approach, both in offline and online settings, applied to the Fast Gradient algorithm.

Abstract: We introduce a machine-learning framework to warm-start fixed-point optimization algorithms. Our architecture consists of a neural network mapping problem parameters to warm starts, followed by a predefined number of fixed-point iterations. We propose two loss functions designed to either minimize the fixed-point residual or the distance to a ground truth solution. In this way, the neural network predicts warm starts with the end-to-end goal of minimizing the downstream loss. An important feature of our architecture is its flexibility, in that it can predict a warm start for fixed-point algorithms run for any number of steps, without being limited to the number of steps it has been trained on. We provide PAC-Bayes generalization bounds on unseen data for common classes of fixed-point operators: contractive, linearly convergent, and averaged. Applying this framework to well-known applications in control, statistics, and signal processing, we observe a significant reduction in the number of iterations and solution time required to solve these problems, through learned warm starts.

Abstract: We investigate a mean-field game (MFG) in which agents can exercise control actions that affect their speed of access to information. The agents can dynamically decide to receive observations with less delay by paying higher observation costs. Agents seek to exploit their active information gathering by making further decisions to influence their state dynamics to maximize rewards. In the mean field equilibrium, each generic agent solves individually a partially observed Markov decision problem in which the way partial observations are obtained is itself also subject of dynamic control actions by the agent. Based on a finite characterisation of the agents' belief states, we show how the mean field game with controlled costly information access can be formulated as an equivalent standard mean field game on a suitably augmented but finite state space.We prove that with sufficient entropy regularisation, a fixed point iteration converges to the unique MFG equilibrium and yields an approximate $\epsilon$-Nash equilibrium for a large but finite population size. We illustrate our MFG by an example from epidemiology, where medical testing results at different speeds and costs can be chosen by the agents.

Abstract: Can we accelerate convergence of gradient descent without changing the algorithm -- just by carefully choosing stepsizes? Surprisingly, we show that the answer is yes. Our proposed Silver Stepsize Schedule optimizes strongly convex functions in $k^{\log_{\rho} 2} \approx k^{0.7864}$ iterations, where $\rho=1+\sqrt{2}$ is the silver ratio and $k$ is the condition number. This is intermediate between the textbook unaccelerated rate $k$ and the accelerated rate $\sqrt{k}$ due to Nesterov in 1983. The non-strongly convex setting is conceptually identical, and standard black-box reductions imply an analogous accelerated rate $\varepsilon^{-\log_{\rho} 2} \approx \varepsilon^{-0.7864}$. We conjecture and provide partial evidence that these rates are optimal among all possible stepsize schedules. The Silver Stepsize Schedule is constructed recursively in a fully explicit way. It is non-monotonic, fractal-like, and approximately periodic of period $k^{\log_{\rho} 2}$. This leads to a phase transition in the convergence rate: initially super-exponential (acceleration regime), then exponential (saturation regime).