Search

Topology optimization problems often support multiple local minima due to a lack of convexity. Typically, gradient-based techniques combined with continuation in model parameters are used to promote convergence to more optimal solutions; however, these methods can fail even in the simplest cases. In this paper, we present an algorithm to perform a systematic exploratory search for the solutions of the optimization problem via second order methods without a good initial guess. The algorithm combines the techniques of deflation, barrier methods, and primal-dual active set solvers in a novel way. We demonstrate this approach on several numerical examples, observe mesh independence in certain cases and show that multiple distinct local minima can be recovered. [ABSTRACT FROM AUTHOR]

This paper presents a recently developed particle simulation code package PIFE-PIC, which is a novel three-dimensional (3-D) parallel immersed finite element (IFE) particle-in-cell (PIC) simulation model for particle simulations of plasma-material interactions. This framework is based on the recently developed nonhomogeneous electrostatic IFE-PIC algorithm, which is designed to handle complex plasma-material interface conditions associated with irregular geometries using a Cartesian mesh-based PIC. Three-dimensional domain decomposition is utilized for both the electrostatic field solver with IFE and the particle operations in PIC to distribute the computation among multiple processors. A simulation of the orbital motion-limited (OML) sheath of a dielectric sphere immersed in a stationary plasma is carried out to validate parallel IFE-PIC and profile the parallel performance of the code package. Furthermore, a large-scale simulation of plasma charging at a lunar crater containing 2 million PIC cells (10 million FE/IFE cells) and about 1 billion particles, running for 20,000 PIC steps in about 154 wall-clock hours, is presented to demonstrate the high-performance computing capability of PIFE-PIC. [ABSTRACT FROM AUTHOR]

In this paper, we address the numerical solution of the optimal transport problem on undirected weighted graphs, taking the shortest path distance as transport cost. The optimal solution is obtained from the long-time limit of the gradient descent dynamics. Among different time stepping procedures for the discretization of this dynamics, a backward Euler time stepping scheme combined with the inexact Newton-Raphson method results in a robust and accurate approach for the solution of the optimal transport problem on graphs. It is found experimentally that the algorithm requires solving between O(1) and O(m0:36) linear systems involving weighted Laplacian matrices, where m is the number of edges. These linear systems are solved via algebraic multigrid methods, resulting in an efficient solver for the optimal transport problem on graphs. [ABSTRACT FROM AUTHOR]

This paper is devoted to the theoretical and numerical study of an optimal design problem in high-temperature superconductivity (HTS). The shape optimization problem is to find an optimal superconductor shape minimizes a certain cost functional under a given target on the electric field over a specific domain of interest. For the governing PDE-model, we consider an elliptic curl-curl variational inequality (VI) of the second kind with an L1-type nonlinearity. In particular, the nonsmooth VI character and the involved H(curl)-structure make the corresponding shape sensitivity analysis challenging. To tackle the nonsmoothness, a penalized dual VI formulation is proposed, leading to the Gateaux differentiability of the corresponding dual variable mapping. This property allows us to derive the distributed shape derivative of the cost functional through rigorous shape calculus on the basis of the averaged adjoint method. The developed shape derivative turns out to be uniformly stable with respect to the penalization parameter, and strong convergence of the penalized problem is guaranteed. Based on the achieved theoretical findings, we propose threedimensional numerical solutions, realized using a level set algorithm and a Newton method with the N\'ed\'elec edge element discretization. Numerical results indicate a favorable and efficient performance of the proposed approach for a specific HTS application in superconducting shielding. [ABSTRACT FROM AUTHOR]

In this paper, we study the quantum learnability of constant-depth classical circuits under the uniform distribution and in the distribution-independent framework of probably approximately correct (PAC) learning. In order to attain our results, we establish connections between quantum learning and quantum-secure cryptosystems. We then achieve the following results. 1. Hardness of PAC learning AC0 and TC0 under the uniform distribution. Our first result concerns the concept class TC0 (resp., AC0), the class of constant-depth, polynomial-sized circuits with unbounded fan-in majority gates (resp., AND, OR, NOT gates). We show the following: if there exists no quantum (quasi-)polynomial-time algorithm to solve the ring-learning with errors (RLWE) problem, then there exists no (quasi-)polynomial-time quantum learning algorithm for TC0; and if there exists no 2O(d1/η)-time quantum algorithm to solve RLWE with dimension d = O(polylogn) (for every constant η > 2), then there exists no O(nlogν n)-time quantum learning algorithm for poly(n)-sized AC0 circuits (for a constant ν > 0), matching the classical upper bound of Linial, Mansour and Nisan [J. ACM, 40 (1993), pp. 607-620], where the learning algorithms are under the uniform distribution (even with access to quantum membership queries). The main technique in these results uses an explicit family of pseudorandom functions that are believed to be quantumsecure to construct concept classes that are hard to learn quantumly under the uniform distribution. 2. Hardness of learning TC20 in the PAC setting. Our second result shows that if there exists no quantum polynomial-time algorithm for the LWE problem, then there exists no polynomial-time quantum-PAC learning algorithm for the class TC20, i.e., depth-2 TC0 circuits. The main technique in this result is to establish a connection between the quantum security of public-key encryption schemes and the learnability of a concept class that consists of decryption functions of the cryptosystem. Our results show that quantum resources do not give an exponential improvement to learning constant-depth polynomial-sized neural networks. This also gives a strong (conditional) negative answer to one of the "Ten Semi-Grand Challenges for Quantum Computing Theory" raised by Aaronson https://www.scottaaronson.com/writings/qchallenge.html, 2005. [ABSTRACT FROM AUTHOR]

