Search

Clustering is a common task in data mining for constructing well-separated groups (clusters) from a large set of data points. The balanced minimum sum-of-squares clustering problem is a variant of the classic minimum sum-of-squares clustering (MSSC) problem and arises from broad real-life applications where the cardinalities of any two clusters differ by at most one. This study presents the first memetic algorithm for solving the balanced MSSC problem. The proposed algorithm combines a backbone-based crossover operator for generating offspring solutions and a responsive threshold search that alternates between a threshold-based exploration procedure and a descent-based improvement procedure for improving new offspring solutions. Numerical results on 16 real-life datasets show that the proposed algorithm competes very favorably with several state-of-the-art methods from the literature. Key components of the proposed algorithm are investigated to understand their effects on the performance of the algorithm.

In this study, we focus mainly on the problem of finding the minimum-length path through a set of circular regions by a fixed-wing unmanned aerial vehicle. Such a problem is referred to as the Dubins traveling salesman problem with neighborhoods (DTSPN). Algorithms developed in the literature for solving DTSPN either are computationally demanding or generate low-quality solutions. To achieve a better trade-off between solution quality and computational cost, an efficient gradient-free descent method is designed. The core idea of the descent method is to decompose DTSPN into a series of subproblems, each of which consists of finding the minimum-length path of a Dubins vehicle from a configuration to another configuration via an intermediate circular region. By analyzing the geometric properties of the subproblems, we use a bisection method to solve the subproblems. As a result, the descent method can efficiently address DTSPN by successively solving a series of subproblems. Finally, several numerical experiments are carried out to demonstrate the descent method in comparison with several existing algorithms.

In this paper, we suggest a descent modification of the conjugate gradient method which converges globally provided that the exact minimization condition is satisfied. Preliminary numerical experiments on some benchmark problems show that the method is efficient and promising.

We propose a global optimization algorithm hybridizing a version of Bayesian global search with local minimization. The implementation of Bayesian algorithm is based on the simplician partition of the feasible region. Our implementation is free from the typical computational complexity of the standard implementations of Bayesian algorithms. The local minimization counterpart improves the efficiency of search in the indicated potential basins of global minimum. The performance of the proposed algorithm is illustrated by the results of a numerical experiment.

This paper proposes a discrete-time, distributed algorithm for multi-agent networks to achieve the minimum l1-norm solution to a group of linear equations known to possess a family of solutions. We assume each agent in the network knows only one equation and can communicate with only its neighbors. The algorithm is developed based on a combination of the projection-consensus idea and the sub-gradient descent method. Given the underlying network graph to be directed and strongly connected, we prove that the algorithm enables all agents to achieve a common minimum l1-norm solution. The major difficulty to be dealt with is the non-smooth nature of the norm and the lack of strict convexity of the associated relevant performance index.

Momentum method has been used extensively in optimizers for deep learning. Recent studies show that distributed training through K-step averaging has many nice properties. We propose a momentum method for such model averaging approaches. At each individual learner level traditional stochastic gradient is applied. At the meta-level (global learner level), one momentum term is applied and we call it block momentum. We analyze the convergence and scaling properties of such momentum methods. Our experimental results show that block momentum not only accelerates training, but also achieves better results.

In this paper, we present a new modified inertial forward–backward algorithm for finding a common solution of the quasi-variational inclusion problem and the variational inequality problem in a q-uniformly smooth Banach space. The proposed algorithm is based on descent, splitting and inertial ideas. Under suitable assumptions, we prove that the sequence generated by the iterative algorithm converges strongly to the unique solution of the abovementioned problems. Numerical examples are also given to demonstrate our results.

