Search

In this paper we consider finding a second-order stationary point (SOSP) of nonconvex equality constrained optimization when a nearly feasible point is known. In particular, we first propose a new Newton-conjugate gradient (Newton-CG) method for finding an approximate SOSP of unconstrained optimization and show that it enjoys a substantially better complexity than the Newton-CG method in [C. W. Royer, M. O'Neill, and S. J. Wright, Math. Program., 180 (2020), pp. 451-488]. We then propose a Newton-CG based augmented Lagrangian (AL) method for finding an approximate SOSP of nonconvex equality constrained optimization, in which the proposed Newton-CG method is used as a subproblem solver. We show that under a generalized linear independence constraint qualification (GLICQ), our AL method enjoys a total inner iteration complexity of O(ε7/peration complexity of O(ε7/2 min\{ n, ε3/4\}) for finding an (ε, ε)-SOSP of nonconvex equality constrained optimization with high probability, which are significantly better than the ones achieved by the proximal AL method in [Y. Xie and S. J. Wright, J. Sci. Comput., 86 (2021), pp. 1-30]. In addition, we show that it has a total inner iteration complexity of O(ε11/2) and an operation complexity of O(ε11/2 min\{ n, ε5/4\}) when the GLICQ does not hold. To the best of our knowledge, all the complexity results obtained in this paper are new for finding an approximate SOSP of nonconvex equality constrained optimization with high probability. Preliminary numerical results also demonstrate the superiority of our proposed methods over the other competing algorithms. [ABSTRACT FROM AUTHOR]

This paper develops an optimization-based theory for the existence and uniqueness of equilibria of a noncooperative game wherein the selfish players' optimization problems are nonconvex and there are side constraints and an associated price clearance to be satisfied by the equilibria. A new concept of equilibrium for such a noncouvex game, which we term a "quasi-Nash equilibrium" (QNE), is introduced as a solution of the variation inequality (VI) obtained by aggregating the first order optimality conditions of the players' problems while retaining the convex constraints (if any) ill the defining set of the VI. Under a second-order sufficiency condition from nonlinear programming, a QNE becomes a local Nash equilibrium of the game. Uniqueness of a QNE is established using a degree-theoretic proof. Under a key bounded ness property of the Karush-Kuhn-Tucker multipliers of the nonconvex constraints and the positive definiteness of the Hessians of the players' Lagrangian functions, we establish the single-valuedness of the players' best-response maps, from which the existence of a Nash equilibrium (NE) of the nonconvex game follows. We also present a distributed algorithm for computing an NE of such a game and provide a matrix-theoretic condition for the convergence of the algorithm. An application is presented that pertains to a special multi-leader follower game wherein the nonconvexity is due to the followers' equilibrium conditions in the leaders' optimization problems. Another application to a cognitive radio paradigm in a signal processing game is described in detail in [G. Scutari and J.S. Pang, IEEE Trans. Inform. Theory, submitted; J.S. Pang and G. Scutari, Joint IEEE Trans. Signal Process, submitted]. [ABSTRACT FROM AUTHOR]

A common thread in all of the recent results concerning the testing of dense graphs is the use of Szemerédi's regularity lemma. In this paper we show that in some sense this is not a coincidence. Our first result is that the property defined by having any given Szemerédi-partition is testable with a constant number of queries. Our second and main result is a purely combinatorial characterization of the graph properties that are testable with a constant number of queries. This characterization (roughly) says that a graph property P can be tested with a constant number of queries if and only if testing P can be reduced to testing the property of satisfying one of finitely many Szemerédi-partitions. This means that in some sense, testing for Szemerédi-partitions is as hard as testing any testable graph property. We thus resolve one of the main open problems in the area of property-testing, which was first raised by Goldreich, Goldwasser, and Ron [J. ACM, 45 (1998), pp. 653-750] in the paper that initiated the study of graph property-testing. This characterization also gives an intuitive explanation as to what makes a graph property testable. [ABSTRACT FROM AUTHOR]

This paper studies the limiting behavior of weighted infeasible central paths for semidefinite programming (SDP) obtained from centrality equations of the form X½ SX½ = vW, where W is a fixed positive definite matrix and v>0 is a parameter, under the assumption that the problem has a strictly complementary primal-dual optimal solution. It is shown that a weighted central path as a function of √v can be extended analytically beyond 0 and hence that the path converges as v↓0. Characterization of the limit points of the path and its normalized first-order derivatives are also provided. As a consequence, it is shown that a weighted central path can have two types of behavior: it converges either as &Tetha;(v) or asT &Tetha;(√v) depending on whether the matrix W on a certain scaled space is block diagonal or not, respectively. We also derive an error bound on the distance between a point lying in a certain neighborhood of the central path and the set of primal-dual optimal solutions. Finally, in light of the results of this paper, we give a characterization of a sufficient condition proposed by Potra and Sheng which guarantees the superlinear convergence of a class of primal-dual interior-point SDP algorithms. [ABSTRACT FROM AUTHOR]

Let M be a 2 × 2 matrix of Laurent polynomials with real coefficients and symmetry. In this paper, we obtain a necessary and sufficient condition for the existence of four Laurent polynomials (or finite-impulse-response filters) u1, u2, v1, v2 with real coefficients and symmetry such that [This symbol cannot be presented in ASCII format] and [Su1](z)[Sv2](z) = [Su2](z)[Sv1](z), where [Sp](z) = p(z)/p(1/z) for a nonzero Laurent polynomial p. Our criterion can be easily checked and a step-by-step algorithm will be given to construct the symmetric filters u1, u2, v1, v2. As an application of this result to symmetric framelet filter banks, we present a necessary and sufficient condition for the construction of a symmetric multiresolution analysis tight wavelet frame with two compactly supported generators derived from a given symmetric refinable function. Once such a necessary and sufficient condition is satisfied, an algorithm will be used to construct a symmetric framelet filter bank with two high-pass filters which is of interest in applications such as signal denoising and image processing. As an illustration of our results and algorithms in this paper, we give several examples of symmetric framelet filter banks with two highpass filters which have good vanishing moments and are derived from various symmetric low-pass filters including some B-spline filters. [ABSTRACT FROM AUTHOR]

Given a directed graph G and an arc weight function w : E(G) → R+, the maximum directed cut problem (max dicut) is that of finding a directed cut δ(X) with maximum total weight. In this paper we consider a version of max dicut--max dicut with given sizes of parts or max dicut with gsp--whose instance is that of max dicut plus a positive integer p, and it is required to find a directed cut δ(X) having maximum weight over all cuts δ(X) with |X| = p. Our main result is a 0.5-approximation algorithm for solving the problem. The algorithm is based on a tricky application of the pipage rounding technique developed in some earlier papers by two of the authors and a remarkable structural property of basic solutions to a linear relaxation. The property is that each component of any basic solution is an element of a set {0,δ, 1/2, 1 - δ, 1}, where δ is a constant that satisfies 0 < δ < 1/2 and is the same for all components. [ABSTRACT FROM AUTHOR]

In this paper we study the inversion of an analytic matrix valued function A(z). This problem can also be viewed as an analytic perturbation of the matrix A0 = A(0). We are mainly interested in the case where A0 is singular but A(z) has an inverse in some punctured disc around z = 0. It is known that A-1 (z) can be expanded as a Laurent series at the origin. The main purpose of this paper is to provide efficient computational procedures for the coefficients of this series. We demonstrate that the proposed algorithms are computationally superior to symbolic algebra when the order of the pole is small. [ABSTRACT FROM AUTHOR]

This paper analyzes the process of merging groups of many Gaussian basis functions into a single basis function in vortex simulations. Analysis of the equations governing this process yields fundamental parameters and uniform estimates of the merger-induced error. In a merging event, the uniform error bound depends only on relationships between nearby computational elements permitting fast and effective merging schemes. In this paper, one such algorithm is proposed and demonstrated. [ABSTRACT FROM AUTHOR]

The Laplace Transform is frequently encountered in mathematics, physics, engineering, and other fields. However, the spectral properties of the Laplace Transform tend to complicate its numerical treatment; therefore, the closely related "Truncated" Laplace Transforms are often used in applications. We have constructed efficient algorithms for the evaluation of the Singular Value Decomposition of Truncated Laplace Transforms; in the current paper, we introduce algorithms for the evaluation of the right singular functions and singular values of Truncated Laplace Transforms. Algorithms for the computation of the left singular functions will be introduced separately in an upcoming paper. The resulting algorithms are applicable to all environments likely to be encountered in applications, including the evaluation of singular functions corresponding to extremely small singular values (e.g., 10-1000). [ABSTRACT FROM AUTHOR]

For matrices with displacement structure, basic operations like multiplication, inversion, and linear system solving can all be expressed in terms of the following task: evaluate the product AB, where A is a structured n × n matrix of displacement rank α, and B is an arbitrary n × α matrix. Given B and a so-called generator of A, this product is classically computed with a cost ranging from O(α² M (n)) to O(α²M (n) log(n)) arithmetic operations, depending on the type of structure of A; here, M is a cost function for polynomial multiplication. In this paper, we first generalize classical displacement operators, based on block diagonal matrices with companion diagonal blocks, and then design fast algorithms to perform the task above for this extended class of structured matrices. The cost of these algorithms ranges from O(αω-1 M (n)) to O(αω-1 M (n) log(n)), with ω such that two n × n matrices can be multiplied using O(nω) ring operations. By combining this result with classical randomized regularization techniques, we obtain faster Las Vegas algorithms for structured inversion and linear system solving. [ABSTRACT FROM AUTHOR]

Phylogenetic trees are used to model evolution: leaves are labeled to represent contemporary species ("taxa""), and interior vertices represent extinct ancestors. Informally, convex characters are measurements on the contemporary species in which the subset of species (both contemporary and extinct) that share a given state form a connected subtree. Kelk and Stamoulis [Adv. Appl. Math., 84 (2017), pp. 34--46] showed how to efficiently count, list, and sample certain restricted subfamilies of convex characters, and algorithmic applications were given. We continue this work in a number of directions. First, we show how combining the enumeration of convex characters with existing parameterized algorithms can be used to speed up exponential-time algorithms for the maximum agreement forest problem in phylogenetics. Second, we revisit the quantity g2(T), defined as the number of convex characters on T in which each state appears on at least 2 taxa. We use this to give an algorithm with running time Oφn poly(n)), where 1.6181 is the golden ratio and n is the number of taxa in the input trees for computation of maximum parsimony distance on two state characters. By further restricting the characters counted by g2(T) we open an interesting bridge to the literature on enumeration of matchings. By crossing this bridge we improve the running time of the aforementioned parsimony distance algorithm to O(1.5895n poly(n)) and obtain a number of new results in themselves relevant to enumeration of matchings on at most binary trees. [ABSTRACT FROM AUTHOR]

We present in this paper two different classes of general multiple-splitting algorithms for solving finite-dimensional convex optimization problems. Under the assumption that the function being minimized can be written as the sum of K convex functions, each of which has a Lipschitz continuous gradient, we prove that the number of iterations needed by the first class of algorithms to obtain an ε-optimal solution is O((K - 1)L/ε), where L is an upper bound on all of the Lipschitz constants. The algorithms in the second class are accelerated versions of those in the first class, where the complexity result is improved to O(√(K - 1)L/ε) while the computational effort required at each iteration is almost unchanged. To the best of our knowledge, the complexity results presented in this paper are the first ones of this type that have been given for splitting and alternating direction-type methods. Moreover, all algorithms proposed in this paper are parallelizable, which makes them particularly attractive for solving certain large-scale problems. [ABSTRACT FROM AUTHOR]

To provide generalized solutions if a given problem admits no actual solution is an important task in mathematics and the natural sciences. It has a rich history dating back to the early 19th century, when Carl Friedrich Gauss developed the method of least squares of a system of linear equations--its solutions can be viewed as fixed points of averaged projections onto hyperplanes. A powerful generalization of this problem is to find fixed points of averaged resolvents (i.e., firmly nonexpansive mappings). This paper concerns the relationship between the set of fixed points of averaged resolvents and certain fixed point sets of compositions of resolvents. It partially extends recent work for two mappings on a question of C. Byrne. The analysis suggests a reformulation in a product space. Algorithmic consequences are also presented. [ABSTRACT FROM AUTHOR]

In this paper, we consider the half-integral disjoint paths packing. For a graph G and k pairs of vertices (s1, t1), (s2, t2), …, (sk, tk) in G, the objective is to find paths P1, …, Pk in G such that Pi joins si and ti for i = 1, 2, …, k, and in addition, each vertex is on at most two of these paths. We give a polynomial-time algorithm to decide the feasibility of this problem with k = O((log n/log log n)1/7). This improves a result by Kleinberg [Proceedings of the 30th ACM Symposium on Theory of Computing, 1998, pp 530-539] who proved the same conclusion when k = O((log log n)2/15). Our algorithm still works for several problems related to the bounded unsplittable flow. These results can all carry over to problems involving edge capacities. Our main technical contribution is to give a "crossbar" of a polynomial size of the tree width of the graph. [ABSTRACT FROM AUTHOR]

Accurate signal recovery or image reconstruction from indirect and possibly undersampled data is a topic of considerable interest; for example, the literature in the recent field of compressed sensing is already quite immense. This paper applies a smoothing technique and an accelerated first-order algorithm, both from Nesterov [Math. Program. Ser. A , 103 (2005), pp. 127-152], and demonstrates that this approach is ideally suited for solving large-scale compressed sensing reconstruction problems as (1) it is computationally efficient, (2) it is accurate and returns solutions with several correct digits, (3) it is flexible and amenable to many kinds of reconstruction problems, and (4) it is robust in the sense that its excellent performance across a wide range of problems does not depend on the fine tuning of several parameters. Comprehensive numerical experiments on realistic signals exhibiting a large dynamic range show that this algorithm compares favorably with recently proposed state-of-the-art methods. We also apply the algorithm to solve other problems for which there are fewer alternatives, such as total-variation minimization and convex programs seeking to minimize the 1 norm of Wx under constraints, in which W is not diagonal. The code is available online as a free package in the MATLAB language. [ABSTRACT FROM AUTHOR]

Compressed sensing (CS) seeks to recover an unknown vector with N entries by making far fewer than N measurements; it posits that the number of CS measurements should be comparable to the information content of tile vector, not simply N. CS combines directly the important task of compression with the measurement task. Since its introduction in 2004 there have been hundreds of papers on CS, a large fraction of which develop algorithms to recover a signal from its compressed measurements. Because of the paradoxical nature of CS--exact reconstruction from seemingly undersampled measurements--it is crucial for acceptance of an algorithm that rigorous analyses verify the degree of undersampling the algorithm permits. The restricted isometry property (RIP) has become the dominant tool used for the analysis in such cases. We present here an asymmetric form of RIP that gives tighter bounds than the usual symmetric one. We give the best known bounds on the RIP constants for matrices from the Gaussian ensemble. Our derivations illustrate the way in which the combinatorial nature of CS is controlled. Our quantitative bounds on the RIP allow precise statements as to how aggressively a signal can be undersampled, the essential question for practitioners. We also document the extent to which RIP gives precise information about the true performance limits of CS, by comparison with approaches from high-dimensional geometry. [ABSTRACT FROM AUTHOR]

This paper presents some guidance for choosing multigrid preconditioners for systems of partial differential equations (PDEs). Rather than developing a black-box algorithm for arbitrary systems of PDEs, the strategy in this paper is to classify systems with multigrid preconditioners. From this classification, a new preconditioner is developed, and it is shown to be suitable for a particular class of strongly cross-coupled systems, solving the whole cross-coupled system almost as effectively as solving just the diagonal system. Also, this paper gives an explanation of why block diagonal preconditioners are somewhat effective for certain strongly cross-coupled systems that at first glance appear to be intractable for multigrid preconditioning. [ABSTRACT FROM AUTHOR]

In this paper, we propose iterative algorithms for solving image restoration problems. The iterative algorithms are based on decoupling of deblurring and denoising steps in the restoration process. In the deblurring step, an efficient deblurring method using fast transforms can be employed. In the denoising step, effective methods such as the wavelet shrinkage denoising method or the total variation denoising method can be used. The main advantage of this proposal is that the resulting algorithms can be very efficient and can produce better restored images in visual quality and signalto-noise ratio than those by the restoration methods using the combination of a data-fitting term and a regularization term. The convergence of the proposed algorithms is shown in the paper. Numerical examples are also given to demonstrate the effectiveness of these algorithms. [ABSTRACT FROM AUTHOR]

The Lloyd algorithm originated in the context of optimal quantization and represents a fixed point iteration for computing an optimal quantizer. Reducing average distortion at every step, it constructs a Voronoi partition of the domain and replaces each generator with the centroid of the corresponding Voronoi cell. Optimal quantization is obtained in the case of a centroidal Voronoi tessellation (CVT), which is a special Voronoi tessellation of a domain Ω ϵ ℝd having the property that the generators of the Voronoi diagram are also the centers of mass, with respect to a given density function ? ⩾ 0, of the corresponding Voronoi cells. The Lloyd iteration is currently the most popular and elegant algorithm for computing CVTs and optimal quantizers, but many questions remain about its convergence, especially in d-dimensional spaces (d > 1). In this paper, we prove that any limit point of the Lloyd iteration in any dimensional spaces is nondegenerate provided that Ω is a convex and bounded set and ? belongs to L¹(Ω) and is positive almost everywhere. This ensures that the fixed point map remains closed and hence the standard theory of descent methods guarantees weak global convergence of the Lloyd iteration to the set of nondegenerate fixed point quantizers. While previously only conjectured, the convergence properties of the Lloyd iteration are rigorously justified under such minimal regularity assumptions on the density functional. The results presented in this paper go beyond existing convergence theories for CVTs and optimal quantization related algorithms and should be of interest to both the mathematical and engineering communities. [ABSTRACT FROM AUTHOR]

In 1996 Ivkovič and Lloyd [A fundamental restriction on fully dynamic maintenance of bin packing, Inform. Process. Lett., 59 (1996), pp. 229-232] gave the lower bound 4/3 on the asymptotic worst-case ratio for so-called fully dynamic bin packing algorithms, where the number of repackable items in each step is restricted by a constant. In this paper we improve this result to about 1.3871. We present our proof for a semionline case of the classical bin packing, but it works for fully dynamic bin packing as well. We prove the lower bound by analyzing and solving a specific optimization problem. The bound can be expressed exactly using the Lambert W function. [ABSTRACT FROM AUTHOR]

This paper approaches optimal control problems for discrete-time controlled Markov processes by representing the value of the problem in a dual Lagrangian form; the value is expressed as an infimum over a family of Lagrangian martingales of an expectation of a pathwise supremum of the objective adjusted by the Lagrangian martingale term. This representation opens up the possibility of numerical methods based on Monte Carlo simulation, which may be advantageous in high-dimensional problems or in problems with complicated constraints. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of minimization of a nonsmooth function under general nonsmooth constraints when no derivatives of the objective or constraint functions are available. We introduce the mesh adaptive direct search (MADS) class of algorithms which extends the generalized pattern search (GPS) class by allowing local exploration, called polling, in an asymptotically dense set of directions in the space of optimization variables. This means that under certain hypotheses, including a weak constraint qualification due to Rockafellar, MADS can treat constraints by the extreme barrier approach of setting the objective to infinity for infeasible points and treating the problem as unconstrained. The main GPS convergence result is to identify limit points x0302;, where the Clarke generalized derivatives are nonnegative in a finite set of directions, called refining directions. Although in the unconstrained case, nonnegative combinations of these directions span the whole space, the fact that there can only be finitely many GPS refining directions limits rigorous justification of the barrier approach to finitely many linear constraints for GPS. The main result of this paper is that the general MADS framework is flexible enough to allow the generation of an asymptotically dense set of refining directions along which the Clarke derivatives are nonnegative. We propose an instance of MADS for which the refining directions are dense in the hypertangent cone at x0302; with probability 1 whenever the iterates associated with the refining directions converge to a single x0302;. The instance of MADS is compared to versions of GPS on some test problems. We also illustrate the limitation of our results with examples. [ABSTRACT FROM AUTHOR]

In this paper, we introduce the doubling transformation, a structure-preserving transformation for symplectic pencils, and present its basic properties. Based on these properties, a unified convergence theory for the structure-preserving doubling algorithms for a class of Riccati-type matrix equations is established, using only elementary matrix theory. [ABSTRACT FROM AUTHOR]

In this paper, an efficient and stable numerical algorithm for computing multiple saddle points with symmetries is developed by modifying the local minimax method established in [Y. Li and J. Zhou, SIAM J. Sci. Comput. 23 (2001), pp. 840--865; Y. Li and J. Zhou, SIAM J. Sci. Comput., 24 (2002), pp. 840--865]. First an invariant space is defined in a more general sense and a principle of invariant criticality is proved for the generalization. Then the orthogonal projection to the invariant space is used to preserve the invariance and to reduce computational error across iterations. Simple averaging formulas are used for the orthogonal projections. Numerical computations of examples with various symmetries, of which some can and others cannot be characterized by a compact group of linear isomorphisms, are carried out to confirm the theory and to illustrate applications. The mathematical features of various problems demonstrated in these examples fall into two categories: nodal solutions of saddle-point type with large Morse indices and nonradial positive solutions via symmetry breaking in radially symmetric elliptic problems. The new numerical algorithm generates these rather unstable solutions in an efficient and stable way. The existence of many unstable solutions and their behavior found in this paper remain to be investigated. [ABSTRACT FROM AUTHOR]

Sweeney--Robertson--Tocher (SRT) division, as it was discovered in the late 1950s, represented an important improvement in the speed of division algorithms for computers at the time. A variant of SRT division is still commonly implemented in computers today. Although some bounds on the performance of the original SRT division method were obtained, a great many questions remained unanswered. In this paper, the original version of SRT division is described as a dynamical system. This enables us to bring modern dynamical systems theory, a relatively new development in mathematics, to bear on an older problem. In doing so, we are able to show that SRT division is ergodic, and is even Bernoulli, for all real divisors and dividends. With the Bernoulli property, we are able to use entropy to prove that the natural extensions of SRT division are isomorphic by way of the Kolmogorov--Ornstein theorem. We demonstrate how our methods and results can be applied to a much larger class of division algorithms. [ABSTRACT FROM AUTHOR]

Property testing is a relaxation of classical decision problems which aims at distinguishing between functions having a predetermined property and functions being far from any function having the property. In this paper we present a novel framework for analyzing property testing algorithms. Our framework is based on a connection of property testing and a new class of problems which we call abstract combinatorial programs. We show that if the problem of testing a property can be reduced to an abstract combinatorial program of small dimension, then the property has an efficient tester. We apply our framework to a variety of problems. We present efficient property testing algorithms for geometric clustering problems, for the reversal distance problem, and for graph and hypergraph coloring problems. We also prove that, informally, any hereditary graph property can be efficiently tested if and only if it can be reduced to an abstract combinatorial program of small size. Our framework allows us to analyze all our testers in a unified way, and the obtained complexity bounds either match or improve the previously known bounds. Furthermore, even if the asymptotic complexity of the testers is not improved, the obtained proofs are significantly simpler than the previous ones. We believe that our framework will help to understand the structure of efficiently testable properties. [ABSTRACT FROM AUTHOR]

In this paper, we study the projection onto the intersection of an affine subspace and a convex set and provide a particular treatment for the cone of positive semidefinite matrices. Among applications of this problem is the calibration of covariance matrices. We propose a Lagrangian dualization of this least-squares problem, which leads us to a convex differentiable dual problem. We propose to solve the latter problem with a quasi-Newton algorithm. We assess this approach with numerical experiments which show that fairly large problems can be solved efficiently. [ABSTRACT FROM AUTHOR]

In this paper we present a. variant of Vavasis and Ye's layered step path following primal-dual interior-point algorithm for linear programming. Our algorithm is a predictor corrector-type algorithm which uses from time to time the layered least squares (LLS) direction it, place of the affine scaling (AS) direction. It, has the same iteration-complexity bound of Vavasis and Ye's algorithm, namely O(n[sup3.5] log(XA + n)), where n is the number of normegative variables and XA is a certain condition number associated with the constraint matrix A. Vavasis and Ye's algorithm requires explicit knowledge of XA (which is very hard to compute or even estimate) in order to compute the layers for the LLS direction. It, contrast, our algorithm uses the AS direction at the current iterate to determine the layers for the LLS direction, and hence does not require the knowledge of XA. A variant with similar properties and with the same complexity has been developed by Megiddo, Mizuno, and Tsuchiya [Math. Programming, 82 (1998), pp. 339-355]. However, their algorithm needs to compute n LLS directions on every iteration, while ours computes at most one LLS direction on any given iteration. [ABSTRACT FROM AUTHOR]

This paper contains a new convergence analysis for the Lewis and Torczon generalized pattern search (GPS) class of methods for unconstrained and linearly constrained optimization. This analysis is motivated by a desire to understand the successful behavior of the algorithm under hypotheses that are satisfied by many practical problems. Specifically, even if the objective function is discontinuous or extended-valued, the methods find a limit point with some minimizing properties. Simple examples show that the strength of the optimality conditions at a limit point depends not only on the algorithm, but also on the directions it uses and on the smoothness of the objective at the limit point in question. The contribution of this paper is to provide a simple convergence analysis that supplies detail about the relation of optimality conditions to objective smoothness properties and to the defining directions for the algorithm, and it gives previous results as corollaries. [ABSTRACT FROM AUTHOR]

A matrix decomposition method for positive semidefinite matrices based on a given subspace is proposed in this paper. It is shown that any positive semidefinite matrix can be decom- posed uniquely into two positive semidefinite parts with specified rank one of which is orthogonal to the subspace. This method is then compared with the rank-additivity decomposition, and the difference as well as the close connection between these two decompositions are given. Finally, the proposed decomposition method is used to develop a new recursive parameter estimation algorithm for linear systems. [ABSTRACT FROM AUTHOR]

The Schwarz alternating method can be used to solve linear elliptic boundary value problems on domains which consist of two or more overlapping subdomains. The solution is approx- imated by an infinite sequence of functions which result from solving a sequence of elliptic boundary value problems in each of the subdomains. This paper considers four Schwarz alternating methods for the N-dimensional, steady, viscous, incompressible Navier­Stokes equations, N ≤ 4. It is shown that the Schwarz sequences converge to the true solution provided that the Reynolds number is sufficiently small. [ABSTRACT FROM AUTHOR]

Consider the 2n (or O(n²)) min-cut problems on a graph with n nodes and nonnegative edge weights. Gomory and Hu [J. Soc. Indust. Appl. Math., 9 (1961), pp. 551–570] showed (essentially) that there are at most n-1 different min-cuts. They also described a compact structure (the flow equivalent tree) of size O(n) with the following property: for any pair of nodes, the value of a min-cut can be obtained from this structure. Furthermore, they showed how this structure can be found by solving only n - 1 min-cut problems. This paper contains generalizations of these results. For example, consider a k-terminal cut problem on a graph: for a given set of k nodes, delete a minimum weight set of edges (called a k-cut) so that each of the k nodes is in a different component. There are kn (or O(nk)) such problems. Hassin [Math. Oper. Res., 13 (1988), pp. 535–542] showed (essentially) that there are at most k-1n-1 (or O(nk-1)) different min k-cuts. We describe a compact structure of size O(nk-1) with the following property: for any k nodes, the value of a min k-cut can be obtained from this structure. We also show how this structure can be found by solving only k-1n-1 k-terminal cut problems. This work builds upon the results of Hassin [Math. Oper. Res., 13 (1988), pp. 535–542], [Oper. Res. Lett., 9 (1990), pp. 315–318], and [Lecture Notes in Comput. Sci. 450, 1990, pp. 228–299]. [ABSTRACT FROM AUTHOR]

The implicitly shifted (bulge-chasing) QZ algorithm is the most popular method for solving the generalized eigenvalue problem Av = λBv. This paper explains why the QZ algorithm functions well even in the presence of infinite eigenvalues. The key to rapid convergence of QZ (and QR) algorithms is the effective transmission of shifts during the bulge chase. In this paper the mechanism of transmission of shifts is identified, and it is shown that this mechanism is not disrupted by the presence of infinite eigenvalues. Both the QZ algorithm and the preliminary reduction to Hessenberg-triangular form tend to push the infinite eigenvalues toward the top of the pencil. Thus they should be deflated at the top. [ABSTRACT FROM AUTHOR]

A transshipment problem with demands that exceed network capacity can be solved by sending flow in several waves. How can this be done in the minimum number, T, of waves, and at minimum cost, if costs are piecewise linear convex functions of the flow? In this paper, we show that this problem can be solved using min{m, log T, log(mΓU) / 1+log(mΓU)-log(mU)} maximum flow computations and one minimum (convex) cost flow computation. Here m is the number of arcs, Γ is the maximum supply or demand, and U is the maximum capacity. When there is only one sink, this problem can be solved in the same asymptotic time as one minimum (convex) cost flow computation. This improves upon the previous best algorithm to solve the problem without costs by a factor of k. Our solutions start with a stationary fractional flow and use rounding to transform this into an integral flow. The rounding procedure takes O(n) time. [ABSTRACT FROM AUTHOR]

Dynamical systems can often be decomposed into loosely coupled subsystems. The system of ordinary differential equations (ODEs) modelling such a problem can then be partitioned corresponding to the subsystems, and the loose couplings can be exploited by special integration methods to solve the problem using a parallel computer or just solve the problem more efficiently than by standard methods. This paper presents accuracy analysis of methods for the numerical integration of stiff partitioned systems of ODEs. The discretization formulas are based on the implicit Euler formula and the second order implicit backward differentiation formula (BDF2). Each subsystem of the partitioned problem is discretized independently, and the couplings to the other subsystems are based on solution values from previous time steps. Applied this way, the discretization formulas are called decoupled. The stability properties of the decoupled implicit Euler formula are well understood. This paper presents error bounds and asymptotic error expansions to be used in controlling step size, relaxation between subsystems and the validity of the partitioning. The decoupled BDF2 formula is analyzed within the same framework. Finally, the analysis is used in the design of a decoupled numerical integration algorithm with variable step size to control the local error and adaptive selection of partitionings. Two versions of the algorithm with decoupled implicit Euler and BDF2, respectively, are used in examples where a realistic problem is solved. The examples compare the results from the decoupled implicit Euler and BDF2 formulas, and compare them with results from the corresponding classical formulas. [ABSTRACT FROM AUTHOR]

Let R be an arbitrary Euclidean domain and A be an n×n matrix of determinant 1 whose entries are elements of R. Gaussian elimination process based on Euclidean division algorithm (on R) allows one to write A as a product of elementary matrices over R. Suslin's stability theorem states that any n×n multivariate polynomial matrix of determinant 1 with n 3 can be written as a product of elementary matrices. This result fails when n = 2, and a counter-example was constructed by P. M. Cohn [Inst. Hautes ´ Etudes Sci. Publ. Math. 30 (1996), pp. 365­413]. In this paper, an algorithm is developed that determines precisely when a given matrix in SL2(R[x1,...,xm]) allows a factorization into elementary matrices and, if it does, expresses it as a product of elementary matrices. This algorithm has potential applications to signal processing, in which case the coefficient ring R is usually taken as a field or a ring Z of integers. Extending the idea used in this algorithm, we disprove a conjecture of Tolhuizen­Hollmann­Kalker regarding the realizability of a certain FIR filter. [ABSTRACT FROM AUTHOR]

Greedy algorithms for ordering sparse matrices for Cholesky factorization can be based on different metrics. Minimum degree, a popular and effective greedy ordering scheme, minimizes the number of nonzero entries in the rank-1 update (degree) at each step of the factorization. Alternatively, minimum deficiency minimizes the number of nonzero entries introduced (deficiency) at each step of the factorization. In this paper we develop two new heuristics: modified minimum deficiency (MMDF) and modified multiple minimum degree (MMMD). The former uses a metric similar to deficiency while the latter uses a degree-like metric. Our experiments reveal that on the average, MMDF orderings result in 21% fewer operations to factor than minimum degree; MMMD orderings result in 15% fewer operations to factor than minimum degree. MMMD requires on the average 7–13% more time than minimum degree, while MMDF requires on the average 33–34% more time than minimum degree. [ABSTRACT FROM AUTHOR]

Computing the Jordan form of a matrix or the Kronecker structure of a pencil is a well-known ill-posed problem. We propose that knowledge of the closure relations, i.e., the stratification, of the orbits and bundles of the various forms may be applied in the staircase algorithm. Here we discuss and complete the mathematical theory of these relationships and show how they may be applied to the staircase algorithm. This paper is a continuation of our Part I paper on versal deformations, but it may also be read independently. [ABSTRACT FROM AUTHOR]

Bender, Richmond, and Wormald showed that in almost all planar 3-connected triangulations (or dually, 3-connected cubic maps) with n edges, the largest 4-connected triangulation (or dually, the largest cyclically 4-edge-connected cubic component) has about n/2 edges [Random Structures Algorithms, 7 (1995), pp. 273-285]. In this paper, we derive some general results about the size of the largest component and apply them to a variety of types of planar maps. [ABSTRACT FROM AUTHOR]

The worst case length of a tour for the Euclidean traveling salesman problem produced by the nearest neighbor (NN) heuristic is studied in this paper. Nearest neighbor tours for a set of arbitrarily located points in the d-dimensional unit cube are considered. A technique is developed for bounding the worst case length of a tour. It is based on identifying sequences of coverings of [0,1]d. Each covering Pk consists of sets Ci, with diameter bounded by the diameter D(Pk) of the covering. For every sequence of coverings a bound is obtained that depends on the cardinality of the coverings and their diameters. The task of bounding the worst case length of an NN tour is reduced to finding appropriate sequences of coverings. Using coverings produced by the rectangular lattice with appropriately shrinking diameter, it is shown that the worst case length of an NN tour through Ar points in [0,1]d is bounded by [d√d/(d-1)]N(d-1)/d + o(N(d-1)/d). For the unit square the tighter bound 2.482→N + o(√N) is obtained using regular hexagonal lattice coverings. [ABSTRACT FROM AUTHOR]

In this paper we describe new constructions for de Bruijn sequences and Perfect Factors. These constructions are all based upon the idea of constructing one sequence (or set of sequences) from another. As a result of this fact, the sequences obtained from these construction methods possess simple decoding algorithms based on decoding the sequences used to construct them. Such decoding algorithms are of importance in position-location applications. [ABSTRACT FROM AUTHOR]

It is known that the First-Fit algorithm for partitioning a poset P into chains uses relatively few chains when P does not have two incomparable chains each of size k. In particular, if P has width w, then Bosek, Krawczyk, and Szczypka [SIAM J. Discrete Math., 23 (2010), pp. 1992-1999], proved an upper bound of ckw² on the number of chains used by First-Fit for some constant c, while Joret and Milans [Order, 28 (2011), pp. 455-464] gave one of ck²w. In this paper we prove an upper bound of the form ckw. This is most possible up to the value of c. [ABSTRACT FROM AUTHOR]

The Nelder-Mead algorithm, a longstanding direct search method for unconstrained optimization published in 1965, is designed to minimize a scalar-valued function f of n real variables using only function values, without any derivative information. Each Nelder-Mead iteration is associated with a nondegenerate simplex defined by n + 1 vertices and their function values; a typical iteration produces a new simplex by replacing the worst vertex by a new point. Despite the method's widespread use, theoretical results have been limited: for strictly convex objective functions of one variable with bounded level sets, the algorithm always converges to the minimizer; for such functions of two variables, the diameter of the simplex converges to zero but examples constructed by McKinnon show that the algorithm may converge to a nonminimizing point. This paper considers the restricted Nelder-Mead algorithm, a variant that does not allow expansion steps. In two dimensions we show that for any nondegenerate starting simplex and any twice-continuously differentiable function with positive definite Hessian and bounded level sets, the algorithm always converges to the minimizer. The proof is based on treating the method as a discrete dynamical system and relies on several techniques that are nonstandard in convergence proofs for unconstrained optimization. [ABSTRACT FROM AUTHOR]

Cops and robber is a classical pursuit-evasion game on undirected graphs, where the task is to identify the minimum number of cops sufficient to catch the robber. In this paper, we investigate the changes in problem's complexity and combinatorial properties with constraining the following natural game parameters: fuel, the number of steps each cop can make; cost, the total sum of steps along edges all cops can make; and time, the number of rounds of the game. [ABSTRACT FROM AUTHOR]

In this paper, a method for solving constrained convex optimization problems is introduced. The problem is cast equivalently as a parametric unconstrained one, the (single) parameter being the optimal value of the original problem. At each stage of the algorithm the parameter is updated, and the resulting subproblem is only approximately solved. A linear rate of convergence of the parameter sequence is established. Using an optimal gradient method due to Nesterov [Dokl. Akad. Nauk SSSR, 269 (1983), pp. 543 547] to solve the arising subproblems, it is proved that the resulting gradient-based algorithm requires an overall of O(log(1/ε)/√ε) inner iterations to obtain an ε-optimal and feasible solution. An image deblurring problem is solved, demonstrating the capability of the algorithm to solve large-scale problems within reasonable accuracy. [ABSTRACT FROM AUTHOR]

The Lloyd algorithm originated in the context of optimal quantization and represents a fixed point iteration for computing an optimal quantizer. Reducing average distortion at every step, it constructs a Voronoi partition of the domain and replaces each generator with the centroid of the corresponding Voronoi cell. Optimal quantization is obtained in the case of a centroidal Voronoi tessellation (CVT), which is a special Voronoi tessellation of a domain Ω ϵ ℝd having the property that the generators of the Voronoi diagram are also the centers of mass, with respect to a given density function ? ⩾ 0, of the corresponding Voronoi cells. The Lloyd iteration is currently the most popular and elegant algorithm for computing CVTs and optimal quantizers, but many questions remain about its convergence, especially in d-dimensional spaces (d > 1). In this paper, we prove that any limit point of the Lloyd iteration in any dimensional spaces is nondegenerate provided that Ω is a convex and bounded set and ? belongs to L¹(Ω) and is positive almost everywhere. This ensures that the fixed point map remains closed and hence the standard theory of descent methods guarantees weak global convergence of the Lloyd iteration to the set of nondegenerate fixed point quantizers. While previously only conjectured, the convergence properties of the Lloyd iteration are rigorously justified under such minimal regularity assumptions on the density functional. The results presented in this paper go beyond existing convergence theories for CVTs and optimal quantization related algorithms and should be of interest to both the mathematical and engineering communities. [ABSTRACT FROM AUTHOR]

In the (k, λ)-subgraph problem, we are given an undirected graph G = (V, E) with edge costs and two positive integers k and λ, and the goal is to find a minimum cost simple λ-edge-connected subgraph of G with at least k nodes. This generalizes several classical problems, such as the minimum cost k-spanning tree problem, or k-MST (which is a (k, 1)-subgraph), and the minimum cost λ-edge-connected spanning subgraph (which is a (|V(G)|, λ-subgraph). The only previously known results on this problem [L. C. Lau, J. S. Naor, M. R. Salavatipour, and M. Singh, SIAM J. Comput., 39 (2009), pp. 1062-1087], [C. Chekuri and N. Korula, in Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Bangalore, India, LIPIcs 2, Schloss Dagstuhl--Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2008, pp. 119-130] show that the (k, 2)-subgraph problem has an O(log² n)-approximation (even for 2-node-connectivity) and that the (k, λ)-subgraph problem in general is almost as hard as the densest k-subgraph problem. In this paper we show that if the edge costs are metric (i.e., satisfy the triangle in equality), like in the k-MST problem, then there is an O(1)-approximation algorithm for the (k, λ)-subgraph problem. This essentially generalizes the k-MST constant factor approximability to higher connectivity. [ABSTRACT FROM AUTHOR]

In the Rudin-Osher-Fatemi (ROF) image denoising model, total variation (TV) is used as a global regularization term. However, as we observe, the local interactions induced by TV do not propagate much at long distances in practice, so that the ROF model is not far from being a local filter. In this paper, we propose building a purely local filter by considering the ROF model in a given neighborhood of each pixel. We show that appropriate weights are required to avoid aliasing-like effects, and we provide an explicit convergence criterion for an associated dual minimization algorithm based on Chambolle's work. We study theoretical properties of the obtained local filter and show that this localization of the ROF model brings an interesting optimization of the bias-variance trade-off, and a strong reduction of an ROF drawback called the "staircasing effect." Finally, we present a new denoising algorithm, TV-means, that efficiently combines the idea of local TV-filtering with the nonlocal means patch-based method. [ABSTRACT FROM AUTHOR]

Let G = (V,E) be a weighted undirected graph having nonnegative edge weights. An estimate δˆ(u, v) of the actual distance d(u, v) between u, v ∈ V is said to be of stretch t if and only if δ(u, v) ≤ δˆ(u, v) = t · δ(u, v). Computing all-pairs small stretch distances efficiently (both in terms of time and space) is a well-studied problem in graph algorithms. We present a simple, novel, and generic scheme for all-pairs approximate shortest paths. Using this scheme and some new ideas and tools, we design faster algorithms for all-pairs t-stretch distances for a whole range of stretch t, and we also answer an open question posed by Thorup and Zwick in their seminal paper [J. ACM, 52 (2005), pp. 1-24]. [ABSTRACT FROM AUTHOR]

In this paper, we give the first approximation algorithm for the problem of max-min fair allocation of indivisible goods. An instance of this problem consists of a set of k people and m indivisible goods. Each person has a known linear utility function over the set of goods which might be different from the utility functions of other people. The goal is to distribute the goods among the people and maximize the minimum utility received by them. The approximation ratio of our algorithm is Ω(1/√k log3 k). As a crucial part of our algorithm, we design and analyze an iterative method for rounding a fractional matching on a tree which might be of independent interest. We also provide better bounds when we are allowed to exclude a small fraction of the people from the problem. [ABSTRACT FROM AUTHOR]