An accelerated first-order method for solving SOS relaxations of unconstrained polynomial optimization problems

Our interest lies in solving sum of squares (SOS) relaxations of large-scale unconstrained polynomial optimization problems. Because interior-point methods for solving these problems are severely limited by the large-scale, we are motivated to explore efficient implementations of an accelerated first-order method to solve this class of problems. By exploiting special structural properties of this problem class, we greatly reduce the computational cost of the first-order method at each iteration. We report promising computational results as well as a curious observation about the behaviour of the first-order method for the SOS relaxations of the unconstrained polynomial optimization problem.     

Stochastic polynomial optimization

ABSTRACT

This paper studies stochastic optimization problems with polynomials. We propose an optimization model with sample averages and perturbations. The Lasserre-type Moment-SOS relaxations are used to solve the sample average optimization. Properties of the optimization and its relaxations are studied. Numerical experiments are presented.     

A New Subdivision Algorithm for the Bernstein Polynomial Approach to Global Optimization

In this paper,an improved algorithm is proposed for unconstrained global optimization to tackle non-convex nonlinear multivariate polynomial programming problems.The proposed algorithm is based on the Bernstein polynomial approach.Novel features of the proposed algorithm are that it uses a new rule for the selection of the subdivision point,modified rules for the selection of the subdivision direction,and a new acceleration device to avoid some unnecessary subdivisions.The performance of the proposed algorithm is numerically tested on a collection of 16 test problems.The results of the tests show the proposed algorithm to be superior to the existing Bernstein algorithm in terms of the chosen performance metrics.     

A new Lagrangian dual global optimization algorithm for solving bilinear matrix inequalities

A new global optimization algorithm for solving bilinear matrix inequalities (BMI) problems is developed. It is based on a dual Lagrange formulation for computing lower bounds that are used in a branching procedure to eliminate partition sets in the space of complicating variables. The advantage of the proposed method is twofold. First, the lower bound computations reduce to solving easily tractable linear matrix inequality (LMI) problems. Secondly, the lower bounding procedure guarantees global convergence of the algorithm when combined with an exhaustive partitioning of the space of complicating variables. A rigorous proof of this fact is provided. Another important feature is that the branching phase takes place in the space of complicating variables only, hence limiting the overall cost of the algorithm. Also, an important point in the method is that separated LMI constraints are encapsulated into an augmented BMI for improving the lower bound computations. Applications of the algorithm to robust structure/controller design are considered. Copyright © 2000 John Wiley & Sons, Ltd.     

Characterizing the solution set of polynomial systems in terms of homogeneous forms: an LMI approach

This paper considers the problem of determining the solution set of polynomial systems, a well‐known problem in control system analysis and design. A novel approach is developed as a viable alternative to the commonly employed algebraic geometry and homotopy methods. The first result of the paper shows that the solution set of the polynomial system belongs to the kernel of a suitable symmetric matrix. Such a matrix is obtained via the solution of a linear matrix inequality (LMI) involving the maximization of the minimum eigenvalue of an affine family of symmetric matrices. The second result concerns the computation of the solution set from the kernel of the obtained matrix. For polynomial systems of degree m in n variables, a basic procedure is available if the kernel dimension does not exceed m+1, while an extended procedure can be applied if the kernel dimension is less than n(m?1)+2. Finally, some application examples are illustrated to show the features of the approach and to make a brief comparison with polynomial resultant techniques. Copyright © 2003 John Wiley & Sons, Ltd.     

Low-rank exploitation in semidefinite programming for control

Many control-related problems can be cast as semidefinite programs. Even though there exist polynomial time algorithms and excellent publicly available solvers, the time it takes to solve these problems can be excessive. What many of these problems have in common, in particular in control, is that some of the variables enter as matrix-valued variables. This leads to a low-rank structure in the basis matrices which can be exploited when forming the Newton equations. In this article, we describe how this can be done, and show how our code, called STRUL, can be used in conjunction with the semidefinite programming solver SDPT3. The idea behind the structure exploitation is classical and is implemented in LMI Lab, but we show that when using a modern semidefinite programming framework such as SDPT3, the computational time can be significantly reduced. Finally, we describe how the modelling language YALMIP has been changed in such a way that our code, which can be freely downloaded, can be interfaced using standard YALMIP commands. This greatly simplifies modelling and usage.     

