Optimization and Control (math.OC)

Abstract: Derivative-free algorithms seek the minimum of a given function based only on function values queried at appropriate points. Although these methods are widely used in practice, their performance is known to worsen as the problem dimension increases. Recent advances in developing randomized derivative-free techniques have tackled this issue by working in low-dimensional subspaces that are drawn at random in an iterative fashion. The connection between the dimension of these random subspaces and the algorithmic guarantees has yet to be fully understood. In this paper, we develop an analysis for derivative-free algorithms (both direct-search and model-based approaches) employing random subspaces. Our results leverage linear local approximations of smooth functions to obtain understanding of the expected decrease achieved per function evaluation. Although the quantities of interest involve multidimensional integrals with no closed-form expression, a relative comparison for different subspace dimensions suggest that low dimension is preferable. Numerical computation of the quantities of interest confirm the benefit of operating in low-dimensional subspaces.

Abstract: In the present paper a detailed mathematical model is derived for district heating networks. After semidiscretization of the convective heat equation and introducing coupling conditions at the nodes of the network one gets a high-dimensional system of differential-algebraic equations (DAEs). Neglecting temporal changes of the water velocity in the pipes, the numerical solutions do not change significantly and the DAEs have index one. Numerical experiments illustrate that the model describes the real situation very well.

Abstract: We study a class of nonlinear hyperbolic partial differential equations with boundary control. This class describes chemical reactions of the type ``$A \to$ product'' carried out in a plug flow reactor (PFR) in the presence of an inert component. An isoperimetric optimal control problem with periodic boundary conditions and input constraints is formulated for the considered mathematical model in order to maximize the mean amount of product over the period. For the single-input system, the optimality of a bang-bang control strategy is proved in the class of bounded measurable inputs. The case of controlled flow rate input is also analyzed by exploiting the method of characteristics. A case study is performed to illustrate the performance of the reaction model under different control strategies.

Abstract: We discuss the sidewise control properties of 1-d waves. In analogy with classical control and inverse problems for wave propagation, the problem consists on controlling the behaviour of waves on part of the boundary of the domain where they propagate, by means of control actions localised on a different subset of the boundary. In contrast with classical problems, the goal is not to control the dynamics of the waves on the interior of the domain, but rather their boundary traces. It is therefore a goal oriented controllability problem. We propose a duality method that reduces the problem to suitable new observability inequalities, which consist of estimating the boundary traces of waves on part of the boundary from boundary measurements done on another subset of the boundary. These inequalities lead to novel questions that do not seem to be treatable by the classical techniques employed in the field, such as Carleman inequalities, non-harmonic Fourier series, microlocal analysis and multipliers. We propose a genuinely 1-d solution method, based on sidewise energy propagation estimates yielding a complete sharp solution. The obtained observability results can be reinterpreted in terms of Fourier series. This leads to new non-standard questions in the context of non-harmonic Fourier series.

Abstract: In this work, we analyze the relation between reparametrizations of gradient flow and the induced implicit bias on general linear models, which encompass various basic classification and regression tasks. In particular, we aim at understanding the influence of the model parameters - reparametrization, loss, and link function - on the convergence behavior of gradient flow. Our results provide user-friendly conditions under which the implicit bias can be well-described and convergence of the flow is guaranteed. We furthermore show how to use these insights for designing reparametrization functions that lead to specific implicit biases like $\ell_p$- or trigonometric regularizers.

Abstract: About ten years ago, a paper proposed the first integer linear programming formulation for the constrained two-dimensional guillotine cutting problem (with unlimited cutting stages). Since, six other formulations followed, five of them in the last two years. This spike of interest gave no opportunity for a comprehensive comparison between the formulations. We review each formulation and compare their empirical results over instance datasets of the literature. We adapt most formulations to allow for piece rotation. The possibility of adaptation was already predicted but not realized by the prior work. The results show the dominance of pseudo-polynomial formulations until the point instances become intractable by them, while more compact formulations keep achieving good primal solutions. Our study also reveals a small but consistent advantage of the Gurobi solver over the CPLEX solver in our context; that the choice of solver hardly benefits one formulation over another; and a mistake in the generation of the T instances, which should have the same optima with or without guillotine cuts. Our study also proposes hybridising the most recent formulation with a prior formulation for a restricted version of the problem. The hybridisations show a reduction of about 20% of the branch-and-bound time thanks to the symmetries broken by the hybridisation.

