Optimization and Control (math.OC)

Abstract: Affine flows on vector bundles with chain transitive base flow are lifted to linear flows and the decomposition into exponentially separated subbundles provided by Selgrade's theorem is determined. The results are illustrated by an application to affine control systems with bounded control range.

Abstract: Scheduling problems are often tackled independently, and rarely solved by leveraging the commonalities across problems. Lack of awareness of this inter-task similarity could impede the search efficacy. A quantifiable relationship between scheduling problems is to-date rather unclear, how to leverage it in combinatorial optimization remains largely unknown, and its effects on search are also undeterminable. This paper addresses these hard questions by delving into quantifiable useful inter-task relationships and, through leveraging the explicit relationship, presenting a speed-up algorithm. After deriving an analytical inter-task distance metric to quantitatively reveal latent similarity across scheduling problems, an adaptive transfer of multi-modality knowledge is devised to promptly adjust the transfer in forms of explicit and implicit knowledge in response to heterogeneity in the inter-task discrepancy. For faintly related problems with disappearing dependences, a problem transformation function is suggested with a matching-feature-based greedy policy, and the function projects faintly related problems into a latent space where these problems gain similarity in a way that creates search speed-ups. Finally, a multi-task scatter search combinatorial algorithm is formed and a large-scale multi-task benchmark is generated serving the purposes of validation. That the algorithm exhibits dramatic speed-ups of 2~3 orders of magnitude, as compared to direct problem solving in strongly related problems and 3 times faster in weakly related ones, suggests leveraging commonality across problems could be successful.

Abstract: In this era of digitalization, data has widely been used in control engineering. While stability analysis is a mainstay for control science, most stability analysis tools still require explicit knowledge of the model or a high-fidelity simulator. In this work, a new data-driven Lyapunov analysis framework is proposed. Without using the model or its simulator, the proposed approach can learn a piece-wise affine Lyapunov function with a finite and fixed off-line dataset. The learnt Lyapunov function is robust to any dynamics that are consistent with the off-line dataset. Along the development of proposed scheme, the Lyapunov stability criterion is generalized. This generalization enables an iterative algorithm to augment the region of attraction.

Abstract: The combinatorial integral approximation (CIA) is a solution technique for integer optimal control problems. In order to regularize the solutions produced by CIA, one can minimize switching costs in one of its algorithmic steps. This leads to combinatorial optimization problems, which are called switching cost aware rounding problems (SCARP). They can be solved efficiently on one-dimensional domains but no efficient solution algorithms have been found so far for multi-dimensional domains. The CIA problem formulation depends on a discretization grid. We propose to reduce the number of variables and thus improve the computational tractability of SCARP by means of a non-uniform grid refinement strategy. We prove that the grid refinement preserves the approximation properties of the combinatorial integral approximation. Computational results are offered to show that the proposed approach is able to achieve, within a prescribed time limit, smaller duality gaps that does the uniform approach. For several large instances, a dual bound could only be obtained through adaptivity.

Abstract: This paper is concerned with the problem of nonlinear (stochastic) filter stability of a hidden Markov model (HMM) with white noise observations. The main contribution is the variance decay property which is used to conclude filter stability. The property is closely inspired by the Poincar\'e inequality (PI) in the study of stochastic stability of Markov processes. In this paper, the property is related to both the ergodicity of the Markov process as well as the observability of the HMM. The proofs are based upon a recently discovered minimum variance duality which is used to transform the nonlinear filtering problem into a stochastic optimal control problem for a backward stochastic differential equation (BSDE).

Abstract: This paper addresses the problem of enumerating all supported efficient solutions for a linear multi-objective integer minimum cost flow problem (MOIMCF). First, we highlight an inconsistency in various definitions of supported nondominated vectors for multi-objective integer linear programs (MOILP). Several characterizations for supported nondominated vectors/efficient solutions are used in the literature, which are equivalent in the non-integer case. However, they may lead to different sets of supported nondominated vectors/efficient solutions for MOILPs. This motivates us to summarize equivalent definitions and characterizations for supported efficient solutions and to distinguish between supported and weakly supported efficient solutions. In this paper we derive an output-polynomial time algorithm to determine all supported efficient solutions for MOIMCF problems. This is the first approach that solves this general problem in output-polynomial time. Moreover, we prove that the existence of an output-polynomial time algorithm to determine all weakly supported nondominated vectors (or all weakly supported efficient solutions) for a MOIMCF problem with a fixed number of d>3 objectives can be excluded, unless P = NP.