Assessment of a non-adaptive deterministic global optimization algorithm for problems with low-dimensional non-convex subspaces

The optimum and at least one optimizing point for convex nonlinear programs can be approximated well by the solution to a linear program (a fact long used in branch and bound algorithms). In more general problems, we can identify subspaces of ‘non-convex variables’ such that, if these variables have sufficiently small ranges, the optimum and at least one optimizing point can be approximated well by the solution of a single linear program. If these subspaces are low-dimensional, this suggests subdividing the variables in the subspace a priori, then producing and solving a fixed, known number of linear programs to obtain an approximation to the solution. The total amount of computation is much more predictable than that required to complete a branch and bound algorithm, and the scheme is ‘embarrassingly parallel’, with little need for either communication or load balancing. We compare such a non-adaptive scheme experimentally to our GlobSol branch and bound implementation, on those problems from the COCONUT project Lib1 test set with non-convex subspaces of dimension four or less, and we discuss potential alterations to both the non-adaptive scheme and our branch and bound process that might change the scope of applicability.     

Globally Optimal Estimates for Geometric Reconstruction Problems

We introduce a framework for computing statistically optimal estimates of geometric reconstruction problems. While traditional algorithms often suffer from either local minima or non-optimality—or a combination of both—we pursue the goal of achieving global solutions of the statistically optimal cost-function. Our approach is based on a hierarchy of convex relaxations to solve non-convex optimization problems with polynomials. These convex relaxations generate a monotone sequence of lower bounds and we show how one can detect whether the global optimum is attained at a given relaxation. The technique is applied to a number of classical vision problems: triangulation, camera pose, homography estimation and last, but not least, epipolar geometry estimation. Experimental validation on both synthetic and real data is provided. In practice, only a few relaxations are needed for attaining the global optimum.     

Hermite matrix in Lagrange basis for scaling static output feedback polynomial matrix inequalities

Using Hermite's formulation of polynomial stability conditions, static output feedback (SOF) controller design can be formulated as a polynomial matrix inequality (PMI), a (generally nonconvex) nonlinear semidefinite programming problem that can be solved (locally) with PENNON, an implementation of a penalty and augmented Lagrangian method. Typically, Hermite SOF PMI problems are badly scaled and experiments reveal that this has a negative impact on the overall performance of the solver. In this note we recall the algebraic interpretation of Hermite's quadratic form as a particular Bézoutian and we use results on polynomial interpolation to express the Hermite PMI in a Lagrange polynomial basis, as an alternative to the conventional power basis. Numerical experiments on benchmark problem instances show the improvement brought by the approach, in terms of problem scaling, number of iterations and convergence behaviour of PENNON.     

An inexact interior-point method for system analysis

In this article, a primal-dual interior-point algorithm for semidefinite programming that can be used for analysing e.g. polytopic linear differential inclusions is tailored in order to be more computationally efficient. The key to the speedup is to allow for inexact search directions in the interior-point algorithm. These are obtained by aborting an iterative solver for computing the search directions prior to convergence. A convergence proof for the algorithm is given. Two different preconditioners for the iterative solver are proposed. The speedup is in many cases more than an order of magnitude. Moreover, the proposed algorithm can be used to analyse much larger problems as compared to what is possible with off-the-shelf interior-point solvers.     

一种新型的全局优化算法——细胞膜优化算法*

通过研究细胞膜的特性及其物质转运方式,从中进行提取优化模型,并结合全局优化算法的基本思想,提出了一种新型的全局优化算法——细胞膜优化算法（CMO）。通过数值实验,验证了细胞膜优化算法具有很好的全局寻优能力、快速的收敛能力和获取高精度解的能力,并与标准粒子群算法（PSO）和人口迁移算法（PMA）进行比较,结果表明,细胞膜优化算法在解决高维优化问题时具有更好的收敛性能。     

Necessary and sufficient conditions for global optimality of eigenvalue optimization problems

The necessary and sufficient conditions for global optimality are derived for an eigenvalue optimization problem. We consider the generalized eigenvalue problem where real symmetric matrices on both sides are linear functions of design variables. In this case, a minimization problem with eigenvalue constraints can be formulated as Semi-Definite Programming (SDP). From the Karush-Kuhn-Tucker conditions of SDP, the necessary and sufficient conditions are derived for arbitrary multiplicity of the lowest eigenvalues for the case where important lower bound constraints are considered for the design variables. Received May 18, 2000     

