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.     

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.     

GpoSolver: a Matlab/C++ toolbox for global polynomial optimization

Global polynomial optimization can be a powerful tool when applied to engineering problems. One of the most successful methods for solving such problems is based on convex linear matrix inequality (LMI) relaxations. Software implementations of this approach can be found for example in Matlab toolboxes GloptiPoly and YALMIP. Matlab language makes it very easy when it comes to modelling polynomial problems. However, when using these toolboxes, Matlab is also required for the problem solving. GpoSolver aims at bridging this gap by providing a Matlab-based problem modelling toolbox supplemented by a problem-solving back end in a form of a C++ template library. Once a problem is conveniently modelled and parametrized in Matlab, a C++ class is automatically generated by GpoSolver. This class can be easily included into an existing codebase and used to solve different instances of the problem based on the supplied parameters.     

A semidefinite method for tensor complementarity problems

In this paper, we study how to compute all real solutions of the tensor complimentary problem, if there are finite many ones. We formulate the problem as a sequence of polynomial optimization problems. The solutions can be computed sequentially. Each of them can be obtained by solving Lasserre's hierarchy of semidefinite relaxations. A semidefinite algorithm is proposed and its convergence properties are discussed. Some numerical experiments are also 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 Kharitonov-like theorem for interval polynomial matrices

As an extension of Kharitonov's theorem, robust stability of interval polynomial matrices is studied. Here a polynomial matrix is said to be stable if its determinant has all roots with negative real parts. The present paper shows that the robust stability of interval polynomial matrices is equivalent to that of the subclasses where each row (column) has only one element that involves Kharitonov edge polynomials and all the other elements take on one of the four Kharitonov vertex polynomials.     

求解约束优化问题的中心引力优化算法及其工程应用

为了平衡算法的全局探测能力和局部搜索能力,提出一种基于交叉与变异的中心引力优化算法用于求解约束优化问题。该算法首先利用佳点集方法构造初始种群以保证粒子的多样性。以一定概率随机选择粒子与当前最优粒子进行算术交叉操作,引导粒子向全局最优解靠拢。对当前最优粒子进行多样性变异以避免算法陷入局部最优。标准测试函数和工程优化应用问题的实验结果表明,新算法能有效求解不同的约束优化问题。     

A polynomial approximation-based approach for chance-constrained optimization

We proposed a polynomial approximation-based approach to solve a specific type of chance-constrained optimization problem that can be equivalently transformed into a convex programme. This type of chance-constrained optimization is in great needs of many applications and most solution techniques are problem-specific. Our key contribution is to provide an all-purpose solution approach through Monte Carlo and establish the linkage between our obtained optimal solution with the true optimal solution. Our approach performs well because: First, our method controls approximation errors for both the function value and its gradient (or subgradient) at the same time. This is the primary advantage of our method in comparison to the commonly used finite difference method. Second, the approximation error is well bounded in our method and, with a properly chosen algorithm, the total computational complexity will be polynomial. We also address issues associated with Monte Carlo, such as discontinuity and nondifferentiability of the function. Thanks to fast-advancing computer hardware, our method would be increasingly appealing to businesses, including small businesses. We present the numerical results to show that our method with Monte Carlo will yield high-quality, timely, and stable solutions.     

Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coefficients

We present a hybrid symbolic-numeric algorithm for certifying a polynomial or rational function with rational coefficients to be non-negative for all real values of the variables by computing a representation for it as a fraction of two polynomial sum-of-squares (SOS) with rational coefficients. Our new approach turns the earlier methods by Peyrl and Parrilo at SNC’07 and ours at ISSAC’08 both based on polynomial SOS, which do not always exist, into a universal algorithm for all inputs via Artin’s theorem.Furthermore, we scrutinize the all-important process of converting the numerical SOS numerators and denominators produced by block semidefinite programming into an exact rational identity. We improve on our own Newton iteration-based high precision refinement algorithm by compressing the initial Gram matrices and by deploying rational vector recovery aside from orthogonal projection. We successfully demonstrate our algorithm on (1) various exceptional SOS problems with necessary polynomial denominators from the literature and on (2) very large (thousands of variables) SOS lower bound certificates for Rump’s model problem (up to n=18, factor degree=17).     

基于混沌多项式的指令鲁棒优化及在飞行控制中的应用

本文提出一种新的方法对随机系统进行运动预测和控制指令设计,该方法可以充分利用已知信息设计控制指令以提高闭环随机系统的鲁棒性.首先采用混沌多项式对随机信息进行数学表述,并利用Galerkin投影法将随机变量的混沌多项式引入常微分方程中.然后,将随机变量的均值和方差考虑至优化问题的成本函数中,并利用伪谱法对控制指令进行鲁棒优化.最后,将该方法应用于飞行器的动力学预测以及控制指令设计.仿真结果表明,该方法能够预测飞行器飞行过程中不确定性的演化,其精度与蒙特卡罗方法相当,并且计算效率更高.此外,获得的控制指令对存在不确定参数或初始条件的随机系统具有强鲁棒性.     

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.     

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.     

一种基于多项式上中国剩余定理的通信编码方案

从数论中的中国剩余定理出发,在分析基于多项式上的中国剩余定理的基础上,提出了一种新的通信编码。该方案对传统的中国剩余定理通信编码方案进行了改进,使得信息在传输时更加安全可靠仿真实验证明了该编码方案大大提高了传输速率,减轻了信道上的负荷。     

