一种求解半定规划的邻近外梯度算法

本文提出了一种求解半定规划的邻近外梯度算法.通过转化半定规划的最优性条件为变分不等式,在变分不等式满足单调性和Lipschitz连续的前提下,构造包含原投影区域的半空间,产生邻近点序列来逼近变分不等式的解,简化了投影的求解过程.将该算法应用到教育测评问题中,数值实验结果表明,该方法是解大规模半定规划问题的一种可行方法.     

On a constructive approach to optimality conditions for convex SIP problems with polyhedral index sets

In the paper, we consider a problem of convex Semi-Infinite Programming with an infinite index set in the form of a convex polyhedron. In study of this problem, we apply the approach suggested in our recent paper [Kostyukova OI, Tchemisova TV. Sufficient optimality conditions for convex Semi Infinite Programming. Optim. Methods Softw. 2010;25:279–297], and based on the notions of immobile indices and their immobility orders. The main result of the paper consists in explicit optimality conditions that do not use constraint qualifications and have the form of criterion. The comparison of the new optimality conditions with other known results is provided.     

Parallel Implementation of Successive Convex Relaxation Methods for Quadratic Optimization Problems

As computing resources continue to improve, global solutions for larger size quadrically constrained optimization problems become more achievable. In this paper, we focus on larger size problems and get accurate bounds for optimal values of such problems with the successive use of SDP relaxations on a parallel computing system called Ninf (Network-based Information Library for high performance computing).     

分块平方和分解

本文定义了分块平方和可分解多项式的概念.粗略地说,它是这样一类多项式,只考虑其支撑集(不考虑系数)就可以把它的平方和分解问题等价地转换为较小规模的同类问题(换句话说,相应的半正定规划问题的矩阵可以分块对角化).本文证明了近年文献中提出的两类方法—分离多项式(split polynomial)和最小坐标投影(minimal coordinate projection)—都可以用分块平方和可分解多项式来描述,证明了分块平方和可分解多项式集在平方和多项式集中为零测集.     

Minimum Ellipsoid Bounds for Solutions of Polynomial Systems via Sum of Squares

We study ellipsoid bounds for the solutions of polynomial systems of equalities and inequalities. The variable μ can be considered as parameters perturbing the solution x. For example, bounding the zeros of a system of polynomials whose coefficients depend on parameters is a special case of this problem. Our goal is to find minimum ellipsoid bounds just for x. Using theorems from real algebraic geometry, the ellipsoid bound can be found by solving a particular polynomial optimization problem with sums of squares (SOS) techniques. Some numerical examples are also given.     

Verifying exactness of relaxations for robust semi-definite programs by solving polynomial systems

In this paper, robust semi-definite programs are considered with the goal of verifying whether a particular LMI relaxation is exact. A procedure is presented showing that verifying exactness amounts to solving a polynomial system. The main contribution of the paper is a new algorithm to compute all isolated solutions of a system of polynomials. Standard techniques in computational algebra, often referred to as Stetter’s method [H.J. Stetter, Numerical Polynomial Algebra, SIAM, 2004], involve the computation of a Gröbner basis of the ideal generated by the polynomials and further require joint eigenvector computations in order to arrive at the zeros of the polynomial system. Our algorithm does neither require structural knowledge on the polynomial system, nor does it rely on the computation of joint eigenvectors.     

整数规划新进展

整数规划是对全部或部分决策变量为整数的最优化问题的模型、算法及应用等的研究, 是运筹学和管理科学中应用最广泛的优化模型之一. 首先简要回顾整数规划的历史和发展进程, 概述线性和非线性整数规划的一些经典方法. 然后着重讨论整数规划若干新进展, 包括0-1二次规划的半定规划~(SDP)~松弛和随机化方法, 带半连续变量和稀疏约束的优化问题的整数规划模型和方法, 以及0-1二次规划的协正锥规划表示和协正锥的层级半定规划~(SDP)~逼近. 最后, 对整数规划未来研究方向进行展望并对一些公开问题进行讨论.     

变分同化结合广义变分最佳分析对微波散射计资料进行海面风场反演

针对微波散射计资料的海面风场反演,本文首先利用QuikSCAT卫星散射计的近实时资料,借助荷兰皇家气象学会的SeaWinds散射计数据处理模式,在不同风速和海域的情况下,采用多解方案结合二维变分同化方法进行风向的模糊去除,达到消除解的不唯一性的目的,且对4种反演结果（低速风、中速风、高速风和近海岸风）与美国国家海洋和大气管理局卫星资料中心的近实时风场数据的对比分析,说明了该技术的有效性.在此基础上,对反演得到的中速风场利用广义变分最佳分析方法进行了调整,调整后的风场结构有了进一步的改善.此方法可为我国散射计资料反演海面风场的研究提供新的思路和方法.     

Strengthening the Lovász bound for graph coloring

The Lovász -number is a way to approximate the independence number of a graph, but also its chromatic number. We express the Lovász bound as the continuous relaxation of a discrete Lovász -number which we derive from Karger et al.s formulation, and which is equal to the chromatic number. We also give another relaxation à la Schrijver-McEliece, which is better than the Lovász -number.     

二次半定规划的增广拉格朗日算法

基于变换X=VV~T,本文将半定规划问题转换为非线性规划问题,提出了解决此问题的增广拉格朗日算法,并证明了算法的线性收敛性.在此算法中,每一次迭代计算的子问题利用最速下降搜索方向和满足wolf条件的线性搜索法求最优解.数值实验表明,此算法是行之有效的,且优于内点算法.