Search

We provide new tools for worst-case performance analysis of the gradient (or steepest descent) method of Cauchy for smooth strongly convex functions, and Newton's method for self-concordant functions, including the case of inexact search directions. The analysis uses semidefinite programming performance estimation, as pioneered by Drori and Teboulle [Mathematical Programming, 145(1-2):451-482, 2014], and extends recent performance estimation results for the method of Cauchy by the authors [Optimization Letters, 11(7), 1185-1199, 2017]. To illustrate the applicability of the tools, we demonstrate a novel complexity analysis of short step interior point methods using inexact search directions. As an example in this framework, we sketch how to give a rigorous worst-case complexity analysis of a recent interior point method by Abernethy and Hazan [PMLR, 48:2520-2528, 2016]., Comment: 22 pages, 1 figure. Title of earlier version was "Worst-case convergence analysis of gradient and Newton methods through semidefinite programming performance estimation"

A linear extension of a polytope Q is any polytope which can be mapped onto Q via an affine transformation. The extension complexity of a polytope is the minimum number of facets of any linear extension of this polytope. In general, computing the extension complexity of a given polytope is difficult. The extension complexity is also equal to the nonnegative rank of any slack matrix of the polytope. In this paper, we introduce a new geometric lower bound on the extension complexity of a polytope, i.e., which relies only on the knowledge of some of its geometric characteristics. It is based on the monotone behaviour of the f -vector of polytopes under affine maps. We present numerical results showing that this bound can improve upon existing geometric lower bounds, and provide a generalization of this lower bound for the nonnegative rank of any matrix.

The standard assumption for proving linear convergence of first order methods for smooth convex optimization is the strong convexity of the objective function, an assumption which does not hold for many practical applications. In this paper, we derive linear convergence rates of several first order methods for solving smooth non-strongly convex constrained optimization problems, i.e. involving an objective function with a Lipschitz continuous gradient that satisfies some relaxed strong convexity condition. In particular, in the case of smooth constrained convex optimization, we provide several relaxations of the strong convexity conditions and prove that they are sufficient for getting linear convergence for several first order methods such as projected gradient, fast gradient and feasible descent methods. We also provide examples of functional classes that satisfy our proposed relaxations of strong convexity conditions. Finally, we show that the proposed relaxed strong convexity conditions cover important applications ranging from solving linear systems, Linear Programming, and dual formulations of linearly constrained convex problems., Comment: 36 pages, 4 figures

In this paper we present a complete iteration complexity analysis of inexact first-order Lagrangian and penalty methods for solving cone-constrained convex problems that have or may not have optimal Lagrange multipliers that close the duality gap. We first assume the existence of optimal Lagrange multipliers and study primal–dual first-order methods based on inexact information and augmented Lagrangian smoothing or Nesterov-type smoothing. For inexact (fast) gradient augmented Lagrangian methods, we derive an overall computational complexity of projections onto a simple primal set in order to attain an ε-optimal solution of the conic convex problem. For the inexact fast gradient method combined with Nesterov-type smoothing, we derive computational complexity projections onto the same set. Then, we assume that optimal Lagrange multipliers might not exist for the cone-constrained convex problem, and analyse the fast gradient method for solving penalty reformulations of the problem. For the fast gradient method combined with penalty framework, we also derive an overall computational complexity of projections onto a simple primal set to attain an ε-optimal solution for the original problem.

Nonnegative matrix factorization is a popular data analysis tool able to extract significant features from nonnegative data. We consider an extension of this problem to handle functional data, using parametrizable nonnegative functions such as polynomials or splines. Factorizing continuous signals using these parametrizable functions improves both the accuracy of the factorization and its smoothness. We introduce a new approach based on a generalization of the Hierarchical Alternating Least Squares algorithm. Our method obtains solutions whose accuracy is similar to that of existing approaches using polynomials or splines, while its computational cost increases moderately with the size of the input, making it attractive for large-scale datasets.

We propose an extended Lanczos bidiagonalization algorithm for finding a low rank approximation of a given matrix. We show that this method can yield better low-rank approximations than standard Lanczos bidiagonalization algorithm, without increasing the cost too much. We also describe a partial reorthogonalization process that can be used to maintain an adequate level of orthogonality of the Lanczos vectors in order to produce accurate low-rank approximations. We demonstrate the effectiveness and applicability of our algorithm for a number of applications.

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,...,A^m\}$ and $\{B^1,...,B^n\}$ such that $X_{i,j}=\text{trace}(A^iB^j)$ for $i=1,...,m$, and $j=1,...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$)., Comment: 21 pages, 3 figures, 3 tables

