Search

Purpose of the paper is to present a model for the railway traffic that consists of train arrivals and departures at different stations and also the passenger movement in stations, boarding trains and alighting at different destinations. This is a classic example of hybrid system for which initially the existing models are evaluated and the needs of model for this problem scenario are identified. The model proposed is utilized to simulate an experimental setup with the traffic based on the Train schedule and passenger flow in the stations to analyse whether it can work without any conflicts, impacts on passenger comforts, all in a single model. With this, we can determine the schedule of the train for an optimised headway time based on constrains for passenger waiting times and train running times. The simulation results are presented with assumed figures of passenger flow and train traffic. At the end, the optimization formulation is shown to arrive at an optimum schedule. [ABSTRACT FROM AUTHOR]

The problem of synchronization over a group G aims to estimate a collection of group elements G 1 ⁎ , ... , G n ⁎ ∈ G based on noisy observations of a subset of all pairwise ratios of the form G i ⁎ G j ⁎ − 1. Such a problem has gained much attention recently and finds many applications across a wide range of scientific and engineering areas. In this paper, we consider the class of synchronization problems in which the group is a closed subgroup of the orthogonal group. This class covers many group synchronization problems that arise in practice. Our contribution is fivefold. First, we propose a unified approach for solving this class of group synchronization problems, which consists of a suitable initialization step and an iterative refinement step based on the generalized power method, and show that it enjoys a strong theoretical guarantee on the estimation error under certain assumptions on the group, measurement graph, noise, and initialization. Second, we formulate two geometric conditions that are required by our approach and show that they hold for various practically relevant subgroups of the orthogonal group. The conditions are closely related to the error-bound geometry of the subgroup — an important notion in optimization. Third, we verify the assumptions on the measurement graph and noise for standard random graph and random matrix models. Fourth, based on the classic notion of metric entropy, we develop and analyze a novel spectral-type estimator. Finally, we show via extensive numerical experiments that our proposed non-convex approach outperforms existing approaches in terms of computational speed, scalability, and/or estimation error. [ABSTRACT FROM AUTHOR]

In this paper, we establish hardness and approximation results for various Lp-ball constrained homogeneous polynomial optimization problems, where p ∈ [2, ∞]. Specifically, we prove that for any given d ≥ 3 and p ∈ [2, ∞], both the problem of optimizing a degree-d homogeneous polynomial over the Lp-ball and the problem of optimizing a degree-d multilinear form (regardless of its super-symmetry) over Lp-balls are NP-hard. On the other hand, we show that these problems can be approximated to within a factor of Ω((log n)(d-2)/p/nd/2-1) in deterministic polynomial time, where n is the number of variables. We further show that with the help of randomization, the approximation guarantee can be improved to Ω((log n/n)d/2-1), which is independent of p and is currently the best for the aforementioned problems. Our results unify and generalize those in the literature, which focus either on the quadratic case or the case where p ∈ {2, ∞}. We believe that the wide array of tools used in this paper will have further applications in the study of polynomial optimization problems. [ABSTRACT FROM AUTHOR]

Consider transceiver designs in a multiuser multi-input single-output (MISO) downlink channel, where the users are to receive the same data stream simultaneously. This problem, known as physical-layer multicasting, has drawn much interest. Presently, a popularized approach is transmit beamforming, in which the beamforming optimization is handled by a rank-one approximation method called semidefinite relaxation (SDR). SDR-based beamforming has been shown to be promising for a small or moderate number of users. This paper describes two new transceiver strategies for physical-layer multicasting. The first strategy, called stochastic beamforming (SBF), randomizes the beamformer in a per-symbol time-varying manner, so that the rank-one approximation in SDR can be bypassed. We propose several efficiently realizable SBF schemes, and prove that their multicast achievable rate gaps with respect to the MISO multicast capacity must be no worse than 0.8314 bits/s/Hz, irrespective of any other factors such as the number of users. The use of channel coding and the assumption of sufficiently long code lengths play a crucial role in achieving the above result. The second strategy combines transmit beamforming and the Alamouti space-time code. The result is a rank-two generalization of SDR-based beamforming. We show by analysis that this SDR-based beamformed Alamouti scheme has a better worst-case effective signal-to-noise ratio (SNR) scaling, and hence a better multicast rate scaling, than SDR-based beamforming. We further the work by combining SBF and the beamformed Alamouti scheme, wherein an improved constant rate gap of 0.39 bits/s/Hz is proven. Simulation results show that under a channel-coded, many-user setting, the proposed multicast transceiver schemes yield significant SNR gains over SDR-based beamforming at the same bit error rate level. [ABSTRACT FROM PUBLISHER]