In 1988, Vazirani gave an NC algorithm for computing the number of perfect matchings in K3,3-minor-free graphs by building on Kasteleyn's scheme for planar graphs, and stated that this "opens up the possibility of obtaining an NC algorithm for finding a perfect matching in K3,3-free graphs." In this paper, we finally settle this 30-year-old open problem. Building on recent NC algorithms for planar and bounded-genus perfect matching by Anari and Vazirani and later by Sankowski, we obtain NC algorithms for perfect matching in any minor-closed graph family that forbids a one-crossing graph. This family includes several well-studied graph families including the K3,3-minor-free graphs and K5-minor-free graphs. Graphs in these families not only have unbounded genus, but can have genus as high as O(n). Our method applies as well to several other problems related to perfect matching. In particular, we obtain NC algorithms for the following problems in any family of graphs (or networks) with a one-crossing forbidden minor: (1) Determining whether a given graph has a perfect matching and, if so, finding one. (2) Finding a minimum-weight perfect matching in the graph, assuming that the edge weights are polynomially bounded. (3) Finding a maximum st-flow in the network, with arbitrary capacities. The main new idea enabling our results is the definition and use of matching-mimicking networks, small replacement networks that behave the same with respect to matching problems involving a fixed set of terminals, as the larger network they replace. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a stochastic projected subgradient method for weakly convex (i.e., uniformly prox-regular) nonsmooth, nonconvex functions---a wide class of functions which includes the additive and convex composite classes. At a high level, the method is an inexact proximal-point iteration in which the strongly convex proximal subproblems are quickly solved with a specialized stochastic projected subgradient method. The primary contribution of this paper is a simple proof that the proposed algorithm converges at the same rate as the stochastic gradient method for smooth nonconvex problems. This result appears to be the first convergence rate analysis of a stochastic (or even deterministic) subgradient method for the class of weakly convex functions. In addition, a two-phase variant is proposed that significantly reduces the variance of the solutions returned by the algorithm. Finally, preliminary numerical experiments are also provided. [ABSTRACT FROM AUTHOR]

A delay Lyapunov matrix corresponding to an exponentially stable system of linear time-invariant delay differential equations can be characterized as the solution of a boundary value problem involving a matrix valued delay differential equation. This boundary value problem can be seen as a natural generalization of the classical Lyapunov matrix equation. Lyapunov matrices play an important role in constructing Lyapunov functionals and in H2 optimal control. In this paper we present a general approach for computing delay Lyapunov matrices and H2 norms for systems with multiple discrete delays, whose applicability extends toward problems where the matrices are large and sparse, and the associated positive semidefinite matrix has a low rank. The problems addressed are challenging, because the boundary value problem is matrix valued with a structure that is much harder to exploit than in the delay-free case, and its solution is in the generic situation nonsmooth. In contrast to existing methods that are based on solving the boundary value problem directly, our method is grounded in solving standard Lyapunov equations of increased dimensions. It combines several ingredients: (i) a spectral discretization of the system of delay equations, (ii) a targeted similarity transformation which induces a desired structure and sparsity pattern and, at the same time, favors accurate low-rank solutions of the corresponding Lyapunov equation, and (iii) a Krylov method for large-scale matrix Lyapunov equations. The structure of the problem is exploited in such a way that the final algorithm does not involve a preliminary discretization step and provides a fully dynamic construction of approximations of increasing rank. Interpretations are also given in terms of a projection method directly applied to a standard linear infinite-dimensional system, which is equivalent to the original time-delay system. Throughout the paper two didactic examples are used to illustrate the properties of the problem, the challenges and methodological choices, while numerical experiments are reported to illustrate the effectiveness of the algorithms. [ABSTRACT FROM AUTHOR]

This paper is devoted to the construction and analysis of new nonlinear optimal weights for weighted ENO (WENO) interpolation capable of raising the order of accuracy close to discontinuities. The new nonlinear optimal weights are constructed using a strategy inspired by the original WENO algorithm, and they work very well for corner or jump singularities, leading to optimal theoretical accuracy. This is the first part of a series of two papers. In this first part we analyze the performance of the new algorithms proposed for univariate function approximation in the point values (interpolation problem). In the second part, we will extend the analysis to univariate function approximation in the cell averages (reconstruction problem). Our aim is twofold: to raise the order of accuracy of the WENO type interpolation schemes both near discontinuities and in the interval which contains the singularity. The first problem can be solved using the new nonlinear optimal weights, but the second one requires a new strategy that locates the position of the singularity inside the cell in order to attain adaption. This new strategy is inspired by the ENO-SR schemes proposed by Harten [J. Comput. Phys., 83 (1989), pp. 148-184]. Thus, we will introduce two different algorithms in the point values. The first one can deal with corner singularities and jump discontinuities for intervals not containing the singularity. The second algorithm can also deal with intervals containing corner singularities, as they can be detected from the point values, but jump discontinuities cannot, as the information of their position is lost during the discretization process. As mentioned before, the second part of this work will be devoted to the cell averages and, in this context, it will be possible to work with jump discontinuities as well. [ABSTRACT FROM AUTHOR]

The present paper is devoted to queueing systems with regenerative input flow in the presence of heavy tails. Our goal is to develop an asymptotics for the probability of the waiting time process in a stationary regime to exceed a high level. In this paper, we consider the total service time of customers arriving during the time-interval [0, t] as an input flow X(t). This allows us to consider a case when the service times {ηn}∞n=1 are dependent random variables that, besides, may be dependent on a number of customers arriving in [0, t]. We obtain conditions for the virtual waiting time process in steady state to have a subexponential distribution function. We apply this result to a system with a Markov modulated semi-Markov input flow. We also consider a queue with a doubly stochastic Poisson flow in the case when the random intensity is a regenerative process. We show that these results could be transferred to corresponding systems with an unreliable server. [ABSTRACT FROM AUTHOR]

This paper revisits the problem of finding the best rank-1 approximation to a symmetric tensor and makes three contributions. First, in contrast to the many long and lingering arguments in the literature, it offers a straightforward justification that generically the best rank-1 approximation to a symmetric tensor is symmetric. Second, in contrast to the typical workhorse in the practice for the low-rank tensor approximation, namely, the alternating least squares (ALS) technique which improves one factor a time, this paper proposes three alternative algorithms based on the singular value decomposition (SVD) that modifies two factors a time. One step of SVD-based iteration is superior to two steps of ALS iterations. Third, it is not only proved that the generalized Rayleigh quotients generated from the three SVD-based algorithms enjoy monotone convergence, but also that the iterates themselves converge. [ABSTRACT FROM AUTHOR]

