Extracting influential nodes on a social network for information diffusion

We address the combinatorial optimization problem of finding the most influential nodes on a large-scale social network for two widely-used fundamental stochastic diffusion models. The past study showed that a greedy strategy can give a good approximate solution to the problem. However, a conventional greedy method faces a computational problem. We propose a method of efficiently finding a good approximate solution to the problem under the greedy algorithm on the basis of bond percolation and graph theory, and compare the proposed method with the conventional method in terms of computational complexity in order to theoretically evaluate its effectiveness. The results show that the proposed method is expected to achieve a great reduction in computational cost. We further experimentally demonstrate that the proposed method is much more efficient than the conventional method using large-scale real-world networks including blog networks.     

Learning with infinitely many features

We propose a principled framework for learning with infinitely many features, situations that are usually induced by continuously parametrized feature extraction methods. Such cases occur for instance when considering Gabor-based features in computer vision problems or when dealing with Fourier features for kernel approximations. We cast the problem as the one of finding a finite subset of features that minimizes a regularized empirical risk. After having analyzed the optimality conditions of such a problem, we propose a simple algorithm which has the flavour of a column-generation technique. We also show that using Fourier-based features, it is possible to perform approximate infinite kernel learning. Our experimental results on several datasets show the benefits of the proposed approach in several situations including texture classification and large-scale kernelized problems (involving about 100 thousand examples).     

An approximate dynamic programming approach to convex quadratic knapsack problems

Quadratic knapsack problem (QKP) has a central role in integer and combinatorial optimization, while efficient algorithms to general QKPs are currently very limited. We present an approximate dynamic programming (ADP) approach for solving convex QKPs where variables may take any integer value and all coefficients are real numbers. We approximate the function value using (a) continuous quadratic programming relaxation (CQPR), and (b) the integral parts of the solutions to CQPR. We propose a new heuristic which adaptively fixes the variables according to the solution of CQPR. We report computational results for QKPs with up to 200 integer variables. Our numerical results illustrate that the new heuristic produces high-quality solutions to large-scale QKPs fast and robustly.     

基于光滑l0范数和修正牛顿法的压缩感知重建算法

基于光滑l0范数最小的压缩感知重建算法——SL0算法,通过引入光滑函数序列去逼近l0范数,从而将l0范数最小的问题转化为光滑函数的最优化问题.针对光滑函数的选取以及求解该函数的最优化问题,提出一种基于光滑l0范数和修正牛顿法的重建算法——NSL0算法.首先采用双曲正切函数序列来逼近l0范数,得到一个新的最优化问题;为了提高该优化问题的计算效率,推导出针对双曲正切函数的修正牛顿方向,并采用修正牛顿法进行求解.实验结果表明,在相同的测试条件下,NSL0算法无论在重建效果还是在计算时间方面都明显优于其他同类算法.     

Numerical Construction of Stackelberg Solutions in a Linear Positional Differential Game Based on the Method of Polyhedra

We consider the problem of constructing approximate Stackelberg solutions in a linear non-zero-sum positional differential game of two players with terminal payoffs and player controls chosen on convex polyhedra. A formalization of player strategies and motions generated by them is based on the formalization and results of the theory of zero-sum positional differential games developed by N.N. Krasovskii and his scientific school. The problem of finding a Stackelberg solution reduces to solving nonstandard optimal control problems. We propose an approach based on operations with convex polyhedra.     

Numerical and computational efficiency of solvers for two-phase problems

We consider two-phase flow problems, modelled by the Cahn–Hilliard equation. In this work, the nonlinear fourth-order equation is decomposed into a system of two coupled second-order equations for the concentration and the chemical potential.We analyse solution methods based on an approximate two-by-two block factorization of the Jacobian of the nonlinear discrete problem. We propose a preconditioning technique that reduces the problem of solving the non-symmetric discrete Cahn–Hilliard system to a problem of solving systems with symmetric positive definite matrices where off-the-shelf multilevel and multigrid algorithms are directly applicable. The resulting solution methods exhibit optimal convergence and computational complexity properties and are suitable for parallel implementation.We illustrate the efficiency of the proposed methods by various numerical experiments, including parallel results for large scale three dimensional problems.     

Wavelet kernel learning

This paper addresses the problem of optimal feature extraction from a wavelet representation. Our work aims at building features by selecting wavelet coefficients resulting from signal or image decomposition on an adapted wavelet basis. For this purpose, we jointly learn in a kernelized large-margin context the wavelet shape as well as the appropriate scale and translation of the wavelets, hence the name “wavelet kernel learning”. This problem is posed as a multiple kernel learning problem, where the number of kernels can be very large. For solving such a problem, we introduce a novel multiple kernel learning algorithm based on active constraints methods. We furthermore propose some variants of this algorithm that can produce approximate solutions more efficiently. Empirical analysis show that our active constraint MKL algorithm achieves state-of-the art efficiency. When used for wavelet kernel learning, our experimental results show that the approaches we propose are competitive with respect to the state-of-the-art on brain–computer interface and Brodatz texture datasets.     

