2024-10-29 | | Total: 37
In this paper, we consider a variant of the so-called minimum flow decomposition (MFD) problem in which uncertainty regarding edge capacities is taken into account from a robustness perspective. In the classical flow decomposition problem, a network flow is decomposed into a set of weighted paths from a fixed source node to a fixed sink node that precisely represents the flow distribution across all edges. While MFDs are often used in bioinformatics applications, they are also applicable in other fields, such as flows of goods or passengers in distribution networks, where the decomposition represents the vehicles and corresponding capacities needed to cover these flows. We generalize this problem to the weighted inexact case with lower and upper bounds on the flow values, provide a detailed analysis, and explore different variants that are solvable in polynomial time. Moreover, we introduce the concept of robust flow decomposition by incorporating uncertain flows and applying different robustness concepts to handle the uncertainty. Finally, we present two different adjustable problem formulations and perform computational experiments illustrating the benefit of adjustability in the uncertain case in a subsequent computational study.
The Sharpe ratio is an important and widely-used risk-adjusted return in financial engineering. In modern portfolio management, one may require an m-sparse (no more than m active assets) portfolio to save managerial and financial costs. However, few existing methods can optimize the Sharpe ratio with the m-sparse constraint, due to the nonconvexity and the complexity of this constraint. We propose to convert the m-sparse fractional optimization problem into an equivalent m-sparse quadratic programming problem. The semi-algebraic property of the resulting objective function allows us to exploit the Kurdyka-Lojasiewicz property to develop an efficient Proximal Gradient Algorithm (PGA) that leads to a portfolio which achieves the globally optimal m-sparse Sharpe ratio under certain conditions. The convergence rates of PGA are also provided. To the best of our knowledge, this is the first proposal that achieves a globally optimal m-sparse Sharpe ratio with a theoretically-sound guarantee.
We consider a new class of repeated zero-sum games in which the payoff is the escape rate of a switched dynamical system, where at every stage, the transition is given by a nonexpansive operator depending on the actions of both players. This generalizes to the two-player (and non-linear) case the notion of joint spectral radius of a family of matrices. We show that the value of this game does exist, and we characterize it in terms of an infinite dimensional non-linear eigenproblem. This provides a two-player analogue of Mañe's lemma from ergodic control. This also extends to the two-player case results of Kohlberg and Neyman (1981), Karlsson (2001), and Vigeral and the second author (2012), concerning the asymptotic behavior of nonexpansive mappings. We discuss two special cases of this game: order preserving and positively homogeneous self-maps of a cone equipped with Funk's and Thompson's metrics, and groups of translations.
Practically relevant problems of quadratic optimization often contain multidimensional arrays of variables interconnected by linear constraints, such as equalities and inequalities. The values of each variable depend on its specific meaning and can be binary, integer, discrete, and continuous. These circumstances make it technically difficult to reduce the original problem statement to the QUBO form. The paper identifies and considers three main transformations of the original problem statement, namely, the transition from a multidimensional to a one-dimensional array of variables, the transition in mixed problems to binary variables, and the inclusion of linear constraints in the objective function in the form of quadratic penalties. Convenient formulas for calculations are presented and proven, simplifying the implementation of these transformations. In particular, the formulas for the transition in the problem statement from a multidimensional to a one-dimensional array of variables are based on the use of the Kronecker product of matrices. The considered transformations are illustrated by numerous examples.
Nonlinear constrained optimization has a wide range of practical applications. In this paper, we consider nonlinear optimization with inequality constraints. The interior point method is considered to be one of the most powerful algorithms for solving large-scale nonlinear inequality constrained optimization. We propose an adaptive regularisation algorithm using cubics based on interior point methods (ARCBIP) for solving nonlinear inequality constrained optimization. For solving the barrier problem, we construct ARC subproblem with linearized constraints and the well-known fraction to the boundary rule that prevents slack variables from approaching their lower bounds prematurely. The ARC subproblem in ARCBIP can avoid incompatibility of the intersection of linearized constraints with trust-region bounds in trust-region methods. We employ composite-step approach and reduced Hessian methods to deal with linearized constraints, where the trial step is decomposed into a normal step and a tangential step. They are obtained by solving two standard ARC subproblems approximately with the fraction to the boundary rule. Requirements on normal steps and tangential steps are given to ensure global convergence. To determine whether the trial step is accepted, we use exact penalty function as the merit function in ARC framework. The updating of the barrier parameter is implemented by adaptive strategies. Global convergence is analyzed under mild assumptions. Preliminary numerical experiments and some comparison results are reported.
We investigate the convergence of the primal-dual algorithm for composite optimization problems when the objective functions are weakly convex. We introduce a modified duality gap function, which is a lower bound of the standard duality gap function. Under the sharpness condition of this new function, we identify the area around the set of saddle points where we obtain the convergence of the primal-dual algorithm. We give numerical examples and applications in image denoising and deblurring to demonstrate our results.
This paper offers a contemporary and comprehensive perspective on the classical algorithms utilized for the solution of minimum-time problem for linear systems (MTPLS). The use of unified notations supported by visual geometric representations serves to highlight the differences between the Neustadt-Eaton and Barr-Gilbert algorithms. Furthermore, these notations assist in the interpretation of the distance-finding algorithms utilized in the Barr-Gilbert algorithm. Additionally, we present a novel algorithm for solving MTPLS and provide a constructive proof of its convergence. Similar to the Barr-Gilbert algorithm, the novel algorithm employs distance search algorithms. The design of the novel algorithm is oriented towards solving such MTPLS for which the analytic description of the reachable set is available. To illustrate the advantages of the novel algorithm, we utilize the isotropic rocket benchmark. Numerical experiments demonstrate that, for high-precision computations, the novel algorithm outperforms others by factors of tens or hundreds and exhibits the lowest failure rate.
This paper develops a parameter-free adaptive proximal bundle method with two important features: 1) adaptive choice of variable prox stepsizes that "closely fits" the instance under consideration; and 2) adaptive criterion for making the occurrence of serious steps easier. Computational experiments show that our method performs substantially fewer consecutive null steps (i.e., a shorter cycle) while maintaining the number of serious steps under control. As a result, our method performs significantly less number of iterations than its counterparts based on a constant prox stepsize choice and a non-adaptive cycle termination criterion. Moreover, our method is very robust relative to the user-provided initial stepsize.
Uncertainty and delayed reactions in human driving behavior lead to stop-and-go traffic congestion on freeways. The freeway traffic dynamics are governed by the Aw-Rascle-Zhang (ARZ) traffic Partial Differential Equation (PDE) models with unknown relaxation time. Motivated by the adaptive traffic control problem, this paper presents a neural operator (NO) based adaptive boundary control design for the coupled 2$\times$2 hyperbolic systems with uncertain spatially varying in-domain coefficients and boundary parameter. In traditional adaptive control for PDEs, solving backstepping kernel online is computationally intensive, as it requires significant resources at each time step to update the estimation of coefficients. To address this challenge, we use operator learning, i.e. DeepONet, to learn the mapping from system parameters to the kernels functions. DeepONet, a class of deep neural networks designed for approximating operators, has shown strong potential for approximating PDE backstepping designs in recent studies. Unlike previous works that focus on approximating single kernel equation associated with the scalar PDE system, we extend this framework to approximate PDE kernels for a class of the first-order coupled 2$\times$2 hyperbolic kernel equations. Our approach demonstrates that DeepONet is nearly two orders of magnitude faster than traditional PDE solvers for generating kernel functions, while maintaining a loss on the order of $10^{-3}$.
This paper introduces a new method for assessing the boundedness and stability of certain vector nonlinear systems with delays and variable coefficients. The approach is based on developing scalar counterparts to the given vector systems. We prove that the solutions to these scalar nonlinear equations, which also include delays and variable coefficients, provide upper bounds for the norms of solutions to the original vector equations if the history functions for both equations are properly matched. This enables the evaluation of the boundedness and stability characteristics of a vector system by analyzing the abridged dynamics of its scalar counterparts. This assessment can be carried out through straightforward simulations or by applying simplified analytical methods. As a result, we introduce new criteria for boundedness and stability and estimate the radii of the balls that contain history functions stemming bounded or stable solutions for the original vector systems. Finally, we validate our inferences through representative simulations that also assess the accuracy of our approach.
We consider a class of learning problem of point estimation for modeling high-dimensional nonlinear functions, whose learning dynamics is guided by model training dataset, while the estimated parameter in due course provides an acceptable prediction accuracy on a different model validation dataset. Here, we establish an evidential connection between such a learning problem and a hierarchical optimal control problem that provides a framework how to account appropriately for both generalization and regularization at the optimization stage. In particular, we consider the following two objectives: (i) The first one is a controllability-type problem, i.e., generalization, which consists of guaranteeing the estimated parameter to reach a certain target set at some fixed final time, where such a target set is associated with model validation dataset. (ii) The second one is a regularization-type problem ensuring the estimated parameter trajectory to satisfy some regularization property over a certain finite time interval. First, we partition the control into two control strategies that are compatible with two abstract agents, namely, a leader, which is responsible for the controllability-type problem and that of a follower, which is associated with the regularization-type problem. Using the notion of Stackelberg's optimization, we provide conditions on the existence of admissible optimal controls for such a hierarchical optimal control problem under which the follower is required to respond optimally to the strategy of the leader, so as to achieve the overall objectives that ultimately leading to an optimal parameter estimate. Moreover, we provide a nested algorithm, arranged in a hierarchical structure-based on successive approximation methods, for solving the corresponding optimal control problem. Finally, we present some numerical results for a typical nonlinear regression problem.
In this paper a novel stochastic optimization and extremum seeking algorithm is presented, one which is based on time-delayed random perturbations and step size adaptation. For the case of a one-dimensional quadratic unconstrained optimization problem, global exponential convergence in expectation and global exponential practical convergence of the variance of the trajectories are proven. The theoretical results are complemented by numerical simulations for one- and multi-dimensional quadratic and non-quadratic objective functions.
We present a novel model of a coupled hydrogen and electricity market on the intraday time scale, where hydrogen gas is used as a storage device for the electric grid. Electricity is produced by renewable energy sources or by extracting hydrogen from a pipeline that is shared by non-cooperative agents. The resulting model is a generalized Nash equilibrium problem. Under certain mild assumptions, we prove that an equilibrium exists. Perspectives for future work are presented.
Given a Hilbert space and a finite family of operators defined on the space, the common fixed point problem (CFPP) is the problem of finding a point in the intersection of the fixed point sets of these operators. A particular case of the problem, when the operators are orthogonal projections, is the convex feasibility problem which has numerous applications in science and engineering. In a previous work [Censor, Reem, and Zaknoon, A generalized block-iterative projection method for the common fixed point problem induced by cutters, J. Global Optim. 84 (2022), 967--987] we studied a block-iterative method with dynamic weights for solving the CFPP assuming the operators belong to a wide class of operators called cutters. In this work we continue the study of this algorithm by allowing extrapolation, namely we weaken the assumption on the relaxation parameters. We prove the convergence of this algorithm when the space is finite dimensional in two different scenarios, one of them is under a seems to be new condition on the weights which is less restrictive than a condition suggested in previous works. Along the way we obtain various new results of independent interest related to cutters, some of them extend, generalize and clarify previously published results.
Inspired by the recent work by Shapiro et al. [45], we propose a Bayesian distributionally robust Nash equilibrium (BDRNE) model where each player lacks complete information on the true probability distribution of the underlying uncertainty represented by a random variable and subsequently determines the optimal decision by solving a Bayesian distributionally robust optimization (BDRO) problem under the Nash conjecture. Unlike most of the DRO models in the literature, the BDRO model assumes (a) the true unknown distribution of the random variable can be approximated by a randomized parametric family of distributions, (b) the average of the worst-case expected value of the objective function with respect to the posterior distribution of the parameter, instead of the worst-case expected value of the objective function is considered in each player's decision making, and (c) the posterior distribution of the parameter is updated as more and more sampling information of the random variable is gathered. Under some moderate conditions, we demonstrate the existence of a BDRNE and derive asymptotic convergence of the equilibrium as the sample size increases. Moreover, we propose to solve the BDRNE problem by Gauss-Seidel-type iterative method in the case when the ambiguity set of each player is constructed via Kullback-Leibler (KL) divergence. Finally, we apply the BDRNE model to a price competition problem under multinomial logit demand. The preliminary numerical test results show that the proposed model and computational scheme perform well.
This work introduces an unconventional inexact augmented Lagrangian method, where the augmenting term is a Euclidean norm raised to a power between one and two. The proposed algorithm is applicable to a broad class of constrained nonconvex minimization problems, that involve nonlinear equality constraints over a convex set under a mild regularity condition. First, we conduct a full complexity analysis of the method, leveraging an accelerated first-order algorithm for solving the Hölder-smooth subproblems. Next, we present an inexact proximal point method to tackle these subproblems, demonstrating that it achieves an improved convergence rate. Notably, this rate reduces to the best-known convergence rate for first-order methods when the augmenting term is a squared Euclidean norm. Our worst-case complexity results further show that using lower powers for the augmenting term leads to faster constraint satisfaction, albeit with a slower decrease in the dual residual. Numerical experiments support our theoretical findings, illustrating that this trade-off between constraint satisfaction and cost minimization is advantageous for certain practical problems.
The paper is concerned with a scalar balance law, where the source term depends on a control function $\alpha(t)$. Given a control $\alpha\in \mathbf{L}^\infty\bigl([0,T]\bigr)$, it is proved that, for generic initial data $\bar u \in \mathcal{C}^3(\mathbb{R})$, the solution has finitely many shocks, interacting at most two at a time. Moreover, at the terminal time $T$ no shock interaction occurs, and no new shock is formed. In addition, a family of optimal control problems is considered, including a running cost and a terminal cost. An example is constructed where the optimal solution contains two shocks merging exactly at the terminal time $T$. Such behavior persists under any suitably small perturbation of the flux, source, and cost functions, and of the initial data. This shows that generic solutions of optimization problems have different qualitative properties, compared with generic solutions to Cauchy problems.
This paper introduces an inexact two-level smoothing optimization framework (ItsOPT) for finding first-order critical points of nonsmooth and nonconvex functions. The framework involves two levels of methodologies: at the upper level, a first- or second-order method will be tailored to minimize a smooth approximation of the cost function; at the lower level, the high-order proximal auxiliary problems will be solved inexactly. As a smoothing technique, in particular, we here introduce the high-order Moreau envelope (HOME) and study its fundamental features under standard assumptions and its differential properties under a variant of prox-regularity. Next, introducing a high-order proximal-point algorithm (HiPPA) and its boosted variant (Boosted HiPPA) at the upper level and solving the proximal subproblem inexactly at the lower level lead to an instance method of the ItsOPT framework. Global and linear convergence results are established under the Kurdyka-Łojasiewicz (KL) property of the cost and envelope functions, along with some reasonable conditions for the accuracy of the proximal terms. Preliminary numerical experiments on a robust low-rank matrix recovery problem indicate a promising performance of the proposed algorithm, validating our theoretical foundations.
This paper presents a mathematical model for determining the movement of the bearing in an internal gear pump. The paper also performs simulation calculations to find the movement trajectory of the shaft with the given input data.
Sum of squares (SOS) optimization is a powerful technique for solving problems where the positivity of a polynomials must be enforced. The common approach to solve an SOS problem is by relaxation to a Semidefinite Program (SDP). The main advantage of this transormation is that SDP is a convex problem for which efficient solvers are readily available. However, while considerable progress has been made in recent years, the standard approaches for solving SDPs are still known to scale poorly. Our goal is to devise an approach that can handle larger, more complex problems than is currently possible. The challenge indeed lies in how SDPs are commonly solved. State-Of-The-Art approaches rely on the interior point method, which requires the factorization of large matrices. We instead propose an approach inspired by polynomial neural networks, which exhibit excellent performance when optimized using techniques from the deep learning toolbox. In a somewhat counter-intuitive manner, we replace the convex SDP formulation with a non-convex, unconstrained, and \emph{over parameterized} formulation, and solve it using a first order optimization method. It turns out that this approach can handle very large problems, with polynomials having over four million coefficients, well beyond the range of current SDP-based approaches. Furthermore, we highlight theoretical and practical results supporting the experimental success of our approach in avoiding spurious local minima, which makes it amenable to simple and fast solutions based on gradient descent. In all the experiments, our approach had always converged to a correct global minimum, on general (non-sparse) polynomials, with running time only slightly higher than linear in the number of polynomial coefficients, compared to higher than quadratic in the number of coefficients for SDP-based methods.
In the study of a non-convex minimization problem by Lachand-Robert and Peletier, they found that the difference between the compactly supported perturbation $u+\epsilon h$ of a strictly convex function $u$, and the $\Gamma$-regularization of $u+\epsilon h$, is at most $o(\epsilon)$. Here we find that this result is optimal, albeit they expected a much stronger estimate.
The Travelling Salesman Problem - TSP is one of the most explored problems in the scientific literature to solve real problems regarding the economy, transportation, and logistics, to cite a few cases. Adapting TSP to solve different problems has originated several variants of the optimization problem with more complex objectives and different restrictions. Metaheuristics have been used to solve the problem in polynomial time. Several studies have tried hybridising metaheuristics with specialised heuristics to improve the quality of the solutions. However, we have found no study to evaluate whether the searching mechanism of a particular metaheuristic is more adequate for exploring hybridization. This paper focuses on the solution of the classical TSP using high-level hybridisations, experimenting with eight metaheuristics and heuristics derived from k-OPT, SISR, and segment intersection search, resulting in twenty-four combinations. Some combinations allow more than one set of searching parameters. Problems with 50 to 280 cities are solved. Parameter tuning of the metaheuristics is not carried out, exploiting the different searching patterns of the eight metaheuristics instead. The solutions' quality is compared to those presented in the literature.
We present skwdro, a Python library for training robust machine learning models. The library is based on distributionally robust optimization using optimal transport distances. For ease of use, it features both scikit-learn compatible estimators for popular objectives, as well as a wrapper for PyTorch modules, enabling researchers and practitioners to use it in a wide range of models with minimal code changes. Its implementation relies on an entropic smoothing of the original robust objective in order to ensure maximal model flexibility. The library is available at https://github.com/iutzeler/skwdro
In this paper, we study an inverse problem of identifying two spatial-temporal source terms in the Schrödinger equation with dynamic boundary conditions from the final time overdetermination. We adopt a weak solution approach to solve the inverse source problem. By analyzing the associated Tikhonov functional, we prove a gradient formula of the functional in terms of the solution to a suitable adjoint system, allowing us to obtain the Lipschitz continuity of the gradient. Next, the existence and uniqueness of a quasi-solution are also investigated. Finally, our theoretical results are validated by numerical experiments in one dimension using the Landweber iteration method.
This paper introduces new methods to study the long time behaviour of the generalised gradient flow associated with a solution of the critical equation for mechanical Hamiltonian system posed on the flat torus $\mathbb{T}^d$. For this analysis it is necessary to look at the critical set of $u$ consisting of all the points on $\mathbb{T}^d$ such that zero belongs to the super-differential of such a solution. Indeed, such a set turns out to be an attractor for the generalised gradient flow. Moreover, being the critical set the union of two subsets of rather different nature, namely the regular critical set and the singular set, we are interested in establishing whether the generalised gradient flow approaches the former or the latter as $t\to \infty$. One crucial tool of our analysis is provided by limiting occupational measures, a family of measures that are invariant under the generalized flow. Indeed, we show that by integrating the potential with respect to such measures, one can deduce whether the generalised gradient flow enters the singular set in finite time, or it approaches the regular critical set as time tends to infinity.