Community detection in graphs that are generated according to stochastic block models (SBMs) has received much attention lately. In this paper, we focus on the binary symmetric SBM—in which a graph of n vertices is randomly generated by first partitioning the vertices into two equal-sized communities and then connecting each pair of vertices with probability that depends on their community memberships—and study the associated exact community recovery problem. Although the maximum-likelihood formulation of the problem is non-convex and discrete, we propose to tackle it using a popular iterative method called projected power iterations. To ensure fast convergence of the method, we initialize it using a point that is generated by another iterative method called orthogonal iterations, which is a classic method for computing invariant subspaces of a symmetric matrix. We show that in the logarithmic sparsity regime of the problem, with high probability the proposed two-stage method can exactly recover the two communities down to the information-theoretic limit in O (n log 2 n / log log n) time, which is competitive with a host of existing state-of-the-art methods that have the same recovery performance. We also conduct numerical experiments on both synthetic and real data sets to demonstrate the efficacy of our proposed method and complement our theoretical development. [ABSTRACT FROM AUTHOR]

In this paper, we study the problem of recovering a low-rank matrix from a number of random linear measurements that are corrupted by outliers taking arbitrary values. We consider a nonsmooth nonconvex formulation of the problem, in which we explicitly enforce the low-rank property of the solution by using a factored representation of the matrix variable and employ an l1- loss function to robustify the solution against outliers. We show that even when a constant fraction (which can be up to almost half) of the measurements are arbitrarily corrupted, as long as certain measurement operators arising from the measurement model satisfy the so-called l1/l2-restricted isometry property, the ground-truth matrix can be exactly recovered from any global minimum of the resulting optimization problem. Furthermore, we show that the objective function of the optimization problem is sharp and weakly convex. Consequently, a subgradient method (SubGM) with geometrically diminishing step sizes will converge linearly to the ground-truth matrix when suitably initialized. We demonstrate the efficacy of the SubGM for the nonconvex robust low-rank matrix recovery problem with various numerical experiments. [ABSTRACT FROM AUTHOR]

We consider optimization problems over the Stiefel manifold whose objective function is the summation of a smooth function and a nonsmooth function. Existing methods for solving this kind of problem can be classified into three categories. Algorithms in the first category rely on information of the subgradients of the objective function and thus tend to converge slowly in practice. Algorithms in the second category are proximal point algorithms, which involve subproblems that can be as difficult as the original problem. Algorithms in the third category are based on operatorsplitting techniques, but they usually lack rigorous convergence guarantees. In this paper, we propose a retraction-based proximal gradient method for solving this class of problems. We prove that the proposed method globally converges to a stationary point. Iteration complexity for obtaining an \epsilon -stationary solution is also analyzed. Numerical results on solving sparse PCA and compressed modes problems are reported to demonstrate the advantages of the proposed method. [ABSTRACT FROM AUTHOR]