Blind audio source separation is well-suited for the application of unsupervised techniques such as nonnegative matrix factorization (NMF). It has been shown that on simple examples, it retrieves sensible solutions even in the single-channel setting, which is highly ill-posed. However, it is now widely accepted that NMF alone cannot solve single-channel source separation, for real world audio signals. Several proposals have appeared recently for systems that allow the user to control the output of NMF, by specifying additional equality constraints on the coefficients of the sources in the time-frequenty domain. In this article; we show that matrix factorization problems involving these constraints can be formulated as convex problems, using the nuclear norm as a low-rank inducing penalty. We propose to solve the resulting nonsmooth convex formulation using a simple subgradient algorithm. Numerical experiments confirm that the nuclear norm penalty allows the recovery of (approximately) low-rank solutions that satisfy the additional user-imposed constraints. Moreover, for a given computational budget, we show that this algorithm matches the performance or even outperforms state-of-the-art NMF methods in terms of the quality of the estimated sources.

In this paper, we analyze different first-order methods of smooth convex optimization employing inexact first-order information. We introduce the notion of an approximate first-order oracle. The list of examples of such an oracle includes smoothing technique, Moreau-Yosida regularization, Modified Lagrangians, and many others. For different methods, we derive complexity estimates and study the dependence of the desired accuracy in the objective function and the accuracy of the oracle. It appears that in inexact case, the superiority of the fast gradient methods over the classical ones is not anymore absolute. Contrary to the simple gradient schemes, fast gradient methods necessarily suffer from accumulation of errors. Thus, the choice of the method depends both on desired accuracy and accuracy of the oracle. We present applications of our results to smooth convex-concave saddle point problems, to the analysis of Modified Lagrangians, to the prox-method, and some others.

The polynomial chaos expansion (PCE) is an efficient numerical method for performing a reliability analysis. It relates the output of a nonlinear system with the uncertainty in its input parameters using a multidimensional polynomial approximation (the so-called PCE). Numerically, such an approximation can be obtained by using a regression method with a suitable design of experiments. The cost of this approximation depends on the size of the design of experiments. If the design of experiments is large and the system is modeled with a computationally expensive FEA (Finite Element Analysis) model, the PCE approximation becomes unfeasible. The aim of this work is to propose an algorithm that generates efficiently a design of experiments of a size defined by the user, in order to make the PCE approximation computationally feasible. It is an optimization algorithm that seeks to find the best design of experiments in the D-optimal sense for the PCE. This algorithm is a coupling between genetic algorithms and the Fedorov exchange algorithm. The efficiency of our approach in terms of accuracy and computational time reduction is compared with other existing methods in the case of analytical functions and finite element based functions.

The problem of finding large complete subgraphs in bipartite graphs (that is, bicliques) is a well-known combinatorial optimization problem referred to as the maximum-edge biclique problem (MBP), and has many applications, e.g., in web community discovery, biological data analysis and text mining. In this paper, we present a new continuous characterization for MBP. Given a bipartite graph $$G$$ , we are able to formulate a continuous optimization problem (namely, an approximate rank-one matrix factorization problem with nonnegativity constraints, R1N for short), and show that there is a one-to-one correspondence between (1) the maximum (i.e., the largest) bicliques of $$G$$ and the global minima of R1N, and (2) the maximal bicliques of $$G$$ (i.e., bicliques not contained in any larger biclique) and the local minima of R1N. We also show that any stationary points of R1N must be close to a biclique of $$G$$ . This allows us to design a new type of biclique finding algorithm based on the application of a block-coordinate descent scheme to R1N. We show that this algorithm, whose algorithmic complexity per iteration is proportional to the number of edges in the graph, is guaranteed to converge to a biclique and that it performs competitively with existing methods on random graphs and text mining datasets. Finally, we show how R1N is closely related to the Motzkin---Strauss formalism for cliques.

