Search

A key challenge in autonomous driving is that Autonomous Vehicles (AVs) must contend with multiple, often conflicting, planning requirements. These requirements naturally form in a hierarchy -- e.g., avoiding a collision is more important than maintaining lane. While the exact structure of this hierarchy remains unknown, to progress towards ensuring that AVs satisfy pre-determined behavior specifications, it is crucial to develop approaches that systematically account for it. Motivated by lexicographic behavior specification in AVs, this work addresses a lexicographic multi-objective motion planning problem, where each objective is incomparably more important than the next -- consider that avoiding a collision is incomparably more important than a lane change violation. This work ties together two elements. Firstly, a multi-objective candidate function that asymptotically represents lexicographic orders is introduced. Unlike existing multi-objective cost function formulations, this approach assures that returned solutions asymptotically align with the lexicographic behavior specification. Secondly, inspired by continuation methods, we propose two algorithms that asymptotically approach minimum rank decisions -- i.e., decisions that satisfy the highest number of important rules possible. Through a couple practical examples, we showcase that the proposed candidate function asymptotically represents the lexicographic hierarchy, and that both proposed algorithms return minimum rank decisions, even when other approaches do not., Comment: 7 pages

To address unfairness issues in federated learning (FL), contemporary approaches typically use frequent model parameter updates and transmissions between the clients and server. In such a process, client-specific information (e.g., local dataset size or data-related fairness metrics) must be sent to the server to compute, e.g., aggregation weights. All of this results in high transmission costs and the potential leakage of client information. As an alternative, we propose a strategy that promotes fair predictions across clients without the need to pass information between the clients and server iteratively and prevents client data leakage. For each client, we first use their local dataset to obtain a synthetic dataset by solving a bilevel optimization problem that addresses unfairness concerns during the learning process. We then pass each client's synthetic dataset to the server, the collection of which is used to train the server model using conventional machine learning techniques (that do not take fairness metrics into account). Thus, we eliminate the need to handle fairness-specific aggregation weights while preserving client privacy. Our approach requires only a single communication between the clients and the server, thus making it computationally cost-effective, able to maintain privacy, and able to ensuring fairness. We present empirical evidence to demonstrate the advantages of our approach. The results illustrate that our method effectively uses synthetic data as a means to mitigate unfairness and preserve client privacy.

Learning uncertain dynamics models using Gaussian process~(GP) regression has been demonstrated to enable high-performance and safety-aware control strategies for challenging real-world applications. Yet, for computational tractability, most approaches for Gaussian process-based model predictive control (GP-MPC) are based on approximations of the reachable set that are either overly conservative or impede the controller's safety guarantees. To address these challenges, we propose a robust GP-MPC formulation that guarantees constraint satisfaction with high probability. For its tractable implementation, we propose a sampling-based GP-MPC approach that iteratively generates consistent dynamics samples from the GP within a sequential quadratic programming framework. We highlight the improved reachable set approximation compared to existing methods, as well as real-time feasible computation times, using two numerical examples., Comment: to be published in 63rd IEEE Conference on Decision and Control (CDC 2024)

The problem of finding aperiodic low auto-correlation binary sequences (LABS) presents a significant computational challenge, particularly as the sequence length increases. Such sequences have important applications in communication engineering, physics, chemistry, and cryptography. This paper introduces a novel dual-step algorithm for long binary sequences with high merit factors. The first step employs a parallel algorithm utilizing skew-symmetry and restriction classes to generate sequence candidates with merit factors above a predefined threshold. The second step uses a priority queue algorithm to refine these candidates further, searching the entire search space unrestrictedly. By combining GPU-based parallel computing and dual-step optimization, our approach has successfully identified new best-known binary sequences for all lengths ranging from 450 to 527, with the exception of length 518, where the previous best-known value was matched with a different sequence. This hybrid method significantly outperforms traditional exhaustive and stochastic search methods, offering an efficient solution for finding long sequences with good merit factors., Comment: 14 pages, 6 figures, 2 tables

A nonlinear generalisation of the PageRank problem involving the Moore-Penrose inverse of the incidence matrix is developed for local graph partitioning purposes. The Levenberg-Marquardt method with a full rank Jacobian variant provides a strategy for obtaining a numerical solution to the generalised problem. Sets of vertices are formed according to the ranking supplied by the solution, and a conductance criterion decides upon the set that best represents the cluster around a starting vertex. Experiments on both synthetic and real-world inspired graphs demonstrate the capability of the approach to not only produce low conductance sets, but to also recover local clusters with an accuracy that consistently surpasses state-of-the-art algorithms.

Robots find extensive applications in industry. In recent years, the influence of robots has also increased rapidly in domestic scenarios. The Q-learning algorithm aims to maximise the reward for reaching the goal. This paper proposes a modified version of the Q-learning algorithm, known as Q-learning with scaled distance metric (Q-SD). This algorithm enhances task learning and makes task completion more meaningful. A robotic manipulator (agent) applies the Q-SD algorithm to the task of table cleaning. Using Q-SD, the agent acquires the sequence of steps necessary to accomplish the task while minimising the manipulator's movement distance. We partition the table into grids of different dimensions. The first has a grid count of 3 times 3, and the second has a grid count of 4 times 4. Using the Q-SD algorithm, the maximum success obtained in these two environments was 86% and 59% respectively. Moreover, Compared to the conventional Q-learning algorithm, the drop in average distance moved by the agent in these two environments using the Q-SD algorithm was 8.61% and 6.7% respectively., Comment: 9 pages, 9 figures, 7 tables