The piecewise optimisation method for approximating uncertain optimal control problems under optimistic value criterion

In this paper, we introduce an approximate model and propose a piecewise optimisation method to simplify the expression of optimal control for an uncertain linear quadratic optimal control problem. First, we consider an optimal control problem of uncertain linear quadratic model under optimistic value criterion. Based on the equation of optimality, we deduce an analytic expression of optimal control. Then, we study an approximate model with control parameter and propose a piecewise optimisation method for solving the optimal parameter of such an approximate model. As an application, a four-wheel steering vehicle optimal control problem is given to show the utility of the proposed approximate model and the efficiency of the proposed piecewise optimisation method.     

On the computational complexity and generalization properties of multi-stage and stage-wise coupled scenario programs

We discuss the computational complexity and feasibility properties of scenario sampling techniques for uncertain optimization programs. We propose an alternative way of dealing with a special class of stage-wise coupled programs and compare it with existing methods in the literature in terms of feasibility and computational complexity. We identify trade-offs between different methods depending on the problem structure and the desired probability of constraint satisfaction. To illustrate our results, an example from the area of approximate dynamic programming is considered.     

An iterative algorithm for elliptic variational inequalities of the second kind

In this paper, we propose an iterative algorithm for a simplified friction problem which is formulated as an elliptic variational inequality of the second kind. We approximate the simplified friction problem by a discrete system with the finite element method. Based on the use of the linearized technique and by constructing a particular function, we put forward the new algorithm to get the discrete solution. This algorithm is attractive due to its simple proof of convergence and easy implementation. A linear equation is solved in each iteration. Numerical results confirm that our algorithm is efficient and mesh independent.     

Legendre–Galerkin spectral approximation for a nonlocal elliptic Kirchhof-type problem

We propose a numerical scheme to obtain an approximate solution of a nonlocal elliptic Kirchhof-type problem. We first reduce the problem to a nonlinear finite dimensional system by a Legendre–Galerkin spectral method and then solve it by an iterative process. Convergence of the iterative process and an error estimation of the approximate solution is provided. Numerical experiments are conducted to illustrate the performance of the proposed method.     

Initialization of Supervised Training for Parametric Estimation

This paper concerns the initialization problem of the training algorithm in Neural Networks. We focus herein on backpropagation networks with one hidden layer. The initialization of the weights is crucial; if the network is incorrectly initialized, it converges to local minima. The classical random initialization therefore appears as a very poor solution. If we were to consider the Taylor development of the mapping problem and the nonlinearity of sigmoids, the improvements could be very significant. We propose a new initialization scheme based on the search for an explicit approximate solution to the problem of mapping between pattern and target. Simulation results are presented which show that these original initializations avoid local minima, reduce training time, obtain a better generalization and estimate the network's size.     

Approximate Matching of Run-Length Compressed Strings

We focus on the problem of approximate matching of strings that have been compressed using run-length encoding. Previous studies have concentrated on the problem of computing the longest common subsequence (LCS) between two strings of length m and n , compressed to m' and n' runs. We extend an existing algorithm for the LCS to the Levenshtein distance achieving O(m'n+n'm) complexity. Furthermore, we extend this algorithm to a weighted edit distance model, where the weights of the three basic edit operations can be chosen arbitrarily. This approach also gives an algorithm for approximate searching of a pattern of m letters (m' runs) in a text of n letters (n' runs) in O(mm'n') time. Then we propose improvements for a greedy algorithm for the LCS, and conjecture that the improved algorithm has O(m'n') expected case complexity. Experimental results are provided to support the conjecture.     

A streamlined approximation and duality scheme for structural optimization

An efficient and commonly used approach to structural optimization is to solve a sequence of approximate design problems that are constructed iteratively. As is well-known, a major part of the computational burden of this scheme lies in the sensitivity analysis needed to state the approximate problems. We propose a possibility for reducing this burden by streamlining the calculations in a combined approximation and duality scheme for structural optimization. The difference between this scheme and the traditional one is that, instead of calculating all the constraint gradients to state an approximate design problem explicitly, linear combinations of these gradients are generated as they are needed during the solution of the approximate problem by the dual method. We show, by analysing some typical scenarios of problem characteristics, that this rearrangement of the calculations may be a computationally viable alternative to the traditional scheme. An advantage of streamlining the calculations is that there is no need to incorporate an active set strategy in the scheme, as is usually done, since all the design constraints may be taken into consideration without any loss of computational efficiency. This may, clearly, enhance the practical rate of convergence of the overall approximation scheme. Moreover, the proposed rearrangement of the calculations may make it computationally viable to apply iterative equation solvers to the structural analysis problem. Numerical results with direct as well as iterative equation solvers show that the streamlined scheme is a feasible and promising approach to structural optimization.     