一种求解约束优化问题的进化算法及其工程应用

提出一种改进的用于求解约束优化问题的进化算法.该算法利用混沌方法初始化个体以保证其均匀分布在搜索空间中.在进化过程中,将种群分为可行子种群和不可行子种群,分别采用不同的交叉和变异操作,以平衡算法的全局和局部搜索能力.标准测试问题的实验结果表明了改进算法的有效性.最后将改进算法应用到两个工程优化设计问题中,得到了满意的结果.     

Set-based discrete particle swarm optimization and its applications: a survey

Particle swarm optimization (PSO) is one of the most popular population-based stochastic algorithms for solving complex optimization problems. While PSO is simple and effective, it is originally defined in continuous space. In order to take advantage of PSO to solve combinatorial optimization problems in discrete space, the set-based PSO (S-PSO) framework extends PSO for discrete optimization by redefining the operations in PSO utilizing the set operations. Since its proposal, S-PSO has attracted increasing research attention and has become a promising approach for discrete optimization problems. In this paper, we intend to provide a comprehensive survey on the concepts, development and applications of S-PSO. First, the classification of discrete PSO algorithms is presented. Then the S-PSO framework is given. In particular, we will give an insight into the solution construction strategies, constraint handling strategies, and alternative reinforcement strategies in S-PSO together with its different variants. Furthermore, the extensions and applications of S-PSO are also discussed systemically. Some potential directions for the research of S-PSO are also discussed in this paper.     

Water wave optimization for combinatorial optimization: Design strategies and applications

Although the community of nature-inspired computing has witnessed a wide variety of metaheuristics, it often requires considerable effort to adapt them to different combinatorial optimization problems (COPs), and few studies have been devoted to reducing this burden. This paper proposes a systematic approach that consists of a set of basic steps and strategies for adapting water wave optimization (WWO), a simple and generic metaheuristic, to concrete heuristic algorithms for different COPs. Taking advantages of the generic algorithmic framework, designers can only focus on adapting the prorogation operator and the wavelength calculation method according to the combinatorial properties of the given problem, and thus easily derive efficient problem-solving algorithms. We illustrate and test our approach on the flow-shop scheduling problem (FSP), the single-objective multidimensional knapsack problem (MKP), and the multi-objective MKP, and then present an application to a machine utilization optimization problem for a large manufacturing enterprise. The results demonstrate that our approach can derive concrete algorithms that are competitive to the state-of-the-arts. Our approach also provides insights into the adaptation of other metaheuristics and the development of new metaheuristics for COPs.     

A No Free Lunch theorem for multi-objective optimization

The No Free Lunch theorem (Schumacher et al., 2001; Wolpert and Macready, 1997 [8] and [10]) is a foundational impossibility result in black-box optimization stating that no optimization technique has performance superior to any other over any set of functions closed under permutation.This paper considers situations in which there is some form of structure on the set of objective values other than the typical total ordering (e.g., Pareto dominance in multi-objective optimization). It is shown that in such cases, when attention is restricted to natural measures of performance and optimization algorithms that measure performance and optimize with respect to this structure, that a No Free Lunch result holds for any class of problems which is structurally closed under permutation. This generalizes the Sharpened No Free Lunch theorem of Schumacher et al. (2001) [8] to non-totally ordered objective spaces.     

一类三角多项式曲线的性质及应用

在三角函数空间Φ₇=span{1,sint,cost,cos2t,sin3t,cos3t,sin4t,cos4t}和Φ₈=span{1,sint,cost,sin2t,cos2t,sin3t,cos3t,sin4t,cos4t}中构造了B-L（Bézier-Like）曲线,并给出其显式表达式。进一步讨论了该曲线的若干性质和应用,给出了不需要有理形式的心脏线、椭圆（圆）弧等的B-L曲线精确表示,椭球（球）面的B-L曲面精确表示,以及圆柱螺线的B-L曲线逼近表示。通过实例说明在造型设计方面使用简便且有效。     

一种改进的药代动力学参数优化方法及其应用

基于药代动力学参数优化方法PKAIN人工免疫网络算法,提出了迭代分组并发单纯形算子,并实现了线性网络抑制函数以简化人工免疫网络的参数设置。为了加快算法的搜索速度和搜索精度,提出了新型的人工免疫网络单纯形混合算法（PKAIN_spx）,用人工免疫网络实现粗粒度全局搜索,随后用单纯形进行精确搜索。仿真实验对改进的PKAIN算法（PKAIN_in）、人工免疫网络单纯形混合算法（PKAIN_spx）以及PKAIN算法进行了比较分析,结果表明PKAIN_spx算法在药代动力学参数优化中取得良好的实验效果。     

一种新的约束优化遗传算法及其工程应用

提出一种新的用于求解约束优化问题的遗传算法,该算法利用佳点集方法初始化个体以维持种群的多样性.在进化过程中,通过可行解与不可行解算术交叉对问题的决策空间进行搜索;对可行种群与不可行种群分别采用高斯变异和柯西变异,从而协调算法的勘探和开采能力.几个标准测试问题的实验结果表明该算法的有效性;应用新算法求解两个工程优化设计问题,结果表明该算法的可行性.