一个新的求解半正定规划问题的原始对偶内点算法

选择合适的核函数对设计求解线性规划与半正定规划的原始对偶内点算法以及复杂性分析都十分重要.Bai等针对线性规划提出三种核函数,并给出求解线性规划的大步迭代复杂界,但未给出数值算例验证算法的实际效果(Bai Y Q,Xie W,Zhang J.New parameterized kernel functions for linear optimization.J Global Optim,2012.DOI 10.1007/s10898-012-9934-z).基于这三种核函数设计了新的求解半正定规划问题的原始对内点算法.进一步分析了算法关于大步方法的计算复杂性界,同时通过数值算例验证了算法的有效性和核函数所带参数对计算复杂性的影响.     

一种基于核心矩阵的原始对偶算法

本文通过对线性规划问题中的核心矩阵的分析，提出了一种基于核心矩阵的原始对偶算法。该算法以核心矩阵为运算单元，一方面呈现了存储空间小，计算量小的特点；另一方面，该算法采用了一种新的转轴规则的外点算法，在保持原始可行的基础上，不断改善对偶解使其可行。数值实验结果表明该算法在迭代次数、转轴效率和存储空间上都有一定的提高。     

求解非线性规划的原始对偶内点法(英文)

In this paper, we propose a primal-dual interior point method for solving general constrained nonlinear programming problems. To avoid the situation that the algorithm we use may converge to a saddle point or a local maximum, we utilize a merit function to guide the iterates toward a local minimum. Especially, we add the parameter ε to the Newton system when calculating the decrease directions. The global convergence is achieved by the decrease of a merit function. Furthermore, the numerical results confirm that the algorithm can solve this kind of problems in an efficient way.     

求解线性规划的对偶算法

单纯形法一般采用行变换进行计算.本文给出了两种列变换的计算方法,一种与原始单纯形法等价,一种与对偶单纯形法等价,本文称之为对偶方法.这两种方法不引入松弛变量或剩余变量,计算规模小,有明显竞争优势.     

二阶锥规划的基于自协调指数核函数的原始-对偶内点算法

基于一个自协调指数核函数, 设计求解二阶锥规划的原始-对偶内点算法. 根据自协调指数核函数的二阶导数与三阶导数的特殊关系, 在求解问题的中心路径时, 用牛顿方向代替了负梯度方向来确定搜索方向. 由于自协调指数核函数不具有``Eligible'性质, 在分析算法的迭代界时, 利用牛顿方法求解目标函数满足自协调性质的无约束优化问题的技术, 估计算法内迭代中自协调指数核函数确定的障碍函数的下降量, 得到原始-对偶内点算法大步校正的迭代界O(2N\frac{\log2N}{\varepsilon}), 这里N是二阶锥的个数. 这个迭代界与线性规划情形下的迭代界一致. 最后, 通过数值算例验证了算法的有效性.     

线性规划的对偶基线算法

In this paper,we studied the dual form of the basic line algorthm for linear programs.It can be easily implemented in tableau that similar to the primal/dual simplex method.Different from primal simplex method or dual simplex method,the dual basic line algorithm can keep primal feasibility and dual feasibility at the same time in a tableau,which makes it more efficient than the former ones.Principles and convergence of dual basic line algorthm were discussed.Some examplex and computational experience were given to illustrate the efficiency of our method.     

框式线性规划的原—对偶仿射尺度算法

本文对框式线性规划问题设计了一个原－对偶仿射尺度算法，并证明该算法的迭代复杂性面式同时。     

解一般线性规划逆问题的一个O（n^3L）算法

本文讨论了一般线性规划逆问题在各种情况下的求解，并基于解凸二次规划的原对偶内点算法，给出了一个O（n3L）算法和一个实用算法．     

一个解半正定规划问题的基于广义对数障碍函数的原始对偶内点算法

本文对经典对数障碍函数推广,给出了一个广义对数障碍函数.基于这个广义对数障碍函数设计了解半正定规划问题的原始-对偶内点算法.分析了该算法的复杂性,得到了一个理论迭代界,它与已有的基于经典对数障碍函数的算法的理论迭代界一致.同时,并给出了一个数值算例,阐明了函数的参数对算法运行时间的影响.     

线性规划的内点法

有解时,记它的最优解为x(v)。则x=x(v)定义了S_+中的一条曲线,称为规划(P)的“中心线”。 1984年,Karmarkar用对数函数为罚函数,把线性规划问题化为无约束最优化问题,然后,使用带投影变换的最速下降法求解,创造了一个新的线性规划多项式算法,从而掀起了深入研究“内点法”的热潮。Karmarkar算法的迭代次数为O(nL),计算复杂性为O(n~(3.5)L),其中L表示问题的数据输入计算机时的编码长度,在复杂性理论中,称为问题的规模。紧接     

A primal-dual interior-point algorithm for quadratic programming

In this paper we propose a primal-dual interior-point method for large, sparse, quadratic programming problems. The method is based on a reduction presented by Gonzalez-Lima, Wei, and Wolkowicz [14] in order to solve the linear systems arising in the primal-dual methods for linear programming. The main features of this reduction is that it is well defined at the solution set and it preserves sparsity. These properties add robustness and stability to the algorithm and very accurate solutions can be obtained. We describe the method and we consider different reductions using the same framework. We discuss the relationship of our proposals and the one used in the LOQO code. We compare and study the different approaches by performing numerical experimentation using problems from the Maros and Meszaros collection. We also include a brief discussion on the meaning and effect of ill-conditioning when solving linear systems.This work was partially supported by DID-USB (GID-001).     