With the development of robotics, there are growing needs for real time motion planning. However, due to obstacles in the environment, the planning problem is highly nonconvex, which makes it difficult to achieve real time computation using existing nonconvex optimization algorithms. This paper introduces the convex feasible set algorithm, which is a fast algorithm for nonconvex optimization problems that have convex costs and nonconvex constraints. The idea is to find a convex feasible set for the original problem and iteratively solve a sequence of subproblems using the convex constraints. The feasibility and the convergence of the proposed algorithm are proved in the paper. The application of this method on motion planning for mobile robots is discussed. The simulations demonstrate the effectiveness of the proposed algorithm. [ABSTRACT FROM AUTHOR]

The goal of this paper is to describe the oscillatory microstructure that can emerge from minimizing sequences for nonconvex energies. We consider integral functionals that are defined on real valued (scalar) functions u(x) which are nonconvex in the gradient ∇ u and possibly also in u. To characterize the microstructures for these nonconvex energies, we minimize the associated relaxed energy using two novel approaches: (i) a semianalytical method based on control systems theory, (ii) and a numerical scheme that combines convex splitting together with a modified version of the split Bregman algorithm. These solutions are then used to gain information about minimizing sequences of the original problem and the spatial distribution of microstructure. [ABSTRACT FROM AUTHOR]

This paper aims at developing two versions of the generalized Newton method to compute local minimizers for nonsmooth problems of unconstrained and constrained optimization that satisfy an important stability property known as tilt stability. We start with unconstrained minimization of continuously differentiable cost functions having Lipschitzian gradients and suggest two second-order algorithms of Newton type: one involving coderivatives of Lipschitzian gradient mappings, and the other based on graphical derivatives of the latter. Then we proceed with the propagation of these algorithms to minimization of extended-real-valued prox-regular functions, while covering in this way problems of constrained optimization, by using Moreau envelopes. Employing advanced techniques of second-order variational analysis and characterizations of tilt stability allows us to establish the solvability of subproblems in both algorithms and to prove the Q-superlinear convergence of their iterations. [ABSTRACT FROM AUTHOR]

Multiple-input multiple-output (MIMO) detection is a fundamental problem in wireless communications and it is strongly NP-hard in general. Massive MIMO has been recognized as a key technology in fifth generation (5G) and beyond communication networks, which on one hand can significantly improve the communication performance and on the other hand poses new challenges of solving the corresponding optimization problems due to the large problem size. While various efficient algorithms such as semidefinite relaxation (SDR) based approaches have been proposed for solving the small-scale MIMO detection problem, they are not suitable to solve the large-scale MIMO detection problem due to their high computational complexities. In this paper, we propose an efficient quadratic programming (QP) relaxation based algorithm for solving the large-scale MIMO detection problem. In particular, we first reformulate the MIMO detection problem as a sparse QP problem. By dropping the sparse constraint, the resulting relaxation problem shares the same global minimizer with the sparse QP problem. In sharp contrast to the SDRs for the MIMO detection problem, our relaxation does not contain any (positive semidefinite) matrix variable and the numbers of variables and constraints in our relaxation are significantly less than those in the SDRs, which makes it particularly suitable for the large-scale problem. Then we propose a projected Newton based quadratic penalty method to solve the relaxation problem, which is guaranteed to converge to the vector of transmitted signals under reasonable conditions. By extensive numerical experiments, when applied to solve small-scale problems, the proposed algorithm is demonstrated to be competitive with the state-of-the-art approaches in terms of detection accuracy and solution efficiency; when applied to solve large-scale problems, the proposed algorithm achieves better detection performance than a recently proposed generalized power method. [ABSTRACT FROM AUTHOR]

In this paper, we propose a primal-dual algorithm with a novel momentum term using the partial gradients of the coupling function that can be viewed as a generalization of the method proposed by Chambolle and Pock in 2016 to solve saddle point problems defined by a convex-concave function L(x,y)=f(x)+Φ(x,y)--h(y) with a general coupling term Φ(x,y) that is not assumed to be bilinear. Assuming ∇xΦ(*, y) is Lipschitz for any fixed y, and ∇yΦ(*, *) is Lipschitz, we show that the iterate sequence converges to a saddle point; and for any (x,y), we derive error bounds in terms of ... for the ergodic sequence ... In particular, we show O(1/k) rate when the problem is merely convex in x. Furthermore, assuming Φ(x,*) is linear for each fixed x and f is strongly convex, we obtain the ergodic convergence rate of O(1/k²) -- we are not aware of another single-loop method in the related literature achieving the same rate when Φ is not bilinear. Finally, we propose a backtracking technique which does not require the knowledge of Lipschitz constants while ensuring the same convergence results. We also consider convex optimization problems with nonlinear functional constraints and we show that using the backtracking scheme, the optimal convergence rate can be achieved even when the dual domain is unbounded. We tested our method against other state-of-the-art first-order algorithms and interior-point methods for solving quadratically constrained quadratic problems with synthetic data, the kernel matrix learning, and regression with fairness constraints arising in machine learning. [ABSTRACT FROM AUTHOR]

This paper studies the problem of maximizing the sum of traces of matrix quadratic forms on a product of Stiefel manifolds. This orthogonal trace-sum maximization (OTSM) problem generalizes many interesting problems such as generalized canonical correlation analysis (CCA),Procrustes analysis, and cryo-electron microscopy of the Nobel prize fame. For these applications finding global solutions is highly desirable, but it has been unclear how to find even a stationary point, let alone test its global optimality. Through a close inspection of Ky Fan's classical result [Proc. Natl. Acad. Sci. USA, 35 (1949), pp. 652--655] on the variational formulation of the sum of largest eigenvalues of a symmetric matrix, and a semi definite programming (SDP) relaxation of the latter, we first provide a simple method to certify global optimality of a given stationary point of OTSM. This method only requires testing whether a symmetric matrix is positive semi definite. Aby-product of this analysis is an unexpected strong duality between Shapiro and Botha [SIAM J.Matrix Anal. Appl., 9 (1988), pp. 378--383] and Zhang and Singer [Linear Algebra Appl., 524 (2017),pp. 159--181]. After showing that a popular algorithm for generalized CCA and Procrustes analysis may generate oscillating iterates, we propose a simple fix that provably guarantees convergence to a stationary point. The combination of our algorithm and certificate reveals novel global optima of various instances of OTSM. [ABSTRACT FROM AUTHOR]