This paper proposes a general framework of Riemannian adaptive optimization methods. The framework encapsulates several stochastic optimization algorithms on Riemannian manifolds and incorporates the mini-batch strategy that is often used in deep learning. Within this framework, we also propose AMSGrad on embedded submanifolds of Euclidean space. Moreover, we give convergence analyses valid for both a constant and a diminishing step size. Our analyses also reveal the relationship between the convergence rate and mini-batch size. In numerical experiments, we applied the proposed algorithm to principal component analysis and the low-rank matrix completion problem, which can be considered to be Riemannian optimization problems. Python implementations of the methods used in the numerical experiments are available at https://github.com/iiduka-researches/202408-adaptive., Comment: 16 figures

We consider the {\em correlated knapsack orienteering} (CSKO) problem: we are given a travel budget $B$, processing-time budget $W$, finite metric space $(V,d)$ with root $\rho\in V$, where each vertex is associated with a job with possibly correlated random size and random reward that become known only when the job completes. Random variables are independent across different vertices. The goal is to compute a $\rho$-rooted path of length at most $B$, in a possibly adaptive fashion, that maximizes the reward collected from jobs that processed by time $W$. To our knowledge, CSKO has not been considered before, though prior work has considered the uncorrelated problem, {\em stochastic knapsack orienteering}, and {\em correlated orienteering}, which features only one budget constraint on the {\em sum} of travel-time and processing-times. We show that the {\em adaptivity gap of CSKO is not a constant, and is at least $\Omega\bigl(\max\sqrt{\log{B}},\sqrt{\log\log{W}}\}\bigr)$}. Complementing this, we devise {\em non-adaptive} algorithms that obtain: (a) $O(\log\log W)$-approximation in quasi-polytime; and (b) $O(\log W)$-approximation in polytime. We obtain similar guarantees for CSKO with cancellations, wherein a job can be cancelled before its completion time, foregoing its reward. We also consider the special case of CSKO, wherein job sizes are weighted Bernoulli distributions, and more generally where the distributions are supported on at most two points (2-CSKO). Although weighted Bernoulli distributions suffice to yield an $\Omega(\sqrt{\log\log B})$ adaptivity-gap lower bound for (uncorrelated) {\em stochastic orienteering}, we show that they are easy instances for CSKO. We develop non-adaptive algorithms that achieve $O(1)$-approximation in polytime for weighted Bernoulli distributions, and in $(n+\log B)^{O(\log W)}$-time for the more general case of 2-CSKO., Comment: Full version of APPROX 2024 paper

We apply numerical optimization and linear algebra algorithms for classical computers to the problem of automatically synthesizing algorithms for quantum computers. Using our framework, we apply several common techniques from these classical domains and numerically examine their suitability for and performance on this problem. Our methods are evaluated on single-qubit systems as well as on larger systems. While the first part of our proposed method outputs a single unitary matrix representing the composite effects of a quantum circuit or algorithm, we use existing tools - and assess the performance of these - to factor such a matrix into a product of elementary quantum gates. This enables our pipeline to be truly end-to-end: starting from desired input/output examples, our code ultimately results in a quantum circuit diagram. We release our code to the research community (upon acceptance)., Comment: 17 pages, 9 figures

PySLSQP is a seamless interface for using the SLSQP algorithm from Python. It wraps the original SLSQP Fortran code sourced from the SciPy repository and provides a host of new features to improve the research utility of the original algorithm. Some of the additional features offered by PySLSQP include auto-generation of unavailable derivatives using finite differences, independent scaling of the problem variables and functions, access to internal optimization data, live-visualization, saving optimization data from each iteration, warm/hot restarting of optimization, and various other utilities for post-processing., Comment: 9 pages with 2 figures. For associated code, see https://github.com/anugrahjo/PySLSQP

The take-home message of this paper is that solving optimal control problems can be computationally straightforward, provided that differentiable partial differential equation (PDE) solvers are available. Although this might seem to be a strong limitation and the development of differentiable PDE solvers might seem arduous, for many problems this is not the case. In particular, for linear partial differential equations, they are equivalent to a linear equation system. Therefore it is just sufficient to be able to solve linear equation systems in an automatic differentiation-capable library like PyTorch and be able to differentiate through the linear solver. Using open-source libraries, like torch_sparse_solve, we have easy to use differentiable direct solvers (here: KLU) at hand, which makes solving linear PDEs straightforward. For nonlinear PDEs, the approach above might be not sufficient, since we do not have an equivalent linear equation system for the underlying PDE. In this case, we can then use the library torch-fenics, which enables us to define PDEs using the finite element library FEniCS and then differentiate through this problem in PyTorch. We complement the proposed methodology with various optimal control problems constrained by stationary and instationary PDEs, linear and nonlinear PDEs (from Poisson to fluid-structure interaction), space-time and time-stepping formulations, parameter estimation, right-hand side control, initial condition control and boundary condition control, finite difference and finite element discretizations and neural network surrogates. All developments of this work are accompanied with the respective source codes published on GitHub.

In this paper, we attempt to compare two distinct branches of research on second-order optimization methods. The first one studies self-concordant functions and barriers, the main assumption being that the third derivative of the objective is bounded by the second derivative. The second branch studies cubic regularized Newton methods (CRNMs) with the main assumption that the second derivative is Lipschitz continuous. We develop a new theoretical analysis for a path-following scheme (PFS) for general self-concordant functions, as opposed to the classical path-following scheme developed for self-concordant barriers. We show that the complexity bound for this scheme is better than that of the Damped Newton Method (DNM) and show that our method has global superlinear convergence. We propose also a new predictor-corrector path-following scheme (PCPFS) that leads to further improvement of constant factors in the complexity guarantees for minimizing general self-concordant functions. We also apply path-following schemes to different classes of constrained optimization problems and obtain the resulting complexity bounds. Finally, we analyze an important subclass of general self-concordant functions, namely a class of strongly convex functions with Lipschitz continuous second derivative, and show that for this subclass CRNMs give even better complexity bounds.