Primal-dual algorithms for linear programming based on the logarithmic barrier method

In this paper, we deal with primal-dual interior point methods for solving the linear programming problem. We present a short-step and a long-step path-following primal-dual method and derive polynomial-time bounds for both methods. The iteration bounds are as usual in the existing literature, namely iterations for the short-step variant andO(nL) for the long-step variant. In the analysis of both variants, we use a new proximity measure, which is closely related to the Euclidean norm of the scaled search direction vectors. The analysis of the long-step method depends strongly on the fact that the usual search directions form a descent direction for the so-called primal-dual logarithmic barrier function.This work was supported by a research grant from Shell, by the Dutch Organization for Scientific Research (NWO) Grant 611-304-028, by the Hungarian National Research Foundation Grant OTKA-2116, and by the Swiss National Foundation for Scientific Research Grant 12-26434.89.     

Primal-dual proximal point algorithm for linearly constrained convex programming problems

A primal-dual version of the proximal point algorithm is developed for linearly constrained convex programming problems. The algorithm is an iterative method to find a saddle point of the Lagrangian of the problem. At each iteration of the algorithm, we compute an approximate saddle point of the Lagrangian function augmented by quadratic proximal terms of both primal and dual variables. Specifically, we first minimize the function with respect to the primal variables and then approximately maximize the resulting function of the dual variables. The merit of this approach exists in the fact that the latter function is differentiable and the maximization of this function is subject to no constraints. We discuss convergence properties of the algorithm and report some numerical results for network flow problems with separable quadratic costs.     

A variant of Karmarkar's linear programming algorithm for problems in standard form

This paper presents a variant of Karmarkar's linear programming algorithm that works directly with problems expressed in standard form and requires no a priori knowledge of the optimal objective function value. Rather, it uses a variation on Todd and Burrell's approach to compute ever better bounds on the optimal value, and it can be run as a prima-dual algorithm that produces sequences of primal and dual feasible solutions whose objective function values convege to this value. The only restrictive assumption is that the feasible region is bounded with a nonempty interior; compactness of the feasible region can be relaxed to compactness of the (nonempty) set of optimal solutions.     

Simplified infeasible interior-point algorithm for linear optimization based on a simple function

Based on a similar kernel function, we present an infeasible version of the interior-point algorithm for linear optimization introduced by Wang et al. (2016). The property of exponential convexity is still important to simplify the analysis of the algorithm. The iteration bound coincides with the currently best iteration bound for infeasible interior-point algorithms.     

Superlinear and quadratic convergence of primal-dual interior-point methods for linear programming revisited

Recently, Zhang, Tapia, and Dennis (Ref. 1) produced a superlinear and quadratic convergence theory for the duality gap sequence in primal-dual interior-point methods for linear programming. In this theory, a basic assumption for superlinear convergence is the convergence of the iteration sequence; and a basic assumption for quadratic convergence is nondegeneracy. Several recent research projects have either used or built on this theory under one or both of the above-mentioned assumptions. In this paper, we remove both assumptions from the Zhang-Tapia-Dennis theory.Dedicated to the Memory of Magnus R. Hestenes, 1906–1991This research was supported in part by NSF Cooperative Agreement CCR-88-09615 and was initiated while the first author was at Rice University as a Visiting Member of the Center for Research in Parallel Computation.The authors thank Yinyu Ye for constructive comments and discussions concerning this material.This author was supported in part by NSF Grant DMS-91-02761 and DOE Grant DE-FG05-91-ER25100.This author was supported in part by AFOSR Grant 89-0363, DOE Grant DE-FG05-86-ER25017, and ARO Grant 9DAAL03-90-G-0093.     

A full-Newton step infeasible interior-point method for linear optimization based on a trigonometric kernel function

An infeasible interior-point method (IIPM) for solving linear optimization problems based on a kernel function with trigonometric barrier term is analysed. In each iteration, the algorithm involves a feasibility step and several centring steps. The centring step is based on classical Newton’s direction, while we used a kernel function with trigonometric barrier term in the algorithm to induce the feasibility step. The complexity result coincides with the best-known iteration bound for IIPMs. To our knowledge, this is the first full-Newton step IIPM based on a kernel function with trigonometric barrier term.     

A modified layered-step interior-point algorithm for linear programming

The layered-step interior-point algorithm was introduced by Vavasis and Ye. The algorithm accelerates the path following interior-point algorithm and its arithmetic complexity depends only on the coefficient matrixA. The main drawback of the algorithm is the use of an unknown big constant in computing the search direction and to initiate the algorithm. We propose a modified layered-step interior-point algorithm which does not use the big constant in computing the search direction. The constant is required only for initialization when a well-centered feasible solution is not available, and it is not required if an upper bound on the norm of a primal—dual optimal solution is known in advance. The complexity of the simplified algorithm is the same as that of Vavasis and Ye. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Research supported in part by ONR contract N00014-94-C-0007 and the Grant-in-Aid for Scientific Research (C) 08680478 and the Grant-in-Aid for Encouragement of Young Scientists (A) 08780227 of the Ministry of Science, Education and Culture of Japan. This research was partially done while S. Mizuno and T. Tsuchiya were visiting IBM Almaden Research Center in the summer of 1995.