Dictionary descent in optimization

The problem of convex optimization is studied. Usually in convex optimization the minimization is over a d-dimensional domain. Very often the convergence rate of an optimization algorithm depends on the dimension d. The algorithms studied in this paper utilize dictionaries instead of a canonical basis used in the coordinate descent algorithms. We show how this approach allows us to reduce dimensionality of the problem. Also, we investigate which properties of a dictionary are beneficial for the convergence rate of typical greedy-type algorithms.     

Accelerated parallel and distributed algorithm using limited internal memory for nonnegative matrix factorization

Nonnegative matrix factorization (NMF) is a powerful technique for dimension reduction, extracting latent factors and learning part-based representation. For large datasets, NMF performance depends on some major issues such as fast algorithms, fully parallel distributed feasibility and limited internal memory. This research designs a fast fully parallel and distributed algorithm using limited internal memory to reach high NMF performance for large datasets. Specially, we propose a flexible accelerated algorithm for NMF with all its \(L_1\) \(L_2\) regularized variants based on full decomposition, which is a combination of exact line search, greedy coordinate descent, and accelerated search. The proposed algorithm takes advantages of these algorithms to converges linearly at an over-bounded rate \((1-\frac{\mu }{L})(1 - \frac{\mu }{rL})^{2r}\) in optimizing each factor matrix when fixing the other factor one in the sub-space of passive variables, where r is the number of latent components, and \(\mu \) and L are bounded as \(\frac{1}{2} \le \mu \le L \le r\). In addition, the algorithm can exploit the data sparseness to run on large datasets with limited internal memory of machines, which is is advanced compared to fast block coordinate descent methods and accelerated methods. Our experimental results are highly competitive with seven state-of-the-art methods about three significant aspects of convergence, optimality and average of the iteration numbers.     

Fast Algorithm of Square Rooting in Some Finite Fields of Odd Characteristic

It was proved that the complexity of square root computation in the Galois field GF(3^s), s = 2^kr, is equal to O(M(2^k)M(r)k + M(r) log₂r) + 2^kkr^1+o(1), where M (n) is the complexity of multiplication of polynomials of degree n over fields of characteristics 3. The complexity of multiplication and division in the field GF(3^s) is equal to O(M(2^k)M(r)) and O(M(2^k)M(r)) + r^1+o(1), respectively. If the basis in the field GF(3^r) is determined by an irreducible binomial over GF(3) or is an optimal normal basis, then the summands 2^kkr^1+o(1) and r^1+o(1) can be omitted. For M(n) one may take n log₂nψ(n) where ψ(n) grows slower than any iteration of the logarithm. If k grow and r is fixed, than all the estimates presented here have the form O_r (M (s) log ₂s) = s (log ₂s)²ψ(s).     

Hybridization of accelerated gradient descent method

We present a gradient descent algorithm with a line search procedure for solving unconstrained optimization problems which is defined as a result of applying Picard-Mann hybrid iterative process on accelerated gradient descent S M method described in Stanimirovi? and Miladinovi? (Numer. Algor. 54, 503–520, 2010). Using merged features of both analyzed models, we show that new accelerated gradient descent model converges linearly and faster then the starting S M method which is confirmed trough displayed numerical test results. Three main properties are tested: number of iterations, CPU time and number of function evaluations. The efficiency of the proposed iteration is examined for the several values of the correction parameter introduced in Khan (2013).     

Two Bilinear (3 × 3)-Matrix Multiplication Algorithms of Complexity 25

As is known, a bilinear algorithm for multiplying 3 × 3 matrices can be constructed by using ordered triples of 3 × 3 matrices A _ρ , B _ρ , C _ρ , \(\rho = \overline {1,r} ,\) where r is the complexity of the algorithm. Algorithms with various symmetries are being extensively studied. This paper presents two algorithms of complexity 25 possessing the following two properties (symmetries): (1) the matricesA₁,B₁, and C1 are identity, (2) if the algorithm involves a tripleA, B, C, then it also involves the triples B, C, A and C, A, B. For example, these properties are inherent in the well-known Strassen algorithm for multiplying 2 × 2 matrices. Many existing (3 × 3)-matrix multiplication algorithms have property (2). Methods for finding new algorithms are proposed. It is shown that the found algorithms are different and new.     

Algorithms for positive semidefinite factorization

This paper considers the problem of positive semidefinite factorization (PSD factorization), a generalization of exact nonnegative matrix factorization. Given an m-by-n nonnegative matrix X and an integer k, the PSD factorization problem consists in finding, if possible, symmetric k-by-k positive semidefinite matrices \(\{A^1,\ldots ,A^m\}\) and \(\{B^1,\ldots ,B^n\}\) such that \(X_{i,j}=\text {trace}(A^iB^j)\) for \(i=1,\ldots ,m\), and \(j=1,\ldots ,n\). PSD factorization is NP-hard. In this work, we introduce several local optimization schemes to tackle this problem: a fast projected gradient method and two algorithms based on the coordinate descent framework. The main application of PSD factorization is the computation of semidefinite extensions, that is, the representations of polyhedrons as projections of spectrahedra, for which the matrix to be factorized is the slack matrix of the polyhedron. We compare the performance of our algorithms on this class of problems. In particular, we compute the PSD extensions of size \(k=1+ \lceil \log _2(n) \rceil \) for the regular n-gons when \(n=5\), 8 and 10. We also show how to generalize our algorithms to compute the square root rank (which is the size of the factors in a PSD factorization where all factor matrices \(A^i\) and \(B^j\) have rank one) and completely PSD factorizations (which is the special case where the input matrix is symmetric and equality \(A^i=B^i\) is required for all i).     

