A randomized scheme for speeding up algorithms for linear and convex programming problems with high constraints-to-variables ratio

We extend Clarkson's randomized algorithm for linear programming to a general scheme for solving convex optimization problems. The scheme can be used to speed up existing algorithms on problems which have many more constraints than variables. In particular, we give a randomized algorithm for solving convex quadratic and linear programs, which uses that scheme together with a variant of Karmarkar's interior point method. For problems withn constraints,d variables, and input lengthL, ifn = (d ²), the expected total number of major Karmarkar's iterations is O(d ²(logn)L), compared to the best known deterministic bound of O( L). We also present several other results which follow from the general scheme.     

Efficient algorithms for solving rank two and rank three bilinear programming problems

Finitely convergent algorithms for solving rank two and three bilinear programming problems are proposed. A rank k bilinear programming problem is a nonconvex quadratic programming problem with the following structure: % MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4baFfea0dXde9vqpa0lb9% cq0dXdb9IqFHe9FjuP0-iq0dXdbba9pe0lb9hs0dXda91qaq-xfr-x% fj-hmeGabaqaciGacaGaaeqabaWaaeaaeaaakeaaieaacaWFTbGaa8% xAaiaa-5gacaWFPbGaa8xBaiaa-LgacaWF6bGaa8xzaiaa-bcacaWF% 7bacbiGaa43yamaaDaaaleaacaGFWaaabaGaa4hDaaaakiaa+Hhaca% GFRaGaa4hzamaaDaaaleaacaGFWaaabaGaa4hDaaaakiaa+LhacaGF% RaWaaabuaeaacaGFJbWaa0baaSqaaiaa+PgaaeaacaGF0baaaOGaam% iEaiabl+y6NjaadsgadaqhaaWcbaGaamOAaaqaaiaadshaaaGccaWG% 5bGaaiiFaaWcbaGaa8NAaiaa-1dacaWFXaaabeqdcqGHris5aOGaa4% hEaiabgIGiolaa+HfacaGFSaGaa4xEaiabgIGiolaa+LfacaWF9bGa% a8hlaaaa!5D2E!\[minimize \{ c_0^t x + d_0^t y + \sum\limits_{j = 1} {c_j^t xd_j^t y|} x \in X,y \in Y\} ,\]where X Rⁿ¹ and Y R ⁿ² are non-empty and bounded polytopes. We show that a variant of parametric simplex algorithm can solve large scale rank two bilinear programming problems efficiently. Also, we show that a cutting-cake algorithm, a more elaborate variant of parametric simplex algorithm can solve medium scale rank three problems.This research was supported in part by Grant-in-Aid for Scientific Research of the Ministry of Education, Science and Culture, Grant No. 63490010.     

A class of smoothing functions for nonlinear and mixed complementarity problems

We propose a class of parametric smooth functions that approximate the fundamental plus function, (x)₊=max{0, x}, by twice integrating a probability density function. This leads to classes of smooth parametric nonlinear equation approximations of nonlinear and mixed complementarity problems (NCPs and MCPs). For any solvable NCP or MCP, existence of an arbitrarily accurate solution to the smooth nonlinear equations as well as the NCP or MCP, is established for sufficiently large value of a smoothing parameter . Newton-based algorithms are proposed for the smooth problem. For strongly monotone NCPs, global convergence and local quadratic convergence are established. For solvable monotone NCPs, each accumulation point of the proposed algorithms solves the smooth problem. Exact solutions of our smooth nonlinear equation for various values of the parameter , generate an interior path, which is different from the central path for interior point method. Computational results for 52 test problems compare favorably with these for another Newton-based method. The smooth technique is capable of solving efficiently the test problems solved by Dirkse and Ferris [6], Harker and Xiao [11] and Pang & Gabriel [28].This material is based on research supported by Air Force Office of Scientific Research Grant F49620-94-1-0036 and National Science Foundation Grant CCR-9322479.     

An algorithm for the enumeration of spanning trees

Enumeration of spanning trees of an undirected graph is one of the graph problems that has received much attention in the literature. In this paper a new enumeration algorithm based on the idea of contractions of the graph is presented. The worst-case time complexity of the algorithm isO(n+m+nt) wheren is the number of vertices,m the number of edges, andt the number of spanning trees in the graph. The worst-case space complexity of the algorithm isO(n ²). Computational analysis indicates that the algorithm requires less computation time than any other of the previously best-known algorithms.     

An enumeration algorithm for combinatorial problems of the reliability analysis of binary coherent systems