Support for seamless data exchanges between web services through information mapping analysis using kernel methods

A challenging issue to web services interoperability is seamless data exchanges between web services to be composed. A solution to this problem is to establish semantic mappings from an information item to another. To do that, we present an approximate information mapping analysis. We propose a kernel-based structural similarity measure for XML documents. Simulation results with industrial XML data show that the proposed kernel-based measure outperforms other existing methods.     

Using evolution strategies to solve DEC-POMDP problems

Decentralized partially observable Markov decision process (DEC-POMDP) is an approach to model multi-robot decision making problems under uncertainty. Since it is NEXP-complete there is no efficient exact algorithm to solve these problems and in spite of the attention it has taken recently, so far only a few approximate solutions that can solve small problems have been proposed. In this study, we offer a novel approximate solution algorithm for DEC-POMDP problems using evolution strategies, and a novel approach to approximately calculate the fitness of the chromosomes which correspond to the expected reward. We also propose a new problem which is a more complex, modified version of the grid meeting problem and solve it. Our results show that our algorithm is scalable and we can solve problems that have more states than the problems attempted in previous studies.     

Construction of discrete-time models for port-controlled Hamiltonian systems with applications

The issues of constructing a discrete-time model for Hamiltonian systems are in general different from those for dissipative systems. We propose an algorithm for constructing an approximate discrete-time model, which guarantees Hamiltonian conservation. We show that the algorithm also preserves, in a weaker sense, the losslessness property of a class of port-controlled Hamiltonian systems. An application of the algorithm to port-controlled Hamiltonian systems with quadratic Hamiltonian is presented, and we use this to solve the stabilization problem for this class of systems based on the approximate discrete-time model constructed using the proposed algorithm. We illustrate the usefulness of the algorithm in designing a discrete-time controller to stabilize the angular velocity of the dynamics of a rigid body.     

A Cascadic Multigrid Algorithm for Semilinear Indefinite Elliptic Problems

We propose a cascadic multigrid algorithm for a semilinear indefinite elliptic problem. We use a standard finite element discretization with piecewise linear finite elements. The arising nonlinear equations are solved by a cascadic organization of Newton's method with frozen derivative on a sequence of nested grids. This gives a simple version of a multigrid method without projections on coarser grids. The cascadic multigrid algorithm starts on a comparatively coarse grid where the number of unknowns is small enough to obtain an approximate solution within sufficiently high precision without substantial computational effort. On each finer grid we perform exactly one Newton step taking the approximate solution from the coarsest grid as initial guess. The linear Newton systems are solved iteratively by a Jacobi-type iteration with special parameters using the approximate solution from the previous grid as initial guess. We prove that for a sufficiently fine initial grid and for a sufficiently good start approximation the algorithm yields an approximate solution within the discretization error on the finest grid and that the method has multigrid complexity with logarithmic multiplier. Received February 1999, revised July 13, 1999     

A stabilizing augmented grid for rectangular discretizations of the convection–diffusion–reaction problems

We propose a numerical method for approximate solution of the convection–diffusion–reaction problems in the case of small diffusion. The method is based on the standard Galerkin finite element method on an extended space defined on the original grid plus a subgrid, where the original grid consists of rectangular elements. On each rectangular elements, we construct a subgrid with few points whose locations are critical for the stabilization of the problem, therefore they are chosen specially depending on some specific conditions that depend on the problem data. The resulting subgrid is combined with the initial coarse mesh, eventually, to solve the problem in the framework of Galerkin method on the augmented grid. The results of the numerical experiments confirm that the proposed method shows similar stability features with the well-known stabilized methods for the critical range of problem parameters.     

A fluid approach to large volume job shop scheduling

We consider large volume job shop scheduling problems, in which there is a fixed number of machines, a bounded number of activities per job, and a large number of jobs. In large volume job shops it makes sense to solve a fluid problem and to schedule the jobs in such a way as to track the fluid solution. There have been several papers which used this idea to propose approximate solutions which are asymptotically optimal as the volume increases. We survey some of these results here. In most of these papers it is assumed that the problem consists of many identical copies of a fixed set of jobs. Our contribution in this paper is to extend the results to the far more general situation in which the many jobs are all different. We propose a very simple heuristic which can schedule such problems. We discuss asymptotic optimality of this heuristic, under a wide range of previously unexplored situations. We provide a software package to explore the performance of our policy, and present extensive computational evidence for its effectiveness.