We revisit the standard ``telescoping sum'' argument ubiquitous in the final steps of analyzing evaluation complexity of algorithms for smooth nonconvex optimization, and obtain a refined formulation of the resulting bound as a function of the requested accuracy $\epsilon$. While bounds obtained using the standard argument typically are of the form $\mathcal{O}(\epsilon^{-\alpha})$ for some positive $\alpha$, the refined results are of the form $o(\epsilon^{-\alpha})$. We then explore to which known algorithms our refined bounds are applicable and finally describe an example showing how close the standard and refined bounds can be., Comment: 10 ages, 1 figure

The Variational Bayesian method (VB) is used to solve the probability distributions of latent variables with the minimum free energy criterion. This criterion is not easy to understand, and the computation is complex. For these reasons, this paper proposes the Semantic Variational Bayes' method (SVB). The Semantic Information Theory the author previously proposed extends the rate-distortion function R(D) to the rate-fidelity function R(G), where R is the minimum mutual information for given semantic mutual information G. SVB came from the parameter solution of R(G), where the variational and iterative methods originated from Shannon et al.'s research on the rate-distortion function. The constraint functions SVB uses include likelihood, truth, membership, similarity, and distortion functions. SVB uses the maximum information efficiency (G/R) criterion, including the maximum semantic information criterion for optimizing model parameters and the minimum mutual information criterion for optimizing the Shannon channel. For the same tasks, SVB is computationally simpler than VB. The computational experiments in the paper include 1) using a mixture model as an example to show that the mixture model converges as G/R increases; 2) demonstrating the application of SVB in data compression with a group of error ranges as the constraint; 3) illustrating how the semantic information measure and SVB can be used for maximum entropy control and reinforcement learning in control tasks with given range constraints, providing numerical evidence for balancing control's purposiveness and efficiency. Further research is needed to apply SVB to neural networks and deep learning., Comment: 21 pages, 7 figures, 39 references

The main goal of this paper is to propose a new quaternion total variation regularization model for solving linear ill-posed quaternion inverse problems, which arise from three-dimensional signal filtering or color image processing. The quaternion total variation term in the model is represented by collaborative total variation regularization and approximated by a quaternion iteratively reweighted norm. A novel flexible quaternion generalized minimal residual method is presented to quickly solve this model. An improved convergence theory is established to obtain a sharp upper bound of the residual norm of quaternion minimal residual method (QGMRES). The convergence theory is also presented for preconditioned QGMRES. Numerical experiments indicate the superiority of the proposed model and algorithms over the state-of-the-art methods in terms of iteration steps, CPU time, and the quality criteria of restored color images., Comment: 26 pages, 2 figures, 4 tables

Constraining a numerical weather prediction (NWP) model with observations via 4D variational (4D-Var) data assimilation is often difficult to implement in practice due to the need to develop and maintain a software-based tangent linear model and adjoint model. One of the most common 4D-Var algorithms uses an incremental update procedure, which has been shown to be an approximation of the Gauss-Newton method. Here we demonstrate that when using a forecast model that supports automatic differentiation, an efficient and in some cases more accurate alternative approximation of the Gauss-Newton method can be applied by combining backpropagation of errors with Hessian approximation. This approach can be used with either a conventional numerical model implemented within a software framework that supports automatic differentiation, or a machine learning (ML) based surrogate model. We test the new approach on a variety of Lorenz-96 and quasi-geostrophic models. The results indicate potential for a deeper integration of modeling, data assimilation, and new technologies in a next-generation of operational forecast systems that leverage weather models designed to support automatic differentiation., Comment: 24 pages, 7 figures

Efficiency increase is seen as one of the main goals in any energy converting device. In this direction, the present study aims to demonstrate that large-scale wind turbines can still be improved in order to generate larger amounts of energy. The research presented in this manuscript consists of two main blocks. Initially, it analyzes via Computational Fluid Dynamics (CFD) the boundary layer dynamics on a set of pre-determined airfoils cut along the DTU-10MW reference blade by using the 2D URANS k omega SST turbulence model. The aim of this initial stage is to identify the boundary layer separation point, its associated frequency, and peak to peak amplitude for each airfoil cut along the blade, evaluating as well their respective aerodynamic characteristics. The second main goal of the present research consists of implementing the Active Flow Control (AFC) technology and, when employing synthetic jets, to reattach the boundary layer in all airfoils where it is separated. To accomplish this second goal efficiently, the five parameters associated to the AFC implementation performed to each airfoil will be obtained through respective genetic algorithm optimizations. An energy assessment is finally undertaken at each airfoil to validate the respective energy gain obtained. When comparing the net power gain, before and after AFC implementation, generated by each of the airfoils evaluated, net power gains between 23 and 36KW are obtained in all airfoils analyzed, clarifying that the proposed technology is capable of improving the performance of the wind turbines, very likely at any operating condition., Comment: 30 pages, 17 figures

