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.     

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.     

非单调信赖域方法求解无约束非光滑优化问题

提出了非单调信赖域算法求解无约束非光滑优化问题,并和经典的信赖域方法作比较分析。同时,设定了一些条件,在这些假设条件下证明了该算法是整体收敛的。数值实验结果表明,非单调策略对无约束非光滑优化问题的求解是行之有效的,拓展了非单调信赖域算法的应用领域。     

一种求解非线性约束优化全局最优的新方法

本文提出了一种求解非线性约束优化的全局最优的新方法—它是基于利用非线性互补函数和不断增加新的约束来重复解库恩-塔克条件的非线性方程组的新方法。因为库恩-塔克条件是非线性约束优化的必要条件,得到的解未必是非线性约束优化的全局最优解,为此,本文首次给出了通过利用该优化问题的先验知识,不断地增加约束来限制全局最优解范围的方法,一些仿真例子表明提出的方法和理论有效的,并且可行的。     

FOM – a MATLAB toolbox of first-order methods for solving convex optimization problems

This paper presents the FOM MATLAB toolbox for solving convex optimization problems using first-order methods. The diverse features of the eight solvers included in the package are illustrated through a collection of examples of different nature.     

求无约束优化问题的无参数填充函数法

填充函数作为求解优化问题的有效方法之一,以填充函数的基本思想为基础,构造了新的无参数填充函数,该函数形式简单,便于计算。分析了该函数的相关性质并设计了相应的算法,最后通过数值实验,结果表明提出的算法是可行的、有效的。     

解决多维全局最优问题的一种新方法

对一种新的全局优化方法(称为APSAM方法)进行了研究,将模拟退火方法的随机搜索策略与局部寻优算法POWELL相结合,使得求解过程可以跳出局部最优值的区域,最终获得全局最优解。最后通过对一些典型的多极值方程进行优化,比较了APSAM方法与模拟退火法、POWELL法和PSAM方法的优化结果,仿真结果说明提出的算法优化能力较强,效果稳定可靠。     

A second order method for unconstrained optimization

An algorithm using second derivatives for solving unconstrained optimization problems is presented. In this brief note the descent direction of the algorithm is based on a modification of the Newton direction, while the Armijo rule for choosing the stepsize is used. The rate of convergence of the algorithm is shown to be superlinear. Our computational experience shows that the method performs quite well and our numerical results are presented in Section 4.     

A variational method for unconstrained optimization problems

We introduce a new method for solving an unconstrained optimization problem. The method is based on the solution of a variational inequality problem and may be considered a modified trust region algorithm. We prove the convergence of the method and present some numerical results.     

一种求解无约束优化问题的非单调信赖域算法

提出了非单调信赖域算法求解基于锥模型的无约束优化问题,该算法在求解信赖域子问题时充分利用了当前迭代点的一阶梯度信息。提出了一个新的信赖域半径的选取机制,并和经典的信赖域方法作比较分析。设定了一些条件,在这些假设条件下证明了算法是整体收敛的。数值实验结果表明,该算法对基于锥模型的无约束优化问题的求解是行之有效的,拓展了非单调信赖域算法的应用领域。     

Interactive balance space approach for solving multi-level multi-objective programming problems

