Nonmonotone Barzilai–Borwein Gradient Algorithm for \ell _{1}-Regularized Nonsmooth Minimization in Compressive Sensing

This study aims to minimize the sum of a smooth function and a nonsmooth \(\ell _{1}\) -regularized term. This problem as a special case includes the \(\ell _{1}\) -regularized convex minimization problem in signal processing, compressive sensing, machine learning, data mining, and so on. However, the non-differentiability of the \(\ell _{1}\) -norm causes more challenges especially in large problems encountered in many practical applications. This study proposes, analyzes, and tests a Barzilai–Borwein gradient algorithm. At each iteration, the generated search direction demonstrates descent property and can be easily derived by minimizing a local approximal quadratic model and simultaneously taking the favorable structure of the \(\ell _{1}\) -norm. A nonmonotone line search technique is incorporated to find a suitable stepsize along this direction. The algorithm is easily performed, where each iteration requiring the values of the objective function and the gradient of the smooth term. Under some conditions, the proposed algorithm appears globally convergent. The limited experiments using some nonconvex unconstrained problems from the CUTEr library with additive \(\ell _{1}\) -regularization illustrate that the proposed algorithm performs quite satisfactorily. Extensive experiments for \(\ell _{1}\) -regularized least squares problems in compressive sensing verify that our algorithm compares favorably with several state-of-the-art algorithms that have been specifically designed in recent years.     

On matrices, automata, and double counting in constraint programming

Matrix models are ubiquitous for constraint problems. Many such problems have a matrix of variables $\mathcal{M}$ , with the same constraint C defined by a finite-state automaton $\mathcal{A}$ on each row of $\mathcal{M}$ and a global cardinality constraint $\mathit{gcc}$ on each column of $\mathcal{M}$ . We give two methods for deriving, by double counting, necessary conditions on the cardinality variables of the $\mathit{gcc}$ constraints from the automaton $\mathcal{A}$ . The first method yields linear necessary conditions and simple arithmetic constraints. The second method introduces the cardinality automaton, which abstracts the overall behaviour of all the row automata and can be encoded by a set of linear constraints. We also provide a domain consistency filtering algorithm for the conjunction of lexicographic ordering constraints between adjacent rows of $\mathcal{M}$ and (possibly different) automaton constraints on the rows. We evaluate the impact of our methods in terms of runtime and search effort on a large set of nurse rostering problem instances.     

Accelerated Bregman Method for Linearly Constrained \ell _1–\ell _2 Minimization

In this paper, we consider the linearly constrained $\ell _1$ – $\ell _2$ minimization, and we propose an accelerated Bregman method for solving this minimization problem. The proposed method is based on the extrapolation technique, which is used in accelerated proximal gradient methods proposed by Nesterov and others, and on the equivalence between the Bregman method and the augmented Lagrangian method. A convergence rate of $\mathcal{O }(\frac{1}{k^2})$ is proved for the proposed method when it is applied to solve a more general linearly constrained nonsmooth convex minimization problem. We numerically test our proposed method on a synthetic problem from compressive sensing. The numerical results confirm that our accelerated Bregman method is faster than the original Bregman method.     

Hybrid back-propagation training with evolutionary strategies

This work presents a hybrid algorithm for neural network training that combines the back-propagation (BP) method with an evolutionary algorithm. In the proposed approach, BP updates the network connection weights, and a ( \(1+1\) ) Evolutionary Strategy (ES) adaptively modifies the main learning parameters. The algorithm can incorporate different BP variants, such as gradient descent with adaptive learning rate (GDA), in which case the learning rate is dynamically adjusted by the stochastic ( \(1+1\) )-ES as well as the deterministic adaptive rules of GDA; a combined optimization strategy known as memetic search. The proposal is tested on three different domains, time series prediction, classification and biometric recognition, using several problem instances. Experimental results show that the hybrid algorithm can substantially improve upon the standard BP methods. In conclusion, the proposed approach provides a simple extension to basic BP training that improves performance and lessens the need for parameter tuning in real-world problems.     

Robust sparsity-preserved learning with application to image visualization

Linear subspace learning is of great importance for the purpose of visualization of high-dimensional observations. Sparsity-preserved learning (SPL) is a recently developed technique for linear subspace learning. Its objective function is formulated by using the $\ell _2$ -norm, which implies that the obtained projection vectors are likely to be distorted by outliers. In this paper, we develop a new SPL algorithm called SPL-L1 based on the $\ell _1$ -norm instead of the $\ell _2$ -norm. The proposed approach seeks projection vectors by minimizing a reconstruction error subject to a constraint of samples dispersion, both of which are defined using the $\ell _1$ -norm. As a robust alternative, SPL-L1 works well in the presence of atypical samples. We design an iterative algorithm under the framework of bound optimization to solve the projection vectors of SPL-L1. The experiments on image visualization demonstrate the superiority of the proposed method.     