In this paper, the distributed optimization problem over multi-cluster networks is considered. Different from the existing works, this paper studies the optimization algorithm under uncoordinated step sizes. More specifically, by combining a random sleep strategy and the round-robin communication among clusters, a new hierarchical algorithm is developed to solve the considered problem. In the proposed algorithm, the random sleep strategy enables each agent to independently choose either performing the projected subgradient descent, or keeping the previous estimate by a Bernoulli decision, based on which the step size of each agent is selected as an uncoordinated form that only relates to the independent Bernoulli decision variable. Technically, by introducing a key definition on the algorithm history, it is proven that the estimates of the proposed algorithm can converge to the optimal solution even with the uncoordinated step sizes. In addition, we also study the convergence performance of the proposed algorithm with simpler constant step sizes. In this case, it is proven that the random sleep strategy can efficiently improve the convergence accuracy of the algorithm. Finally, the theoretical findings are verified via simulation examples.

This paper presents an optimal control problem to analyze the efficacy of counter-terrorism tactics. We present an algorithm that efficiently combines the Minimum Principle of Pontryagin, the shooting method and the cyclic descent of coordinates. We also present a result that allows us to know a priori the steady state solutions. Using this technique we are able to choose parameters that reach a specific solution, of which there are two. Numerical examples are presented to illustrate the possibilities of the method. Finally, we study the sufficient conditions for optimality and suggest an improvement on the functional which also guarantees local optimality.

Sparse channel estimation for massive multiple-input multiple-output systems has drawn much attention in recent years. The required pilots are substantially reduced when the sparse channel state vectors can be reconstructed from a few numbers of measurements. A popular approach for sparse reconstruction is to solve the least-squares problem with a convex regularization. However, the convex regularizer is either too loose to force sparsity or lead to biased estimation. In this paper, the sparse channel reconstruction is solved by minimizing the least-squares objective with a nonconvex regularizer, which can exactly express the sparsity constraint and avoid introducing serious bias in the solution. A novel algorithm is proposed for solving the resulting nonconvex optimization via the difference of convex functions programming and the gradient projection descent. Simulation results show that the proposed algorithm is fast and accurate, and it outperforms the existing sparse recovery algorithms in terms of reconstruction errors., Comment: 2020 IEEE Global Communications Conference

Logistic regression is a classic classification method in machine learning. Classical logistic regression uses a general gradient descent method to solve the best parameters of the loss function, but it is easy to fall into the dilemma of local extremes. The fractional step descent method cannot converge to the exact extreme point, and there is always a deviation, so we use a variable fractional step descent method to simulate a new type of iteration to ensure the global convergence of the optimization algorithm. In this paper, the new variable fractional gradient descent method is used to solve the optimal parameters of the loss function, which overcomes the limitation of the gradient function on the step size of the loss function. In this paper, logistic regression and variable fractional step descent methods are used to deal with the problem of data dimensionality reduction to verify the effectiveness of the algorithm after optimization.

We present a novel probabilistic Zeroth-Order optimization method, which can handle higher dimensions, and can also be used for fast online optimization, for instance for multichannel source separation. We compared it to the Gradientless Descent (GLD) algorithm on a multichannel source separation task, and found that our method results in faster and better separation (for the 2-channels case). For the multichannel case, only our method resulted in useful separation. We also applied it to separating sources from 3-dimensional microphone arrays, with comparable results.

International audience; In this paper, we consider the integrated Berth Allocation and Crane Assignment problem, with availability constraints and high tides restrictions, in bulk port context. We were inspired by a real case study of a port owned by our industrial partner. The objective is to minimize the total penalty of tardiness. First, we implemented a greedy heuristic to compute an initial solution. Then, we proposed a sequential Variable Neighborhood Descent (seq-VND) for the problem. In addition, we compared the efficiency of different scenarios for the seq-VND against results given by a mathematical model for the problem.