We study the worst-case convergence rates of the proximal gradient method for minimizing the sum of a smooth strongly convex function and a non-smooth convex function whose proximal operator is available. We establish the exact worst-case convergence rates of the proximal gradient method in this setting for any step size and for different standard performance measures: objective function accuracy, distance to optimality and residual gradient norm. The proof methodology relies on recent developments in performance estimation of first-order methods based on semidefinite programming. In the case of the proximal gradient method, this methodology allows obtaining exact and non-asymptotic worst-case guarantees that are conceptually very simple, although apparently new. On the way, we discuss how strong convexity can be replaced by weaker assumptions, while preserving the corresponding convergence rates. We also establish that the same fixed step size policy is optimal for all three performance measures. Finally, we extend recent results on the worst-case behavior of gradient descent with exact line search to the proximal case., Comment: Journal of Optimization Theory and Algorithms (DOI:10.1007/s10957-018-1298-1) [V4: correction of a minor typo and one updated reference]

In multiple criteria decision aiding, it is common to use methods that are capable of automatically extracting a decision or evaluation model from partial information provided by the decision maker about a preference structure. In general, there is more than one possible model, leading to an indetermination which is dealt with sometimes arbitrarily in existing methods. This paper aims at filling this theoretical gap: we present a novel method, based on the computation of the analytic center of a polyhedron, for the selection of additive value functions that are compatible with holistic assessments of preferences. We demonstrate the most important characteristics of this technique with an experimental and comparative study of several existing methods belonging to the UTA family.

Nonnegative Matrix Factorization consists in (approximately) factorizing a nonnegative data matrix by the product of two low-rank nonnegative matrices. It has been successfully applied as a data analysis technique in numerous domains, e.g., text mining, image processing, microarray data analysis, collaborative filtering, etc. We introduce a novel approach to solve NMF problems, based on the use of an underapproximation technique, and show its effectiveness to obtain sparse solutions. This approach, based on Lagrangian relaxation, allows the resolution of NMF problems in a recursive fashion. We also prove that the underapproximation problem is NP-hard for any fixed factorization rank, using a reduction of the maximum edge biclique problem in bipartite graphs. We test two variants of our underapproximation approach on several standard image datasets and show that they provide sparse part-based representations with low reconstruction error. Our results are comparable and sometimes superior to those obtained by two standard Sparse Nonnegative Matrix Factorization techniques., Comment: Version 2 removed the section about convex reformulations, which was not central to the development of our main results; added material to the introduction; added a review of previous related work (section 2.3); completely rewritten the last part (section 4) to provide extensive numerical results supporting our claims. Accepted in J. of Pattern Recognition

We provide a framework for computing the exact worst-case performance of any algorithm belonging to a broad class of oracle-based first-order methods for composite convex optimization, including those performing explicit, projected, proximal, conditional and inexact (sub)gradient steps. We simultaneously obtain tight worst-case guarantees and explicit instances of optimization problems on which the algorithm reaches this worst-case. We achieve this by reducing the computation of the worst-case to solving a convex semidefinite program, generalizing previous works on performance estimation by Drori and Teboulle [13] and the authors [43]. We use these developments to obtain a tighter analysis of the proximal point algorithm and of several variants of fast proximal gradient, conditional gradient, subgradient and alternating projection methods. In particular, we present a new analytical worst-case guarantee for the proximal point algorithm that is twice better than previously known, and improve the standard worst-case guarantee for the conditional gradient method by more than a factor of two. We also show how the optimized gradient method proposed by Kim and Fessler in [22] can be extended by incorporating a projection or a proximal operator, which leads to an algorithm that converges in the worst-case twice as fast as the standard accelerated proximal gradient method [2]., Published in SIOPT (updated version with corrected typo) Code available at https://github.com/AdrienTaylor/Performance-Estimation-Toolbox

In this paper, we formulate the lp-norm optimization problem as a conic optimization problem, derive its duality properties (weak duality, zero duality gap, and primal attainment) using standard conic duality and show how it can be solved in polynomial time applying the framework of interior-point algorithms based on self-concordant barriers.