We assess the suitability of Reynolds-Averaged Navier-Stokes (RANS) simulation using the Spallart-Almaras (SA) turbulence model as a closure in analysing the performance of fluidic Active Flow Control (AFC) applications. In particular, we focus on the optimal set of actuation parameters found by Tousi et al. [1, 2] for a SD7003 airfoil at a Reynolds number Re = 6 e4 and post-stall angle of attack alpha = 14 degrees fitted with a Synthetic Jet Actuator (SJA). The Large Eddy Simulation (LES) presented in that work is taken as the reference to identify the best choice of boundary conditions for the turbulence field nu' at both domain inlet and jet orifice in two-dimensional RANS-SA computations. Although SA-RANS is far less accurate than LES, our findings show that it can still predict macroscopic aggregates such as lift and drag coefficients quite statisfactorily and at a much lower computational cost, provided that turbulence levels of the actuator jet are set to a realistic value. An adequate value of nu'is instrumental in capturing the correct flow behaviour of the reattached boundary layers for close-to-optimal actuated cases. This validates the use of RANS-SA as a reliable and cost-effective simulation method for the preliminary optimisation of SJA parameters in AFC applications., Comment: 18 pages, 7 figures

The present research aims to enhance the efficiency of a DTU-10MW Horizontal Axis Wind Turbine (HAWT) via Active Flow Control (AFC) implementation and using Synthetic Jets (SJ). In the initial part of the study the flow around two airfoil sections cut along the wing turbine blade and for a wind speed of 10m/s is simulated using CFD-2D-RANS-K{\omega}-SST turbulence model, in order to obtain the time averaged boundary layer separation point and the associated vortex shedding frequency. This information is used, on a second stage of the paper, to set, in one of these two airfoils where the boundary layer is having an early separation, two of the AFC parameters while optimizing the remaining three. The optimization is performed employing a parametric analysis and demonstrates that a considerable WT power increase can be obtained when managing to reattach the former separated boundary layer. This is further clarified thanks to the energy assessment presented in the final part of the paper. Although the AFC optimization needs to be extended for the rest of the blade sections, the procedure outlined in the present research clarifies the different steps to be followed to optimize the performance of any HAWT under any operating conditions. The Reynolds numbers associated to the respective airfoil sections analyzed in the present manuscript are Re = 14.088 e6 and Re = 14.877 e6, the characteristic length being the corresponding chord length for each airfoil., Comment: 35 pages, 17 figures

A new decoder for the SIF test problems of the CUTEst collection is described, which produces problem files allowing the computation of values and derivatives of the objective function and constraints of most \cutest\ problems directly within ``native'' Matlab, Python or Julia, without any additional installation or interfacing with MEX files or Fortran programs. When used with Matlab, the new problem files optionally support reduced-precision computations.

Deep learning algorithms - typically consisting of a class of deep neural networks trained by a stochastic gradient descent (SGD) optimization method - are nowadays the key ingredients in many artificial intelligence (AI) systems and have revolutionized our ways of working and living in modern societies. For example, SGD methods are used to train powerful large language models (LLMs) such as versions of ChatGPT and Gemini, SGD methods are employed to create successful generative AI based text-to-image creation models such as Midjourney, DALL-E, and Stable Diffusion, but SGD methods are also used to train DNNs to approximately solve scientific models such as partial differential equation (PDE) models from physics and biology and optimal control and stopping problems from engineering. It is known that the plain vanilla standard SGD method fails to converge even in the situation of several convex optimization problems if the learning rates are bounded away from zero. However, in many practical relevant training scenarios, often not the plain vanilla standard SGD method but instead adaptive SGD methods such as the RMSprop and the Adam optimizers, in which the learning rates are modified adaptively during the training process, are employed. This naturally rises the question whether such adaptive optimizers, in which the learning rates are modified adaptively during the training process, do converge in the situation of non-vanishing learning rates. In this work we answer this question negatively by proving that adaptive SGD methods such as the popular Adam optimizer fail to converge to any possible random limit point if the learning rates are asymptotically bounded away from zero. In our proof of this non-convergence result we establish suitable pathwise a priori bounds for a class of accelerated and adaptive SGD methods, which are also of independent interest., Comment: 54 pages

A fully stochastic second-order adaptive-regularization method for unconstrained nonconvex optimization is presented which never computes the objective-function value, but yet achieves the optimal $\mathcal{O}(\epsilon^{-3/2})$ complexity bound for finding first-order critical points. The method is noise-tolerant and the inexactness conditions required for convergence depend on the history of past steps. Applications to cases where derivative evaluation is inexact and to minimization of finite sums by sampling are discussed. Numerical experiments on large binary classification problems illustrate the potential of the new method., Comment: 32 pages, 9 figures

We consider the fractional influence maximization problem, i.e., identifying users on a social network to be incentivized with potentially partial discounts to maximize the influence on the network. The larger the discount given to a user, the higher the likelihood of its activation (adopting a new product or innovation), who then attempts to activate its neighboring users, causing a cascade effect of influence through the network. Our goal is to devise efficient algorithms that assign initial discounts to the network's users to maximize the total number of activated users at the end of the cascade, subject to a constraint on the total sum of discounts given. In general, the activation likelihood could be any non-decreasing function of the discount, whereas, our focus lies on the case when the activation likelihood is an affine function of the discount, potentially varying across different users. As this problem is shown to be NP-hard, we propose and analyze an efficient (1-1/e)-approximation algorithm. Furthermore, we run experiments on real-world social networks to show the performance and scalability of our method., Comment: 5 pages, 2 figures, and 1 table

Differentially private stochastic gradient descent (DP-SGD) refers to a family of optimization algorithms that provide a guaranteed level of differential privacy (DP) through DP accounting techniques. However, current accounting techniques make assumptions that diverge significantly from practical DP-SGD implementations. For example, they may assume the loss function is Lipschitz continuous and convex, sample the batches randomly with replacement, or omit the gradient clipping step. In this work, we analyze the most commonly used variant of DP-SGD, in which we sample batches cyclically with replacement, perform gradient clipping, and only release the last DP-SGD iterate. More specifically - without assuming convexity, smoothness, or Lipschitz continuity of the loss function - we establish new R\'enyi differential privacy (RDP) bounds for the last DP-SGD iterate under the mild assumption that (i) the DP-SGD stepsize is small relative to the topological constants in the loss function, and (ii) the loss function is weakly-convex. Moreover, we show that our bounds converge to previously established convex bounds when the weak-convexity parameter of the objective function approaches zero. In the case of non-Lipschitz smooth loss functions, we provide a weaker bound that scales well in terms of the number of DP-SGD iterations.