The eigensystem realization algorithm (ERA) is a data-driven approach for subspacesystem identification and is widely used in many areas of engineering. However, the computationalcost of the ERA is dominated by a step that involves the singular value decomposition (SVD) ofa large, dense matrix with block Hankel structure. This paper develops computationally efficientalgorithms for reducing the computational cost of the SVD step by using randomized subspaceiteration and exploiting the block Hankel structure of the matrix. We provide a detailed analysis ofthe error in the identified system matrices and the computational cost of the proposed algorithms.We demonstrate the accuracy and computational benefits of our algorithms on two test problems:the first involves a partial differential equation that models the cooling of steel rails, and the secondis an application from power systems engineering. [ABSTRACT FROM AUTHOR]

We consider a classical k-center problem in trees. Let T be a tree of n vertices such that every vertex has a nonnegative weight. The problem is to find k centers on the edges of T such that the maximum weighted distance from all vertices to their closest centers is minimized. Megiddo and Tamir [SIAM J. Comput., 12 (1983), pp. 751-758] gave an algorithm that can solve the problem in O(n log²n) time by using Cole's parametric search. Since then it has been open for over three decades whether the problem can be solved in O(n log n) time. In this paper, we present an O(n log n) time algorithm for the problem and thus settle the open problem affirmatively. [ABSTRACT FROM AUTHOR]

Let G = (V, E) be a weighted graph or multigraph, with f or b a function assigning a nonnegative integer to each vertex. An f-factor is a subgraph whose degree function is f; a perfect b-matching is a b-factor in the graph formed from G by adding an unlimited number of copies of each edge. This two-part paper culminates in an efficient algebraic algorithm to find a maximum f-factor, i.e., f-factor with maximum weight. Along the way it presents simpler special cases of interest. Part II presents the maximum f-factor algorithm and the special case of shortest paths in conservative undirected graphs (negative edges allowed). Part I presents these results: An algebraic algorithm for maximum b-matching, i.e., maximum weight b-matching. It is almost identical to its special case b ≡ 1, ordinary weighted matching. The time is O(Wb(V)ω) for W the maximum magnitude of an edge weight, b(V) = ∑v∈V b(v), and ω < 2:373 the exponent of matrix multiplication. An algebraic algorithm to find an f-factor. The time is O(f(V)ω) for f(V ) = ∑v∈V f(v). The specialization of the f-factor algorithm to bipartite graphs and its extension to maximum/minimum bipartite f-factors. This improves the known complexity bounds for vertex capacitated max- ow and min-cost max-flow on a subclass of graphs. Each algorithm is randomized and has two versions achieving the above time bound: For worst-case time the algorithm is correct with high probability. For expected time the algorithm is Las Vegas. [ABSTRACT FROM AUTHOR]

Tropical geometry has been recently used to obtain new complexity results in convex optimization and game theory. In this paper, we present an application of this approach to a famous class of algorithms for linear programming, i.e., log-barrier interior point methods. We show that these methods are not strongly polynomial by constructing a family of linear programs with 3r + 1 inequalities in dimension 2r for which the number of iterations performed is in Ω(2r). The total curvature of the central path of these linear programs is also exponential in r, disproving a continuous analogue of the Hirsch conjecture proposed by Deza, Terlaky, and Zinchenko. These results are obtained by analyzing the tropical central path, which is the piecewise linear limit of the central paths of parameterized families of classical linear programs viewed through "logarithmic glasses." This allows us to provide combinatorial lower bounds for the number of iterations and the total curvature in a general setting. [ABSTRACT FROM AUTHOR]

We consider a linear problem over a finite set of integer vectors and assume that there is a verification oracle, which is an algorithm being able to verify whether a given vector optimizes a given linear function over the feasible set. Given an initial solution, the algorithm proposed in this paper finds an optimal solution of the problem together with a path, in the 1-skeleton of the convex hull of the feasible set, from the initial solution to the optimal solution found. The length of this path is bounded by the sum of distinct values which can be taken by the components of feasible solutions, minus the dimension of the problem. In particular, in the case when the feasible set is a set of binary vectors, the length of the constructed path is bounded by the number of variables, independently of the objective function. [ABSTRACT FROM AUTHOR]

In this paper, we address the problem of maximizing the Steklov eigenvalues with a diameter constraint. We provide an estimate of the Steklov eigenvalues for a convex domain in terms of its diameter and volume, and we show the existence of an optimal convex domain. We establish that balls are never maximizers, even for the first nontrivial eigenvalue that contrasts with the case of volume or perimeter constraints. Under an additional regularity assumption, we are able to prove that the Steklov eigenvalue is multiple for the optimal domain. We illustrate our theoretical results by giving some optimal domains in the plane thanks to a numerical algorithm. [ABSTRACT FROM AUTHOR]

Clustering is one of the fundamental tasks in data analytics and machine learning. In many situations, dierent clusterings of the same data set become relevant. For example, different algorithms for the same clustering task may return dramatically different solutions. We are interested in applications in which one clustering has to be transformed into another, e.g., when a gradual transition from an old solution to a new one is required. In this paper, we devise methods for constructing such a transition based on linear programming and network theory. We use a so-called clustering-difference graph to model the desired transformation and provide methods for decomposing the graph into a sequence of elementary moves that accomplishes the transformation. These moves are equivalent to the edge directions, or circuits, of the underlying partition polytopes. Therefore, in addition to a conceptually new metric for measuring the distance between clusterings, we provide new bounds on the circuit diameter of these partition polytopes. [ABSTRACT FROM AUTHOR]

Submodularity is one of the most important properties in combinatorial optimization, and k-submodularity is a generalization of submodularity. Maximization of a k-submodular function requires an exponential number of value oracle queries, and approximation algorithms have been studied. For unconstrained k-submodular maximization, Iwata, Tanigawa, and Yoshida, [Improved approximation algorithms for k-submodular function maximization, in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2016, pp. 404-413] gave a randomized k/(2k 1)-approximation algorithm for monotone functions and a randomized 1/2-approximation algorithm for nonmonotone functions. In this paper, we present improved randomized algorithms for nonmonotone functions. Our algorithm gives a k2+1 2k2+1 -approximation for k geq 3. We also give a randomized surd 17 3 2 -approximation algorithm for k = 3. We use the same framework used in Iwata, Tanigawa, and Yoshida, [Improved approximation algorithms for k-submodular function maximization, in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2016, pp. 404--413] and Ward and v Zivn'y [ACM Trans. Algorithms, 12 (2016), pp. 46:1--47:26] with different probabilities. [ABSTRACT FROM AUTHOR]