The exact nonnegative matrix factorization (exact NMF) problem is the following: given an $m$-by-$n$ nonnegative matrix $X$ and a factorization rank $r$, find, if possible, an $m$-by-$r$ nonnegative matrix $W$ and an $r$-by-$n$ nonnegative matrix $H$ such that $X = WH$. In this paper, we propose two heuristics for exact NMF, one inspired from simulated annealing and the other from the greedy randomized adaptive search procedure. We show that these two heuristics are able to compute exact nonnegative factorizations for several classes of nonnegative matrices (namely, linear Euclidean distance matrices, slack matrices, unique-disjointness matrices, and randomly generated matrices) and as such demonstrate their superiority over standard multi-start strategies. We also consider a hybridization between these two heuristics that allows us to combine the advantages of both methods. Finally, we discuss the use of these heuristics to gain insight on the behavior of the nonnegative rank, i.e., the minimum factorization rank such that an exact NMF exists. In particular, we disprove a conjecture on the nonnegative rank of a Kronecker product, propose a new upper bound on the extension complexity of generic $n$-gons and conjecture the exact value of (i) the extension complexity of regular $n$-gons and (ii) the nonnegative rank of a submatrix of the slack matrix of the correlation polytope., Comment: 32 pages, 2 figures, 16 tables

We show that the exact worst-case performance of fixed-step first-order methods for unconstrained optimization of smooth (possibly strongly) convex functions can be obtained by solving convex programs. Finding the worst-case performance of a black-box first-order method is formulated as an optimization problem over a set of smooth (strongly) convex functions and initial conditions. We develop closed-form necessary and sufficient conditions for smooth (strongly) convex interpolation, which provide a finite representation for those functions. This allows us to reformulate the worst-case performance estimation problem as an equivalent finite dimension-independent semidefinite optimization problem, whose exact solution can be recovered up to numerical precision. Optimal solutions to this performance estimation problem provide both worst-case performance bounds and explicit functions matching them, as our smooth (strongly) convex interpolation procedure is constructive. Our works build on those of Drori and Teboulle in [Math. Prog. 145 (1-2), 2014] who introduced and solved relaxations of the performance estimation problem for smooth convex functions. We apply our approach to different fixed-step first-order methods with several performance criteria, including objective function accuracy and gradient norm. We conjecture several numerically supported worst-case bounds on the performance of the fixed-step gradient, fast gradient and optimized gradient methods, both in the smooth convex and the smooth strongly convex cases, and deduce tight estimates of the optimal step size for the gradient method., Comment: Accepted for publication in Mathematical Programming, DOI 10.1007/s10107-016-1009-3. Performance estimation code: http://perso.uclouvain.be/adrien.taylor/#projects

In this paper we develop random block coordinate gradient descent methods for minimizing large scale linearly constrained separable convex problems over networks. Since we have coupled constraints in the problem, we devise an algorithm that updates in parallel $\tau \geq 2$ (block) components per iteration. Moreover, for this method the computations can be performed in a distributed fashion according to the structure of the network. However, its complexity per iteration is usually cheaper than of the full gradient method when the number of nodes $N$ in the network is large. We prove that for this method we obtain in expectation an $\epsilon$-accurate solution in at most $\mathcal{O}(\frac{N}{\tau \epsilon})$ iterations and thus the convergence rate depends linearly on the number of (block) components $\tau$ to be updated. For strongly convex functions the new method converges linearly. We also focus on how to choose the probabilities to make the randomized algorithm to converge as fast as possible and we arrive at solving a sparse SDP. Finally, we describe several applications that fit in our framework, in particular the convex feasibility problem. Numerically, we show that the parallel coordinate descent method with $\tau>2$ accelerates on its basic counterpart corresponding to $\tau=2$., Comment: 21 pages, 3 figure

The purpose of this paper is to provide improved complexity results for several classes of structured convex optimization problems using the theory of self-concordant functions developed by Nesterov and Nemirovski in SIAM Studies in Applied Mathematics, SIAM Publications, Philadelphia, 1994. We describe the classical short-step interior-point method and optimize its parameters in order to provide the best possible iteration bound. We also discuss the necessity of introducing two parameters in the definition of self-concordancy and which one is the best to fix. A lemma due to den Hertog et al. in Mathematical Programming Series B 69 (1) (1995) is improved, which allows us to review several classes of structured convex optimization problems and improve the corresponding complexity results.

An efficient gradient-based optimization method was recently proposed for the array synthesis problems with free antenna positions. It relies on the use of a cost function that averages sidelobe levels using a (weighted) p-norm. We show how the gradient of this cost function can be evaluated using a Fourier transform, and hence computed quickly. We provide details about the FFT implementation of this computation. Numerical results for arrays comprising about 256 elements with constant magnitudes are reported, and the effects of mutual coupling between elements are demonstrated.