The discrete logarithm problem (DLP) is a cornerstone in the public-key cryptography with various applications. Recently there is a new computational record for the DLP in a 795-bit prime field using the number field sieve for discrete logarithms (NFS-DL). The main technique used in the computation is choosing good parameters for each step of NFS-DL which reduces the time estimated by the asymptotic complexity significantly. In this article, we propose a new algorithm to find relations for high degree prime ideals and remove the previous restriction that only degree one prime ideals are allowed to appear in the descent step. This will increase the success probability of the descent step and reduce the actual running time. As the descent step could be done separately in some sense, improving the descent step is beneficial to find optimal parameters such as the smoothness bound which may result in better performance of the NFS-DL algorithm. We also give an experiment to demonstrate the effectiveness of our algorithm.

In this work, we applied the Supervised Descent Method (SDM) to 3D model-based inversion with limited microwave data. The target shapes are described by parameters based on prior information. The values of these parameters are reconstructed iteratively using SDM in which the descent directions are learned from data set constructed based on prior information. The model-based inversion has less non-uniqueness compared with typical pixel-based inversion. Furthermore, sufficient prior information allows SDM to predict the parameter values with a good accuracy, even with data of limited view. This algorithm is validated using synthetic data. The results show that we can correctly recover target shape parameters with only mono-static reflection data.

It is well-known that for general convex optimization problems, block-coordinate descent can get stuck in poor local optima. Despite that, versions of this method known as convergent message passing are very successful to approximately solve the dual LP relaxation of the MAP inference problem in graphical models. In attempt to identify the reason why these methods often achieve good local minima, we argue that if in block-coordinate descent the set of minimizers over a variable block has multiple elements, one should choose an element from the relative interior of this set. We show that this rule is not worse than any other rule for choosing block-minimizers. Based on this observation, we develop a theoretical framework for block-coordinate descent applied to general convex problems. We illustrate this theory on convergent message-passing methods.

The physical support of the Internet infrastructure is fiber-optics network (FON). Since the global Internet traffic doubles each year, FONs are suffering the capacity crunch problem, and several proposals offer content-oriented solutions, combined with a smart spectral utilization.It is well known that the physical implementation of FONs is robust under single failures on its links, or 2-connected. Unfortunately, simultaneous failures occur, and the service is disrupted for some hours per year in average.In this paper we propose a smart network augmentation which solves the previous problems simultaneously. The resulting network is a locally most-reliable 3-connected augmentation. Our methodology to build 3-connected networks is supported by the theory of uniformly most-reliable networks, elementary properties of cubic networks and a careful selection of local searches in a Variable Neighborhood Descent (VND) metaheuristic.

In this article, a deterministic annealing neural network algorithm is proposed to solve the minimum concave cost transportation problem. Specifically, the algorithm is derived from two neural network models and Lagrange–barrier functions. The Lagrange function is used to handle linear equality constraints, and the barrier function is used to force the solution to move to the global or near-global optimal solution. In both neural network models, two descent directions are constructed, and an iterative procedure for the optimization of the neural network is proposed. As a result, two corresponding Lyapunov functions are naturally obtained from these two descent directions. Furthermore, the proposed neural network models are proved to be completely stable and converge to the stable equilibrium state, therefore, the proposed algorithm converges. At last, the computer simulations on several test problems are made, and the results indicate that the proposed algorithm always generates global or near-global optimal solutions.

Block-coordinate descent (BCD) is a popular method in large-scale optimization. Unfortunately, its fixed points are not global optima even for convex problems. A succinct characterization of convex problems optimally solvable by BCD is unknown. Focusing on linear programs, we show that BCD fixed points are identical to fixed points of another method, which uses constraint propagation to detect infeasibility of a system of linear inequalities in a primal-dual loop (a special case of this method is the Virtual Arc Consistency algorithm by Cooper et al.). This implies that BCD fixed points are global optima iff a certain propagation rule decides feasibility of a certain class of systems of linear inequalities.