Solving set-valued constraint satisfaction problems

In this paper, we consider the resolution of constraint satisfaction problems in the case where the variables of the problem are subsets of ${\mathbb{R}^{n}}$ . In order to use a constraint propagation approach, we introduce set intervals (named i-sets), which are sets of subsets of ${\mathbb{R}^{n}}$ with a lower bound and an upper bound with respect to the inclusion. Then, we propose basic operations for i-sets. This makes possible to build contractors that are then used by the propagation to solve problem involving sets as unknown variables. In order to illustrate the principle and the efficiency of the approach, a testcase is provided.     

New preconditioners for systems of linear equations with Toeplitz structure

In this paper, we consider applying the preconditioned conjugate gradient (PCG) method to solve system of linear equations $T x = \mathbf b $ where $T$ is a block Toeplitz matrix with Toeplitz blocks (BTTB). We first consider Level-2 circulant preconditioners based on generalized Jackson kernels. Then, BTTB preconditioners based on a splitting of BTTB matrices are proposed. We show that the BTTB preconditioners based on splitting are special cases of embedding-based BTTB preconditioners, which are also good BTTB preconditioners. As an application, we apply the proposed preconditioners to solve BTTB least squares problems. Our preconditioners work for BTTB systems with nonnegative generating functions. The implementations of the construction of the preconditioners and the relevant matrix-vector multiplications are also presented. Finally, Numerical examples, including image restoration problems, are presented to demonstrate the efficiency of our proposed preconditioners.     

A new set distance and its application to shape registration

We propose a new distance measure, called Complement weighted sum of minimal distances, between finite sets in ${\mathbb Z }^n$ and evaluate its usefulness for shape registration and matching. In this set distance the contribution of each point of each set is weighted according to its distance to the complement of the set. In this way, outliers and noise contribute less to the new similarity measure. We evaluate the performance of the new set distance for registration of shapes in binary images and compare it to a number of often used set distances found in the literature. The most extensive evaluation uses a set of synthetic 2D images. We also show three examples of real problems: registering a set of 2D images extracted from synchrotron radiation micro-computed tomography (SR $\upmu $ CT) volumes depicting bone implants; the difficult multi-modal registration task of finding the exact location of a 2D slice of a bone implant, as imaged by a light microscope, within a 3D SR $\upmu $ CT volume of the same implant; and finally recognition of handwritten characters. The evaluation shows that our new set distance performs well for all tasks and outperforms the other observed distance measures in most cases. It is therefore useful in many image registration and shape comparison tasks.     

An optimal arc consistency algorithm for a particular case of sequence constraint

The AtMostSeqCard constraint is the conjunction of a cardinality constraint on a sequence of n variables and of n???q?+?1 constraints AtMost u on each subsequence of size q. This constraint is useful in car-sequencing and crew-rostering problems. In van Hoeve et al. (Constraints 14(2):273–292, 2009), two algorithms designed for the AmongSeq constraint were adapted to this constraint with an O(2 ^q n) and O(n ³) worst case time complexity, respectively. In Maher et al. (2008), another algorithm similarly adaptable to filter the AtMostSeqCard constraint with a time complexity of O(n ²) was proposed. In this paper, we introduce an algorithm for achieving arc consistency on the AtMostSeqCard constraint with an O(n) (hence optimal) worst case time complexity. Next, we show that this algorithm can be easily modified to achieve arc consistency on some extensions of this constraint. In particular, the conjunction of a set of m AtMostSeqCard constraints sharing the same scope can be filtered in O(nm). We then empirically study the efficiency of our propagator on instances of the car-sequencing and crew-rostering problems.     

Global minimum cost design of a welded square stiffened plate supported at four corners

