On the Black-Box Complexity of Sperner’s Lemma

We present several results on the complexity of various forms of Sperner’s Lemma in the black-box model of computing. We give a deterministic algorithm for Sperner problems over pseudo-manifolds of arbitrary dimension. The query complexity of our algorithm is linear in the separation number of the skeleton graph of the manifold and the size of its boundary. As a corollary we get an deterministic query algorithm for the black-box version of the problem 2D-SPERNER, a well studied member of Papadimitriou’s complexity class PPAD. This upper bound matches the deterministic lower bound of Crescenzi and Silvestri. The tightness of this bound was not known before. In another result we prove for the same problem an lower bound for its probabilistic, and an lower bound for its quantum query complexity, showing that all these measures are polynomially related. Research supported by the European Commission IST Integrated Project Qubit Application (QAP) 015848, the OTKA grants T42559 and T46234, and by the ANR Blanc AlgoQP grant of the French Research Ministry.     

Combining the Hanning windowed interpolated FFT in both directions

The interpolated fast Fourier transform (IFFT) has been proposed as a way to eliminate the picket fence effect (PFE) of the fast Fourier transform. The modulus based IFFT, cited in most relevant references, makes use of only the 1st and 2nd highest spectral lines. An approach using three principal spectral lines is proposed. This new approach combines both directions of the complex spectrum based IFFT with the Hanning window. The optimal weight to minimize the estimation variance is established on the first order Taylor series expansion of noise interference. A numerical simulation is carried out, and the results are compared with the Cramer-Rao bound. It is demonstrated that the proposed approach has a lower estimation variance than the two-spectral-line approach. The improvement depends on the extent of sampling deviating from the coherent condition, and the best is decreasing variance by 2/7. However, it is also shown that the estimation variance of the windowed IFFT with the Hanning is significantly higher than that of without windowing.     

Improved robust exponential stability for Takagi–Sugeno fuzzy uncertain systems with time-varying delays

This paper concerns managing the robust exponential stability problem of uncertain Takagi–Sugeno fuzzy systems with time-varying delay by employing a further improved integral inequality matrix approach. Based on the linear matrix inequality (LMI) approach, delay-dependent robust exponential stability criteria have been developed. By taking the relationship among the time-varying delay, its upper bound and their difference into account, some less conservative LMI-based delay-dependent robust exponential stability criteria are obtained without ignoring any useful terms in the derivative of Lyapunov–Krasovskii functionals. Maximum allowable upper bound for time-varying delays is determined. Numerical examples are provided to show that the obtained results significantly improve the allowed upper bounds of delay size over some methods existing in the literature.     

An efficient optimal algorithm for the quantity discount problem in material requirement planning

An optimal algorithm based on branch-and-bound approach is presented in this paper to determine lot sizes for a single item in material requirement planning environments with deterministic time-phased demand and constant ordering cost with zero lead time, where all-units discounts are available from vendors and backlog is not permitted. On the basis of the proven properties of optimal order policy, a tree-search procedure is presented to construct the sequence of optimal orders. Some useful fathom rules have been proven, which make the algorithm very efficient. To compare the performance of this algorithm with the other existing optimal algorithms, an experimental design with various environments has been developed. Experimental results show that the performance of our optimal algorithm is much better than the performance of other existing optimal algorithms. Considering computational time as the performance measure, this algorithm is considered the best among the existing optimal algorithms for real problems with large dimensions (i.e. large number of periods and discount levels).     

The labeled maximum matching problem

Given a graph G where a label is associated with each edge, we address the problem of looking for a maximum matching of G using the minimum number of different labels, namely the labeled maximum matching problem. It is a relatively new problem whose application is related to the timetabling problem. We prove it is NP-complete and present four different mathematical formulations. Moreover, we propose an exact algorithm based on a branch-and-bound approach to solve it. We evaluate the performance of our algorithm on a wide set of instances and compare our computational times with the ones required by CPLEX to solve the proposed mathematical formulations. Test results show the effectiveness of our procedure, that hugely outperforms the solver.     

Least trace extended set-membership filter

To improve the consistency of estimation result, a least-trace extended set-membership filter (LTESMF) is presented for a class of nonlinear stochastic systems, which has linear output and unknown- but-bounded noise. Feedback technique is used instead of the intersection of ellipsoid-sets in the measurement update. The feedback parameter is optimized in order to minimize the trace of error bounded ellipsoid’s envelop matrix. A new stability analysis method was developed to prove the stochastic system’s stab...     

交互式凸组合法的混合时滞不确定中立系统的稳定性

针对带分布时滞和离散时滞的不确定中立型系统进行稳定性研究. 基于交互式凸组合方法和下界引理, 通过构造恰当的李雅普诺夫泛函, 适当分割时滞区间, 处理一组由凸参数逆加权的正函数线性组合(交互式凸组合), 给出线性矩阵不等式形式的系统鲁棒稳定性判据. 该方法允许离散时滞为变时滞, 增强了系统的鲁棒性能. 数值算例验证了所得结果的有效性和合理性.

     

Decentralised sampled-data control for large-scale systems with nonlinear interconnections

This paper presents a decentralised sampled-data control technique for a class of large-scale systems, which are considered to consist of linear subsystems and nonlinear interconnections. The decentralised sampled-data controller design problem is established using a closed-loop subsystem. Based on the controller design problem, the stability condition is derived for a closed-loop large-scale system, and the maximum interconnection bound is guaranteed to satisfy the stability condition. Also, its sufficient condition is formulated in terms of linear matrix inequalities. Finally, the effectiveness of the proposed technique is verified by using an example of the multi-machine power system.     

On Convergence of Volterra Series Expansion of a Class of Nonlinear Systems

A fundamental issue in conducting the analysis and design of a nonlinear system via Volterra series theory is how to ensure the excitation magnitude and/or model parameters will be in the appropriate range such that the nonlinear system has a convergent Volterra series expansion. To this aim, parametric convergence bounds of Volterra series expansion of nonlinear systems described by a NARX model, which can reveal under what excitation magnitude or within what parameter range a given NARX system is able to have a convergent Volterra series expansion subject to any given input signal, are investigated systematically in this paper. The existing bound results often are given as a function of the maximum input magnitude, which could be suitable for single‐tone harmonic inputs but very conservative for complicated inputs (e.g. multi‐tone or arbitrary inputs). In this study, the output response of nonlinear systems is expressed in a closed form, which is not only determined by the input magnitude but also related to the input energy or waveform. These new techniques result in more accurate bound criteria, which are not only functions of model parameters and the maximum input magnitude but also consider a factor reflecting the overall input energy or wave form. This is significant to practical applications, since the same nonlinear system could exhibit chaotic behavior subject to a simple single‐tone input but might not with respect to other different input signals (e.g. multi‐tone inputs) of the same input magnitude. The results provide useful guidance for the application of Volterra series‐based theory and methods from an engineering point of view. The Duffing equation is used as a benchmark example to show the effectiveness of the results.     

The ski-rental problem with multiple discount options

We propose the ski-rental problem with multiple discount options in which there are n options to rent an equipment. Every option has a rental duration; the longer the duration, the more the discount. This generalizes the standard ski-rental problem where one can only rent or buy. We present a 4-competitive on-line algorithm for our problem and show that no deterministic algorithm can have a smaller competitive ratio when n is large enough. Comparing with the original ski-rental problem, the competitive ratio becomes larger when there are more options.