一类凸规划的多项式预估校正内点法

1、引言 1990年由Mehrotra对线性规划问题提出了一个称为预估校正的方法,并在1992年给出了其数值算法．1993年Mizuno,Todd和Y．Ye．给出了改进的预估校正内点法,使得一个预估步后只跟一个校正步．1994年F．A．Potra给出了不可行预估校正内点法,使得可以从一个不可行的初始点开始算法的迭代,并证明了其为二次收敛．     

求解凸二次规划问题的势下降内点算法

1　引　言二次规划问题的求解是数学规划和工业应用等领域的一个重要课题 ,同时也是解一般非线性规划问题的序列二次规划算法的关键 .求解二次规划问题的早期技术是利用线性规划问题的单纯形方法求解二次规划问题的 KKT最优性必要条件[1 ] .这类算法比较直观 ,但在处理不等式约束时 ,松弛变量的引进很容易导致求解过程的明显减慢 .有效集策略是求解二次规划问题的另一类主要技术 .这类方法一般都是稳定的 ,但随着问题中大量不等式约束的出现 ,其收敛速度将越来越低[2 ] .简约空间技术将所求问题的 Hessian阵投影到自由变量所在的子空间中 …     

框式线性规划的多项式预估校正内点算法

本文研究带线性约束的框式线性规划问题,给出了一个预估校正内点算法,分析了该算法的多项式计算复杂性,并证明其迭代复杂度为Ο(nL).     

一个改进的线性规划预校正算法

本文我们提出了一个改进型线性规划预校正算法，我们的预步和校正步方向与Mizuno－Todd-Ye[4]的方向是不同的．我们的算法的迭代复杂度为，然而在校正步，我们降低对偶间隙一个常数因子．     

关于宏观经济的凸二次规划模型

本文运用凸二次规划理论，通过引入价格变量建立观经济的凸二次规划模型．并指出在社会主义市场经济中企业、产业、国家可以同时达到最优．     

凸二次规划的预估校正光滑算法

本文研究了凸二次规划的一种光滑算法,将规划的对应中心线条件改造成一个非线性方程组,对其应用牛顿法及其变形形式,并且证明了算法的全局收敛性.     

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

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.     

AN ALGORITHM FOR L-SHAPED CONVEX PROGRAMMING

In this paper we study L-shaped convex programming. An algorithm for itis given. The result of computation shows that the algorithm is effective. The algorithmcan be applied to two stage problem of stochastic convex programming.     

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

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

线性规划基于预-校正的组合同伦多项式算法

本文针对线性规划问题提出了一个新的内点方法——组合同伦内点方法，并采用预估校正算法来跟踪组合同伦路径从而得到问题的ε-解.最后讨论了该算法的收敛性，并证明了该算法为多项式算法。     

二次规划的内椭球算法

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

A INTERIOR POINT ALGORITHM FOR CONVEX NONLINEAR PROGRAMMING PROBLEMS

This paper describes a primal-dual interior paint algorithm for convex nonlinear programming problems subject to linear constraints. The algorithm is based on the path following idea. Each iteration updates a penalty parameter and finds a Newton step associated with the simplified Karush-Kuhn-Tucker system of equations which characterizes a solution of the logarithmic barrier function problem for that parameter. It is shown that the duality gap if reduced at each iteration by a factor of (1 - δ / n~(1/n) ), where S is positive and depends on some parameters associated with the objective function.     

求解随机凸规划概率约束问题的对偶算法

1引言随机规划中的概率约束问题在工程和管理中有广泛的应用.因为问题中包含非线性的概率约束,它们的求解非常困难.如果目标函数是线性的,问题的求解就比较容易.给出了一个求解随机线性规划概率约束问题的综述.原-对偶算法和切平面算法是比较有效的.在本文中,我们讨论随机凸规划概率约束问题:     

关于国民生产总值最优的凸二次规划模型

本文通过在文［１］的模型中引入中间消耗系数,建立追求国民生产总值最优的宏观经济凸二次规划模型,并指出实施合理的宏观调控可以实现企业、产业、国家同时达到最优．     

SMOOTHING BY CONVEX QUADRATIC PROGRAMMING

In this paper, we study the relaxed smoothing problems with general closed convex constraints. It is pointed out that such problems can be converted to a convex quadratic minimization problem for which there are good programs in software libraries.     

A NEW FRAMEWORK OF PRIMAL-DUAL INFEASIBLE INTERIOR-POINT METHOD FOR LINEAR PROGRAMMING*

On the basis of the formulations of the logarithmic barrier function and the idea of following the path of minimizers for the logarithmic barrier family of problems the so called "centralpath" for linear programming, we propose a new framework of primal-dual infeasible interiorpoint method for linear programming problems. Without the strict convexity of the logarithmic barrier function, we get the following results: (a) if the homotopy parameterμcan not reach to zero,then the feasible set of these programming problems is empty; (b) if the strictly feasible set is nonempty and the solution set is bounded, then for any initial point x, we can obtain a solution of the problems by this method; (c) if the strictly feasible set is nonempty and the solution set is unbounded, then for any initial point x, we can obtain a (?)-solution; and(d) if the strictly feasible set is nonempty and the solution set is empty, then we can get the curve x(μ), which towards to the generalized solutions.     

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

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.     

非线性规划的序列仿射尺度投影内点算法

本文提出了求解非线性规划的一种序列二次规划内点算法,与其他算法的不同之处在于引进了仿射尺度变换,且避免了一维搜索,这使得该算法的计算量获得了明显的减少,本文给出了算法的详细迭代步骤并讨论了算法的收敛性。     

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

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

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

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=…