The renewed interest in Steepest Descent (SD) methods following the work of Barzilai and Borwein [IMA Journal of Numerical Analysis, 8 (1988)] has driven us to consider a globalization strategy based on SD, which is applicable to any line-search method. In particular, we combine Newton-type directions with scaled SD steps to have suitable descent directions. Scaling the SD directions with a suitable step length makes a significant difference with respect to similar globalization approaches, in terms of both theoretical features and computational behavior. We apply our strategy to Newton's method and the BFGS method, with computational results that appear interesting compared with the results of well-established globalization strategies devised ad hoc for those methods., Comment: 22 pages, 11 Figures

Some methods for finding the maximum feasible subsystems of systems of linear inequalities are considered. The problem of finding the most accurate algorithm in a parametric family of linear classification algorithms is one of the most important problems in machine learning. In order to solve this discrete optimization problem, an exact (combinatorial) algorithm, its approximations (relaxation and greedy combinatorial descent algorithms), and the approximation algorithm are given. The latter consists in replacing the original discrete optimization problem with a nonlinear programming problem by changing from linear inequalities to their sigmoid functions. The initial results of their comparison are presented.

Although different satisfiability decision procedures can be combined by algorithms such as those of Nelson–Oppen or Shostak, current tools typically can only support a finite number of theories to use in such combinations. To make SMT solving more widely applicable one needs theory-generic satisfiability algorithms allowing a potentially infinite number of decidable theories to be user-definable, instead of needing to be built in by tool implementers. This work studies how folding variant narrowing, a generic unification algorithm that offers good extensibility in unification theory, can be extended to a generic variant-based satisfiability algorithm for the initial algebras of user-specified input theories when such theories satisfy Comon and Delaune's finite variant property (FVP) and some extra conditions. Several, increasingly larger infinite classes of theories whose initial algebras enjoy decidable variant-based satisfiability are identified and illustrated with examples. A method based on descent maps to bring other theories into these classes and to improve the generic algorithm's efficiency is also proposed.

Optic disc (OD) segmentation is an important step in analyzing the color fundus image. Most existing approaches are based on the shape prior and visual appearance of the OD boundary. However, the current ways of integrating the shape and appearance are simple. We argue that the performance of OD segmentation can be improved by better shape-appearance modeling. In this paper, we propose to learn a sequence of supervised descent directions between the coordinates of OD boundary and their surrounding visual appearances for OD segmentation. In addition, we introduce the histograms of gradient orientations to represent the OD appearance. Experimental results on six datasets clearly show that the proposed method improves the OD segmentation and outperforms the state-of-the-art.

In this paper, we propose a distributed algorithm, called Directed-Distributed Subgradient Descent (D-DSD), to solve multi-agent optimization problems over directed graphs. Existing algorithms mostly deal with similar problems under the assumption of undirected networks, i.e., requiring the weight matrices to be doubly-stochastic. The row-stochasticity of the weight matrix guarantees that all agents reach consensus, while the column-stochasticity ensures that each agent’s local (sub)gradient contributes equally to the global objective. In a directed graph, however, it may not be possible to construct a doubly-stochastic weight matrix in a distributed manner. We overcome this difficulty by augmenting an additional variable for each agent to record the change in the state evolution. In each iteration, the algorithm simultaneously constructs a row-stochastic matrix and a column-stochastic matrix instead of only a doubly-stochastic matrix. The convergence of the new weight matrix, depending on the row-stochastic and column-stochastic matrices, ensures agents to reach both consensus and optimality. The analysis shows that the proposed algorithm converges at a rate of O ( ln k k ) , where k is the number of iterations.