Quasi-Newton methods form an important class of methods for solving nonlinear optimization problems. In such methods, first order information is used to approximate the second derivative. The aim is to mimic the fast convergence that can be guaranteed by Newton-based methods. In the best case, quasi-Newton methods will far outperform steepest descent and other first order methods, without the computational cost of calculating the exact second derivative. These convergence guarantees hold locally, which follows closely from the fact that if the objective function is strongly convex it can be approximated well by a quadratic function close to the solution. Understanding the performance of quasi-Newton methods on quadratic problems with a symmetric positive definite Hessian is therefore of vital importance. In the classic case, an approximation of the Hessian is updated at every iteration and exact line search is used. It is well known that the algorithm terminates finitely, even when the Hessian approximation is memoryless, i.e. requires only the most recent information. In this paper, we explore the possibilities in which reliance on exact line search and dependence on conjugate search directions can be relaxed, while preserving finite termination properties of quasi-Newton methods on quadratic problems., Comment: 12 pages, no figures

Gradient-based optimization has been critical to the success of machine learning, updating a single set of parameters to minimize a single loss. A growing number of applications rely on a generalization of this, where we have a bilevel or nested optimization of which subsets of parameters update on different objectives nested inside each other. We focus on motivating examples of hyperparameter optimization and generative adversarial networks. However, naively applying classical methods often fails when we look at solving these nested problems on a large scale. In this thesis, we build tools for nested optimization that scale to deep learning setups., Comment: View more research details at https://www.jonlorraine.com/

Real-world decision and optimization problems, often involve constraints and conflicting criteria. For example, choosing a travel method must balance speed, cost, environmental footprint, and convenience. Similarly, designing an industrial process must consider safety, environmental impact, and cost efficiency. Ideal solutions where all objectives are optimally met are rare; instead, we seek good compromises and aim to avoid lose-lose scenarios. Multicriteria optimization offers computational techniques to compute Pareto optimal solutions, aiding decision analysis and decision making. This reader offers an introduction to this topic and has been developed on the basis of the revised edition of the reader for the MSc computer science course "Multicriteria Optimization and Decision Analysis" at the Leiden Institute of Advanced Computer Science, Leiden University, The Netherlands. This course was taught annually by the first author from 2007 to 2023 as a single semester course with lectures and practicals. Our aim was to make the material accessible to MSc students who do not study mathematics as their core discipline by introducing basic numerical analysis concepts when necessary and providing numerical examples for interesting cases. The introduction is organized in a unique didactic manner developed by the authors, starting from more simple concepts such as linear programming and single-point methods, and advancing from these to more difficult concepts such as optimality conditions for nonlinear optimization and set-oriented solution algorithms. Besides, we focus on the mathematical modeling and foundations rather than on specific algorithms, though not excluding the discussion of some representative examples of solution algorithms., Comment: 102 pages, Lecture notes

When training deep learning models, the performance depends largely on the selected hyperparameters. However, hyperparameter optimization (HPO) is often one of the most expensive parts of model design. Classical HPO methods treat this as a black-box optimization problem. However, gray-box HPO methods, which incorporate more information about the setup, have emerged as a promising direction for more efficient optimization. For example, using intermediate loss evaluations to terminate bad selections. In this work, we propose an HPO method for neural networks using logged checkpoints of the trained weights to guide future hyperparameter selections. Our method, Forecasting Model Search (FMS), embeds weights into a Gaussian process deep kernel surrogate model, using a permutation-invariant graph metanetwork to be data-efficient with the logged network weights. To facilitate reproducibility and further research, we open-source our code at https://github.com/NVlabs/forecasting-model-search., Comment: See the project website at https://research.nvidia.com/labs/toronto-ai/FMS/

I show how to express the question of whether a polyform tiles the plane isohedrally as a Boolean formula that can be tested using a SAT solver. This approach is adaptable to a wide range of polyforms, requires no special-case code for different isohedral tiling types, and integrates seamlessly with existing software for computing Heesch numbers of polyforms., Comment: In Proceedings GASCom 2024, arXiv:2406.14588

In portfolio risk minimization, the inverse covariance matrix of returns is often unknown and has to be estimated in practice. This inverse covariance matrix also prescribes the hedge trades in which a stock is hedged by all the other stocks in the portfolio. In practice with finite samples, however, multicollinearity gives rise to considerable estimation errors, making the hedge trades too unstable and unreliable for use. By adopting ideas from current methodologies in the existing literature, we propose 2 new estimators of the inverse covariance matrix, one which relies only on the l2 norm while the other utilizes both the l1 and l2 norms. These 2 new estimators are classified as shrinkage estimators in the literature. Comparing favorably with other methods (sample-based estimation, equal-weighting, estimation based on Principal Component Analysis), a portfolio formed on the proposed estimators achieves substantial out-of-sample risk reduction and improves the out-of-sample risk-adjusted returns of the portfolio, particularly in high-dimensional settings. Furthermore, the proposed estimators can still be computed even in instances where the sample covariance matrix is ill-conditioned or singular, Comment: B.Sc. Dissertation

