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

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

求解非凸半定规划的一个非线性Lagrange算法及其收敛性分析

本文提出了一个求解非凸半定规划的非线性Lagrange算法,当二阶充分条件以及严格互补条件成立时,证明了这一算法的收敛性定理.收敛结果表明,当惩罚参数小于某个阀值时,算法是局部收敛的;此外,还给出了解的一个依赖于惩罚参数的误差界.     

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

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

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

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

半定规划的逆问题

本文提出了半定规划的逆问题,利用半定规划的最优性条件,分别给出了其在ｌ∞,ｌ１,ｌ２ 模意义下的数学模型,它们仍为半定规划问题．     

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

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

凸二次规划问题逆问题的模型与解法

本文分别考虑带非负约束和不带大量负约束凸二次规划问题逆问题。首先得到各个逆问题的数学模型,然后对不同的模型给出不同的求解方法。     

半定规划的一种非精确不可行内点法

本文给出了求解半定规划的一种基于KM方向的非精确不可行内点法 ,分析了其收敛性 ,结果表明 ,该算法最多可以在O(n2 ln( 1 /ε) )步内求出半定规划的一个ε 近似解 ,与YZhang所提出的精确不可行内点法有相同的界 .     

半定规划的一种修正原对偶内点算法研究

提出了半定规划(SDP)的一种修正的原对偶内点算法,对初始点的选取进行了改进,提高了算法的计算效率,并证明了新算法的迭代复杂性是O(n).     

半定规划的近似中心投影法

1．引言半定规划问题标准形的数学形式是这里C,AIEIR”””及变量XEIRn“”为对称矩阵,Tr（·）表示矩阵的迹,用符号＞0和三0分别表示矩阵正定和半正定．由于半定规划在控制论,结构优化,组合优化方面有重要应用［1,3,16,17］以及线性规划内点法取得的巨大成就［7］,将线性规划的内点法推广到半定规划上,是数学规划领域内近年来受到重视的一个研究课题．线性规划内点法中的势函数下降法［10,16］原始对偶中心路径跟踪法［2,4,8,9,11。15］已经先后被推广到半定规划上．ROOS－Visl近似中心法则是求解线性规划的另一类内…     

Convergence Analysis of an Inexact Infeasible Interior Point Method for Semidefinite Programming

In this paper we present an extension to SDP of the well known infeasible Interior Point method for linear programming of Kojima, Megiddo and Mizuno (A primal-dual infeasible-interior-point algorithm for Linear Programming, Math. Progr., 1993). The extension developed here allows the use of inexact search directions; i.e., the linear systems defining the search directions can be solved with an accuracy that increases as the solution is approached. A convergence analysis is carried out and the global convergence of the method is proved.     

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

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

凸二次半定规划一个长步原始对偶路径跟踪算法

本文基于Nesterov-Todd方向,并引进中心路径测量函数以及原始对偶对数障碍函数,建立了一个求解凸二次半定规划的长步路径跟踪法.算法保证当迭代点落在中心路径附近时步长1被接受.算法至多迭代O(n|lnε|)次可得到一个ε最优解.论文最后报告了初步的数值试验结果.     

全局收敛的凸规划的原始—对偶不可行内点算法

本对一类凸规划提出了一个原始-对偶不可行内点算法,并证明了算法的全局收敛性。     

多目标半定规划的加权中心路径法

对于线性型多目标半定规划问题，引进加权中心路径的概念，并利用单目标半定规划的中心路径法，提出了求解多目标半定规划问题的加权中心路径法，先得型对一个叔向量的有效解，然后在此基础上，提出了通过一次迭代得到对应一定范围内其他任意权向量的有效解的一步修正方法．     

Computational Experience with Ill-Posed Problems in Semidefinite Programming

Many theoretical and algorithmic results in semidefinite programming are based on the assumption that Slater's constraint qualification is satisfied for the primal and the associated dual problem. We consider semidefinite problems with zero duality gap for which Slater's condition fails for at least one of the primal and dual problem. We propose a numerically reasonable way of dealing with such semidefinite programs. The new method is based on a standard search direction with damped Newton steps towards primal and dual feasibility.     

A Note on the Calculation of Step-Lengths in Interior-Point Methods for Semidefinite Programming

In each iteration of an interior-point method for semidefinite programming, the maximum step-length that can be taken by the iterate while maintaining the positive semidefiniteness constraint needs to be estimated. In this note, we show how the maximum step-length can be estimated via the Lanczos iteration, a standard iterative method for estimating the extremal eigenvalues of a matrix. We also give a posteriori error bounds for the estimate. Numerical results on the performance of the proposed method against two commonly used methods for calculating step-lengths (backtracking via Cholesky factorizations and exact eigenvalues computations) are included.