We propose a new selection rule for the coordinate selection in coordinate descent methods for huge-scale optimization. The efficiency of this novel scheme is provably better than the efficiency of uniformly random selection, and can reach the efficiency of steepest coordinate descent (SCD), enabling an acceleration of a factor of up to $n$, the number of coordinates. In many practical applications, our scheme can be implemented at no extra cost and computational efficiency very close to the faster uniform selection. Numerical experiments with Lasso and Ridge regression show promising improvements, in line with our theoretical guarantees.

Jun 27 2017

math.OC arXiv:1706.08150v1

This paper is concerned with two-person dynamic zero-sum games. Let games for some family have common dynamics, running costs and capabilities of players, and let these games differ in densities only. We show that the Dynamic Programming Principle directly leads to the General Tauberian Theorem---that the existence of a uniform limit of the value functions for uniform distribution or for exponential distribution implies that the value functions uniformly converge to the same limit for arbitrary distribution from large class. No assumptions on strategies are necessary.

Jun 27 2017

math.OC arXiv:1706.08483v1

Newton's method for finding an unconstrained minimizer for strictly convex functions, generally speaking, does not converge from any starting point. We introduce and study the damped regularized Newton's method (DRNM). It converges globally for any strictly convex function, which has a minimizer in $R^n$. Locally DRNM converges with a quadratic rate. We characterize the neighborhood of the minimizer, where the quadratic rate occurs. Based on it we estimate the number of DRNM's steps required for finding an $\varepsilon$- approximation for the minimizer.

Kaczmarz method is one popular iterative method for solving inverse problems, especially in computed tomography. Recently, it was established that a randomized version of the method enjoys an exponential convergence for well-posed problems, and the convergence rate is determined by a variant of the condition number. In this work, we analyze the preasymptotic convergence behavior of the randomized Kaczmarz method, and show that the low-frequency error (with respect to the right singular vectors) decays faster during first iterations than the high-frequency error. Under the assumption that the inverse solution is smooth (e.g., sourcewise representation), the result explains the fast empirical convergence behavior, thereby shedding new insights into the excellent performance of the randomized Kaczmarz method in practice. Further, we propose a simple strategy to stabilize the asymptotic convergence of the iteration by means of variance reduction. We provide extensive numerical experiments to confirm the analysis and to elucidate the behavior of the algorithms.

Jun 27 2017

math.OC arXiv:1706.08438v1

Speakman and Lee analytically developed the idea of using volume as a measure for comparing relaxations in the context of spatial branch-and-bound. Specifically, for trilinear monomials, they analytically compared the three possible "double-McCormick relaxations" with the tight convex-hull relaxation. Here, again using volume as a measure, for the convex-hull relaxation of trilinear monomials, we establish simple rules for determining the optimal branching variable and optimal branching point. Additionally, we compare our results with current practice in software.

Jun 27 2017

math.OC arXiv:1706.08398v1

We discuss risked competitive partial equilibrium in a setting in which agents are endowed with coherent risk measures. In contrast to socialplanning models, we show by example that risked equilibria are not unique, even when agents' objective functions are strictly concave. We also show that standard computational methods find only a subset of the equilibria, even with multiple starting points.

Jun 27 2017

math.OC arXiv:1706.08264v1

Within the mining discipline, mine planning is the component that studies how to transform the information about the ore resources into value for the owner. For open-pit mines, an optimal block scheduling maximizes the discounted value of the extracted blocks (period by period), called the net present value (NPV). However, to be feasible, a mine schedule must respect the slope constraints. The optimal open-pit block scheduling problem (OPBSP) consists, therefore, in finding such an optimal schedule. On the one hand, we introduce the dynamical optimization approach to mine scheduling in the deterministic case, and we propose a class of (suboptimal) adaptive strategies, the so-called index strategies. We show that they provide upper and lower bounds for the NPV, and we provide numerical results. On the other hand, we introduce a theoretical framework for OPBSP under uncertainty and learning.

Jun 27 2017

math.OC arXiv:1706.08253v1

Given a finite Borel measure $\mu$ on R n and basic semi-algebraic sets $\Omega$\_i $\subset$ R n , i = 1,. .. , p, we provide a systematic numerical scheme to approximate as closely as desired $\mu$(∪\_i $\Omega$\_i), when all moments of $\mu$ are available (and finite). More precisely , we provide a hierarchy of semidefinite programs whose associated sequence of optimal values is monotone and converges to the desired value from above. The same methodology applied to the complement R n \ (∪\_i $\Omega$\_i) provides a monotone sequence that converges to the desired value from below. When $\mu$ is the Lebesgue measure we assume that $\Omega$ := ∪\_i $\Omega$\_i is compact and contained in a known box B and in this case the complement is taken to be B \ $\Omega$. In fact, not only $\mu$($\Omega$) but also every finite vector of moments of $\mu$\_$\Omega$ (the restriction of $\mu$ on $\Omega$) can be approximated as closely as desired, and so permits to approximate the integral on $\Omega$ of any given polynomial.

