Optimization and Control (math.OC)

Abstract: This paper studies a variant of an accelerated gradient algorithm of Nesterov and Spokoiny. We call this algorithm the Nesterov-Spokoiny Acceleration (NSA). The NSA algorithm satisfies the following properties for smooth convex programs, 1. The sequence $\{ \mathbf{x}_k \}_{k \in \mathbb{N}} $ governed by the NSA satisfies $ \limsup\limits_{k \to \infty } k^2 ( f (\mathbf{x}_k ) - f^* ) = 0 $, where $f^* > -\infty$ is the minimum of the smooth convex function $f$. 2. The sequence $\{ \mathbf{x}_k \}_{k \in \mathbb{N}} $ governed by the NSA satisfies $ \liminf\limits_{k \to \infty } k^2 \log k \log\log k ( f (\mathbf{x}_k ) - f^* ) = 0 $. 3. The sequence $\{ \mathbf{y}_k \}_{k \in \mathbb{N}} $ governed by NSA satisfies $ \liminf\limits_{k \to \infty } k^3 \log k \log\log k \| \nabla f ( \mathbf{y}_k ) \|^2 = 0 $. Item 1 above is perhaps more important than items 2 and 3: For general smooth convex programs, NSA is the first gradient algorithm that achieves $o(k^{-2})$ convergence rate without proximal operations. Some extensions of the NSA algorithm are also studied. Also, our study on a zeroth-order variant of NSA shows that $o(1/k^2)$ convergence can be achieved via estimated gradient.

Abstract: In this paper, we address the so-called general Fokker-Planck control problem for discrete-time first-order linear systems. Unlike conventional treatments, we don't assume the distributions of the system states to be Gaussian. Instead, we only assume the existence and finiteness of the first several order power moments of the distributions. It is proved in the literature that there doesn't exist a solution, which has a form of conventional feedback control, to this problem. We propose a moment representation of the system to turn the original problem into a finite-dimensional one. Then a novel feedback control term, which is a mixture of a feedback term and a Markovian transition kernel term is proposed to serve as the control input of the moment system. The states of the moment system are obtained by maximizing the smoothness of the state transition. The power moments of the transition kernels are obtained by a convex optimization problem, of which the solution is proved to exist and be unique. Then they are mapped back to the probability distributions. The control inputs to the original system are then obtained by sampling from the realized distributions. Simulation results are provided to validate our algorithm in treating the general discrete-time Fokker-Planck control problem.

Abstract: Dispatchable region for renewables (DRR) depicts a space for renewables that a power system operator can manage by dispatching controllable resources. The DRR can be used to evaluate the distance from an operating point to a secure boundary and identify ramping events with the highest risk. However, existing approaches based on MILP reformulation or iteration-based LP algorithms may be computationally challenging. This paper investigates if advanced computation techniques, including high-performance computing and parallel computing techniques, can improve the computational performance.

Abstract: The paper considers the problem to estimate a graphical model corresponding to an autoregressive moving-average (ARMA) Gaussian stochastic process. We propose a new maximum entropy covariance and cepstral extension problem and we show that the problem admits an approximate solution which represents an ARMA graphical model whose topology is determined by the selected entries of the covariance lags considered in the extension problem. Then, we show how the corresponding dual problem is connected with the maximum likelihood principle. Such connection allows to design a Bayesian model and characterize an approximate maximum a posteriori estimator of the ARMA graphical model in the case the graph topology is unknown. We test the performance of the proposed method through some numerical experiments.

Abstract: A challenge in same-day delivery operations is that delivery requests are typically not known beforehand, but are instead revealed dynamically during the day. This uncertainty introduces a trade-off between dispatching vehicles to serve requests as soon as they are revealed to ensure timely delivery, and delaying the dispatching decision to consolidate routing decisions with future, currently unknown requests. In this paper we study the dynamic dispatch waves problem, a same-day delivery problem in which vehicles are dispatched at fixed decision moments. At each decision moment, the system operator must decide which of the known requests to dispatch, and how to route these dispatched requests. The operator's goal is to minimize the total routing cost while ensuring all requests are served on time. We propose iterative conditional dispatch (ICD), an iterative solution construction procedure based on a sample scenario approach. ICD iteratively solves sample scenarios to classify requests to be dispatched, postponed, or undecided. The set of undecided requests shrinks in each iteration until a final dispatching decision is made in the last iteration We develop two variants of ICD: one variant based on thresholds, and another variant based on similarity. A significant strength of ICD is that it is conceptually simple and easy to implement. This simplicity does not harm performance: through rigorous numerical experiments, we show that both variants efficiently navigate the large state and action spaces of the dynamic dispatch waves problem and quickly converge to a high-quality solution. In particular, the threshold-based ICD variant improves over a greedy myopic strategy by 27.2% on average, and outperforms methods from the literature by 0.8% on average, and up to 1.5% in several cases.

