GRASP and path relinking for the matrix bandwidth minimization

In this article we develop a greedy randomized adaptive search procedure (GRASP) for the problem of reducing the bandwidth of a matrix. This problem consists of finding a permutation of the rows and columns of a given matrix, which keeps the non-zero elements in a band that is as close as possible to the main diagonal. The proposed method may be coupled with a path relinking strategy to search for improved outcomes. Empirical results indicate that the proposed GRASP implementation compares favourably to classical heuristics. GRASP with path relinking is also found to be competitive with a recently published Tabu search algorithm that is considered one of the best currently available for bandwidth minimization.     

A branch and bound algorithm for the matrix bandwidth minimization

In this article, we first review previous exact approaches as well as theoretical contributions for the problem of reducing the bandwidth of a matrix. This problem consists of finding a permutation of the rows and columns of a given matrix which keeps the non-zero elements in a band that is as close as possible to the main diagonal. This NP-complete problem can also be formulated as a labeling of vertices on a graph, where edges are the non-zero elements of the corresponding symmetrical matrix. We propose a new branch and bound algorithm and new expressions for known lower bounds for this problem. Empirical results with a collection of previously reported instances indicate that the proposed algorithm compares favourably to previous methods.     

Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problem

The dynamic programming algorithm of [12.] for the bandwidth minimization problem is improved. It is shown that, for all k > 1, BANDWIDTH(k) can be solved in O(n^k) steps and simultaneous O(n^k) space, where n is the number of vertices in the graph, and that each such problem is in NSPACE(log n). The same improved dynamic programming algorithm approach works to show that the MINCUT LINEAR ARRANGEMENT problem restricted to the fixed value k, denoted by MINCUT(k), is solvable in O(n^k) steps and simultaneous O(n^k) space and is in the class NSPACE(log n).     

An improved simulated annealing algorithm for bandwidth minimization

In this paper, a simulated annealing algorithm is presented for the bandwidth minimization problem for graphs. This algorithm is based on three distinguished features including an original internal representation of solutions, a highly discriminating evaluation function and an effective neighborhood. The algorithm is evaluated on a set of 113 well-known benchmark instances of the literature and compared with several state-of-the-art algorithms, showing improvements of some previous best results.     

Heuristics for matrix bandwidth reduction

In this work, we provide two heuristic algorithms for the matrix bandwidth reduction problem. The first is a genetic algorithm and the second uses node label adjustments. Experiments show these heuristics improve solution quality when compared with the well-known GPS algorithm and recently-developed methods using tabu search and GRASP with Path Relinking. Further, the node adjustment approach obtains solutions at speeds comparable to the fast GPS algorithm.     

Adaptive memory programming: local search parallel algorithms for phylogenetic tree construction

One of the most important aspect of molecular and computational biology is the reconstruction of evolutionary relationships. The area is well explored after decades of intensive research. Despite this fact there remains a need for good and efficient algorithms that are capable of reconstructing the evolutionary relationship in reasonable time.     

Global minimization algorithms for concave quadratic programming problems

Abstract: In this article, we consider the concave quadratic programming problem which is known to be NP hard. Based on the improved global optimality conditions by [Dür, M., Horst, R. and Locatelli, M., 1998, Necessary and sufficient global optimality conditions for convex maximization revisited, Journal of Mathematical Analysis and Applications, 217, 637–649] and [Hiriart-Urruty, J.B. and Ledyav, J.S., 1996, A note in the characterization of the global maxima of a convex function over a convex set, Journal of Convex Analysis, 3, 55–61], we develop a new approach for solving concave quadratic programming problems. The main idea of the algorithms is to generate a sequence of local minimizers either ending at a global optimal solution or at an approximate global optimal solution within a finite number of iterations. At each iteration of the algorithms we solve a number of linear programming problems with the same constraints of the original problem. We also present the convergence properties of the proposed algorithms under some conditions. The efficiency of the algorithms has been demonstrated with some numerical examples.     

A semidefinite programming method for integer convex quadratic minimization

We consider the NP-hard problem of minimizing a convex quadratic function over the integer lattice \({\mathbf{Z}}^n\). We present a simple semidefinite programming (SDP) relaxation for obtaining a nontrivial lower bound on the optimal value of the problem. By interpreting the solution to the SDP relaxation probabilistically, we obtain a randomized algorithm for finding good suboptimal solutions, and thus an upper bound on the optimal value. The effectiveness of the method is shown for numerical problem instances of various sizes.     

