The Polyhedral Active Set Algorithm (PASA) is designed to optimize a general nonlinear function over a polyhedron. Phase one of the algorithm is a nonmonotone gradient projection algorithm, while phase two is an active set algorithm that explores faces of the constraint polyhedron. A gradient-based implementation is presented, where a projected version of the conjugate gradient algorithm is employed in phase two. Asymptotically, only phase two is performed. Comparisons are given with IPOPT using polyhedral-constrained problems from CUTEst and the Maros/Meszaros quadratic programming test set.

Partitioning graphs is a common and useful operation in many areas, from parallel computing to VLSI design to sparse matrix algorithms. In this article, we introduce Mongoose, a multilevel hybrid graph partitioning algorithm and library. Building on previous work in multilevel partitioning frameworks and combinatoric approaches, we introduce novel stall-reducing and stall-free coarsening strategies, as well as an efficient hybrid algorithm leveraging (1) traditional combinatoric methods and (2) continuous quadratic programming formulations. We demonstrate how this new hybrid algorithm outperforms either strategy in isolation, and we also compare Mongoose to METIS and demonstrate its effectiveness on large and social networking (power law) graphs.

This article considers the problem of minimizing a convex, separable quadratic function subject to a knapsack constraint and a box constraint. An algorithm called NAPHEAP has been developed to solve this problem. The algorithm solves the Karush-Kuhn-Tucker system using a starting guess to the optimal Lagrange multiplier and updating the guess monotonically in the direction of the solution. The starting guess is computed using the variable fixing method or is supplied by the user. A key innovation in our algorithm is the implementation of a heap data structure for storing the break points of the dual function and computing the solution of the dual problem. Also, a new version of the variable fixing algorithm is developed that is convergent even when the objective Hessian is not strictly positive definite. The hybrid algorithm NAPHEAP that uses a Newton-type method (variable fixing method, secant method, or Newton's method) to bracket a root, followed by a heap-based monotone break point search, can be faster than a Newton-type method by itself, as demonstrated in the numerical experiments.

A new algorithm is presented for efficiently solving image reconstruction problems that arise in partially parallel magnetic resonance imaging. This algorithm minimizes an objective function of the form φ(Bu) + 1/2||FpSu - f||2, where φ is the regularization term which may be nonsmooth. In image reconstruction, the φ term corresponds to total variation smoothing and/or L1 regularization term. The least square term 1/2||FpSu - f||2is the fidelity term. In our application, f represents undersampled data from a partially parallel imaging (PPI) system. The proposed algorithm is a generalization of the Bregman operator splitting algorithm with variable stepsize (BOSVS) in which the previous Barzilai-Borwein (BB) step is replaced by a cyclic BB (CBB) step, and an L1 term Ψ is added to the energy function. Experimental results on clinical partially parallel imaging data are given.

This paper presents two fast algorithms for total variation–based image reconstruction in a magnetic resonance imaging technique known as partially parallel imaging (PPI), where the inversion matrix is large and ill-conditioned. These algorithms utilize variable splitting techniques to decouple the original problem into more easily solved subproblems. The first method reduces the image reconstruction problem to an unconstrained minimization problem, which is solved by an alternating proximal minimization algorithm. One phase of the algorithm solves a total variation (TV) denoising problem, and the second phase solves an ill-conditioned linear system. Linear and sublinear convergence results are given, and an implementation based on a primal-dual hybrid gradient (PDHG) scheme for the TV problem and on a Barzilai–Borwein scheme for the linear inversion is proposed. The second algorithm exploits the special structure of the PPI reconstruction problem by decomposing it into one subproblem involving Fourier transforms and another subproblem that can be treated by the PDHG scheme. Numerical results and comparisons with recently developed methods indicate the efficiency of the proposed algorithms.

The convergence rate is analyzed for the sparse reconstruction by separable approximation (SpaRSA) algorithm for minimizing a sum $f(\mathbf{x})+\psi(\mathbf{x})$, where f is smooth and $\psi$ is convex, but possibly nonsmooth. It is shown that if f is convex, then the error in the objective function at iteration k is bounded by $a/k$ for some a independent of k. Moreover, if the objective function is strongly convex, then the convergence is R-linear. An improved version of the algorithm based on a cyclic version of the BB iteration and an adaptive line search is given. The performance of the algorithm is investigated using applications in the areas of signal processing and image reconstruction.

The supernodal method for sparse Cholesky factorization represents the factor L as a set of supernodes, each consisting of a contiguous set of columns of L with identical nonzero pattern. A conventional supernode is stored as a dense submatrix. While this is suitable for sparse Cholesky factorization where the nonzero pattern of L does not change, it is not suitable for methods that modify a sparse Cholesky factorization after a low-rank change to A (an update/downdate, Ā = A ± WW T ). Supernodes merge and split apart during an update/downdate. Dynamic supernodes are introduced which allow a sparse Cholesky update/downdate to obtain performance competitive with conventional supernodal methods. A dynamic supernodal solver is shown to exceed the performance of the conventional (BLAS-based) supernodal method for solving triangular systems. These methods are incorporated into CHOLMOD, a sparse Cholesky factorization and update/downdate package which forms the basis of x = A\b MATLAB when A is sparse and symmetric positive definite.

CHOLMOD is a set of routines for factorizing sparse symmetric positive definite matrices of the form A or AA T , updating/downdating a sparse Cholesky factorization, solving linear systems, updating/downdating the solution to the triangular system Lx = b , and many other sparse matrix functions for both symmetric and unsymmetric matrices. Its supernodal Cholesky factorization relies on LAPACK and the Level-3 BLAS, and obtains a substantial fraction of the peak performance of the BLAS. Both real and complex matrices are supported. CHOLMOD is written in ANSI/ISO C, with both C and MATLAB TM interfaces. It appears in MATLAB 7.2 as x = A\b when A is sparse symmetric positive definite, as well as in several other sparse matrix functions.

Recently, a new nonlinear conjugate gradient scheme was developed which satisfies the descent condition g T k d k ≤ −7/8 ‖ g k ‖ 2 and which is globally convergent whenever the line search fulfills the Wolfe conditions. This article studies the convergence behavior of the algorithm; extensive numerical tests and comparisons with other methods for large-scale unconstrained optimization are given.

AdaBoost rarely suffers from overfitting problems in low noise data cases. However, recent studies with highly noisy patterns clearly showed that overfitting can occur. A natural strategy to alleviate the problem is to penalize the distribution skewness in the learning process to prevent several hardest examples from spoiling decision boundaries. In this paper, we describe in detail how a penalty scheme can be pursued in the mathematical programming setting as well as in the Boosting setting. By using two smooth convex penalty functions, two new soft margin concepts are defined and two new regularized AdaBoost algorithms are proposed. The effectiveness of the proposed algorithms is demonstrated through a large scale experiment. Compared with other regularized AdaBoost algorithms, our methods can achieve at least the same or much better performances.

We present a multi-input multi-output (MIMO) transceiver design that combines the geometric mean decomposition (GMD) with either the conventional zero-forcing VBLAST decoder (ZF-VBLAST), or the zero-forcing dirty paper precoder (ZF-DP). Our approach decomposes a MIMO channel into multiple identical subchannels, which obviates the need of bit allocation and simplifies the design of modulation/demodulation and coding/decoding schemes. Moreover, we prove that our scheme is asymptotically optimal for high signal-to-noise ratio (SNR) in terms of both the channel throughput and the bit-error-rate (BER) performance.

A continuous quadratic programming formulation is given for min-cut graph partitioning problems. In these problems, we partition the vertices of a graph into a collection of disjoint sets satisfying specified size constraints, while minimizing the sum of weights of edges connecting vertices in different sets. An optimal solution is related to an eigenvector (Fiedler vector) corresponding to the second smallest eigenvalue of the graph's Laplacian. Necessary and sufficient conditions characterizing local minima of the quadratic program are given. The effect of diagonal perturbations on the number of local minimizers is investigated using a test problem from the literature.