This paper studies a multi-level multi-objective decision-making (ML-MODM) problems with linear or non-linear constraints. The objective functions at each level are non-linear functions, which are to be maximized or minimized.This paper presents a three-level multi-objective decision-making (TL-MODM) model and an interactive algorithm for solving such a model. The algorithm simplifies three-level multi-objective decision-making problems by transforming them into separate multi-objective decision making problems at each level, thereby avoiding the difficulty associated with non-convex mathematical programming. Our algorithm is an extension of the work of Shi and Xia [X. Shi, H. Xia, Interactive bi-level multi-objective decision making, Journal of the Operational Research Society 48 (1997) 943-949], which dealt with interactive bi-level multi-objective decision-making problems, with some modifications in assigning satisfactoriness to each objective function in all the levels of the TL-MODM problem. Also, we solve each separate multi-objective decision making problem of the TL-MODM problem by the balance space approach.A new formula is introduced to interconnect the satisfactoriness and the proportions of deviation needed to reflect the relative importance of each objective function. Thus, we have the proportions of deviation including satisfactoriness.In addition, we present new definitions for the satisfactoriness and the preferred solution in view of singular-level multi-objective decision making problems that corresponds to the η-optimal solution of the balance space approach. Also, new definitions for the feasible solution and the preferred solution (η-optimal point) of the TL-MODM problem are presented. An illustrative numerical example is given to demonstrate the algorithm.     

An exact penalty function algorithm for solving general constrained parameter optimization problems

An exact penalty function type of algorithm is proposed to solve a general class of constrained parameter optimization problems. The proposed algorithm has the property that any solution obtained by it will always satisfy the problem constraints, and that it will obtain a solution to the constrained problem, within a given specified tolerance, by solving a single unconstrained problem, i.e. it is not necessary to solve a sequence of unconstrained optimization problems. The algorithm applies a modification of Rosenbrock's (Rosenbrock, 1960) polynomial boundary penalty function, and a negative exponential penalty function with moving parameters, to modify the objective function in the neighborhood of the constrained region; a robust unconstrained algorithm (Davison and Wong, 1975) is then used to solve the resulting unconstrained optimization problem. Some standard test functions are included to show the performance of the algorithhm. Application of the algorithm is then made to solve some computer-aided design problems occurring in the area of control system synthesis.     

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 spectral conjugate gradient method for solving large-scale unconstrained optimization

This paper establishes a spectral conjugate gradient method for solving unconstrained optimization problems, where the conjugate parameter and the spectral parameter satisfy a restrictive relationship. The search direction is sufficient descent without restarts in per-iteration. Moreover, this feature is independent of any line searches. Under the standard Wolfe line searches, the global convergence of the proposed method is proved when $\left|{\beta }_k\right|\le {\beta }_k^{FR}$ holds. The preliminary numerical results are presented to show effectiveness of the proposed method.     

A first-order multigrid method for bound-constrained convex optimization

The aim of this paper is to design an efficient multigrid method for constrained convex optimization problems arising from discretization of some underlying infinite dimensional problems. Due to problem dependency of this approach, we only consider bound constraints with (possibly) a single equality constraint. As our aim is to target large-scale problems, we want to avoid computation of second derivatives of the objective function, thus excluding Newton-like methods. We propose a smoothing operator that only uses first-order information and study the computational efficiency of the resulting method.     

无约束最优化问题的BFGS松弛异步并行算法

为解决大规模非线性最优化问题的串行求解速度慢的问题,提出应用松弛异步并行算法求解无约束最优化问题。根据无约束最优化问题的BFGS串行算法,在PC机群环境下将其并行化。利用CHOLESKY方法分解系数为对称正定矩阵的线性方程组,运用无序松弛异步并行方法求解解向量和Wolfe-Powell非线性搜索步长,并行求解BFGS修正公式,构建BFGS松弛异步并行算法,并对算法的时间复杂性、加速比进行分析。在PC机群的实验结果表明,该算法提高了无约束最优化问题的求解速度且负载均衡,算法具有线性加速比。     

The improved Farmer–Loizou method for finding polynomial zeros

An improvement of the Farmer–Loizou method for the simultaneous determination of simple roots of algebraic polynomials is proposed. Using suitable corrections of Newton's type, the convergence of the basic method is increased from 4 to 5 without any additional calculations. In this manner, a higher computational efficiency of the improved method is achieved. We prove a local convergence of the presented method under initial conditions which depend on a geometry of zeros and their initial approximations. Numerical examples are given to demonstrate the convergence behaviour of the proposed method and related methods.