Numerical solution to generalized Lyapunov/Stein and rational Riccati equations in stochastic control

We consider the numerical solution of the generalized Lyapunov and Stein equations in \(\mathbb {R}^{n}\), arising respectively from stochastic optimal control in continuous- and discrete-time. Generalizing the Smith method, our algorithms converge quadratically and have an O(n³) computational complexity per iteration and an O(n²) memory requirement. For large-scale problems, when the relevant matrix operators are “sparse”, our algorithm for generalized Stein (or Lyapunov) equations may achieve the complexity and memory requirement of O(n) (or similar to that of the solution of the linear systems associated with the sparse matrix operators). These efficient algorithms can be applied to Newton’s method for the solution of the rational Riccati equations. This contrasts favourably with the naive Newton algorithms of O(n⁶) complexity or the slower modified Newton’s methods of O(n³) complexity. The convergence and error analysis will be considered and numerical examples provided.     

On the complexity of the gradient of a rational function

The Baur-Strassen method implies L(?f) ? 4L(f), where L(f) is the complexity of computing a rational function f by arithmetic circuits, and ?f is the gradient of f. We show that L(? f) ? 3L(f) + n, where n is the number of variables in f. In addition, the depth of a circuit for the gradient is estimated.     

A flexible coordinate descent method

We present a novel randomized block coordinate descent method for the minimization of a convex composite objective function. The method uses (approximate) partial second-order (curvature) information, so that the algorithm performance is more robust when applied to highly nonseparable or ill conditioned problems. We call the method Flexible Coordinate Descent (FCD). At each iteration of FCD, a block of coordinates is sampled randomly, a quadratic model is formed about that block and the model is minimized approximately/inexactly to determine the search direction. An inexpensive line search is then employed to ensure a monotonic decrease in the objective function and acceptance of large step sizes. We present several high probability iteration complexity results to show that convergence of FCD is guaranteed theoretically. Finally, we present numerical results on large-scale problems to demonstrate the practical performance of the method.     

Mappings connected with the gradient of conformal radius

In this paper we prove the following conformity criterion for the gradient of conformal radius ?R(D, z) of a convex domain D: the boundary ?D has to be a circumference. We calculate coefficients K(r) for K(r)-quasiconformal mappings ?R(D(r), z), D(r) ? D, 0 < r < 1, and complete the results obtained by F. G. Avkhadiev and K.-J. Wirths for the structure of boundary elements of quasiconformal mappings of the domain D.     

Parallel Nesterov’s method for large-scale minimization of partially separable functions

A parallel Nesterov algorithm, for solving unconstrained minimization of large scale partially separable convex functions, is presented. The problem is first transformed into a linearly constrained minimization of a separable function. A fast projected gradient (Nesterov) method is then applied to obtain a decomposition method with \(O(1/k^2)\) rate of convergence (where k is the iteration number). Preliminary numerical experiments show the efficiency of the proposed approach.     

<Emphasis Type="Italic">r</Emphasis>-Dynamic Chromatic Number of Some Line Graphs

An r-dynamic coloring of a graph G is a proper coloring c of the vertices such that |c(N(v))| ≥ min {r, deg(v)}, for each v ∈ V (G). The r-dynamic chromatic number of a graph G is the smallest k such that G admits an r-dynamic coloring with k colors. In this paper, we obtain the r-dynamic chromatic number of the line graph of helm graphs H_n for all r between minimum and maximum degree of H_n. Moreover, our proofs are constructive, what means that we give also polynomial time algorithms for the appropriate coloring. Finally, as the first, we define an equivalent model for edge coloring.     

Decomposition Techniques for Bilinear Saddle Point Problems and Variational Inequalities with Affine Monotone Operators

The majority of first-order methods for large-scale convex–concave saddle point problems and variational inequalities with monotone operators are proximal algorithms. To make such an algorithm practical, the problem’s domain should be proximal-friendly—admit a strongly convex function with easy to minimize linear perturbations. As a by-product, this domain admits a computationally cheap linear minimization oracle (LMO) capable to minimize linear forms. There are, however, important situations where a cheap LMO indeed is available, but the problem domain is not proximal-friendly, which motivates search for algorithms based solely on LMO. For smooth convex minimization, there exists a classical algorithm using LMO—conditional gradient. In contrast, known to us similar techniques for other problems with convex structure (nonsmooth convex minimization, convex–concave saddle point problems, even as simple as bilinear ones, and variational inequalities with monotone operators, even as simple as affine) are quite recent and utilize common approach based on Fenchel-type representations of the associated objectives/vector fields. The goal of this paper was to develop alternative (and seemingly much simpler) decomposition techniques based on LMO for bilinear saddle point problems and for variational inequalities with affine monotone operators.     