Abstract: Learning-to-optimize (L2O) is an emerging research area in large-scale optimization for data science applications. Very recently, researchers have proposed a novel L2O framework called learned mirror descent (LMD), based on the classical mirror descent (MD) algorithm, with learnable mirror maps parameterized by input-convex neural networks. The LMD approach has been shown to significantly accelerate convex solvers while inheriting the convergence properties of the classical MD algorithm. Despite the initial successes in small-/mid-scale optimization problems demonstrating the potential of this framework, there is still a long way to go to make this scheme scalable and practical for high-dimensional problems. In this work, we provide several practical extensions of the LMD algorithm. We first propose accelerated and stochastic variants of LMD, leveraging classical momentum-based acceleration and stochastic optimization techniques for improving the convergence rate and per-iteration complexity. Moreover, for the particular application of training neural networks, we derive and propose a novel and efficient parameterization for the mirror potential, exploiting the equivariant structure of the training problems to significantly reduce the dimensionality of the underlying problem. We provide theoretical convergence guarantees for our schemes under standard assumptions, and demonstrate their effectiveness in various computational imaging and machine learning applications such as image inpainting and the training of SVMs.

Abstract: We investigate the strong convergence properties of a Nesterov type algorithm with two Tikhonov regularization terms in connection to the minimization problem of a smooth convex function $f.$ We show that the generated sequences converge strongly to the minimal norm element from $\argmin f$. We also show that from a practical point of view the Tikhonov regularization does not affect Nesterov's optimal convergence rate of order $\mathcal{O}(n^{-2})$ for the potential energies $f(x_n)-\min f$ and $f(y_n)-\min f$, where $(x_n),\,(y_n)$ are the sequences generated by our algorithm. Further, we obtain fast convergence to zero of the discrete velocity, but also some estimates concerning the value of the gradient of the objective function in the generated sequences.

Abstract: As a follow-up of the industrial problems dealt with in 2018, 2019, 2021 and 2022, in partnership with CCEE and CEPEL, in 2023 the study group Energy planning and environmental constraints focused on the impact that prioritizing multiple uses of water has on the electric energy production systems, specially in predominantly hydro systems, which is the case of Brazil. In order to model environmental constraints in the long-term hydrothermal generation planning problem, the resulting large-scale multi-stage linear programming problem was modelled in JuMP and solved by stochastic dual dynamic programming. To assess if the development represented well the behavior of the Brazilian power system, the Julia formulation first was benchmarked with Brazil s official model, Newave. Environmental constraints were introduced in this problem by two different approaches, one that represents the multiple uses of water by means of 0-1 variables, and another one that makes piecewise linear approximations of the relevant constraints. Numerical results show that penalties of slack variables strongly affect the obtained water values.

Abstract: This paper proposes pandemic mitigation vaccination policies for Newfoundland and Labrador (NL) based on two compact mixed integer programming (MIP) models of the distance-based critical node detection problem (DCNDP). Our main focus is on two variants of the DCNDP that seek to minimize the number of connections with lengths of at most one (1-DCNDP) and two (2-DCNDP). A polyhedral study for the 1-DCNDP is conducted, and new aggregated inequalities are provided for the 2-DCNDP. The computational experiments show that the 2-DCNDP with aggregated inequalities outperforms the one with disaggregated inequalities for graphs with a density of at least 0.5%. We also study the strategic vaccine allocation problem as a real-world application of the DCNDP and conduct a set of computational experiments on a simulated contact network of NL. Our computational results demonstrate that the DCNDP-based strategies can have a better performance in comparison with the real-world strategies implemented during COVID-19.

Abstract: Preference disaggregation analysis (PDA) is a widely used approach in multicriteria decision analysis that aims to extract preferential information from holistic judgments provided by decision makers. This paper presents an original methodological framework for PDA that addresses two significant challenges in this field. Firstly, it considers the multidimensional structure of data to capture decision makers' preferences based on descriptive measures of the criteria time series, such as trend and average. This novel approach enables an understanding of decision makers' preferences in decision-making scenarios involving time series analysis, which is common in medium- to long-term impact decisions. Secondly, the paper addresses the robustness issue commonly encountered in PDA methods by proposing a multi-objective and Monte Carlo simulation approach. This approach enables the consideration of multiple preference models and provides a mechanism to converge towards the most likely preference model. The proposed method is evaluated using real data, demonstrating its effectiveness in capturing preferences based on criteria and time series descriptive measures. The multi-objective analysis highlights the generation of multiple solutions, and, under specific conditions, reveals the possibility of achieving convergence towards a single solution that represents the decision maker's preferences.