非线性半定规划若干进展

讨论非线性半定规划的四个专题,包括半正定矩阵锥的变分分析、非凸半定规划问题的最优性条件、非凸半定规划问题的扰动分析和非凸半定规划问题的增广Lagrange方法．     

多目标半定规划的最优性条件及对偶理论

在不变凸的假设下来讨论多目标半定规划的最优性条件、对偶理论以及非凸半定规划的最优性条件.首先给出了非凸半定规划的一个KKT条件成立的充分必要条件,并利用此定理证明了其最优性必要条件.其次讨论了多目标半定规划的最优性必要条件、充分条件,并对其建立Wolfe对偶模型,证明了弱对偶定理和强对偶定理.     

凸半定规划中关于非奇异性的一个等价条件

本文将给出凸半定规划中关于非奇异性的一个等价条件,它可以看作线性半定规划中非奇异性的等价条件的推广.     

非凸半定规划的增广Lagrangian的微分的计算

迄今为止，还未见出版过有关求解非凸半定规划的算法，但在最近，Chen，et.al(2000)和Sun＆Sun(1999)关于非凸半定规划(SDP)的增广Lagrangian的研究是非常有用的，在本文中，我们证明非凸半定规划的增广Lagrangian是可微的，并且给出它的可微表达式．     

非凸半定规划的广义Fakars引理及最优性条件

1引言在本文中,我们用(?),S~n,S_ ~n分别表示有限维向量空间,n阶对称矩阵空间及n阶半正定矩阵锥.我们考虑如下形式的非凸半定规划问题:     

基于半定规划松弛的凸二层规划问题算法研究

提出使用凸松弛的方法求解二层规划问题,通过对一般带有二次约束的二次规划问题的半定规划松弛的探讨,研究了使用半定规划(SDP)松弛结合传统的分枝定界法求解带有凸二次下层问题的二层二次规划问题,相比常用的线性松弛方法,半定规划松弛方法可快速缩小分枝节点的上下界间隙,从而比以往的分枝定界法能够更快地获得问题的全局最优解.     

基于最优D.C.分解的单二次约束非凸二次规划精确算法

本文提出一种基于最优D.C.分解的单二次约束非凸二次规划精确算法.本文首先对非凸二次日标函数进行D.C.分解,然后对D.C.分解中凹的部分进行线性下逼近得到一个凸二次松弛问题.本文证明了最优D.C.分解可通过求解一个半定规划问题得到,而原问题的最优解可以通过计算最优凸二次松弛问题的满足某种互补条件的解得到.最后,本文报告了初步数值计算结果.     

带阀点效应水火联合调度问题的一种半定凸松弛求解法

水火联合调度问题是电力系统中一类复杂的优化问题。合理安排调度周期内的水火电出力,确定一个最优发电计划,可以带来巨大的经济效益。在实际系统中,汽轮机调汽阀开启时出现的拔丝现象会使机组耗量特性产生阀点效应。忽略阀点效应,在一定程度上降低求解的精度。本文考虑带阀点效应的水火联合调度问题。该问题非凸非光滑,且带有非线性约束,直接使用确定性全局优化方法求解是相当困难的。本文使用高效的半定规划求解此问题。首先用耗量特性函数的初始周期代替其余有限的周期,并对其进行二次拉格朗日插值拟合。再通过引进0-1变量,得到整个耗量特性函数的近似,进而把问题松弛为半定规划模型。最后,采用凸规划应用软件包CVX求解一个仿真算例,得到一个近似全局最优解。     

多目标半定规划的互补弱鞍点和G-鞍点最优性条件

对于含矩阵函数半定约束和多个目标函数的多目标半定规划问题，给出Lagrange函数在弱有效意义下的互补弱鞍点和Geofrrion恰当有效意义下的G-鞍点的定义及其等价定义．然后，在较弱的凸性条件下，利用含矩阵和向量约束的择一性定理，建立多目标半定规划的互补弱鞍点和G-鞍点充分必要条件．     

求解最大割问题的半定规划松驰的序列线性规划方法

本文基于最大割问题的半定规划松弛,利用矩阵分解的方法给出了与半定规划松弛等价的非线性规划模型,提出一种序列线性规划方法求解该模型.并在适当的条件下,证明了算法的全局收敛性.数值实验表明:序列线性规划方法在时间上要优于半定规划的内点算法.所以序列线性规划方法能更有效地求解大规模的最大割问题的半定规划松弛.     

Space tensor conic programming

Space tensors appear in physics and mechanics. Mathematically, they are tensors in the three-dimensional Euclidean space. In the research area of diffusion magnetic resonance imaging, convex optimization problems are formed where higher order positive semi-definite space tensors are involved. In this short paper, we investigate these problems from the viewpoint of conic linear programming (CLP). We characterize the dual cone of the positive semi-definite space tensor cone, and study the CLP formulation and the duality of positive semi-definite space tensor conic programming.     