In this paper the problem of the generation of all elements of a system of sets is investigated and a backtrack algorithm (Al) is given solving this problem.The algorithm is applied to combinatorial problems of reliability:

A t-graph is interpreted as a binary coherent system S and the system function of S is represented as the sum of Boolean orthogonal products. This approach is a simple and efficient alternative to a method suggested by Satyanarayana and N. Hagstbom [9].

A directed p-graph is also interpreted as a binary coherent system S and both the minimal cuts of S and the cocycles of G are determined.     

A linear system solver based on a modified Krylov subspace method for breakdown recovery

Despite its usefulness in solving eigenvalue problems and linear systems of equations, the nonsymmetric Lanczos method is known to suffer from a potential breakdown problem. Previous and recent approaches for handling the Lanczos exact and near-breakdowns include, for example, the look-ahead schemes by Parlett-Taylor-Liu [23], Freund-Gutknecht-Nachtigal [9], and Brezinski-Redivo Zaglia-Sadok [4]; the combined look-ahead and restart scheme by Joubert [18]; and the low-rank modified Lanczos scheme by Huckle [17]. In this paper, we present yet another scheme based on a modified Krylov subspace approach for the solution of nonsymmetric linear systems. When a breakdown occurs, our approach seeks a modified dual Krylov subspace, which is the sum of the original subspace and a new Krylov subspaceK _m (w _j ,A ^T ) wherew _j is a newstart vector (this approach has been studied by Ye [26] for eigenvalue computations). Based on this strategy, we have developed a practical algorithm for linear systems called the MLAN/QM algorithm, which also incorporates the residual quasi-minimization as proposed in [12]. We present a few convergence bounds for the method as well as numerical results to show its effectiveness.Research supported by Natural Sciences and Engineering Research Council of Canada.     

Maximal transitive sets with singularities for genericC 1 vector fields

A transitive set of a vector fieldX ismaximal transitive if it contains every transitive set ofX intersecting it. We shall prove that ifX isC ¹ generic then every singularity ofX with either only one positive or only one negative eigenvalue belongs to a maximal transitive set ofX. In particular, we characterize maximal transitive sets with singularities for genericC ¹ vector fields on closed 3-manifolds in terms of homoclinic classes associated to a unique singularity. We apply our results to the examples introduced in [3] and [15].This work is partially supported by CNPq 001/2000, FAPERJ and PRONEX/Dynamical Systems, FINEP-CNPq.     

Multilevel preconditioning on the refined interface and optimal boundary solvers for the Laplace equation

In this paper we propose and analyze some strategies to construct asymptotically optimal algorithms for solving boundary reductions of the Laplace equation in the interior and exterior of a polygon. The interior Dirichlet or Neumann problems are, in fact, equivalent to a direct treatment of the Dirichlet-Neumann mapping or its inverse, i.e., the Poincaré-Steklov (PS) operator. To construct a fast algorithm for the treatment of the discrete PS operator in the case of polygons composed of rectangles and regular right triangles, we apply the Bramble-Pasciak-Xu (BPX) multilevel preconditioner to the equivalent interface problem in theH ^1/2-setting. Furthermore, a fast matrix-vector multiplication algorithm is based on the frequency cutting techniques applied to the local Schur complements associated with the rectangular substructures specifying the nonmatching decomposition of a given polygon. The proposed compression scheme to compute the action of the discrete interior PS operator is shown to have a complexity of the orderO(N log ^q N),q [2, 3], with memory needsO(N log² N), whereN is the number of degrees of freedom on the polygonal boundary under consideration. In the case of exterior problems we propose a modification of the standard direct BEM whose implementation is reduced to the wavelet approximation applied to either single layer or hypersingular harmonic potentials and, in addition, to the matrix-vector multiplication for the discrete interior PS operator.     

A path following algorithm for a class of convex programming problems

We present a primal-dual path following interior algorithm for a class of linearly constrained convex programming problems with non-negative decision variables. We introduce the definition of a Scaled Lipschitz Condition and show that if the objective function satisfies the Scaled Lipschitz Condition then, at each iteration, our algorithm reduces the duality gap by at least a factor of (1–/n), where is positive and depends on the curvature of the objective function, by means of solving a system of linear equations which requires no more than O(n³) arithmetic operations. The class of functions having the Scaled Lipschitz Condition includes linear, convex quadratic and entropy functions.     

Parallelization Strategies for Rollout Algorithms