Adaptive smoothing algorithms for nonsmooth composite convex minimization

We propose an adaptive smoothing algorithm based on Nesterov’s smoothing technique in Nesterov (Math Prog 103(1):127–152, 2005) for solving “fully” nonsmooth composite convex optimization problems. Our method combines both Nesterov’s accelerated proximal gradient scheme and a new homotopy strategy for smoothness parameter. By an appropriate choice of smoothing functions, we develop a new algorithm that has the \(\mathcal {O}\left( \frac{1}{\varepsilon }\right) \)-worst-case iteration-complexity while preserves the same complexity-per-iteration as in Nesterov’s method and allows one to automatically update the smoothness parameter at each iteration. Then, we customize our algorithm to solve four special cases that cover various applications. We also specify our algorithm to solve constrained convex optimization problems and show its convergence guarantee on a primal sequence of iterates. We demonstrate our algorithm through three numerical examples and compare it with other related algorithms.     

A least-distance programming procedure for minimization problems under linear constraints

In this paper, an algorithm is developed for solving a nonlinear programming problem with linear contraints. The algorithm performs two major computations. First, the search vector is determined by projecting the negative gradient of the objective function on a polyhedral set defined in terms of the gradients of the equality constraints and the near binding inequality constraints. This least-distance program is solved by Lemke's complementary pivoting algorithm after eliminating the equality constraints using Cholesky's factorization. The second major calculation determines a stepsize by first computing an estimate based on quadratic approximation of the function and then finalizing the stepsize using Armijo's inexact line search. It is shown that any accumulation point of the algorithm is a Kuhn-Tucker point. Furthermore, it is shown that, if an accumulation point satisfies the second-order sufficiency optimality conditions, then the whole sequence of iterates converges to that point. Computational testing of the algorithm is presented.     

Iterative reweighted minimization methods for l_p regularized unconstrained nonlinear programming

In this paper we study general \(l_p\) regularized unconstrained minimization problems. In particular, we derive lower bounds for nonzero entries of the first- and second-order stationary points and hence also of local minimizers of the \(l_p\) minimization problems. We extend some existing iterative reweighted \(l_1\) ( \(\mathrm{IRL}_1\) ) and \(l_2\) ( \(\mathrm{IRL}_2\) ) minimization methods to solve these problems and propose new variants for them in which each subproblem has a closed-form solution. Also, we provide a unified convergence analysis for these methods. In addition, we propose a novel Lipschitz continuous \({\epsilon }\) -approximation to \(\Vert x\Vert ^p_p\) . Using this result, we develop new \(\mathrm{IRL}_1\) methods for the \(l_p\) minimization problems and show that any accumulation point of the sequence generated by these methods is a first-order stationary point, provided that the approximation parameter \({\epsilon }\) is below a computable threshold value. This is a remarkable result since all existing iterative reweighted minimization methods require that \({\epsilon }\) be dynamically updated and approach zero. Our computational results demonstrate that the new \(\mathrm{IRL}_1\) method and the new variants generally outperform the existing \(\mathrm{IRL}_1\) methods (Chen and Zhou in 2012; Foucart and Lai in Appl Comput Harmon Anal 26:395–407, 2009).     

Limited memory quasi-newton method for large-scale linearly equality-constrained minimization

1. IntroductionConsider the following linearly constrained nonlinear programming problemwhere x e R", A E Rmxn and f E C2. We are interested in the case when n and m arelarge and when the Hessian matrix of f is difficult to compute or is dense. It is ajssumed thatA is a matrix of full row rank and that the level set S(xo) = {x: f(x) 5 f(xo), Ax ~ b} isnonempty and compact.In the past few years j there were two kinds of methods for solving the large-scaleproblem (1.1). FOr the one kind, pr…     

A joint matrix minimization approach for multi-image face recognition