A multi-period, multi-echelon, multi-product, and multi-modal sustainable supply chain network design problem is considered. The problem is formulated as a multi-objective Mixed-Integer Linear Programming (MILP) model that explicitly considers the environmental footprint and social responsibilities. We introduce the Multi-Neighborhood Descent Traversal Algorithm (MNDTA), which can solve this problem efficiently. The MNDTA begins with a structured initial solution of the model and improves the incumbent solution by sequentially traversing several specifically designed neighborhoods over generations. A lower-bound-based evaluation method is introduced to reduce the computational complexity involved in solving the integer programming problem. Experimental results demonstrate that the proposed MNDTA can provide high-quality solutions that are close to the optimal solutions with a negligibly small (relative) gap and can solve large instances much more quickly than CPLEX can. In addition, the MNDTA outperforms existing solution algorithms. A numerical comparison of the results of the proposed model with those of a model that only considers financial aspects demonstrates that explicitly using our model when designing a supply chain network can substantially reduce the environmental impact and increase social responsibility at a negligible cost increase.

We propose an unsupervised method for saliency detection with multiple functions by a universal descent model. The basic descent model is concise, which is a minimization equation conducted by a relationship matrix and background prior. The relationship matrix is calculated by the contrast of features which contains much information between superpixels. So saliency maps with high performance can be obtained even if only one feature is included. Besides, various terms can be appended to the basic descent model to achieve multiple functions. For example, considering an neighbor matrix into the basic model can further smooth saliency maps. The refinement term can also refine existing results by introducing prior saliency maps, demonstrating the universal applications of our model. Extensive experiments on different datasets indicate that the basic model outperforms state-of-the-art methods. The universal descent models with smoothness and refinement terms are able to promote the performance of state-of-the-art methods by a large margin.

This paper describes an optimization technique of neural networks radial basis function multi-model identification of nonlinear system. Indeed, this paper treats the multi-model approach based on parametric identification. The used architecture of the neural multi-model is radial basis function. We have used the descent gradient and the genetic algorithm technique and we have compared the found results. The effectiveness of the proposed approach is shown through a numerical simulation of a nonlinear system and we have confirmed that the genetic algorithm give a very good results.

We propose a policy search method for synthesizing optimal feedback control laws for reference tracking directly from data. During the learning phase, the control law is optimized by using stochastic gradient descent iterations and (optionally) applied to the plant while collecting data. Differently from model-based methods, in which a full model of the open-loop plant is first identified from data, here a simple linear model is recursively identified with forgetting factor for the only reason of computing approximately the gradients required for the descent. We report examples showing that the method recovers the optimal feedback law in case the underlying plant is linear, and outperforms the best control law that is achieved by first identifying an open-loop linear model in case the underlying plant is nonlinear.

In this paper, we consider the large-scale case of the robust beamforming problem with interference temperature constraints. Previous semidefinite relaxation (SDR) method becomes impracticable because of its expensive computational cost. Even successive convex approximation (SCA) method, the state-of-the-art method, cannot tackle this problem efficiently. Thus, we are motivated to design two efficient first-order methods, multi-block alternating direction method of multipliers (ADMM) and linear programming-assisted subgradient descent (LPA-SD), to solve it. Numerical results demonstrate the potential of our proposed methods in terms of both computational efficiency and solution quality.

In this paper, a stochastic trust region method is proposed to solve unconstrained minimization problems with stochastic objectives. Particularly, this method can be used to deal with nonconvex problems. At each iteration, we construct a quadratic model of the objective function. In the model, stochastic gradient is used to take the place of deterministic gradient for both the determination of descent directions and the approximation of the Hessians of the objective function. The behavior and the convergence properties of the proposed method are discussed under some reasonable conditions. Some preliminary numerical results show that our method is potentially efficient.

Supervised Descent Method (SDM) is an efficient and accurate approach for facial landmark locating and face alignment. In the training phase, it requires a large amount of training samples to learn the descent directions and get the corresponding regressors. Then in the test phase, it uses the corresponding regressors to estimate the descent directions and locate the facial landmarks. However, when the facial expression or direction changes too much, generally SDM cannot obtain good performance due to the large variation between the initial shape (the initial shape of SDM is the mean shape of the training samples) and the target shape. Therefore, we propose a coarse-to-fine SDM (CFSDM) method to improve the accuracy of the test results. This method predicts the approximate coordinates of the facial landmarks with a simple CNN (Convolutional Neural Network) network (here we introduce the channel-wise attention mechanism, which can predict the coordinates of the landmarks more accurately with a relatively simple structure) in advance, and then SDM will take the coordinates as its initial shape’s coordinates, which reduces the distance between the initial shape and the target shape, thereby solving the problem that SDM cannot achieve good results when the facial expression or direction changes greatly.