Rollout algorithms are innovative methods, recently proposed by Bertsekas et al. [3], for solving NP-hard combinatorial optimization problems. The main advantage of these approaches is related to their capability of magnifying the effectiveness of any given heuristic algorithm. However, one of the main limitations of rollout algorithms in solving large-scale problems is represented by their computational complexity. Innovative versions of rollout algorithms, aimed at reducing the computational complexity in sequential environments, have been proposed in our previous work [9]. In this paper, we show that a further reduction can be accomplished by using parallel technologies. Indeed, rollout algorithms have very appealing characteristics that make them suitable for efficient and effective implementations in parallel environments, thus extending their range of relevant practical applications.We propose two strategies for parallelizing rollout algorithms and we analyze their performance by considering a shared-memory paradigm. The computational experiments have been carried out on a SGI Origin 2000 with 8 processors, by considering two classical combinatorial optimization problems. The numerical results show that a good reduction of the execution time can be obtained by exploiting parallel computing systems.     

A procedure for finding the nucleolus of a cooperativen person game

The nucleolus is a central concept of solution in the theory of cooperativen person games with side payments; it has been introduced and studied by Schmeidler [1969] and several methods for finding the nucleolus have been proposed byKopelowitz [1967],Bruyneel [1979],Stearns [1968] andJustman [1977], respectively. The aim of the present paper is that of giving a new algorithm for finding the nucleolus and to discuss the relationship of this algorithm with those given by Kopelowitz and Bruyneel.The algorithm is based upon the concept of minimal balanced set of a finite set; this last concept has been introduced for other purposes byShapley [1967]. The relationship between the nucleolus and the balanced sets has been studied byKohlberg [1971], where it has been shown that the so-called coalition array of an imputation is the coalition array of the nucleolus iff some parts of it are balanced sets. Our algorithm computes such a coalition array by finding a sequence of minimal balanced sets. Any element of the sequence can be found be solving a LP problem, then the nucleolus is easily found from the coalition array.The algorithm is in some sense a dual of the Kopelowitz algorithm. It clarifies completely the relationship between the nucleolus and the minimal balanced sets, that allowed the statement of the Bruyneel's algorithm; moreover, our algorithm doesn't assume the knowledge of the list of weight vectors associated to the set of minimal balanced sets, but constructs only the part of the list needed for finding the nucleolus.

---

Zusammenfassung Ein kooperativesn-Personen-Spiel wird durch eine endliche MengeN (die Spielermenge) und eine nicht additive Mengenfunktionv, definiert auf der Potenzmenge vonN (d.h. auf den Koalitionen), charakterisiert. Auf Schmeidler geht der Begriff des Nukleolus als eines für ein kooperatives Spiel geeigneten Lösungskonzeptes zurück. Bruyneel und Kopelowitz haben jeweils Algorithmen zur Berechnung des Nukleolus eines vorgegebenen kooperativen Spieles angegeben. Das vorliegende Papier gibt einen weiteren Algorithmus an. Dieser ist — ähnlich wie der von Bruyneel entwickelte — begrifflich gestützt auf das Konzept der minimal balancierten Koalitionssysteme (eingeführt von Shapley). In seiner direkten Form benötigt der Algorithmus die Liste aller zu minimal balancierten Mengensystemen gehörenden Gewichtsvektoren, jedoch wird in Abschnitt 2 eine Methode angegeben, diese Liste mit Hilfe einer Folge linearer Programme zu vermeiden. Es stellt sich heraus, daß der vorgelegte Algorithmus in gewisser Weise dual zu dem von Kopelowitz entwickelten ist. Ein Vergleich aller drei nunmehr vorliegenden Algorithmen findet sich in Abschnitt 2.

     

Algorithms for confluent Vandermonde systems

Two compact algorithms are developed for solving systems of linear equationsV x=b andV ^T a=f, whereV=V( ₀, ₁, ..., _n ) is a confluent Vandermonde matrix of Hermite type. The solution is obtained by one forward and one backward vector recursion, starting with the right hand side. The total amount of storage is only 2n. The number of arithmetic operations needed isO(n ²) and compares favourably with other proposed methods.     

The numerical solution of Fredholm integral equations of the second kind with singular kernels

A numerical method is given for integral equations with singular kernels. The method modifies the ideas of product integration contained in [3], and it is analyzed using the general schema of [1]. The emphasis is on equations which were not amenable to the method in [3]; in addition, the method tries to keep computer running time to a minimum, while maintaining an adequate order of convergence. The method is illustrated extensively with an integral equation reformulation of boundary value problems for u–P(r ²)u=0; see [9].This research was supported in part by NSF grant GP-8554.     