Filter design: a finite dimensional convex optimization approach

We consider the design of transfer functions (filters) satisfying upper and lower bounds on the frequency response magnitude or on phase response, in the continuous and discrete time domains. The paper contribution is to prove that such problems are equivalent to finite dimensional convex optimization problems involving linear matrix inequality constraints. At now, such optimization problems can be efficiently solved. Note that this filter design problem is usually reduced to a semi infinite dimensional linear programming optimization problem under the additional assumption that the filter poles are fixed (for instance, when considering FIR design). Furthermore, the semi infinite dimensional optimization is practically solved, using a gridding approach on the frequency. In addition to be finite dimensional, our formulation allows to set or not the filter poles. These problems were mainly considered in signal processing. Our interest is to propose an approach dedicated to automatic control problems. In this paper, we focus on the following problems: design of weighting transfers for H_∞ control and design of lead‐lag networks for control. Numerical applications emphasize the interest of the proposed results. Copyright © 2003 John Wiley & Sons, Ltd.     

SPECTRA – a Maple library for solving linear matrix inequalities in exact arithmetic

This document describes our freely distributed Maple library spectra, for Semidefinite Programming solved Exactly with Computational Tools of Real Algebra. It solves linear matrix inequalities with symbolic computation in exact arithmetic and it is targeted to small-size, possibly degenerate problems for which symbolic infeasibility or feasibility certificates are required.     

XGRouter: high-quality global router in X-architecture with particle swarm optimization

This paper presents a high-quality very large scale integration (VLSI) global router in X-architecture, called XGRouter, that heavily relies on integer linear programming (ILP) techniques, partition strategy and particle swarm optimization (PSO). A new ILP formulation, which can achieve more uniform routing solution than other formulations and can be effectively solved by the proposed PSO is proposed. To effectively use the new ILP formulation, a partition strategy that decomposes a large-sized problem into some small-sized sub-problems is adopted and the routing region is extended progressively from the most congested region. In the post-processing stage of XGRouter, maze routing based on new routing edge cost is designed to further optimize the total wire length and mantain the congestion uniformity. To our best knowledge, XGRouter is the first work to use a concurrent algorithm to solve the global routing problem in X-architecture. Experimental results show that XGRouter can produce solutions of higher quality than other global routers. And, like several state-of-the-art global routers, XGRouter has no overflow.     

一种有效的解无约束全局优化的进化算法

为了解决进化算法在求解全局优化时易陷入局部最优和收敛速度慢的问题,设计了一个杂交算子,利用种群中最好点与其他点间的关系确定搜索方向,从而快速地找到实值函数的下降方向,一旦算法找到优于种群中最好点的点,利用所构造的两条直线交点的投影对其进行进一步优化,使函数值更迅速地下降.提出了适合杂交算子的初始种群生成方法.设计了一个既能提高收敛速度又能摆脱局部最优的变异算子以增强算法的效果.在此基础上,提出了一个求解全局优化问题的高效进化算法,并从理论上证明了全局收敛性,从数值上验证了有效性.     

Free material optimization for stress constraints

Free material design deals with the question of finding the lightest structure subject to one or more given loads when both the distribution of material and the material itself can be freely varied. We additionally consider constraints on local stresses in the optimal structure. We discuss the choice of formulation of the problem and the stress constraints. The chosen formulation leads to a mathematical program with matrix inequality constraints, so-called nonlinear semidefinite program. We present an algorithm that can solve these problems. The algorithm is based on a generalized augmented Lagrangian method. A number of numerical examples demonstrate the effect of stress constraints in free material optimization. Dedicated to Pauli Pedersen on the occasion of his 70th birthday.     

L分析的线性矩阵不等式方法及其优化算法

通过采用S—过程和投影引理，得到了结构奇异值上界的LMI判据，该判据是基于状态空间描述的，从而消除了频率扫描过程和频率响应曲线拟合过程，并具有较好的数值性态，以该判据为基础，给出了计算结构奇异值上界的优化投影迭代算法，并将该方法应用于基准测试系统和典型电力系统，以验证其有效性，数值结果表明，该方法与经典频域方法和状态空间方法相比具有更好的求解效率。