In this paper, by incorporating a multi-step scheme into the doubly stabilized bundle method (DSBM) recently developed by Oliveira and Solodov (2016), we propose a multi-step doubly stabilized bundle method (MDSBM) for solving nonsmooth convex optimization problems. In contrast to a single sequence generated by DSBM, the MDSBM generates three related iteration sequences. One is used to build the cutting-planes model of the objective function, another is served as the stability centers, and the third is the sequence of solutions to our new doubly stabilized subproblems. In addition, we present a new descent test criterion, aiming to take advantage of the multi-step scheme. We establish global convergence of the proposed method, and finally present some promising numerical results.

K-nearest neighbor graphs (K-NNGs) are used in many data-mining and machine-learning algorithms. Naive construction of K-NNGs has a complexity of O(n2), which could be a problem for large-scale data sets. In order to achieve higher efficiency, many exact and approximate algorithms have been developed, including the NN-Descent algorithm of Dong, Charikar and Li. Empirical evidence suggests that the practical complexity of this algorithm is in O(n1.14), which is a significant improvement over brute force construction. However, NN-Descent has a major drawback --- it produces good results only on data of low intrinsic dimensionality. This paper presents an experimental analysis of this behavior, and investigates possible solutions. We link the quality of performance of NN-Descent with the phenomenon of hubness, defined as the tendency of intrinsically high-dimensional data to contain hubs --- points with high in-degrees in the K-NNG. We propose two approaches to alleviate the observed negative influence of hubs on NN-Descent performance.

This paper introduces descent moment distributions for analysis of single and multi permutation codes defined via Levenshtein (VT) codes. Originally this work is motivated by computer experiments of deletion spheres for contant weight codes and the authors proved properties in a theoretical manner.

We want to solve fuzzy linear programming problems with fuzzy coefficients in the objective function using a new variable neighborhood search algorithm. In our proposed algorithm, the local search is defined based on descent directions. We make use of our recently proposed modified Kerre's method for finding descent directions. The fuzzy optimization problem is solved directly, without changing it to a crisp program. We show the effectiveness of our proposed method in comparison with some available methods by using a non-parametric statistical sign test. The objective function values obtained by our proposed method turn to be more accurate the ones obtained by other methods.

A recently proposed clustering method, called the Nearest Descent (ND), can organize the whole dataset into a sparsely connected graph, called the In-tree. This ND-based In-tree structure proves able to reveal the clustering structure underlying the dataset, except one imperfect place, that is, there are some undesired edges in this In-tree which require to be removed. Here, we propose an effective way to automatically remove the undesired edges in In-tree via an effective combination of the In-tree structure with affinity propagation (AP). The key for the combination is to add edges between the reachable nodes in In-tree before using AP to remove the undesired edges. The experiments on both synthetic and real datasets demonstrate the effectiveness of the proposed method.

The Frank-Wolfe (FW) algorithm has been widely used in solving nuclear norm constrained problems, since it does not require projections. However, FW often yields high rank intermediate iterates, which can be very expensive in time and space costs for large problems. To address this issue, we propose a rank-drop method for nuclear norm constrained problems. The goal is to generate descent steps that lead to rank decreases, maintaining low-rank solutions throughout the algorithm. Moreover, the optimization problems are constrained to ensure that the rank-drop step is also feasible and can be readily incorporated into a projection-free minimization method, e.g., Frank-Wolfe. We demonstrate that by incorporating rank-drop steps into the Frank-Wolfe algorithm, the rank of the solution is greatly reduced compared to the original Frank-Wolfe or its common variants.