A parametric class of trust-region algorithms for constrained nonconvex optimization is analyzed, where the objective function is never computed. By defining appropriate first-order stationarity criteria, we are able to extend the Adagrad method to the newly considered problem and retrieve the standard complexity rate of the projected gradient method that uses both the gradient and objective function values. Furthermore, we propose an additional iteration-dependent scaling with slightly inferior theoretical guarantees. In both cases, the bounds are essentially sharp, and curvature information can be used to compute the stepsize. The adaptation of the algorithm to the convex constrained case is discussed, and initial experimental results for noisy bound-constrained instances illustrate the benefits of the objective-free approach.

Classical model reduction techniques project the governing equations onto a linear subspace of the original state space. More recent data-driven techniques use neural networks to enable nonlinear projections. Whilst those often enable stronger compression, they may have redundant parameters and lead to suboptimal latent dimensionality. To overcome these, we propose a multistep algorithm that induces sparsity in the encoder-decoder networks for effective reduction in the number of parameters and additional compression of the latent space. This algorithm starts with sparsely initialized a network and training it using linearized Bregman iterations. These iterations have been very successful in computer vision and compressed sensing tasks, but have not yet been used for reduced-order modelling. After the training, we further compress the latent space dimensionality by using a form of proper orthogonal decomposition. Last, we use a bias propagation technique to change the induced sparsity into an effective reduction of parameters. We apply this algorithm to three representative PDE models: 1D diffusion, 1D advection, and 2D reaction-diffusion. Compared to conventional training methods like Adam, the proposed method achieves similar accuracy with 30% less parameters and a significantly smaller latent space., Comment: 27 pages, 20 figures, 4 tables

We present a theoretical framework for the analysis of amplitude transfer in Quantum Variational Algorithms (QVAs) for combinatorial optimisation with mixing unitaries defined by vertex-transitive graphs, based on their continuous-time quantum walk (CTQW) representation and the theory of graph automorphism groups. This framework leads to a heuristic for designing efficient problem-specific QVAs. Using this heuristic, we develop novel algorithms for unconstrained and constrained optimisation. We outline their implementation with polynomial gate complexity and simulate their application to the parallel machine scheduling and portfolio rebalancing combinatorial optimisation problems, showing significantly improved convergence over preexisting QVAs. Based on our analysis, we derive metrics for evaluating the suitability of graph structures for specific problem instances, and for establishing bounds on the convergence supported by different graph structures. For mixing unitaries characterised by a CTQW over a Hamming graph on $m$-tuples of length $n$, our results indicate that the amplification upper bound increases with problem size like $\mathcal{O}(e^{n \log m})$.

Recent advances in {matrix-mimetic} tensor frameworks have made it possible to preserve linear algebraic properties for multilinear data analysis and, as a result, to obtain optimal representations of multiway data. Matrix mimeticity arises from interpreting tensors as operators that can be multiplied, factorized, and analyzed analogous to matrices. Underlying the tensor operation is an algebraic framework parameterized by an invertible linear transformation. The choice of linear mapping is crucial to representation quality and, in practice, is made heuristically based on expected correlations in the data. However, in many cases, these correlations are unknown and common heuristics lead to suboptimal performance. In this work, we simultaneously learn optimal linear mappings and corresponding tensor representations without relying on prior knowledge of the data. Our new framework explicitly captures the coupling between the transformation and representation using variable projection. We preserve the invertibility of the linear mapping by learning orthogonal transformations with Riemannian optimization. We provide original theory of uniqueness of the transformation and convergence analysis of our variable-projection-based algorithm. We demonstrate the generality of our framework through numerical experiments on a wide range of applications, including financial index tracking, image compression, and reduced order modeling. We have published all the code related to this work at https://github.com/elizabethnewman/star-M-opt., Comment: 46 pages, 15 figures

Geodesic metric spaces support a variety of averaging constructions for given finite sets. Computing such averages has generated extensive interest in diverse disciplines. Here we consider the inverse problem of recognizing computationally whether or not a given point is such an average, exactly or approximately. In nonpositively curved spaces, several averaging notions, including the usual weighted barycenter, produce the same "mean set". In such spaces, at points where the tangent cone is a Euclidean space, the recognition problem reduces to Euclidean projection onto a polytope. Hadamard manifolds comprise one example. Another consists of CAT(0) cubical complexes, at relative-interior points: the recognition problem is harder for general points, but we present an efficient semidefinite-programming-based algorithm.

The integrity and precision of nuclear data are crucial for a broad spectrum of applications, from national security and nuclear reactor design to medical diagnostics, where the associated uncertainties can significantly impact outcomes. A substantial portion of uncertainty in nuclear data originates from the subjective biases in the evaluation process, a crucial phase in the nuclear data production pipeline. Recent advancements indicate that automation of certain routines can mitigate these biases, thereby standardizing the evaluation process, reducing uncertainty and enhancing reproducibility. This article contributes to developing a framework for automated evaluation techniques testing, emphasizing automated fitting methods that do not require the user to provide any prior information. This approach simplifies the process and reduces the manual effort needed in the initial evaluation stage. It highlights the capability of the framework to validate and optimize subroutines, targeting the performance analysis and optimization of the fitting procedure using high-fidelity synthetic data (labeled experimental data) and the concept of a fully controlled computational experiment. An error metric is introduced to provide a clear and intuitive measure of the fitting quality by quantifying the accuracy and performance across the specified energy. This metric sets a scale for comparison and optimization of routines or hyperparameter selection, improving the entire evaluation process methodology and increasing reproducibility and objectivity., Comment: 39 pages, 12 figures; As a follow-up to arXiv:2303.09698 and arXiv:2402.14122

