解半定规划的二次摄动方法

半定规划在系统论,控制论,组合优化,和特征值优化等领域有着广泛的应用。本文将半定规划摄动成二次半定规划,它的唯一解恰为原问题的解,并且对其偶问题等价于一个线性对称的投影方程,可方便地用投影收缩方法求解,从而获得原半定规划问题的解。文章给出了算法及其收敛性分析,数值试验结果表明摄动方法是解半定规划的一种有效的方法。     

一类半定二次规划逆问题

本文求解了一类半定二次规划的逆问题.具体可描述为在保证一个可行的解是原半定二次规划问题的最优解的前提下,使目标函数中的参数以及约束条件中右端项参数与它们的估计值的距离最小.我们将该逆问题转换为具有线性约束和半正定锥互补约束的问题.再利用对偶理论,又将上述问题转化成只有半正定锥互补约束的问题,但此时也是一个难问题,通过引入一个非光滑的惩罚函数来惩罚互补约束,进而将原问题转化为一个DC问题.再采用序列凸规划方法来求解它,同时给出惩罚方法以及序列凸规划方法的收敛性分析.最后的数值实验表明我们采用的方法对于本文提出的问题求解还是非常有效的.     

求解大规模带二次简单约束的二次规划的显式自调比投影收缩算法

1　引　　言我们来考虑如下的带二次简单约束的二次规划问题12 x TH x +c Tx =mins.t.,‖ x‖ 2 ≤ a (1)其中 H∈ Rn× n是一个半正定对称矩阵 ,c∈ Rn,这里 a是一个确定的参数 .求解问题 (1)的最基本的方法是构造 L agrange函数 :L (x,λ) =x TH x +2 c Tx +λ(x Tx - a2 ) (2 )当约束起作用时 ,由 x L (x,λ) =0 ,　　 λL (x,λ) =0 ,得H x +c+λx =0‖ x‖ =a (3)即(H +λI) x +c =0‖ x‖ =a从而有‖ (H +λI) - 1 c‖ =a令φ(λ) =‖ (H +λI) - 1 c‖ ,　　 S(λ) =(H +λI) - 1 c则φ2 (λ) =STS =c T(H +λI) - 2 c=…     

无界域上不定二次规划的一个算法

本给出了无界域上不定二次规划一个算法，该算法将不定二次规划转化为一系列凸二次规划，并证明了算法的收敛性。     

无界域上不定二次规划的一个算法

本文给出了无界域上不定二次规划一个算法 ,该算法将不定二次规划转化为一系列凸二次规划 ,并证明了算法的收敛性 .     

框式约束凸二次规划问题的内点算法

In this paper,a primal-dual interior point algorithm for convex quadratic progromming problem with box constrains is presented.It can be started at any primal-dual interior feasible point.If the initial point is close to the central path,it becomes a central path-following alogorithm and requires a total of O(√nL)number of iterations,where L is the input length.     

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

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

二次规划的内椭球算法

对于标准型的凸二次规划问题本文给出了一个新算法，算法的一每步迭代，利用内椭球的思想来近似求解一个线性质规划子问题而得到迭代方向，再适当选取步长而使之成为多项式算法，其迭代步数为Ｏ（ｎＬ＾２），每一步迭代所需计算量为Ｏ（ｎ＾３）。其中ｎ为变量个数，Ｌ为问题的输入长度。     

THE PRIMAL—DUAL POTENTIAL REDUCTION ALGORITHM FOR POSITIVE SEMI—DEFINITE PROGRAMMING

In this paper we introduce a primal-dual potential reduction algorithm for positive semi-definite programming. Using the symetric preserving scalings for both primal and dual interior matrices, we can construct an algorithm which is very similar to the primal-dual potential reduction algorithm of Huang and Kortanek [6] for linear programming. The complexity of the algorithm is either O(nlog(X0 · S0/ε) or O(nlog(X0· S0/ε) depends on the value of ρ in the primal-dual potential function, where X0 and S0 is the initial interior matrices of the positive semi-definite programming.     

用Levenberg-Marquardt类的投影收缩方法解运输问题

For solving linear variational inequalities (LVI), the projection and contraction method of Levenberg-Marquardt type needs less iterations than an elementary projection and contraction method. However, the method of Levenberg-Marquardt type has to calculate the inverse of a matrix and hence it is unsuitable for large problems. In this paper, using the special structure of the constraint matrix, we present a PC method of Levenberg-Marquardt type for LVI arising from transportation problem without calculating any inverse matrices.Several computational experiments are presentded to indicate that the methods is good for solving the transportation problem.     

A NEW INEXACT SEQUENTIAL QUADRATIC PROGRAMMING ALGORITHM

This paper represents an inexact sequential quadratic programming (SQP) algorithm which can solve nonlinear programming (NLP) problems. An inexact solution of the quadratic programming subproblem is determined by a projection and contraction method such that only matrix-vector product is required. Some truncated criteria are chosen such that the algorithm is suitable to large scale NLP problem. The global convergence of the algorithm is proved.     

一个投影收缩算法的新步长

本文研究了求解单调变分不等式问题的一个投影收缩算法.利用何炳生教授的分析手法,给出了新步长,并且证明了在该步长下算法的全局收敛性.初步的数值试验表明了新步长的实用性.     

A PREDICTOR-CORRECTOR INTERIOR-POINT ALGORITHM FOR CONVEX QUADRATIC PROGRAMMING

The simplified Newton method, at the expense of fast convergence, reduces the work required by Newton method by reusing the initial Jacobian matrix. The composite Newton method attempts to balance the trade-off between expense and fast convergence by composing one Newton step with one simplified Newton step. Recently, Mehrotra suggested a predictor-corrector variant of primal-dual interior point method for linear programming. It is currently the interior-point method of the choice for linear programming. In this work we propose a predictor-corrector interior-point algorithm for convex quadratic programming. It is proved that the algorithm is equivalent to a level-1 perturbed composite Newton method. Computations in the algorithm do not require that the initial primal and dual points be feasible. Numerical experiments are made.     

一类二次特征值反问题的中心对称解及其最佳逼近

1引言给定n阶实矩阵M,C和K,二次特征值问题:求数λ和非零向量x使得Q(λ)x=0, (1．1)其中Q(λ)=λ2M λC K称为二次束．数λ和相应的非零向量x分别称为二次束Q(λ)的特征值和特征向量．Tisseur和Meerbergen概述了二次特征值问题的各种应用、数学理论和数值方法．在工程技术,特别是结构动力模型修正技术领域经常遇到与二次特征值问题相反的问题(称之为二次特征值反问题)．对阻尼结构进行动力分析时,应用有限元方法可得到系统的质量矩阵M,阻尼矩阵C和刚度矩阵K,从而可求得二次特征值问题的特征值(频率)和特征向量(振型)．但是有限元模型毕竟是实际结构系统的离散化,并且     

变量有界半定最小二乘问题

<正>1引言设A_i∈S~n,i=1,…,m,定义线性算子A:S~n→R~m,AX=(A_1·X,…,A_m·X)~T,其相应的伴随算子为A~*:R~m→S~n,且A~*y=sum from i=1 to my_iA_i.X∈S~n,b∈R~m.Malick.J在[6]中讨论了如下标准半定最小二乘问题(SDLS):     

凸二次交叉规划的等价形式

利用参数规划逆问题考虑凸二次交叉规划与多目标规划的关系 ,把交叉规划转变为同变量规划组 ,再把同变量规划组变为多目标规划 ,证明了凸二次交叉规划的均衡解与多目标规划的最优解的关系。