International audience; Sparsity-inducing penalties are useful tools in variational methods for machine learning. In this paper, we propose two block-coordinate descent strategies for learning a sparse multiclass support vector machine. The first one works by selecting a subset of features to be updated at each iteration, while the second one performs the selection among the training samples. These algorithms can be efficiently implemented thanks to the flexibility offered by recent randomized primal-dual proximal methods. Experiments carried out for the supervised classification of handwritten digits demonstrate the interest of considering the primal-dual approach in the context of block-coordinate descent, and the efficiency of the proposed algorithms is assessed through a comparison of execution times and classification errors. Index Terms— Sparsity, multiclass SVM, proximal algorithm, random update, block-coordinate descent.

We present a unifying framework for adapting the update direction in gradient-based iterative optimization methods. As natural special cases we re-derive classical momentum and Nesterov's accelerated gradient method, lending a new intuitive interpretation to the latter algorithm. We show that a new algorithm, which we term Regularised Gradient Descent, can converge more quickly than either Nesterov's algorithm or the classical momentum algorithm.

International audience; The NP-hard capacitated clustering problem (CCP) is a general model with a number of relevant applications. This paper proposes a highly effective iterated variable neighborhood search (IVNS) algorithm for solving the problem. IVNS combines an extended variable neighborhood descent method and a randomized shake procedure to explore effectively the search space. The computational results obtained on three sets of 133 benchmarks reveal that the proposed algorithm competes favorably with the state-of-the-art algorithms in the literature both in terms of solution quality and computational efficiency. In particular, IVNS discovers an improved best known result (new lower bounds) for 28 out of 83 most popular instances, while matching the current best known results for the remaining 55 instances. Several essential components of the proposed algorithm are investigated to understand their impacts on the performance of algorithm.

In this paper a Variable Neighborhood Descent (VND) approach, is developed to solve the Single Machine Total Weighted Tardiness Problem (SMTWTP). New strategy was proposed to select iteratively the accurate neighborhood. Our approach was compared to VND state-of-the-art approaches. Statistical tests were also applied on the empirical results, to show that the DR_VND outperforms the proposed approaches for 72 % of instances for the SMTWTP. The proposed approach was applied on a real case.

This work presents a new algorithm for dictionary learning. Existing algorithms such as MOD and K-SVD often fail to find the best dictionary because they get trapped in a local minimum. Olshausen and Field's Sparsenet algorithm relies on a fixed step projected gradient descent. With the right step, it can avoid local minima and converge towards the global minimum. The problem then becomes to find the right step size. In this work we provide the expression of the optimal step for the gradient descent but the step we use is twice as large as the optimal step. That large step allows the descent to bypass local minima and yields significantly better results than existing algorithms. The algorithms are compared on synthetic data. Our method outperforms existing algorithms both in approximation quality and in perfect recovery rate if an oracle support for the sparse representation is provided.

International audience; We study a “hard” optimization problem for metaheuristic search, where a natural neighborhood (that consists of moves for flipping the values of zero-one variables) confronts two local optima, separated by a maximum possible number of moves in the feasible space. Once a descent method reaches the first local optimum, all sequences of feasible moves to reach the second, which is the global optimum, must ultimately pass through solutions that are progressively worse until reaching the worst solution of all, which is adjacent to the global optimum. We show how certain alternative neighborhoods can locate the global more readily, but disclose that each of these approaches encounters serious difficulties by slightly changing the problem formulation. We also identify other possible approaches that seem at first to be promising but turn out to have deficiencies. Finally, we observe that a strategic oscillation approach for transitioning between feasible and infeasible space overcomes these difficulties, reinforcing recent published observations about the utility of solution trajectories that alternate between feasibility and infeasibility. We also sketch features of such an approach that have implications for future research.