Subadditive Separating Maps

Let X and Y denote compact Hausdorff spaces and let K = R (real numbers) or C(complex numbers). C(X) and C(Y) denote the spaces of K-valued continuous functions on X and Y, respectively. A map H : C(X) C(Y) is separating if fg = 0 implies that HfHg = 0. Results about automatic continuity and the form of additive and linear separating maps have been developed in [1], [2], [3], [4], [5], [7], [8], and [10]. In this article similar results are developed for subadditive separating maps. We show (Theorem 5.11) that certain biseparating, subadditive bijections H are automatically continuous.     

A generalized duality method for solving variational inequalities Applications to some nonlinear Dirichlet problems

Summary. In [2] Bermúdez and Moreno introduced a duality algorithm for the numerical solution of variational inequalities; this algorithm is based on some properties of the Yosida regularization of maximal monotone operators. The performances of this algorithm strongly depend on the choice of two constant parameters. A generalization of the algorithm with automatic choice of parameters was discussed in [13], where the constant parameters were replaced by scalar functions, thus improving the convergence of the algorithm. In this article we present a generalization of the Bermúdez-Moreno algorithm that allows the use of very general operators as parameters, extending some of the results in [2], [13] and [14]. As a particular case, we analyze the use of scalar and matrix-valued parameters in a L^p()^M context. We apply the results developed to some boundary value problems involving the p-Laplacian operator, where it is shown that the use of matrix-valued parameters improves the convergence of the algorithm.Mathematics Subject Classification (1991): 47J20 – 65N12     

On randomized algorithms for the majority problem

In the majority problem, we are given n balls coloured black or white and we are allowed to query whether two balls have the same colour or not. The goal is to find a ball of majority colour in the minimum number of queries. The answer is known to be n−B(n) where B(n) is the number of 1’s in the binary representation of n. In this paper we study randomized algorithms for determining majority, which are allowed to err with probability at most ε. We show that any such algorithm must have expected running time at least . Moreover, we provide a randomized algorithm which shows that this result is best possible. These extend a result of De Marco and Pelc [G. De Marco, A. Pelc, Randomized algorithms for determining the majority on graphs, Combin. Probab. Comput. 15 (2006) 823-834].     

Interior-point algorithm for quadratically constrained entropy minimization problems

In this paper, we develop an interior point algorithm for quadratically constrained entropy problems. The algorithm uses a variation of Newton's method to follow a central path trajectory in the interior of the feasible set. The primal-dual gap is made less than a given in at most steps, wheren is the dimension of the problem andm is the number of quadratic inequality constraints.     

A Method for Global Approximation of the Initial Value Problem

For the numerical solution of the initial value problem a parallel, global integration method is derived and studied. It is a collocation method. If f(x,y)f(x) the method coincides with the Filippi's modified Clenshaw–Curtis quadrature [11]. Two numerical algorithms are considered and implemented, one of which is the application of the new method to Picard iterations, so it is a waveform relaxation technique [3]. Numerical experiments are favourably compared with the ones given by the known GAM [2], GBS [14] and Sarafyan [18] methods.     

Solving Random Quadratic Systems of Equations Is Nearly as Easy as Solving Linear Systems

We consider the fundamental problem of solving quadratic systems of equations in , and is unknown. We propose a novel method, which starts with an initial guess computed by means of a spectral method and proceeds by minimizing a nonconvex functional as in the Wirtinger flow approach [13]. There are several key distinguishing features, most notably a distinct objective functional and novel update rules, which operate in an adaptive fashion and drop terms bearing too much influence on the search direction. These careful selection rules provide a tighter initial guess, better descent directions, and thus enhanced practical performance. On the theoretical side, we prove that for certain unstructured models of quadratic systems, our algorithms return the correct solution in linear time, i.e., in time proportional to reading the data {a_i} and {y_i} as soon as the ratio m/n between the number of equations and unknowns exceeds a fixed numerical constant. We extend the theory to deal with noisy systems in which we only have and prove that our algorithms achieve a statistical accuracy, which is nearly unimprovable. We complement our theoretical study with numerical examples showing that solving random quadratic systems is both computationally and statistically not much harder than solving linear systems of the same size—hence the title of this paper. For instance, we demonstrate empirically that the computational cost of our algorithm is about four times that of solving a least squares problem of the same size. © 2016 Wiley Periodicals, Inc.