A method is proposed for the synthesis of large planar non-regular arrays assuming constant magnitude for the excitation of the elements. The approach, which combines global and local optimization, is based on distinguishing aperture-type and non-coherent parts of the array factor. The following constraints are considered: minimal separation of the antennas, maximum size of the array and fixed mainbeam width. The level of the sidelobes is reduced via the minimization of a new type of flexible averaging cost function based on an Lp-norm. Possible applications of this model lie in the field of radio astronomy, satellite communications and radar systems. The proposed optimization strategy consists of three successive steps designed to be independent of each other. Starting with an equivalent continuous aperture, the first two steps act as global transformations of the radial and azimuthal positions of the elements in the initial array, while the third step performs a local optimization of individual elements of the array. This last step heavily relies on computations of the gradient of the cost function, which can be done quickly using an FFT-based procedure. The method is illustrated for several large-scale examples by considering as inputs four different types of non-regular arrays.

Topological optimization tool using genetic algorithm as optimization algorithm are known as very expensive in computation time. In this paper, we study an approach to improve performance of topological optimization tool by introducing a dynamic variation of the population size of children during the process of optimization. This method allows to improve performance of each generation by adapting the number of children created and by introducing a coefficient of reproduction for each individual inside the population of parents. Through this coefficient of reproduction, the number of children assigns to each parent is calculated. The number of evaluations at each generation changes and the tool can saves evaluations in order to increase the number of iterations.

Approximate matrix factorization techniques with both nonnegativity and orthogonality constraints, referred to as orthogonal nonnegative matrix factorization (ONMF), have been recently introduced and shown to work remarkably well for clustering tasks such as document classification. In this paper, we introduce two new methods to solve ONMF. First, we show athematical equivalence between ONMF and a weighted variant of spherical k-means, from which we derive our first method, a simple EM-like algorithm. This also allows us to determine when ONMF should be preferred to k-means and spherical k-means. Our second method is based on an augmented Lagrangian approach. Standard ONMF algorithms typically enforce nonnegativity for their iterates while trying to achieve orthogonality at the limit (e.g., using a proper penalization term or a suitably chosen search direction). Our method works the opposite way: orthogonality is strictly imposed at each step while nonnegativity is asymptotically obtained, using a quadratic penalty. Finally, we show that the two proposed approaches compare favorably with standard ONMF algorithms on synthetic, text and image data sets., 17 pages, 8 figures. New numerical experiments (document and synthetic data sets)

Weighted low-rank approximation (WLRA), a dimensionality reduction technique for data analysis, has been successfully used in several applications, such as in collaborative filtering to design recommender systems or in computer vision to recover structure from motion. In this paper, we study the computational complexity of WLRA and prove that it is NP-hard to find an approximate solution, even when a rank-one approximation is sought. Our proofs are based on a reduction from the maximum-edge biclique problem, and apply to strictly positive weights as well as binary weights (the latter corresponding to low-rank matrix approximation with missing data)., Comment: Proof of Lemma 4 (Lemma 3 in v1) has been corrected. Some remarks and comments have been added. Accepted in SIAM Journal on Matrix Analysis and Applications

The nonnegative rank of a nonnegative matrix is the minimum number of nonnegative rank-one factors needed to reconstruct it exactly. The problem of determining this rank and computing the corresponding nonnegative factors is difficult; however it has many potential applications, e.g., in data mining, graph theory and computational geometry. In particular, it can be used to characterize the minimal size of any extended reformulation of a given combinatorial optimization program. In this paper, we introduce and study a related quantity, called the restricted nonnegative rank. We show that computing this quantity is equivalent to a problem in polyhedral combinatorics, and fully characterize its computational complexity. This in turn sheds new light on the nonnegative rank problem, and in particular allows us to provide new improved lower bounds based on its geometric interpretation. We apply these results to slack matrices and linear Euclidean distance matrices and obtain counter-examples to two conjectures of Beasly and Laffey, namely we show that the nonnegative rank of linear Euclidean distance matrices is not necessarily equal to their dimension, and that the rank of a matrix is not always greater than the nonnegative rank of its square.