Reduced model spaces, such as reduced bases and polynomial chaos, are linear spaces Vn of finite dimension n which are designed for the efficient approximation of certain families of parametrized PDEs in a Hilbert space V. The manifold M that gathers the solutions of the PDE for all admissible parameter values is globally approximated by the space Vn with some controlled accuracy εn, which is typically much smaller than when using standard approximation spaces of the same dimension such as finite elements. Reduced model spaces have also been proposed in [Y. Maday et al., Internat. J. Numer. Methods Ergrg., 102 (2015), pp. 933-965] as a vehicle to design a simple linear recovery algorithm of the state u ∈ M corresponding to a particular solution instance when the values of parameters are unknown but a set of data is given by m linear measurements of the state. The measurements are of the form ℓj(u), j = 1, ..., m, where the ℓj are linear functionals on V. The analysis of this approach in [P. Binev et al., SIAM/ASA J. Uncertain. Quantif., 5 (2017), pp. 1-29] shows that the recovery error is bounded by μnεn, where μn = μ(Vn, W) is the inverse of an inf-sup constant that describe the angle between Vn and the space W spanned by the Riesz representers of (ℓ1, ..., ℓm). A reduced model space which is efficient for approximation might thus be ineffective for recovery if μn is large or infinite. In this paper, we discuss the existence and effective construction of an optimal reduced model space for this recovery method. We extend our search to affine spaces which are better adapted than linear spaces for various purposes. Our basic observation is that this problem is equivalent to the search of an optimal affine algorithm for the recovery of M in the worst case error sense. This allows us to perform our search by a convex optimization procedure. Numerical tests illustrate that the reduced model spaces constructed from our approach perform better than the classical reduced basis spaces. [ABSTRACT FROM AUTHOR]

This paper proposes a parallel domain decomposition Rayleigh--Ritz projection scheme to compute a selected number of eigenvalues (and, optionally, associated eigenvectors) of large and sparse symmetric pencils. The projection subspace associated with interface variables is built by computing a few of the eigenvectors and associated leading derivatives of a zeroth-order approximation of the nonlinear matrix-valued interface operator. On the other hand, the projection subspace associated with interior variables is built independently in each subdomain by exploiting local eigenmodes and matrix resolvent approximations. The sought eigenpairs are then approximated by a Rayleigh--Ritz projection onto the subspace formed by the union of these two subspaces. Several theoretical and practical details are discussed, and upper bounds of the approximation errors are provided. Our numerical experiments demonstrate the efficiency of the proposed technique on sequential/distributed memory architectures as well as its competitiveness against schemes such as shift-and-invert Lanczos and automated multilevel substructuring combined with p-way vertex-based partitionings. [ABSTRACT FROM AUTHOR]

Randomized iterative algorithms have recently been proposed to solve large-scale linear systems. In this paper, we present a simple randomized extended average block Kaczmarz algorithm that exponentially converges in the mean square to the unique minimum norm least squares solution of a given linear system of equations. The proposed algorithm is pseudoinversefree and therefore different from the projection-based randomized double block Kaczmarz algorithm of Needell, Zhao, and Zouzias [Linear Algebra Appl., 484 (2015), pp. 322--343]. We emphasize that our method works for all types of linear systems (consistent or inconsistent, overdetermined or underdetermined, full-rank or rank-deficient). Moreover, our approach can be implemented for parallel computation, yielding remarkable improvements in computational time. Numerical examples are given to show the efficiency of the new algorithm. [ABSTRACT FROM AUTHOR]

This paper generalizes the optimized gradient method (OGM) [Y. Drori and M. Teboulle, Math. Program., 145 (2014), pp. 451-482], [D. Kim and J. A. Fessler, Math. Program., 159 (2016), pp. 81-107], [D. Kim and J. A. Fessler, J. Optim. Theory Appl., 172 (2017), pp. 187-205] that achieves the optimal worst-case cost function bound of first-order methods for smooth convex minimization [Y. Drori, J. Complexity, 39 (2017), pp. 1-16]. Specifically, this paper studies a generalized formulation of OGM and analyzes its worst-case rates in terms of both the function value and the norm of the function gradient. This paper also develops a new algorithm called OGM-OG that is in the generalized family of OGM and that has the best known analytical worst-case bound with rate O(1/N1.5) on the decrease of the gradient norm among fixed-step first-order methods. This paper also proves that Nesterov's fast gradient method [Y. Nesterov, Dokl. Akad. Nauk. USSR, 269 (1983), pp. 543-547], [Y. Nesterov, Math. Program., 103 (2005), pp. 127-152] has an O(1/N1.5) worst-case gradient norm rate but with constant larger than OGM-OG. The proof is based on the worst-case analysis called the Performance Estimation Problem in [Y. Drori and M. Teboulle, Math. Program., 145 (2014), pp. 451-482]. [ABSTRACT FROM AUTHOR]

There has been much recent interest in finding unconstrained local minima of smooth functions, due in part to the prevalence of such problems in machine learning and robust statistics. A particular focus is algorithms with good complexity guarantees. Second-order Newton-type methods that make use of regularization and trust regions have been analyzed from such a perspective. More recent proposals, based chiey on first-order methodology, have also been shown to enjoy optimal iteration complexity rates, while providing additional guarantees on computational cost. In this paper, we present an algorithm with favorable complexity properties that differs in two significant ways from other recently proposed methods. First, it is based on line searches only: Each step involves computation of a search direction, followed by a backtracking line search along that direction. Second, its analysis is rather straightforward, relying for the most part on the standard technique for demonstrating sufficient decrease in the objective from backtracking. In the latter part of the paper, we consider inexact computation of the search directions, using iterative methods in linear algebra: the conjugate gradient and Lanczos methods. We derive modified convergence and complexity results for these more practical methods. [ABSTRACT FROM AUTHOR]