The Schatten p-quasi-norm regularized minimization problem has attracted extensive attention in machine learning, image recognition, signal reconstruction, etc. Meanwhile, the l_(2,1)-regularized matrix optimization models are also popularly used for its joint sparsity. Naturally, the pseudo matrix norm l_(2,p) is expected to carry over the advantages of both l_p and l_(2,1). This paper proposes a mixed l_(2,q)-l_(2,p) matrix minimization approach for multi-image face recognition. To uniformly solve this optimization problem for any q ∈ [1,2] and p ∈(0,2], an iterative quadratic method(IQM) is developed. IQM is proved to iescend strictly until it gets a stationary point of the mixed l_(2,q)-l_(2,p)matrix minimization. Moreover, a more practical IQM is presented for large-scale case. Experimental results on three public facial image databases show that the joint matrix minimization approach with practical IQM not only saves much computational cost but also achievez better performance in face recognition than state-of-the-art methods.     

Convergence of projected Landweber iteration for matrix rank minimization

In this paper, we study the performance of the projected Landweber iteration (PLW) for the general low rank matrix recovery. The PLW was first proposed by Zhang and Chen (2010) [43] based on the sparse recovery algorithm APG (Daubechies et al., 2008) [14] in the matrix completion setting, and numerical experiments have been given to show its efficiency (Zhang and Chen, 2010) [43]. In this paper, we focus on providing a convergence rate analysis of the PLW in the general setting of low rank matrix recovery with the affine transform having the matrix restricted isometry property. We show robustness of the algorithm to noise with a strong geometric convergence rate even for noisy measurements provided that the affine transform satisfies a matrix restricted isometry property condition.     

Numerical experiments on dual matrix algorithms for function minimization

In Ref. 2, four algorithms of dual matrices for function minimization were introduced. These algorithms are characterized by the simultaneous use of two matrices and by the property that the one-dimensional search for the optimal stepsize is not needed for convergence. For a quadratic function, these algorithms lead to the solution in at mostn+1 iterations, wheren is the number of variables in the function. Since the one-dimensional search is not needed, the total number of gradient evaluations for convergence is at mostn+2. In this paper, the above-mentioned algorithms are tested numerically by using five nonquadratic functions. In order to investigate the effects of the stepsize on the performances of these algorithms, four schemes for the stepsize factor are employed, two corresponding to small-step processes and two corresponding to large-step processes. The numerical results show that, in spite of the wide range employed in the choice of the stepsize factor, all algorithms exhibit satisfactory convergence properties and compare favorably with the corresponding quadratically convergent algorithms using one-dimensional searches for optimal stepsizes.     

Global minimization of a generalized linear multiplicative programming

This article presents a simplicial branch and bound algorithm for globally solving generalized linear multiplicative programming problem (GLMP). Since this problem does not seem to have been studied previously, the algorithm is apparently the first algorithm to be proposed for solving such problem. In this algorithm, a well known simplicial subdivision is used in the branching procedure and the bound estimation is performed by solving certain linear programs. Convergence of this algorithm is established, and some experiments are reported to show the feasibility of the proposed algorithm.     

Adaptive constraint reduction for convex quadratic programming

We propose an adaptive, constraint-reduced, primal-dual interior-point algorithm for convex quadratic programming with many more inequality constraints than variables. We reduce the computational effort by assembling, instead of the exact normal-equation matrix, an approximate matrix from a well chosen index set which includes indices of constraints that seem to be most critical. Starting with a large portion of the constraints, our proposed scheme excludes more unnecessary constraints at later iterations. We provide proofs for the global convergence and the quadratic local convergence rate of an affine-scaling variant. Numerical experiments on random problems, on a data-fitting problem, and on a problem in array pattern synthesis show the effectiveness of the constraint reduction in decreasing the time per iteration without significantly affecting the number of iterations. We note that a similar constraint-reduction approach can be applied to algorithms of Mehrotra’s predictor-corrector type, although no convergence theory is supplied.     

A regularized limited memory BFGS method for nonconvex unconstrained minimization

The limited memory BFGS method (L-BFGS) is an adaptation of the BFGS method for large-scale unconstrained optimization. However, The L-BFGS method need not converge for nonconvex objective functions and it is inefficient on highly ill-conditioned problems. In this paper, we proposed a regularization strategy on the L-BFGS method, where the used regularization parameter may play a compensation role in some sense when the condition number of Hessian approximation tends to become ill-conditioned. Then we proposed a regularized L-BFGS method and established its global convergence even when the objective function is nonconvex. Numerical results show that the proposed method is efficient.