This paper presents the application of a refined version of the original Snyman–Fatti (SF) global continuous optimization algorithm (Snyman and Fatti, J Optimiz Theory Appl 54:121–141, 1987) to the optimal design of welded square stiffened plates. In particular we investigate square plates of square symmetry subjected to uniformly distributed normal static loads, supported at four corners, and stiffened by a square symmetrical orthogonal grid of ribs. Halved rolled I-section stiffeners are used welded to the base plate by double fillet welds. Profiles of different size are used for internal and edge stiffeners. A cost calculation method, developed by the first two authors and mainly used for welded structures (Farkas and Jármai 2003), allows for the computation of cost for different proposed designs of the welded stiffened plates. The cost function includes material, welding as well as painting costs, and is formulated according to the fabrication sequence. Design variables include base plate thickness as well as the dimensions of the edge and internal stiffeners. Constraints on stress in the base plate and in stiffeners, as well as on deflection of edge stiffeners and of internal stiffeners are considered. For this purpose the Snyman–Fatti (SF) global unconstrained trajectory method is adapted to handle constraints of this type. For control purposes a particle swarm optimization (PSO) algorithm is also applied to confirm the results given by the SF algorithm. Since the torsional stiffness of open section stiffeners is very small, the stiffened plates are modelled as a torsionless gridwork. We present an algorithm for calculating the moments and deflections for torsionless gridworks with different number of internal stiffeners, using the force method.     

Accelerated Linearized Bregman Method

In this paper, we propose and analyze an accelerated linearized Bregman (ALB) method for solving the basis pursuit and related sparse optimization problems. This accelerated algorithm is based on the fact that the linearized Bregman (LB) algorithm first proposed by Stanley Osher and his collaborators is equivalent to a gradient descent method applied to a certain dual formulation. We show that the LB method requires O(1/?) iterations to obtain an ?-optimal solution and the ALB algorithm reduces this iteration complexity to $O(1/\sqrt{\epsilon})$ while requiring almost the same computational effort on each iteration. Numerical results on compressed sensing and matrix completion problems are presented that demonstrate that the ALB method can be significantly faster than the LB method.     

Single-processor scheduling with time restrictions

We consider the following list scheduling problem. We are given a set \(S\) of jobs which are to be scheduled sequentially on a single processor. Each job has an associated processing time which is required for its processing. Given a particular permutation of the jobs in \(S\) , the jobs are processed in that order with each job started as soon as possible, subject only to the following constraint: For a fixed integer \(B \ge 2\) , no unit time interval \([x, x+1)\) is allowed to intersect more than \(B\) jobs for any real \(x\) . It is not surprising that this problem is NP-hard when the value \(B\) is variable (which is typical of many scheduling problems). There are several real world situations for which this restriction is natural. For example, suppose in addition to our jobs being executed sequentially on a single main processor, each job also requires the use of one of \(B\) identical subprocessors during its execution. Each time a job is completed, the subprocessor it was using requires one unit of time in order to reset itself. In this way, it is never possible for more than \(B\) jobs to be worked on during any unit interval. In this paper we carry out a classical worst-case analysis for this situation. In particular, we show that any permutation of the jobs can be processed within a factor of \(2-1/(B-1)\) of the optimum (plus an additional small constant) when \(B \ge 3\) and this factor is best possible. For the case \(B=2\) , the situation is rather different, and in this case the corresponding factor we establish is \(4/3\) (plus an additional small constant), which is also best possible. It is fairly rare that best possible bounds can be obtained for the competitive ratios of list scheduling problems of this general type.     

A note on reverse scheduling with maximum lateness objective

The inverse and reverse counterparts of the single-machine scheduling problem $1||L_{\max }$ are studied in [2], in which the complexity classification is provided for various combinations of adjustable parameters (due dates and processing times) and for five different types of norm: $\ell _{1},\ell _{2},\ell _{\infty },\ell _{H}^{\Sigma } $ , and $\ell _{H}^{\max }$ . It appears that the $O(n^{2})$ -time algorithm for the reverse problem with adjustable due dates contains a flaw. In this note, we present the structural properties of the reverse model, establishing a link with the forward scheduling problem with due dates and deadlines. For the four norms $\ell _{1},\ell _{\infty },\ell _{H}^{\Sigma }$ , and $ \ell _{H}^{\max }$ , the complexity results are derived based on the properties of the corresponding forward problems, while the case of the norm $\ell _{2}$ is treated separately. As a by-product, we resolve an open question on the complexity of problem $1||\sum \alpha _{j}T_{j}^{2}$ .     

Variational Image Segmentation Models Involving Non-smooth Data-Fidelity Terms