We consider a decentralized optimization problem for networks affected by communication delays. Examples of such networks include collaborative machine learning, sensor networks, and multi-agent systems. To mimic communication delays, we add virtual non-computing nodes to the network, resulting in directed graphs. This motivates investigating decentralized optimization solutions on directed graphs. Existing solutions assume nodes know their out-degrees, resulting in limited applicability. To overcome this limitation, we introduce a novel gossip-based algorithm, called DT-GO, that does not need to know the out-degrees. The algorithm is applicable in general directed networks, for example networks with delays or limited acknowledgment capabilities. We derive convergence rates for both convex and non-convex objectives, showing that our algorithm achieves the same complexity order as centralized Stochastic Gradient Descent. In other words, the effects of the graph topology and delays are confined to higher-order terms. Additionally, we extend our analysis to accommodate time-varying network topologies. Numerical simulations are provided to support our theoretical findings., Comment: arXiv admin note: text overlap with arXiv:2401.11344

This paper proposes a problem-independent GRASP metaheuristic using the random-key optimizer (RKO) paradigm. GRASP (greedy randomized adaptive search procedure) is a metaheuristic for combinatorial optimization that repeatedly applies a semi-greedy construction procedure followed by a local search procedure. The best solution found over all iterations is returned as the solution of the GRASP. Continuous GRASP (C-GRASP) is an extension of GRASP for continuous optimization in the unit hypercube. A random-key optimizer (RKO) uses a vector of random keys to encode a solution to a combinatorial optimization problem. It uses a decoder to evaluate a solution encoded by the vector of random keys. A random-key GRASP is a C-GRASP where points in the unit hypercube are evaluated employing a decoder. We describe random key GRASP consisting of a problem-independent component and a problem-dependent decoder. As a proof of concept, the random-key GRASP is tested on five NP-hard combinatorial optimization problems: traveling salesman problem, tree of hubs location problem, Steiner triple covering problem, node capacitated graph partitioning problem, and job sequencing and tool switching problem., Comment: 24 pages, 8 figures

The intersection between quantum computing and optimisation has been an area of interest in recent years. There have been numerous studies exploring the application of quantum and quantum-hybrid solvers to various optimisation problems. This work explores scalarisation methods within the context of solving the bi-objective quadratic assignment problem using a quantum-hybrid solver. We show results that are consistent with previous research on a different Ising machine., Comment: 4 pages

We demonstrated the analogy between Economics and Gauge Theory of Plasticity and used it to describe the relationship between money supply and inflation at the economic market. The received equations of economical dynamics in phase space are similar to the plasticity equations and economic variables - choice, competition and profit correspond to the state of the market with inflation. We described the meaning of equations and the role of its variables in the stabilization mechanism of the market with inflation. The equation of market equilibrium including the Profit turnover, time changes of competition, capital and choice was discussed in detail., Comment: 9 pages

Goldstein's 1977 idealized iteration for minimizing a Lipschitz objective fixes a distance - the step size - and relies on a certain approximate subgradient. That "Goldstein subgradient" is the shortest convex combination of objective gradients at points within that distance of the current iterate. A recent implementable Goldstein-style algorithm allows a remarkable complexity analysis (Zhang et al. 2020), and a more sophisticated variant (Davis and Jiang, 2022) leverages typical objective geometry to force near-linear convergence. To explore such methods, we introduce a new modulus, based on Goldstein subgradients, that robustly measures the slope of a Lipschitz function. We relate near-linear convergence of Goldstein-style methods to linear growth of this modulus at minimizers. We illustrate the idea computationally with a simple heuristic for Lipschitz minimization.

Computational marketing has become increasingly important in today's digital world, facing challenges such as massive heterogeneous data, multi-channel customer journeys, and limited marketing budgets. In this paper, we propose a general framework for marketing AI systems, the Neural Optimization with Adaptive Heuristics (NOAH) framework. NOAH is the first general framework for marketing optimization that considers both to-business (2B) and to-consumer (2C) products, as well as both owned and paid channels. We describe key modules of the NOAH framework, including prediction, optimization, and adaptive heuristics, providing examples for bidding and content optimization. We then detail the successful application of NOAH to LinkedIn's email marketing system, showcasing significant wins over the legacy ranking system. Additionally, we share details and insights that are broadly useful, particularly on: (i) addressing delayed feedback with lifetime value, (ii) performing large-scale linear programming with randomization, (iii) improving retrieval with audience expansion, (iv) reducing signal dilution in targeting tests, and (v) handling zero-inflated heavy-tail metrics in statistical testing., Comment: KDD 2024

Neural networks have emerged as a tool for solving differential equations in many branches of engineering and science. But their progress in frequency domain acoustics is limited by the vanishing gradient problem that occurs at higher frequencies. This paper discusses a formulation that can address this issue. The problem of solving the governing differential equation along with the boundary conditions is posed as an unconstrained optimization problem. The acoustic field is approximated to the output of a neural network which is constructed in such a way that it always satisfies the boundary conditions. The applicability of the formulation is demonstrated on popular problems in plane wave acoustic theory. The predicted solution from the neural network formulation is compared with those obtained from the analytical solution. A good agreement is observed between the two solutions. The method of transfer learning to calculate the particle velocity from the existing acoustic pressure field is demonstrated with and without mean flow effects. The sensitivity of the training process to the choice of the activation function and the number of collocation points is studied., Comment: Published Journal Article

Directional fields, including unit vector, line, and cross fields, are essential tools in the geometry processing toolkit. The topology of directional fields is characterized by their singularities. While singularities play an important role in downstream applications such as meshing, existing methods for computing directional fields either require them to be specified in advance, ignore them altogether, or treat them as zeros of a relaxed field. While fields are ill-defined at their singularities, the graphs of directional fields with singularities are well-defined surfaces in a circle bundle. By lifting optimization of fields to optimization over their graphs, we can exploit a natural convex relaxation to a minimal section problem over the space of currents in the bundle. This relaxation treats singularities as first-class citizens, expressing the relationship between fields and singularities as an explicit boundary condition. As curvature frustrates finite element discretization of the bundle, we devise a hybrid spectral method for representing and optimizing minimal sections. Our method supports field optimization on both flat and curved domains and enables more precise control over singularity placement., Comment: 20 pages, 21 figures; to appear at SIGGRAPH 2024