Jun 27 2017

math.OC arXiv:1706.08191v1

We consider the co-design problem of sparse output feedback and row/column-sparse output matrix. A row-sparse (resp. column-sparse) output matrix implies a small number of outputs (resp. sensor measurements). We impose row/column-cardinality constraint on the output matrix and the cardinality constraint on the output feedback gain. The resulting nonconvex, nonsmooth optimal control problem is solved by using the proximal alternating linearization method (PALM). One advantage of PALM is that the proximal operators for sparsity constraints admit closed-form expressions and are easy to implement. Furthermore, the bilinear matrix function introduced by the multiplication of the feedback gain and the output matrix lends itself well to PALM. By establishing the Lipschitz conditions of the bilinear function, we show that PALM is globally convergent and the objective value is monotonically decreasing throughout the algorithm. Numerical experiments verify the convergence results and demonstrate the effectiveness of our approach on an unstable system with 60,000 design variables.

This paper considers the problem of phase retrieval, where the goal is to recover a signal $z\in C^n$ from the observations $y_i=|a_i^* z|$, $i=1,2,\cdots,m$. While many algorithms have been proposed, the alternating minimization algorithm has been one of the most commonly used methods, and it is very simple to implement. Current work has proved that when the observation vectors $\{a_i\}_{i=1}^m$ are sampled from a complex Gaussian distribution $N(0, I)$, it recovers the underlying signal with a good initialization when $m=O(n)$, or with random initialization when $m=O(n^2)$, and it conjectured that random initialization succeeds with $m=O(n)$. This work proposes a modified alternating minimization method in a batch setting, and proves that when $m=O(n\log^{3}n)$, the proposed algorithm with random initialization recovers the underlying signal with high probability. The proof is based on the observation that after each iteration of alternating minimization, with high probability, the angle between the estimated signal and the underlying signal is reduced.

We develop a simple routine unifying the analysis of several important recently-developed stochastic optimization methods including SAGA, Finito, and stochastic dual coordinate ascent (SDCA). First, we show an intrinsic connection between stochastic optimization methods and dynamic jump systems, and propose a general jump system model for stochastic optimization methods. Our proposed model recovers SAGA, SDCA, Finito, and SAG as special cases. Then we combine jump system theory with several simple quadratic inequalities to derive sufficient conditions for convergence rate certifications of the proposed jump system model under various assumptions (with or without individual convexity, etc). The derived conditions are linear matrix inequalities (LMIs) whose sizes roughly scale with the size of the training set. We make use of the symmetry in the stochastic optimization methods and reduce these LMIs to some equivalent small LMIs whose sizes are at most 3 by 3. We solve these small LMIs to provide analytical proofs of new convergence rates for SAGA, Finito and SDCA (with or without individual convexity). We also explain why our proposed LMI fails in analyzing SAG. We reveal a key difference between SAG and other methods, and briefly discuss how to extend our LMI analysis for SAG. An advantage of our approach is that the proposed analysis can be automated for a large class of stochastic methods under various assumptions (with or without individual convexity, etc).

Jun 27 2017

math.OC arXiv:1706.08076v1

Nguyen (2016, 2017) claimed that he has developed a simplifying set of the Kohlberg criteria that involves checking the balancedness of at most $(n-1)$ sets of coalitions. This claim is not true. Analogous to Nguyen and Thomas (2016), he has incorrectly applied the indirect proof by $(\phi \Rightarrow \bot) \Leftrightarrow \neg \phi$. He established in his purported proofs of the main results that a truth implies a falsehood. This is a wrong statement and such a hypotheses must be rejected (cf. Meinhardt (2015,2016a,2016b,2017)). Executing a logical correct interpretation ought immediately lead him to the conclusion that his proposed algorithms are deficient. In particular, he had to detect that the imposed balancedness requirement on the test condition $(\cup_{j=1}^{k}\,T_{j})$ within his proposed methods cannot be appropriate. Hence, one cannot expect that one of these algorithms makes a correct selection. The supposed algorithms are wrongly designed and cannot be set in any relation with Kohlberg. Therefore, our objections from (Meinhardt,2017) are still valid with some modifications. In particular, he failed to work out modified necessary and sufficient conditions of the nucleolus.

Jun 27 2017

math.OC arXiv:1706.08015v1