Nonnegative Matrix Factorization (NMF) is the problem of approximating a nonnegative matrix with the product of two low-rank nonnegative matrices and has been shown to be particularly useful in many applications, e.g., in text mining, image processing, computational biology, etc. In this paper, we explain how algorithms for NMF can be embedded into the framework of multilevel methods in order to accelerate their convergence. This technique can be applied in situations where data admit a good approximate representation in a lower dimensional space through linear transformations preserving nonnegativity. A simple multilevel strategy is described and is experimentally shown to speed up significantly three popular NMF algorithms (alternating nonnegative least squares, multiplicative updates and hierarchical alternating least squares) on several standard image datasets., 23 pages, 10 figures. Section 6 added discussing limitations of the method. Accepted in Journal of Computational and Applied Mathematics

In this paper, we solve a class of convex infinite-dimensional optimization problems using a numerical approximation method that does not rely on discretization. Instead, we restrict the decision variable to a sequence of finite-dimensional linear subspaces of the original infinite-dimensional space and solve the corresponding finite-dimensional problems in a efficient way using structured convex optimization techniques. We prove that, under some reasonable assumptions, the sequence of these optimal values converges to the optimal value of the original infinite-dimensional problem and give an explicit description of the corresponding rate of convergence.

To perform parameter and shape optimization, an initial topology is required which affects the final solution. Topology optimization methods have the advantage to release this constraint. They are based on a splitting of the design space into cells, in which they attempt to distribute optimally some given materials. In this paper, the optimization is based on a discrete formulation of the Maxwell equations obtained thanks to a finite element model. The gradient of the objective function is computed immediately from this discrete form, which is more convenient than the adjoint variable method. A line-search method (steepest descent direction) is then applied. The step size is computed by a simple and quick algorithm, to achieve good and fast convergence. Several convexity issues were already highlighted in topology optimization. We explain how we can face some of them by performing the optimization on a variable linked to the permeability by a given mapping. This mapping actually affects the value of intermediate materials and must be selected carefully to avoid the algorithm to be trapped in some local minimizers. In order to illustrate the concepts presented along the paper, the method is applied for the topology optimization of a linear reluctant actuator.

We consider the single-facility location problem with mixed norms, i.e. the problem of minimizing the sum of the distances from a point to a set of fixed points in R, where each distance can be measured according to a different p-norm. We show how this problem can be expressed into a structured conic format by decomposing the nonlinear components of the objective into a series of constraints involving three-dimensional cones. Using the availability of a self-concordant barrier for these cones, we present a polynomial-time algorithm (a long-step path-following interior-point scheme) to solve the problem up to a given accuracy. Finally, we report computational results for this algorithm and compare with standard nonlinear optimization solvers applied to this problem.

In this paper, we propose new lower and upper bounds on the linear extension complexity of regular $n$-gons. Our bounds are based on the equivalence between the computation of (i) an extended formulation of size $r$ of a polytope $P$, and (ii) a rank-$r$ nonnegative factorization of a slack matrix of the polytope $P$. The lower bound is based on an improved bound for the rectangle covering number (also known as the boolean rank) of the slack matrix of the $n$-gons. The upper bound is a slight improvement of the result of Fiorini, Rothvoss and Tiwary [Extended Formulations for Polygons, Discrete Comput. Geom. 48(3), pp. 658-668, 2012]. The difference with their result is twofold: (i) our proof uses a purely algebraic argument while Fiorini et al. used a geometric argument, and (ii) we improve the base case allowing us to reduce their upper bound $2 \left\lceil \log_2(n) \right\rceil$ by one when $2^{k-1} < n \leq 2^{k-1}+2^{k-2}$ for some integer $k$. We conjecture that this new upper bound is tight, which is suggested by numerical experiments for small $n$. Moreover, this improved upper bound allows us to close the gap with the best known lower bound for certain regular $n$-gons (namely, $9 \leq n \leq 13$ and $21 \leq n \leq 24$) hence allowing for the first time to determine their extension complexity., 20 pages, 3 figures. New contribution: improved lower bound for the boolean rank of the slack matrices of n-gons

International audience; We present a new family of sums of squares (SOS) relaxations to cones of positive polynomials. The SOS relaxations employed in the literature are cones of polynomials which can be represented as ratios, with an SOS as numerator and a fixed positive polynomial as denominator. We employ nonlinear transformations of the arguments instead. A fixed cone of positive polynomials, considered as a subset in an abstract coefficient space, corresponds to an infinite, partially ordered set of concrete cones of positive polynomials of different degrees and in a different number of variables. To each such concrete cone corresponds its own SOS cone, leading to a hierarchy of increasingly tighter SOS relaxations for the abstract cone.