We propose a new family of inexact sequential quadratic approximation (SQA) methods, which we call the inexact regularized proximal Newton (IRPN) method, for minimizing the sum of two closed proper convex functions, one of which is smooth and the other is possibly non-smooth. Our proposed method features strong convergence guarantees even when applied to problems with degenerate solutions while allowing the inner minimization to be solved inexactly. Specifically, we prove that when the problem possesses the so-called Luo–Tseng error bound (EB) property, IRPN converges globally to an optimal solution, and the local convergence rate of the sequence of iterates generated by IRPN is linear, superlinear, or even quadratic, depending on the choice of parameters of the algorithm. Prior to this work, such EB property has been extensively used to establish the linear convergence of various first-order methods. However, to the best of our knowledge, this work is the first to use the Luo–Tseng EB property to establish the superlinear convergence of SQA-type methods for non-smooth convex minimization. As a consequence of our result, IRPN is capable of solving regularized regression or classification problems under the high-dimensional setting with provable convergence guarantees. We compare our proposed IRPN with several empirically efficient algorithms by applying them to the ℓ 1 -regularized logistic regression problem. Experiment results show the competitiveness of our proposed method. [ABSTRACT FROM AUTHOR]

In this paper we consider the cubic regularization (CR) method, a regularized version of the classical Newton method, for minimizing a twice continuously differentiable function. While it is well known that the CR method is globally convergent and enjoys a superior global iteration complexity, existing results on its local quadratic convergence require a stringent nondegeneracy condition. We prove that under a local error bound (EB) condition, which is a much weaker requirement than the existing nondegeneracy condition, the sequence of iterates generated by the CR method converges at least Q-quadratically to a second-order critical point. This indicates that adding cubic regularization not only equips Newton's method with remarkable global convergence properties but also enables it to converge quadratically even in the presence of degenerate solutions. As a by-product, we show that without assuming convexity the proposed EB condition is equivalent to a quadratic growth condition, which could be of independent interest. To demonstrate the usefulness and relevance of our convergence analysis, we focus on two concrete nonconvex optimization problems that arise in phase retrieval and low-rank matrix recovery and prove that with overwhelming probability the sequence of iterates generated by the CR method for solving these two problems converges at least Q-quadratically to a global minimizer. To support and complement our theoretical development, we also present numerical results of the CR method when applied to solve these two problems. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the maximum flow routing strategy with dynamic link allocation under a constraint on the number of transceivers for space information networks (SINs). Specifically, the time-expanded graph (TEG) is exploited to characterize the dynamic topology of SINs. Furthermore, although there exist multiple feasible links for SINs, only a limited number of them can be actually established due to the constraint on the number of transceivers. Traditionally the established link is fixed within one time interval in the TEG. In order to fully exploit the resource of multiple feasible links, we divide each time interval in the TEG into multiple fine-grained time periods and design the maximum flow routing strategy by jointly optimizing both the fine-grained time period duration and the link allocation as well as the amount of data transmitted on each transmission link and the amount of data stored in each caching link. This problem can be formulated as a mixed-integer quadratic program (MIQP), which is difficult to solve. To overcome this difficulty, we transform the MIQP into an equivalent mixed-integer linear program (MILP), which can be effectively solved by existing methods. Simulation results show that the proposed dynamic link allocation strategy can significantly outperform the fixed link allocation strategy within each time interval. [ABSTRACT FROM AUTHOR]

This study presents PRISM, a probabilistic simplex component analysis approach to identifying the vertices of a data-circumscribing simplex from data. The problem has a rich variety of applications, the most notable being hyperspectral unmixing in remote sensing and non-negative matrix factorization in machine learning. PRISM uses a simple probabilistic model, namely, uniform simplex data distribution and additive Gaussian noise, and it carries out inference by maximum likelihood. The inference model is sound in the sense that the vertices are provably identifiable under some assumptions, and it suggests that PRISM can be effective in combating noise when the number of data points is large. PRISM has strong, but hidden, relationships with simplex volume minimization, a powerful geometric approach for the same problem. We study these fundamental aspects, and we also consider algorithmic schemes based on importance sampling and variational inference. In particular, the variational inference scheme is shown to resemble a matrix factorization problem with a special regularizer, which draws an interesting connection to the matrix factorization approach. Numerical results are provided to demonstrate the potential of PRISM. [ABSTRACT FROM AUTHOR]