二次半定规划问题及其投影收缩算法

In this paper,we discuss the relations among the quadratic semi-definite programming problem,the linear semi-definite porgramming and the linearquadratic semi-definite programming problem.The duality theories are presented.After proving the equivalence of its optimality conditions and monotonous linear variational inequalities,we use the projection and contraction algorithms to solve(QSDP),We present the algorithms and its convergence analysis.     

A Continuation Algorithm for Max-Cut Problem

A continuation algorithm for the solution of max-cut problems is proposed in this paper. Unlike the available semi-definite relaxation, a max-cut problem is converted into a continuous nonlinear programming by employing NCP functions, and the resulting nonlinear programming problem is then solved by using the augmented Lagrange penalty function method. The convergence property of the proposed algorithm is studied. Numerical experiments and comparisons with the Geomeans and Williamson randomized algorithm made on some max-cut test problems show that the algorithm generates satisfactory solutions for all the test problems with much less computation costs.     

Tight wavelet frames via semi-definite programming

In this paper we state the “oblique extension principle” as a problem of semi-definite programming. Using this optimization technique we show that the existence of a tight frame is equivalent to the existence of a certain matrix from a cone of positive semi-definite matrices, whose entries satisfy linear constraints. We also discuss how to use the optimization techniques to reduce the number of frame generators in univariate and multivariate cases. We apply our results for constructing tight frames for several subdivision schemes.     

A dual-active-set algorithm for positive semi-definite quadratic programming

Because of the many important applications of quadratic programming, fast and efficient methods for solving quadratic programming problems are valued. Goldfarb and Idnani (1983) describe one such method. Well known to be efficient and numerically stable, the Goldfarb and Idnani method suffers only from the restriction that in its original form it cannot be applied to problems which are positive semi-definite rather than positive definite. In this paper, we present a generalization of the Goldfarb and Idnani method to the positive semi-definite case and prove finite termination of the generalized algorithm. In our generalization, we preserve the spirit of the Goldfarb and Idnani method, and extend their numerically stable implementation in a natural way. Supported in part by ATERB, NSERC and the ARC. Much of this work was done in the Department of Mathematics at the University of Western Australia and in the Department of Combinatorics and Optimization at the University of Waterloo.     

整数规划新进展

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

Estimation of failure probability using semi-definite logit model

We will propose a new and practical method for estimating the failure probability of a large number of small to medium scale companies using their balance sheet data. We will use the maximum likelihood method to estimate the best parameters of the logit function, where the failure intensity function in its exponent is represented as a convex quadratic function instead of a commonly used linear function. The reasons for using this type of function are : (i) it can better represent the observed nonlinear dependence of failure probability on financial attributes, (ii) the resulting likelihood function can be maximized using a cutting plane algorithm developed for nonlinear semi-definite programming problems.We will show that we can achieve better prediction performance than the standard logit model, using thousands of sample companies.Revised: December 2002,     

Trust-region problems with linear inequality constraints: exact SDP relaxation,global optimality and robust optimization

The trust-region problem, which minimizes a nonconvex quadratic function over a ball, is a key subproblem in trust-region methods for solving nonlinear optimization problems. It enjoys many attractive properties such as an exact semi-definite linear programming relaxation (SDP-relaxation) and strong duality. Unfortunately, such properties do not, in general, hold for an extended trust-region problem having extra linear constraints. This paper shows that two useful and powerful features of the classical trust-region problem continue to hold for an extended trust-region problem with linear inequality constraints under a new dimension condition. First, we establish that the class of extended trust-region problems has an exact SDP-relaxation, which holds without the Slater constraint qualification. This is achieved by proving that a system of quadratic and affine functions involved in the model satisfies a range-convexity whenever the dimension condition is fulfilled. Second, we show that the dimension condition together with the Slater condition ensures that a set of combined first and second-order Lagrange multiplier conditions is necessary and sufficient for global optimality of the extended trust-region problem and consequently for strong duality. Through simple examples we also provide an insightful account of our development from SDP-relaxation to strong duality. Finally, we show that the dimension condition is easily satisfied for the extended trust-region model that arises from the reformulation of a robust least squares problem (LSP) as well as a robust second order cone programming model problem (SOCP) as an equivalent semi-definite linear programming problem. This leads us to conclude that, under mild assumptions, solving a robust LSP or SOCP under matrix-norm uncertainty or polyhedral uncertainty is equivalent to solving a semi-definite linear programming problem and so, their solutions can be validated in polynomial time.     

A remark on the Kochen-Specker theorem and some characterizations of the determinant on sets of Hermitian matrices

In this paper we describe the general forms of all (nonlinear) continuous functionals on the sets of positive definite, positive semi-definite and Hermitian matrices which are multiplicative on the commuting elements. As a consequence, we obtain some new characterizations of the determinant on those classes of matrices.