Rapidly computing sparse Legendre expansions via sparse Fourier transforms

In this paper, we propose a general strategy for rapidly computing sparse Legendre expansions. The resulting methods yield a new class of fast algorithms capable of approximating a given function f : [?1, 1] → ? with a near-optimal linear combination of s Legendre polynomials of degree ≤ N in just \((s \log N)^{\mathcal {O}(1)}\)-time. When s ? N, these algorithms exhibit sublinear runtime complexities in N, as opposed to traditional Ω(NlogN)-time methods for computing all of the first N Legendre coefficients of f. Theoretical as well as numerical results demonstrate the effectiveness of the proposed methods.     

A new infeasible-interior-point algorithm for linear programming over symmetric cones

In this paper we present an infeasible-interior-point algorithm, based on a new wide neighbourhood N(τ₁, τ₂, η), for linear programming over symmetric cones. We treat the classical Newton direction as the sum of two other directions. We prove that if these two directions are equipped with different and appropriate step sizes, then the new algorithm has a polynomial convergence for the commutative class of search directions. In particular, the complexity bound is O(r^1.5logε^?1) for the Nesterov-Todd (NT) direction, and O(r²logε^?1) for the xs and sx directions, where r is the rank of the associated Euclidean Jordan algebra and ε > 0 is the required precision. If starting with a feasible point (x⁰, y⁰, s⁰) in N(τ₁, τ₂, η), the complexity bound is \(O\left( {\sqrt r \log {\varepsilon ^{ - 1}}} \right)\) for the NT direction, and O(rlogε^?1) for the xs and sx directions. When the NT search direction is used, we get the best complexity bound of wide neighborhood interior-point algorithm for linear programming over symmetric cones.     

Approximate solution of the <Emphasis Type="Italic">p</Emphasis>-median minimization problem

A version of the facility location problem (the well-known p-median minimization problem) and its generalization—the problem of minimizing a supermodular set function—is studied. These problems are NP-hard, and they are approximately solved by a gradient algorithm that is a discrete analog of the steepest descent algorithm. A priori bounds on the worst-case behavior of the gradient algorithm for the problems under consideration are obtained. As a consequence, a bound on the performance guarantee of the gradient algorithm for the p-median minimization problem in terms of the production and transportation cost matrix is obtained.     

Intermediate links of plane curves

For a smooth complex curve C ? ?² we consider the link L_r = C ∩ ?B_r, where B_r denotes an Euclidean ball of radius r > 0. We prove that the diagram D_r obtained from L_r by a complex stereographic projection satisfies χ(C ∩B_r) = rot(D_r)?wr(D_r). As a consequence we show that if D_r has no negative Seifert circles and L_r is strongly quasipositive and fibered, then the Yamada–Vogel algorithm applied to D_r yields a quasipositive braid.     

On the additive complexity of GCD and LCM matrices

In the paper, the additive complexity of matrices formed by positive integer powers of greatest common divisors and least common multiples of the indices of the rows and columns is considered. It is proved that the complexity of the n × n matrix formed by the numbers GCD^r(i, k) over the basis {x + y} is asymptotically equal to rn log²n as n→∞, and the complexity of the n × n matrix formed by the numbers LCM^r(i, k) over the basis {x + y,?x} is asymptotically equal to 2rn log₂n as n→∞.     

Computing Proximal Points of Convex Functions with Inexact Subgradients

Locating proximal points is a component of numerous minimization algorithms. This work focuses on developing a method to find the proximal point of a convex function at a point, given an inexact oracle. Our method assumes that exact function values are at hand, but exact subgradients are either not available or not useful. We use approximate subgradients to build a model of the objective function, and prove that the method converges to the true prox-point within acceptable tolerance. The subgradient g _k used at each step k is such that the distance from g _k to the true subdifferential of the objective function at the current iteration point is bounded by some fixed ε > 0. The algorithm includes a novel tilt-correct step applied to the approximate subgradient.     

On automorphisms of distance-regular graphs with intersection arrays {2<Emphasis Type="Italic">r</Emphasis> + 1, 2<Emphasis Type="Italic">r</Emphasis> − 2, 1; 1, 2, 2<Emphasis Type="Italic">r</Emphasis> + 1}

Let Γ be an antipodal graph with intersection array {2r+1, 2r?2, 1; 1, 2, 2r+1}, where 2r(r + 1) ≤ 4096. If 2r + 1 is a prime power, then Mathon’s scheme provides the existence of an arc-transitive graph with this intersection array. Note that 2r + 1 is not a prime power only for r ∈ {7, 17, 19, 22, 25, 27, 31, 32, 37, 38, 42, 43}. We study automorphisms of hypothetical distance-regular graphs with the specified values of r. The cases r ∈ {7, 17, 19} were considered earlier. We prove that, if Γ is a vertex-symmetric graph with intersection array {2r + 1, 2r ? 2, 1; 1, 2, 2r +1}, 2r + 1 is not a prime power, and r ≤ 43, then r = 25, 27, or 31.