An inexact hybrid projection-proximal point algorithm for solving generalized mixed variational inequalities

In this paper, we investigate an inexact hybrid projection-proximal method for solving a class of generalized mixed variational inequalities in Hilbert spaces. We construct a general inexact hybrid projection-proximal point algorithm, in which an inexact relaxed proximal point step is followed by a suitable orthogonal projection onto a hyperplane. Under some suitable conditions concerned with the pseudomonotone set-valued mapping T, the nonsmooth convex function f and the step size λ_k, we prove the convergence of the inexact hybrid projection-proximal point algorithm for solving generalized mixed variational inequalities in Hilbert spaces.     

Step sequence planning for a biped robot by means of a cylindrical shape model and a high-resolution 2.5D map

A novel step sequence planning (SSP) method for biped-walking robots is presented. The method adopts a free space representation custom-designed for efficient biped robot motion planning. The method rests upon the approximation of the robot shape by a set of 3D cylindrical solids. This feature allows efficient determination of feasible paths in a 2.5D map, comprising stepping over obstacles and stair climbing. A SSP algorithm based on A^∗-search is proposed which uses the advantages of the aforementioned environment representation. The efficiency of the proposed approach is evaluated by a series of simulations performed for eight walking scenarios.     

A comparative runtime analysis of heuristic algorithms for satisfiability problems

The satisfiability problem is a basic core NP-complete problem. In recent years, a lot of heuristic algorithms have been developed to solve this problem, and many experiments have evaluated and compared the performance of different heuristic algorithms. However, rigorous theoretical analysis and comparison are rare. This paper analyzes and compares the expected runtime of three basic heuristic algorithms: RandomWalk, (1+1) EA, and hybrid algorithm. The runtime analysis of these heuristic algorithms on two 2-SAT instances shows that the expected runtime of these heuristic algorithms can be exponential time or polynomial time. Furthermore, these heuristic algorithms have their own advantages and disadvantages in solving different SAT instances. It also demonstrates that the expected runtime upper bound of RandomWalk on arbitrary k-SAT (k?3) is O(n(k−1)), and presents a k-SAT instance that has Θ(n(k−1)) expected runtime bound.     

Multi-frequency disturbance rejection via blending control technique for hard disk drives

This paper is concerned with the rejection of multiple narrowband disturbances in hard disk drives (HDDs). Inspired by a control blending idea, the multi-frequency disturbance rejection is formulated as a blending control problem. Each disturbance rejection is accomplished by using the H₂ optimal control method. Based on all H₂ optimal controllers, the blending technique is applied to yield a single controller which is capable of achieving rejection of all disturbances. Rejections of two and three disturbances for a 1.8-inch HDD VCM actuator are taken as application examples in the paper. Simulation and experimental results show that the ultimate controller results in a simultaneous attenuation of disturbances with frequencies higher or lower than the closed-loop system bandwidth. Moreover, the method turns out to be able to lift phase and thus prevent phase margin loss when it is used to deal with disturbances near bandwidth.     

Observer-based networked control for continuous-time systems with random sensor delays

This paper is concerned with the networked control system design for continuous-time systems with random measurement, where the measurement channel is assumed to subject to random sensor delay. A design scheme for the observer-based output feedback controller is proposed to render the closed-loop networked system exponentially mean-square stable with H_∞ performance requirement. The technique employed is based on appropriate delay systems approach combined with a matrix variable decoupling technique. The design method is fulfilled through solving linear matrix inequalities. A numerical example is used to verify the effectiveness and the merits of the present results.     

An alternative Kalman-Yakubovich-Popov lemma and some extensions

This paper introduces an alternative formulation of the Kalman-Yakubovich-Popov (KYP) Lemma, relating an infinite dimensional Frequency Domain Inequality (FDI) to a pair of finite dimensional Linear Matrix Inequalities (LMI). It is shown that this new formulation encompasses previous generalizations of the KYP Lemma which hold in the case the coefficient matrix of the FDI does not depend on frequency. In addition, it allows the coefficient matrix of the frequency domain inequality to vary affinely with the frequency parameter. One application of this results is illustrated in an example of computing upper bounds to the structured singular value with frequency-dependent scalings.     

Consistency constraints and 3D building reconstruction

Virtual architectural (indoor) scenes are often modeled in 3D for various types of simulation systems. For instance, some authors propose methods dedicated to lighting, heat transfer, acoustic or radio-wave propagation simulations. These methods rely in most cases on a volumetric representation of the environment, with adjacency and incidence relationships. Unfortunately, many buildings data are only given by 2D plans and the 3D needs varies from one application to another. To face these problems, we propose a formal representation of consistency constraints dedicated to building interiors and associated with a topological model. We show that such a representation can be used for: (i) reconstructing 3D models from 2D architectural plans (ii) detecting automatically geometrical, topological and semantical inconsistencies (iii) designing automatic and semi-automatic operations to correct and enrich a 2D plan. All our constraints are homogeneously defined in 2D and 3D, implemented with generalized maps and used in modeling operations. We explain how this model can be successfully used for lighting and radio-wave propagation simulations.     

On the decoding of binary cyclic codes with the Newton identities

We revisit in this paper the concept of decoding binary cyclic codes with Gröbner bases. These ideas were first introduced by Cooper, then Chen, Reed, Helleseth and Truong, and eventually by Orsini and Sala. We discuss here another way of putting the decoding problem into equations: the Newton identities. Although these identities have been extensively used for decoding, the work was done manually, to provide formulas for the coefficients of the locator polynomial. This was achieved by Reed, Chen, Truong and others in a long series of papers, for decoding quadratic residue codes, on a case-by-case basis. It is tempting to automate these computations, using elimination theory and Gröbner bases.Thus, we study in this paper the properties of the system defined by the Newton identities, for decoding binary cyclic codes. This is done in two steps, first we prove some facts about the variety associated with this system, then we prove that the ideal itself contains relevant equations for decoding, which lead to formulas.Then we consider the so-called online Gröbner basis decoding, where the work of computing a Gröbner basis is done for each received word. It is much more efficient for practical purposes than preprocessing and substituting into the formulas. Finally, we conclude with some computational results, for codes of interesting length (about one hundred).     

A comparison of tools for teaching formal software verification

We compare four tools regarding their suitability for teaching formal software verification, namely the Frege Program Prover, the Key system, Perfect Developer, and the Prototype Verification System (PVS). We evaluate them on a suite of small programs, which are typical of courses dealing with Hoare-style verification, weakest preconditions, or dynamic logic. Finally we report our experiences with using Perfect Developer in class.