A strong bound on the integral of the central path curvature and its relationship with the iteration-complexity of primal-dual path-following LP algorithms

The main goals of this paper are to: i) relate two iteration-complexity bounds derived for the Mizuno-Todd-Ye predictor-corrector (MTY P-C) algorithm for linear programming (LP), and; ii) study the geometrical structure of the LP central path. The first iteration-complexity bound for the MTY P-C algorithm considered in this paper is expressed in terms of the integral of a certain curvature function over the traversed portion of the central path. The second iteration-complexity bound, derived recently by the authors using the notion of crossover events introduced by Vavasis and Ye, is expressed in terms of a scale-invariant condition number associated with m × n constraint matrix of the LP. In this paper, we establish a relationship between these bounds by showing that the first one can be majorized by the second one. We also establish a geometric result about the central path which gives a rigorous justification based on the curvature of the central path of a claim made by Vavasis and Ye, in view of the behavior of their layered least squares path following LP method, that the central path consists of long but straight continuous parts while the remaining curved part is relatively “short”. R. D. C. Monteiro was supported in part by NSF Grants CCR-0203113 and CCF-0430644 and ONR grant N00014-05-1-0183. T. Tsuchiya was supported in part by Japan-US Joint Research Projects of Japan Society for the Promotion of Science “Algorithms for linear programs over symmetric cones” and the Grants-in-Aid for Scientific Research (C) 15510144 of Japan Society for the Promotion of Science.     

On the Number of Topological Types Occurring in a Parameterized Family of Arrangements

Let be an o-minimal structure over ℝ, a closed definable set, and

Distributed mirror descent method for saddle point problems over directed graphs

In this article, we consider a mini‐max multi‐agent optimization problem where multiple agents cooperatively optimize a sum of local convex–concave functions, each of which is available to one specific agent in a network. To solve the problem, we propose a distributed optimization method by extending classical mirror descent algorithms to the distributed setting. We obtain the convergence of the algorithm under wild conditions that the agent communication follows a directed graph and the related weighted matrices are row stochastic. In particular, when the weighted matrices are restricted to be doubly stochastic, we provide the explicit convergence rate of the algorithm by choosing the stepsize in a suitable way. The proposed algorithm can be viewed as a generalization of the subgradient projection methods since it utilizes a customized Bregman divergence instead of the usual Euclidean squared distance. Finally, some simulation results on a matrix game are presented to illustrate the performance of the algorithm. © 2016 Wiley Periodicals, Inc. Complexity 21: 178–190, 2016     

Quiz games as a model for information hiding

We present a general computation model inspired in the notion of information hiding in software engineering. This model has the form of a game which we call quiz game. It allows in a uniform way to prove exponential lower bounds for several complexity problems.     

Easy and hard instances of arc ranking in directed graphs

In this paper we deal with the arc ranking problem of directed graphs. We give some classes of graphs for which the arc ranking problem is polynomially solvable. We prove that deciding whether , where G is an acyclic orientation of a 3-partite graph is an NP-complete problem. In this way we answer an open question stated by Kratochvil and Tuza in 1999.     

A new exclusion test for finding the global minimum

Exclusion algorithms have been used recently to find all solutions of a system of nonlinear equations or to find the global minimum of a function over a compact domain. These algorithms are based on a minimization condition that can be applied to each cell in the domain. In this paper, we consider Lipschitz functions of order α and give a new minimization condition for the exclusion algorithm. Furthermore, convergence and complexity results are presented for such algorithm.     

求鳞状因子循环矩阵的逆阵及广义逆阵的快速付氏变换法

借助快速付立叶变换(FFT),本文给出一种求n阶鳞状因子循环矩阵的逆阵、自反g-逆、群逆、Moore-Penrose逆的快速算法,该算法的计算复杂性为O(nlog2n),最后给出的两个数值算例表明了该算法的有效性.