Network synthesis problem (NSP) is the problem of designing a minimum-cost network (from the empty network) satisfying a given connectivity requirement. Hau, Hirai, and Tsuchimura showed that if the edge-cost is a tree metric, then a simple greedy-type algorithm solves NSP to obtain a half-integral optimal solution. This is a generalization of the classical result by Gomory and Hu for the uniform edge-cost. In this note, we present an integer version of Hau, Hirai, and Tsuchimura's result for integer network synthesis problem (INSP), where a required network must have an integer capacity. We prove that if each connectivity requirement is at least 2 and the edge-cost is a tree metrc, then INSP can be solved in polynomial time.

Jun 27 2017

math.OC arXiv:1706.07993v1

We examine the behavior of accelerated gradient methods in smooth nonconvex unconstrained optimization. Each of these methods is typically a linear combination of a gradient direction and the previous step. We show by means of the stable manifold theorem that the heavy-ball method method does not converge to critical points that do not satisfy second-order necessary conditions. We then examine the behavior of two accelerated gradient methods - the heavy-ball method and Nesterov's method - in the vicinity of the saddle point of a nonconvex quadratic function, showing in both cases that the accelerated gradient method can diverge from this point more rapidly than steepest descent.

Jun 27 2017

math.OC arXiv:1706.07928v1

This paper studies sparsest feedback selection of linear time invariant structured systems. The hardness of this problem is addressed in \citeCarPeqAguKarPap:15. This paper points out an error in the proof given in \citeCarPeqAguKarPap:15. We consider a cyclic structured systems with dedicated inputs and outputs. We show that sparsest feedback selection is of linear complexity for cyclic structural systems with dedicated inputs and outputs. To the best of our knowledge, this addresses a long-standing open problem in the structural systems.

Jun 27 2017

math.OC arXiv:1706.07907v1

We consider cooperative multi-agent consensus optimization problems over both static and time-varying communication networks, where only local communications are allowed. The objective is to minimize the sum of agent-specific possibly non-smooth composite convex functions over agent-specific private conic constraint sets; hence, the optimal consensus decision should lie in the intersection of these private sets. Assuming the sum function is strongly convex, we provide convergence rates in suboptimality, infeasibility and consensus violation; examine the effect of underlying network topology on the convergence rates of the proposed decentralized algorithms.

General purpose correct-by-construction synthesis methods are limited to systems with low dimensionality or simple specifications. In this work we consider highly symmetrical counting problems and exploit the symmetry to synthesize provably correct controllers for systems with tens of thousands of states. The key ingredients of the solution are an aggregate abstraction procedure for mildly heterogeneous systems and subsequent formulation of counting constraints as linear inequalities.

Jun 27 2017

math.OC arXiv:1706.07833v1

In this paper we deal with optimality conditions that can be verified by a nonlinear optimization algorithm, where only a single Lagrange multiplier is avaliable. In particular, we deal with a conjecture formulated in [R. Andreani, J.M. Martinez, M.L. Schuverdt, "On second-order optimality conditions for nonlinear programming", Optimization, 56:529--542, 2007], which states that whenever a local minimizer of a nonlinear optimization problem fulfills the Mangasarian-Fromovitz Constraint Qualification and the rank of the set of gradients of active constraints increases at most by one in a neighborhood of the minimizer, a second-order optimality condition that depends on one single Lagrange multiplier is satisfied. This conjecture generalizes previous results under a constant rank assumption or under a rank deficiency of at most one. In this paper we prove the conjecture under the additional assumption that the Jacobian matrix has a smooth singular value decomposition, which is weaker than previously considered assumptions. We also review previous literature related to the conjecture.

We propose an axiomatic approach for design and performance analysis of noisy linear consensus networks by introducing a notion of systemic performance measure. This class of measures are spectral functions of Laplacian eigenvalues of the network that are monotone, convex, and orthogonally invariant with respect to the Laplacian matrix of the network. It is shown that several existing gold-standard and widely used performance measures in the literature belong to this new class of measures. We build upon this new notion and investigate a general form of combinatorial problem of growing a linear consensus network via minimizing a given systemic performance measure. Two efficient polynomial-time approximation algorithms are devised to tackle this network synthesis problem: a linearization-based method and a simple greedy algorithm based on rank-one updates. Several theoretical fundamental limits on the best achievable performance for the combinatorial problem is derived that assist us to evaluate optimality gaps of our proposed algorithms. A detailed complexity analysis confirms the effectiveness and viability of our algorithms to handle large-scale consensus networks.

In this paper, we present a new leader-follower type solution to the formation maneuvering problem for multiple, nonholonomic wheeled mobile robots. The solution is based on the graph that models the coordination among the robots being a spanning tree. Our decentralized control law ensures, in the least squares sense, that the robots globally acquire a given planar formation while the formation as a whole globally tracks a desired trajectory. The control law is first designed at the kinematic level and then extended to the dynamic level. In the latter, we consider that parametric uncertainty exists in the equations of motion. These uncertainties are accounted for by employing an adaptive control scheme. The proposed formation maneuvering controls are demonstrated experimentally and numerically.