A framework, PhaseLift, was recently proposed to solve the phase retrieval problem. In this framework, the problem is solved by optimizing a cost function over the set of complex Hermitian positive semidefinite matrices. This approach to phase retrieval motivates a more general consideration of optimizing cost functions on semidefinite Hermitian matrices where the desired minimizers are known to have low rank. This paper considers an approach based on an alternative cost function defined on a union of appropriate manifolds. It is related to the original cost function in a manner that preserves the ability to find a global minimizer and is significantly more efficient computationally. A rank-based optimality condition for stationary points is given and optimization algorithms based on state-of-the-art Riemannian optimization and dynamically reducing rank are proposed. Empirical evaluations are performed using the PhaseLift problem. The new approach is shown to be an effective method of phase retrieval with computational efficiency increased substantially compared to a state-of-the-art algorithm, the Wirtinger flow algorithm. A preliminary version of this paper can be found in [W. Huang, K. A. Gallivan, and X. Zhang, Procedia Comput. Sci., 80 (2016), pp. 1125-1134]. [ABSTRACT FROM AUTHOR]

A monotone drawing of a graph G is a straight-line drawing of G such that, for every pair of vertices u,w in G, there exists a path Puw in G that is monotone in some direction luw. (Namely, the order of the orthogonal projections of the vertices of Puw on luw is the same as the order in which they appear in Puw.) The problem of finding monotone drawings for trees has been studied in several recent papers. The main focus is to reduce the size of the drawing. Currently, the smallest drawing size is O(n log n) × O(n log n). In this paper, we present an algorithm for constructing monotone drawings of trees on a grid of size at most 12n × 12n. The smaller drawing size is achieved by a procedure that carefully assigns primitive vectors to the paths of the input tree T. We also show that there exists a tree T0 such that any monotone drawing of T0 must use a grid of size at least n/9 × n/9. So the size of our monotone drawings is asymptotically optimal. [ABSTRACT FROM AUTHOR]

Assume that we are given a set of applicants and a set of posts such that each applicant has a preference list over the posts. A matching M between the applicants and the posts is said to be popular if there is no other matching N such that the number of applicants that prefer N to M is larger than the number of applicants that prefer M to N. Then, the goal of the popular matching problem is to decide whether there is a popular matching, and nd a popular matching if one exists. Abraham, Irving, Kavitha, and Mehlhorn proved that this problem can be solved in polynomial time even if the preference lists contain ties. In this paper, we consider the popular matching problem with matroid constraints. In this problem, for each post, we are given a matroid on the set of applicants. A set of applicants assigned to each post must be an independent set of its matroid. Kamiyama proved that if there is not a tie in the preference lists, then this problem can be solved in polynomial time. In this paper, we prove that even if there are ties in the preference lists, this problem can be solved in polynomial time. [ABSTRACT FROM AUTHOR]