Abstract: We consider a smooth system of the form $\dot q=f_0(q)+\sum\limits_{i=1}^k u_i f_i(q)$, $q\in M,\ u_i\in\mathbb R,$ and study controllability issues on the group of diffeomorphisms of $M$. It is well-known that the system can arbitrarily well approximate the movement in the direction of any Lie bracket polynomial of $f_1,\ldots,f_k$. Any Lie bracket polynomial of $f_1,\ldots,f_k$ is good in this sense. Moreover, some combinations of Lie brackets which involve the drift term $f_0$ are also good but surely not all of them. In this paper we try to characterize good ones and, in particular, all universal good combinations, which are good for any nilpotent truncation of any system.

Abstract: We consider an online version of a longest path problem in an undirected and planar graph that is motivated by a location and routing problem occurring in the board game "Turn & Taxis". Path extensions have to be selected based on only partial knowledge on the order in which nodes become available in later iterations. Besides board games, online path extension problems have applications in disaster relief management when infrastructure has to be rebuilt after natural disasters. For example, flooding may affect large parts of a road network, and parts of the network may become available only iteratively and decisions may have to be made without the possibility of planning ahead. We suggest and analyse selection criteria that identify promising nodes (locations) for path extensions. We introduce the concept of tentacles of paths as an indicator for the future extendability. Different initialization and extension heuristics are suggested on compared to an ideal solution that is obtained by an integer linear programming formulation assuming complete knowledge, i.e., assuming that the complete sequence in which nodes become available is known beforehand. All algorithms are tested and evaluated on the original "Turn & Taxis" graph, and on an extended version of the "Turn & Taxis" graph, with different parameter settings. The numerical results confirm that the number of tentacles is a useful criterion when selecting path extensions, leading to near-optimal paths at relatively low computational costs.

Abstract: This paper is concerned with stochastic systems whose state is a diffusion process governed by an Ito stochastic differential equation (SDE). In the framework of a nominal white-noise model, the SDE is driven by a standard Wiener process. For a scenario of statistical uncertainty, where the driving noise acquires a state-dependent drift and thus deviates from its idealised model, we consider the perturbation of the invariant probability density function (PDF) as a steady-state solution of the Fokker-Planck-Kolmogorov equation. We discuss an upper bound on a logarithmic Dirichlet form for the ratio of the invariant PDF to its nominal counterpart in terms of the Kullback-Leibler relative entropy rate of the actual noise distribution with respect the Wiener measure. This bound is shown to be achievable, provided the PDF ratio is preserved by the nominal steady-state probability flux. The logarithmic Dirichlet form bound is used in order to obtain an upper bound on the relative entropy of the perturbed invariant PDF in terms of quadratic-exponential moments of the noise drift in the uniform ellipticity case. These results are illustrated for perturbations of Gaussian invariant measures in linear stochastic systems involving linear noise drifts.

Abstract: In machine learning applications, it is well known that carefully designed learning rate (step size) schedules can significantly improve the convergence of commonly used first-order optimization algorithms. Therefore how to set step size adaptively becomes an important research question. A popular and effective method is the Polyak step size, which sets step size adaptively for gradient descent or stochastic gradient descent without the need to estimate the smoothness parameter of the objective function. However, there has not been a principled way to generalize the Polyak step size for algorithms with momentum accelerations. This paper presents a general framework to set the learning rate adaptively for first-order optimization methods with momentum, motivated by the derivation of Polyak step size. It is shown that the resulting methods are much less sensitive to the choice of momentum parameter and may avoid the oscillation of the heavy-ball method on ill-conditioned problems. These adaptive step sizes are further extended to the stochastic settings, which are attractive choices for stochastic gradient descent with momentum. Our methods are demonstrated to be more effective for stochastic gradient methods than prior adaptive step size algorithms in large-scale machine learning tasks.

