We propose a fast population game dynamics, motivated by the analogy with infection and immunization processes within a population of “players,” for finding dominant sets, a powerful graph-theoretical notion of a cluster. Each step of the proposed dynamics is shown to have a linear time/space complexity and we show that, under the assumption of symmetric … Read more
Let P be a pointed, polyhedral cone in R_n. In this paper, we study the cone C = cone{xx^T: x \in P} of quadratic forms. Understanding the structure of C is important for globally solving NP-hard quadratic programs over P. We establish key characteristics of C and construct a separation algorithm for C provided one … Read more
BOBYQA is an iterative algorithm for finding the minimum of a function F(x) subject to lower and upper bounds on the variables, F(x) being specified by a “black box” that returns the value F(x) for any feasible x. Each iteration employs a quadratic approximation Q to F that satisfies Q(y_j) = F(y_j), j=1,2,…,m, the interpolation … Read more
Iterative algorithms aimed at solving some problems are discussed. For certain problems, such as finding a common point in the intersection of a finite number of convex sets, there often exist iterative algorithms that impose very little demand on computer resources. For other problems, such as finding that point in the intersection at which the … Read more
In this paper, we analyze two popular semidefinite programming \SDPb relaxations for quadratically constrained quadratic programs \QCQPb with matrix variables. These are based on \emph{vector-lifting} and on \emph{matrix lifting} and are of different size and expense. We prove, under mild assumptions, that these two relaxations provide equivalent bounds. Thus, our results provide a theoretical guideline … Read more
We present new insights into how to achieve higher frequencies in large-scale nonlinear predictive control using truncated-like schemes. The basic idea is that, instead of solving the full nonlinear programming (NLP) problem at each sampling time, we solve a single, truncated quadratic programming (QP) problem. We present conditions guaranteeing stability of the approximation error derived … Read more
While the product of finitely many convex functions has been investigated in the field of global optimization, some fundamental issues such as the convexity condition and the Legendre-Fenchel transform for the product function remain unresolved. Focusing on quadratic forms, this paper is aimed at addressing the question: \emph{When is the product of finitely many positive … Read more
I present a multilevel optimization approach (termed MG/Opt) for the solution of constrained optimization problems. The approach assumes that one has a hierarchy of models, ordered from fine to coarse, of an underlying optimization problem, and that one is interested in finding solutions at the finest level of detail. In this hierarchy of models calculations … Read more
The matrix completion problem is to recover a low-rank matrix from a subset of its entries. The main solution strategy for this problem has been based on nuclear-norm minimization which requires computing singular value decompositions — a task that is increasingly costly as matrix sizes and ranks increase. To improve the capacity of solving large-scale … Read more
In this paper we generalize to an arbitrary order, under minimal hypotheses, some sufficient conditions for Lipschitz continuity of the solution of a state constrained optimal control problems. The proof combines the approach by Hager in 1979 for dealing with first-order state constraints, and the high-order alternative formulation of the optimality conditions. CitationPublished as INRIA … Read more