This paper is a sequel to a paper entitled Variations on the sum-product problem by the same authors [SIAM J. Discrete Math., 29 (2015), pp. 514{540]. In this sequel, we quantitatively improve several of the main results of the rst paper as well as generalize a method from it to give a near-optimal bound for a new expander. The main new results are the following bounds, which hold for any finite set A ⊂ ℝ: Ǝa ∈ A such that ∣A(A + a)∣ ≳ ∣A∣3/2+1/186, ∣A(A - A)∣ ≳ ∣A∣3/2+1/34, ∣A(A + A)∣ ≳ ∣A∣ 3/2+5/242, ∣{(a1 + a2 + a3 + a4)² + log a5 : ai ∈ A}∣ ⪢ ∣A∣²/log ∣A∣. [ABSTRACT FROM AUTHOR]

In this paper, we propose two novel non-stationary first-order primal-dual algorithms to solve non-smooth composite convex optimization problems. Unlike existing primal-dual schemes where the parameters are often fixed, our methods use predefined and dynamic sequences for parameters. We prove that our first algorithm can achieve an O(1/k) convergence rate on the primal-dual gap, and primal and dual objective residuals, where k is the iteration counter. Our rate is on the non-ergodic (i.e., the last iterate) sequence of the primal problem and on the ergodic (i.e., the averaging) sequence of the dual problem, which we call the semi-ergodic rate. By modifying the step-size update rule, this rate can be boosted even faster on the primal objective residual. When the problem is strongly convex, we develop a second primal-dual algorithm that exhibits an O(1/k²) convergence rate on the same three types of guarantees. Again by modifying the step-size update rule, this rate becomes faster on the primal objective residual. Our primal-dual algorithms are the first ones to achieve such fast convergence rate guarantees under mild assumptions compared to existing works, to the best of our knowledge. As byproducts, we apply our algorithms to solve constrained convex optimization problems and prove the same convergence rates on both the objective residuals and the feasibility violation. We still obtain at least O(1/k²) rates even when the problem is "semi-strongly" convex. We verify our theoretical results via two well-known numerical examples. [ABSTRACT FROM AUTHOR]

A quadratically constrained quadratic program (QCQP) is an optimization problem in which the objective function is a quadratic function and the feasible region is defined by quadratic constraints. Solving nonconvex QCQP to global optimality is a well-known NP-hard problem and a traditional approach is to use convex relaxations and branch-and-bound algorithms. This paper makes a contribution in this direction by showing that the exact convex hull of a general quadratic equation intersected with any bounded polyhedron is second-order cone representable. We present a simple constructive proof and some preliminary applications of this result. [ABSTRACT FROM AUTHOR]

In this paper we consider the unconstrained minimization problem of a smooth function in ℝn in a setting where only function evaluations are possible. We design a novel randomized derivative-free algorithm--the stochastic three points (STP) method-and analyze its iteration complexity. At each iteration, STP generates a random search direction according to a certain fixed probability law. Our assumptions on this law are very mild: roughly speaking, all laws which do not concentrate all measures on any halfspace passing through the origin will work. For instance, we allow for the uniform distribution on the sphere and also distributions that concentrate all measures on a positive spanning set. Although our approach is designed to not explicitly use derivatives, it covers some first order methods. For instance, if the probability law is chosen to be the Dirac distribution concentrated on the sign of the gradient, then STP recovers the signed gradient descent method. If the probability law is the uniform distribution on the coordinates of the gradient, then STP recovers the randomized coordinate descent method. The complexity of STP depends on the probability law via a simple characteristic closely related to the cosine measure which is used in the analysis of deterministic direct search (DDS) methods. Unlike in DDS, where O(n) (n is the dimension of x) function evaluations must be performed in each iteration in the worst case, our method only requires two new function evaluations per iteration. Consequently, while the complexity of DDS depends quadratically on n, our method depends linearly on n. [ABSTRACT FROM AUTHOR]

We study the iteration complexity of the optimistic gradient descent-ascent (OGDA) method and the extragradient (EG) method for finding a saddle point of a convex-concave unconstrained min-max problem. To do so, we first show that both OGDA and EG can be interpreted as approximate variants of the proximal point method. This is similar to the approach taken in (A. Nemirovski (2004), SIAM J. Optim., 15, pp. 229-251) which analyzes EG as an approximation of the "conceptual mirror prox." In this paper, we highlight how gradients used in OGDA and EG try to approximate the gradient of the proximal point method. We then exploit this interpretation to show that both algorithms produce iterates that remain within a bounded set. We further show that the primal-dual gap of the averaged iterates generated by both of these algorithms converge with a rate of O(1/k). Our theoretical analysis is of interest as it provides the first convergence rate estimate for OGDA in the general convex-concave setting. Moreover, it provides a simple convergence analysis for the EG algorithm in terms of function value without using a compactness assumption. [ABSTRACT FROM AUTHOR]

We consider the problem of realizable interval sequences. An interval sequence is comprised of n integer intervals [ai, bi] such that 0 leq ai leq bi leq n 1 and is said to be graphic/realizable if there exists a graph with degree sequence, say, D = (d1, . . ., dn), satisfying the condition ai leq di leq bi for each i\in [1, n]. There is a characterization (also implying an O(n) verifying algorithm) known for realizability of interval sequences, which is a generalization of the ErdH os--Gallai characterization for graphic sequences. However, given any realizable interval sequence, there is no known algorithm for computing a corresponding graphic certificate in o(n2) time. In this paper, we provide an O(n log n) time algorithm for computing a graphic sequence for any realizable interval sequence. In addition, when the interval sequence is nonrealizable, we show how to find a graphic sequence having minimum deviation with respect to the given interval sequence in the same time. Finally, we consider variants of the problem, such as computing the most-regular graphic sequence and computing a minimum extension of a length p nongraphic sequence to a graphic one. [ABSTRACT FROM AUTHOR]

In this paper, we present a novel numerical method that redistributes unevenly given points on an evolving closed curve to satisfy equi-arclength(-like) condition. Without substantial difficulty, it is also capable of remeshing or employing adaptive mesh refinement. The key idea is to find the discrete inverse of the arclength(-like) function in the framework of the Fourier spectral method to obtain overall spectral accuracy. Both equi-arclength and curvature-dependent redistributions are extensively studied, and their spectral accuracy is verified by application to smoothly perturbed points on various curves. We further confirm that our method converges even for the points being perturbed nonsmoothly and randomly. To leverage the robustness of our method, a remeshing technique is applied in which the accuracy is not affected. Application to a periodic planar curve without any modification of our algorithm is also discussed. Then, to show the practical applicability, an evolving curve with large deformation is studied by coupling with point redistribution and remeshing in various flows such as mean curvature flow, Willmore flow, and Stokes flow. [ABSTRACT FROM AUTHOR]

This paper explores the design problem of consensus algorithms in a class of convex geometric metric spaces. Using the techniques of convex analysis and possibility analysis, a simple assumption for designing consensus algorithms in a strict max-convex space is proposed, under which all dynamical points in a system achieve consensus asymptotically if and only if their associated interaction graph uniformly contains at least one directed spanning tree. Three efficient consensus algorithms under the assumption are presented, and their applications are demonstrated together with efficiency studies. [ABSTRACT FROM AUTHOR]

We consider questions that arise from the intersection between the areas of polynomial-time approximation algorithms, subexponential-time algorithms, and fixed-parameter tractable (FPT) algorithms. The questions, which have been asked several times, are whether there is a nontrivial FPT-approximation algorithm for the Maximum Clique (Clique) and Minimum Dominating Set (DomSet) problems parameterized by the size of the optimal solution. In particular, letting OPT be the optimum and N be the size of the input, is there an algorithm that runs in t(OPT)poly(N) time and outputs a solution of size f(OPT) for any computable functions t and f that are independent of N (for Clique, we want f (OPT) = omega(1))? In this paper, we show that both Clique and DomSet admit no nontrivial FPT-approximation algorithm, i.e., there is no o(OPT)-FPT-approximation algorithm for Clique and no f (OPT)-FPT-approximation algorithm for DomSet for any function f. In fact, our results imply something even stronger: The best way to solve Clique and DomSet, even approximately, is to essentially enumerate all possibilities. Our results hold under the Gap Exponential Time Hypothesis [I. Dinur. ECCC, TR16-128, 2016; P. Manurangsi and P. Raghavendra, preprint, arXiv:1607.02986, 2016], which states that no 2(o(n))-time algorithm can distinguish between a satisfiable 3 SAT formula and one which is not even (1 - epsilon)-satisfiable for some constant epsilon > 0. Besides Clique and DomSet, we also rule out nontrivial FPT-approximation for the Maximum Biclique problem, the problem of finding maximum subgraphs with hereditary properties (e.g., Maximum Induced Planar Subgraph), and Maximum Induced Matching in bipartite graphs, and we rule out the k(o(1))-FPT-approximation algorithm for the Densest k-Subgraph problem. [ABSTRACT FROM AUTHOR]

We consider the problem of optimizing an unknown function over a multidimensional continuous domain, where function evaluation is noisy and expensive. We assume that a globally accurate model of the function is not available, but there exist some parametric models that can well approximate the function in local regions. In this paper, we propose an algorithm in the optimal learning framework that learns the shape of the function and finds the optimal design with a limited number of measurements. We construct belief functions using a radial basis function--based local approximation technique, and use the knowledge gradient policy to decide where to measure, aiming at maximizing the value of information from each measurement. Experiments on both synthetic test problems and a real materials science application show the strong performance of our algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we study active set identification results for the away-step Frank--Wolfe algorithm in different settings. We first prove a local identification property that we apply, in combination with a convergence hypothesis, to get an active set identification result. We then prove, for nonconvex objectives, a novel O() convergence rate result and active set identification for different step sizes (under suitable assumptions on the set of stationary points). By exploiting those results, we also give explicit active set complexity bounds for both strongly convex and nonconvex objectives. While we initially consider the probability simplex as feasible set, in an appendix we show how to adapt some of our results to generic polytopes. [ABSTRACT FROM AUTHOR]

The Douglas{Rachford algorithm (DRA) is a powerful optimization method for minimizing the sum of two convex (not necessarily smooth) functions. The vast majority of previous research dealt with the case when the sum has at least one minimizer. In the absence of minimizers, it was recently shown that for the case of two indicator functions, the DRA converges to a best approximation solution. In this paper, we present a new convergence result on the DRA applied to the problem of minimizing a convex function subject to a linear constraint. Indeed, a normal solution may be found even when the domain of the objective function and the linear subspace constraint have no point in common. As an important application, a new parallel splitting result is provided. We also illustrate our results through various examples. [ABSTRACT FROM AUTHOR]

This paper studies the class of two-stage stochastic programs with a linearly biparameterized recourse function defined by a convex quadratic program. A distinguishing feature of this new class of nonconvex stochastic programs is that the objective function in the second stage is linearly parameterized by the first-stage decision variable, in addition to the standard linear parameterization in the constraints. While a recent result has established that the resulting recourse function is of the difference-of-convex (dc) kind, the associated dc decomposition of the recourse function does not provide an easy way to compute a directional stationary solution of the two-stage stochastic program. Based on an implicit convex-concave property of the bi-parameterized recourse function, we introduce the concept of a generalized critical point of such a recourse function and provide a sufficient condition for such a point to be a directional stationary point of the stochastic program. We describe an iterative algorithm that combines regularization, convexification, and sampling and establish the subsequential convergence of the algorithm to a generalized critical point, with probability 1. [ABSTRACT FROM AUTHOR]

Undirected graphical models have been especially popular for learning the conditional independence structure among a large number of variables where the observations are drawn independently and identically from the same distribution. However, many modern statistical problems would involve categorical data or time-varying data, which might follow different but related underlying distributions. In order to learn a collection of related graphical models simultaneously, various joint graphical models inducing sparsity in graphs and similarity across graphs have been proposed. In this paper, we aim to propose an implementable proximal point dual Newton algorithm (PPDNA) for solving the group graphical Lasso model, which encourages a shared pattern of sparsity across graphs. Though the group graphical Lasso regularizer is nonpolyhedral, the asymptotic superlinear convergence of our proposed method PPDNA can be obtained by leveraging on the local Lipschitz continuity of the Karush--Kuhn--Tucker solution mapping associated with the group graphical Lasso model. A variety of numerical experiments on real data sets illustrates that the PPDNA for solving the group graphical Lasso model can be highly efficient and robust. [ABSTRACT FROM AUTHOR]

This paper initiates the study of the classic balanced graph partitioning problem from an online perspective: Given an arbitrary sequence of pairwise communication requests between n nodes, with patterns that may change over time, the objective is to service these requests efficiently by partitioning the nodes into L clusters, each of size k, such that frequently communicating nodes are located in the same cluster. The partitioning can be updated dynamically by migrating nodes between clusters. The goal is to devise online algorithms which jointly minimize the amount of intercluster communication and migration cost. The problem features interesting connections to other well-known online problems. For example, scenarios with L = 2 generalize online paging, and scenarios with k = 2 constitute a novel online variant of maximum matching. We present several lower bounds and algorithms for settings both with and without cluster-size augmentation. In particular, we prove that any deterministic online algorithm has a competitive ratio of at least k, even with significant augmentation. Our main algorithmic contributions are an O(k log k)-competitive deterministic algorithm for the general setting with constant augmentation and a constant competitive algorithm for the maximum matching variant. [ABSTRACT FROM AUTHOR]

In this paper we consider one of the most basic scheduling problems where jobs have their respective arrival times and deadlines. The goal is to schedule as many jobs as possible nonpreemptively by their respective deadlines on m identical parallel machines. For the last decade, the best approximation ratio known for the single-machine case (m = 1) has been 1 - 1/e-∈ ≈ 0.632 due to Chuzhoy, Ostrovsky, and Rabani [FOCS 2001] and [MOR 2006]. We break this barrier and give an improved 0.644-approximation. For the multiple-machine case, we give an algorithm whose approximation guarantee becomes arbitrarily close to 1 as the number of machines increases. This improves upon the previous best 1 - 1/(1+1/m)m approximation due to Bar-Noy et al. [STOC 1999] and [SICOMP 2009], which converges to 1 - 1/e as m goes to infinity. Our result for the multiple-machine case extends to the weighted throughput objective where jobs have different weights, and the goal is to schedule jobs with the maximum total weight. Our results show that the 1 - 1/e approximation factor widely observed in various coverage problems is not tight for the nonpreemptive maximum throughput scheduling problem. [ABSTRACT FROM AUTHOR]

Optimal control problems are inherently hard to solve as the optimization must be performed simultaneously with updating the underlying system. Starting from an initial guess, Howard's policy improvement algorithm separates the step of updating the trajectory of the dynamical system from the optimization and iterations of this should converge to the optimal control. In the discrete space-time setting this is often the case and even rates of convergence are known. In the continuous space-time setting of controlled diffusion the algorithm consists of solving a linear PDE followed by a maximization problem. This has been shown to converge; in some situations, however, no global rate is known. The first main contribution of this paper is to establish global rate of convergence for the policy improvement algorithm and a variant, called here the gradient iteration algorithm. The second main contribution is the proof of stability of the algorithms under perturbations to both the accuracy of the linear PDE solution and the accuracy of the maximization step. The proof technique is new in this context as it uses the theory of backward stochastic differential equations. [ABSTRACT FROM AUTHOR]