In this paper we theoretically show that interior-point methods based on self-concordant barriers possess favorable global complexity beyond their standard application area of convex optimization. To do that we propose first- and second-order methods for non-convex optimization problems with general convex set constraints and linear constraints. Our methods attain a suitably defined class of approximate first- or second-order KKT points with the worst-case iteration complexity similar to unconstrained problems, namely $O(\varepsilon^{-2})$ (first-order) and $O(\varepsilon^{-3/2})$ (second-order), respectively., Comment: arXiv admin note: text overlap with arXiv:2111.00100

The incorporation of generative models as regularisers within variational formulations for inverse problems has proven effective across numerous image reconstruction tasks. However, the resulting optimisation problem is often non-convex and challenging to solve. In this work, we show that score-based generative models (SGMs) can be used in a graduated optimisation framework to solve inverse problems. We show that the resulting graduated non-convexity flow converge to stationary points of the original problem and provide a numerical convergence analysis of a 2D toy example. We further provide experiments on computed tomography image reconstruction, where we show that this framework is able to recover high-quality images, independent of the initial value. The experiments highlight the potential of using SGMs in graduated optimisation frameworks. The source code is publicly available on GitHub., Comment: 8 pages

Stochastic matching is the stochastic version of the well-known matching problem, which consists in maximizing the rewards of a matching under a set of probability distributions associated with the nodes and edges. In most stochastic matching problems, the probability distributions inherent in the nodes and edges are set a priori and are not controllable. However, many resource allocation platforms can control the probability distributions by changing prices. For example, a rideshare platform can control the distribution of the number of requesters by setting the fare to maximize the reward of a taxi-requester matching. Although several methods for optimizing price have been developed, optimizations in consideration of the matching problem are still in its infancy. In this paper, we tackle the problem of optimizing price in the consideration of the resulting bipartite graph matching, given the effect of the price on the probabilistic uncertainty in the graph. Even though our problem involves hard to evaluate objective values and is non-convex, we construct a (1-1/e)-approximation algorithm under the assumption that a convex min-cost flow problem can be solved exactly., Comment: 29 pages, 2 figures, 4 tables

Driven by the significant advantages offered by quantum computing, research in quantum machine learning has increased in recent years. While quantum speed-up has been demonstrated in some applications of quantum machine learning, a comprehensive understanding of its underlying mechanisms for improved performance remains elusive. Our study fills this gap by examining the expressibility of quantum circuits integrated within a convolutional neural network (CNN). Through numerical training on the MNIST dataset, our hybrid quantum-classical CNN model exhibited superior feature selection capabilities and significantly reduced the required training steps compared to the classical CNN. To understand the root of this enhanced performance, we conducted an analytical investigation of the functional expressibility of quantum circuits and derived a quantum activation function. We demonstrated that this quantum activation is more efficient in selecting important features and discarding unimportant information of input images. These findings not only deepen our comprehension of quantum-enhanced machine-learning models but also advance the classical machine-learning technique by introducing the quantum-inspired activation function., Comment: 12 pages, 6 figures

In the classical best approximation pair (BAP) problem, one is given two nonempty, closed, convex and disjoint subsets in a finite- or an infinite-dimensional Hilbert space, and the goal is to find a pair of points, each from each subset, which realizes the distance between the subsets. This problem, which has a long history, has found applications in science and technology. We discuss the problem in more general normed spaces and with possibly non-convex subsets, and focus our attention on the issues of uniqueness and existence of the solution to the problem. To the best of our knowledge these fundamental issues have not received much attention. In particular, we present several sufficient geometric conditions for the (at most) uniqueness of a BAP relative to these subsets. These conditions are related to the structure of the boundaries of the subsets, their relative orientation, and the structure of the unit sphere of the space. In addition, we present many sufficient conditions for the existence of a BAP, possibly without convexity . Our results allow us to significantly extend the horizon of the recent alternating simultaneous Halpern-Lions-Wittmann-Bauschke (A-S-HLWB) algorithm [Censor, Mansour and Reem, The alternating simultaneous Halpern-Lions-Wittmann-Bauschke algorithm for finding the best approximation pair for two disjoint intersections of convex sets, arXiv:2304.09600 (2023)] for solving the BAP problem.

Inexact interior-point methods (IPMs) are a type of interior-point methods that inexactly solve the linear equation system for obtaining the search direction. On the other hand, arc-search IPMs approximate the central path with an ellipsoidal arc obtained by solving two linear equation systems in each iteration, while conventional line-search IPMs solve one linear system. Therefore, the improvement due to the inexact solutions of the linear equation systems can be more beneficial in arc-search IPMs than conventional IPMs. In this paper, we propose an inexact infeasible arc-search interior-point method. We establish that the proposed method is a polynomial-time algorithm through its convergence analysis. The numerical experiments for the large benchmark problems show that the proposed method using the conjugate gradient method as the inexact linear system solver can reduce both of the number of iterations and the computation time compared to the existing inexact IPM due to the reduction in computational complexity by the arc-search. Andmore, it can reduce the computation time compared to the existing exact IPMs because the dependence of the computational complexity on the dimension $n$ of the coefficient matrix is smaller for the conjugate gradient method than for the Cholesky factorization., Comment: 25 pages, 3 figures