Abstract: In this paper, we consider a distributed online convex optimization problem over a time-varying multi-agent network. The goal of this network is to minimize a global loss function through local computation and communication with neighbors. To effectively handle the optimization problem with a high-dimensional and complicated constraint set, we develop a distributed online multiple Frank-Wolfe algorithm to avoid the expensive computational cost of projection operation. The dynamic regret bounds are established as $\mathcal{O}(T^{1-\gamma}+H_T)$ with the linear oracle number $\mathcal{O} (T^{1+\gamma})$, which depends on the horizon (total iteration number) $T$, the function variation $H_T$, and the tuning parameter $0<\gamma<1$. In particular, when the stringent computation requirement is satisfied, the bound can be enhanced to $\mathcal{O} (1+H_T)$. Moreover, we illustrate the significant advantages of the multiple iteration technique and reveal a trade-off between computational cost and dynamic regret bound. Finally, the performance of our algorithm is verified and compared through the distributed online ridge regression problems with two constraint sets.

Abstract: In this paper, we propose the first sketch-and-project Newton method with fast $\mathcal O(k^{-2})$ global convergence rate for self-concordant functions. Our method, SGN, can be viewed in three ways: i) as a sketch-and-project algorithm projecting updates of Newton method, ii) as a cubically regularized Newton ethod in sketched subspaces, and iii) as a damped Newton method in sketched subspaces. SGN inherits best of all three worlds: cheap iteration costs of sketch-and-project methods, state-of-the-art $\mathcal O(k^{-2})$ global convergence rate of full-rank Newton-like methods and the algorithm simplicity of damped Newton methods. Finally, we demonstrate its comparable empirical performance to baseline algorithms.

Abstract: The problem of finding the minimizer of a sum of convex functions is central to the field of optimization. In cases where the functions themselves are not fully known (other than their individual minimizers and convexity parameters), it is of interest to understand the region containing the potential minimizers of the sum based only on those known quantities. Characterizing this region in the case of multivariate strongly convex functions is far more complicated than the univariate case. In this paper, we provide both outer and inner approximations for the region containing the minimizer of the sum of two strongly convex functions, subject to a constraint on the norm of the gradient at the minimizer of the sum. In particular, we explicitly characterize the boundary and interior of both outer and inner approximations. Interestingly, the boundaries as well as the interiors turn out to be identical and we show that the boundary of the region containing the potential minimizers is also identical to that of the outer and inner approximations.

Abstract: We consider the problem of unconstrained minimization of finite sums of functions. We propose a simple, yet, practical way to incorporate variance reduction techniques into SignSGD, guaranteeing convergence that is similar to the full sign gradient descent. The core idea is first instantiated on the problem of minimizing sums of convex and Lipschitz functions and is then extended to the smooth case via variance reduction. Our analysis is elementary and much simpler than the typical proof for variance reduction methods. We show that for smooth functions our method gives $\mathcal{O}(1 / \sqrt{T})$ rate for expected norm of the gradient and $\mathcal{O}(1/T)$ rate in the case of smooth convex functions, recovering convergence results of deterministic methods, while preserving computational advantages of SignSGD.

Abstract: The clustering of data is one of the most important and challenging topics in data science. The minimum sum-of-squares clustering (MSSC) problem asks to cluster the data points into $k$ clusters such that the sum of squared distances between the data points and their cluster centers (centroids) is minimized. This problem is NP-hard, but there exist exact solvers that can solve such problem to optimality for small or medium size instances. In this paper, we use a branch-and-bound solver based on semidefinite programming relaxations called SOS-SDP to compute the optimum solutions of the MSSC problem for various $k$ and for multiple datasets, with real and artificial data, for which the data provider has provided ground truth clustering. Next, we use several extrinsic and intrinsic measures to evaluate how the optimum clustering and ground truth clustering matches, and how well these clusterings perform with respect to the criteria underlying the intrinsic measures. Our calculations show that the ground truth clusterings are generally far from the optimum solution to the MSSC problem. Moreover, the intrinsic measures evaluated on the ground truth clusterings are generally significantly worse compared to the optimum clusterings. However, when the ground truth clustering is in the form of convex sets, e.g., ellipsoids, that are well separated from each other, the ground truth clustering comes very close to the optimum clustering.