Abstract: We analyse a non-cooperative game between two competing ride-hailing platforms, each of which is modeled as a two-sided queueing system, where drivers (with a limited level of patience) are assumed to arrive according to a Poisson process at a fixed rate, while the arrival process of (price-sensitive) passengers is split across the two platforms based on Quality of Service (QoS) considerations. As a benchmark, we also consider a monopolistic scenario, where each platform gets half the market share irrespective of its pricing strategy. The key novelty of our formulation is that the total market share is fixed across the platforms. The game thus captures the competition between the platforms over market share, with pricing being the lever used by each platform to influence its share of the market. The market share split is modeled via two different QoS metrics: (i) probability that an arriving passenger gets a ride (driver availability), and (ii) probability that an arriving passenger gets an acceptable ride (driver availability and acceptable price). The platform aims to maximize the rate of revenue generated from matching drivers and passengers. In each of the above settings, we analyse the equilibria associated with the game in a certain limiting regime, where driver patience is scaled to infinity. We also show that these equilibria remain relevant in the more practically meaningful `pre-limit,' where drivers are highly (but not infinitely) patient. Interestingly, under the second QoS metric, we show that for a certain range of system parameters, no pure Nash equilibrium exists. Instead, we demonstrate a novel solution concept called an \textit{equilibrium cycle}, which has interesting dynamic connotations. Our results highlight the interplay between competition, passenger-side price sensitivity, and passenger/driver arrival rates.

Abstract: In this manuscript we consider optimal control problems of deterministic and stochastic differential equations with delays in the state and in the control. First we prove an equivalent Markovian reformulation on Hilbert spaces of the state equation. Then, using the dynamic programming approach for infinite-dimensional systems, we prove that the value function is the unique viscosity solution of the infinite-dimensional Hamilton Jacobi Bellman equation. Finally we apply this result to a stochastic optimal advertising problem with delays in the state and in the control.

Abstract: In this paper we investigate the turnpike property for constrained LQ optimal control problem in connection with dissipativity of the control system. We determine sufficient conditions to ensure the turnpike property in the case of a turnpike reference possibly occurring on the boundary of the state constraint set.

Abstract: This paper proposes a real moment-HSOS hierarchy for complex polynomial optimization problems with real coefficients. We show that this hierarchy provides the same sequence of lower bounds as the complex analogue, yet is much cheaper to solve. In addition, we prove that global optimality is achieved when the ranks of the moment matrix and certain submatrix equal two in case that a sphere constraint is present, and as a consequence, the complex polynomial optimization problem has either two real optimal solutions or a pair of conjugate optimal solutions. A simple procedure for extracting a pair of conjugate optimal solutions is given in the latter case. Various numerical examples are presented to demonstrate the efficiency of this new hierarchy, and an application to polyphase code design is also provided.

Abstract: We study the composite convex optimization problems with a Quasi-Self-Concordant smooth component. This problem class naturally interpolates between classic Self-Concordant functions and functions with Lipschitz continuous Hessian. Previously, the best complexity bounds for this problem class were associated with trust-region schemes and implementations of a ball-minimization oracle. In this paper, we show that for minimizing Quasi-Self-Concordant functions we can use instead the basic Newton Method with Gradient Regularization. For unconstrained minimization, it only involves a simple matrix inversion operation (solving a linear system) at each step. We prove a fast global linear rate for this algorithm, matching the complexity bound of the trust-region scheme, while our method remains especially simple to implement. Then, we introduce the Dual Newton Method, and based on it, develop the corresponding Accelerated Newton Scheme for this problem class, which further improves the complexity factor of the basic method. As a direct consequence of our results, we establish fast global linear rates of simple variants of the Newton Method applied to several practical problems, including Logistic Regression, Soft Maximum, and Matrix Scaling, without requiring additional assumptions on strong or uniform convexity for the target objective.

Abstract: This paper considers an extension of the vehicle routing problem with synchronization constraints and introduces the vehicle routing problem with multiple synchronization constraints and variable service time. This important problem is motivated by a real-world problem faced by one of the largest agricultural companies in the world providing precision agriculture services to their clients who are farmers and growers. The solution to this problem impacts the performance of farm spraying operations and can help design policies to improve spraying operations in large-scale farming. We propose a Mixed Integer Programming (MIP) model for this challenging problem, along with problem-specific valid inequalities. A three-phase powerful matheuristic is proposed to solve large instances enhanced with a novel local search method. We conduct extensive numerical analysis using realistic data. Results show that our matheuristic is fast and efficient in terms of solution quality and computational time compared to the state-of-the-art MIP solver. Using real-world data, we demonstrate the importance of considering an optimization approach to solve the problem, showing that the policy implemented in practice overestimates the costs by 15-20%. Finally, we compare and contrast the impact of various decision-maker preferences on several key performance metrics by comparing different mathematical models.