This article introduces a class of piecewise-constant image segmentation models that involves $L^1$ norms as data fidelity measures. The $L^1$ norms enable to segment images with low contrast or outliers such as impulsive noise. The regions to be segmented are represented as smooth functions instead of the Heaviside expression of level set functions as in the level set method. In order to deal with both non-smooth data-fitting and regularization terms, we use the variable splitting scheme to obtain constrained optimization problems, and apply an augmented Lagrangian method to solve the problems. This results in fast and efficient iterative algorithms for piecewise-constant image segmentation. The segmentation framework is extended to vector-valued images as well as to a multi-phase model to deal with arbitrary number of regions. We show comparisons with Chan-Vese models that use $L^2$ fidelity measures, to enlight the benefit of the $L^1$ ones.     

Integrated damping parameter and control design in structural systems for \bf{\mathcal{H}^2} and {\mathcal{H}^{\infty}} specifications

The paper presents a linear matrix inequality (LMI)-based approach for the simultaneous optimal design of output feedback control gains and damping parameters in structural systems with collocated actuators and sensors. The proposed integrated design is based on simplified $\mathcal{H}^2$ and $\mathcal{H}^{\infty}$ norm upper bound calculations for collocated structural systems. Using these upper bound results, the combined design of the damping parameters of the structural system and the output feedback controller to satisfy closed-loop $\mathcal{H}^2$ or $\mathcal{H}^{\infty}$ performance specifications is formulated as an LMI optimization problem with respect to the unknown damping coefficients and feedback gains. Numerical examples motivated from structural and aerospace engineering applications demonstrate the advantages and computational efficiency of the proposed technique for integrated structural and control design. The effectiveness of the proposed integrated design becomes apparent, especially in very large scale structural systems where the use of classical methods for solving Lyapunov and Riccati equations associated with $\mathcal{H}^2$ and $\mathcal{H}^{\infty}$ designs are time-consuming or intractable.     

An empirical comparison of learning algorithms for nonparametric scoring: the TreeRank algorithm and other methods

The TreeRank algorithm was recently proposed in [1] and [2] as a scoring-based method based on recursive partitioning of the input space. This tree induction algorithm builds orderings by recursively optimizing the Receiver Operating Characteristic curve through a one-step optimization procedure called LeafRank. One of the aim of this paper is the in-depth analysis of the empirical performance of the variants of TreeRank/LeafRank method. Numerical experiments based on both artificial and real data sets are provided. Further experiments using resampling and randomization, in the spirit of bagging and random forests are developed [3, 4] and we show how they increase both stability and accuracy in bipartite ranking. Moreover, an empirical comparison with other efficient scoring algorithms such as RankBoost and RankSVM is presented on UCI benchmark data sets.     

Evolutionary Algorithms for Quantum Computers

In this article, we formulate and study quantum analogues of randomized search heuristics, which make use of Grover search (in Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pp. 212–219. ACM, New York, 1996) to accelerate the search for improved offsprings. We then specialize the above formulation to two specific search heuristics: Random Local Search and the (1+1) Evolutionary Algorithm. We call the resulting quantum versions of these search heuristics Quantum Local Search and the (1+1) Quantum Evolutionary Algorithm. We conduct a rigorous runtime analysis of these quantum search heuristics in the computation model of quantum algorithms, which, besides classical computation steps, also permits those unique to quantum computing devices. To this end, we study the six elementary pseudo-Boolean optimization problems OneMax, LeadingOnes, Discrepancy, Needle, Jump, and TinyTrap. It turns out that the advantage of the respective quantum search heuristic over its classical counterpart varies with the problem structure and ranges from no speedup at all for the problem Discrepancy to exponential speedup for the problem TinyTrap. We show that these runtime behaviors are closely linked to the probabilities of performing successful mutations in the classical algorithms.     

Optimal Error Estimates of Two Mixed Finite Element Methods for Parabolic Integro-Differential Equations with Nonsmooth Initial Data

In the first part of this article, a new mixed method is proposed and analyzed for parabolic integro-differential equations (PIDE) with nonsmooth initial data. Compared to the standard mixed method for PIDE, the present method does not bank on a reformulation using a resolvent operator. Based on energy arguments combined with a repeated use of an integral operator and without using parabolic type duality technique, optimal $L^2$ L 2 -error estimates are derived for semidiscrete approximations, when the initial condition is in $L^2$ L 2 . Due to the presence of the integral term, it is, further, observed that a negative norm estimate plays a crucial role in our error analysis. Moreover, the proposed analysis follows the spirit of the proof techniques used in deriving optimal error estimates for finite element approximations to PIDE with smooth data and therefore, it unifies both the theories, i.e., one for smooth data and other for nonsmooth data. Finally, we extend the proposed analysis to the standard mixed method for PIDE with rough initial data and provide an optimal error estimate in $L^2,$ L 2 , which improves upon the results available in the literature.