We consider the problem of minimizing the $\ell _1$ norm of a linear map over the sphere, which arises in various machine learning applications such as orthogonal dictionary learning (ODL) and robust subspace recovery (RSR). The problem is numerically challenging due to its nonsmooth objective and nonconvex constraint, and its algorithmic aspects have not been well explored. In this paper, we show how the manifold structure of the sphere can be exploited to design fast algorithms with provable guarantees for tackling this problem. Specifically, our contribution is fourfold. First, we present a manifold proximal point algorithm (ManPPA) for the problem and show that it converges at a global sublinear rate. Furthermore, we show that ManPPA can achieve a local quadratic convergence rate when applied to sharp instances of the problem. Second, we develop a semismooth Newton-based inexact augmented Lagrangian method for computing the search direction in each iteration of ManPPA and show that it has an asymptotic superlinear convergence rate. Third, we propose a stochastic variant of ManPPA called StManPPA, which is well suited for large-scale computation, and establish its sublinear convergence rate. Both ManPPA and StManPPA have provably faster convergence rates than existing subgradient-type methods. Fourth, using ManPPA as a building block, we propose a new heuristic method for solving a matrix analog of the problem, in which the sphere is replaced by the Stiefel manifold. The results from our extensive numerical experiments on the ODL and RSR problems demonstrate the efficiency and efficacy of our proposed methods. [ABSTRACT FROM AUTHOR]

Consider the following problem: A multi-antenna base station (BS) sends multiple symbol streams to multiple single-antenna users via precoding. However, unlike conventional multiuser precoding, the transmitted signals are subjected to binary, unit-modulus, or even discrete unit-modulus constraints. Such constraints arise in the one-bit and constant-envelope (CE) massive MIMO scenarios, wherein high-resolution digital-toanalog converters (DACs) are replaced by one-bit DACs and phase shifters, respectively, for cutting down hardware cost and energy consumption. Multiuser precoding under one-bit and CE restrictions poses significant design difficulty. In this paper we establish a framework for designing multiuser precoding under the one-bit, continuous CE and discrete CE scenarios all within one theme. We first formulate a precoding design that focuses on minimization of the symbol-error probabilities (SEPs), assuming quadrature amplitude modulation (QAM) symbol constellations. We then devise an algorithm for our SEP-based design. The algorithm combines i) a novel penalty method for handling binary, unit-modulus and discrete unit-modulus constraints; and ii) a first-order non-convex optimization recipe custom-built for the design. Specifically, the latter is an inexact majorizationminimization method via accelerated projected gradient, which, as shown by simulations, runs very fast and can handle a large number of decision variables. Simulation results indicate that the proposed design offers significantly better bit-error rate performance than the existing designs. [ABSTRACT FROM AUTHOR]

Objective: The objective of this study is to apply machine learning algorithms for real-time and personalized waiting time prediction in emergency departments. We also aim to introduce the concept of systems thinking to enhance the performance of the prediction models., Methods: Four popular algorithms were applied: (i) stepwise multiple linear regression; (ii) artificial neural networks; (iii) support vector machines; and (iv) gradient boosting machines. A linear regression model served as a baseline model for comparison. We conducted computational experiments based on a dataset collected from an emergency department in Hong Kong. Model diagnostics were performed, and the results were cross-validated., Results: All the four machine learning algorithms with the use of systems knowledge outperformed the baseline model. The stepwise multiple linear regression reduced the mean-square error by almost 15%. The other three algorithms had similar performances, reducing the mean-square error by approximately 20%. Reductions of 17 - 22% in mean-square error due to the utilization of systems knowledge were observed., Discussion: The multi-dimensional stochasticity arising from the ED environment imposes a great challenge on waiting time prediction. The introduction of the concept of systems thinking led to significant enhancements of the models, suggesting that interdisciplinary efforts could potentially improve prediction performance., Conclusion: Machine learning algorithms with the utilization of the systems knowledge could significantly improve the performance of waiting time prediction. Waiting time prediction for less urgent patients is more challenging., (Copyright © 2020 Elsevier B.V. All rights reserved.)