参数最短路的原始-对偶算法

本文利用原始－对偶方法,对于含参数λ的网络（Ｖ,Ｅ,ｆ_１-λｆ_２）,给出了某一点至其它各点的参数最短路的求解算法,其时间复杂度为 Ｏ（ｎｍ＋ｎ~２ｌｏｇｎ）．     

一种基于邻近点算法的变步长原始-对偶算法

本文考虑求解一种源于信号及图像处理问题的鞍点问题.基于邻近点算法的思想,我们对原始-对偶算法进行改进,构造一种对称正定且可变的邻近项矩阵,得到一种新的原始-对偶算法.新算法可以看成一种邻近点算法,因此它的收敛性易于分析,且无需较强的假设条件.初步实验结果表明,当新算法被应用于求解图像去模糊问题时,和其他几种主流的高效算法相比,新算法能得到较高质量的结果,且计算时间也是有竞争力的.     

基于一个有限罚函数的二阶锥优化的原始-对偶内点算法

本文基于一个有限罚函数,设计了关于二阶锥优化问题的原始-对偶路径跟踪内点算法,由于该罚函数在可行域的边界取有限值,因而它不是常规的罚函数,尽管如此,它良好的解析性质使得我们能分析算法并得到基于大步校正和小步校正方法目前较好的多项式时间复杂性分别为O(N~(1/2)log N log N/ε)和O(N~(1/2)log N/ε),其中N为二阶锥的个数．     

随机容错设施选址问题的原始-对偶近似算法

研究两阶段随机容错设施选址问题,其中需要服务的顾客在第二阶段出现（在第一阶段不知道）．两个阶段中每个设施的开设费用可以不同,设施的开设依赖于阶段和需要服务的顾客集合（称为场景）．并且在出现的场景里的每个顾客都有相同的连接需求,即每个顾客需要由r个不同的设施服务．给定所有可能的场景及相应的概率,目标是在两个阶段分别选取开设的设施集合,将出现场景的顾客连接到r个不同的开设设施上,使得包括设施费用和连接费用的总平均费用最小．根据问题的特定结构,给出了原始。对偶（组合）3-近似算法．     

求解两阶段线性规划的原始-对偶分解算法

本介绍一种求解两阶段线性规划的原始-对偶分解算法。该方法在两方面上明显优于传统分解方法。即具有平衡的分解结构和良好的收敛特性。新分解结构将原问题分解为一对受限制的原始和对偶子问题，每一个子问题都保存有对方以前迭代的所有信息，而在传统的主-子分解结构中。子问题只保留主问题传递来的当前信息。新的迭代机制使两个子问题在迭代过程中始终保持单调改善的收敛特性。在相当一般的条件下，新算法可以在有限次迭代中收敛于预先指定的收敛误差之内。     

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

在原始对偶内点算法的设计和分析中,障碍函数对算法的搜索方法和复杂性起着重要的作用.本文由核函数来确定障碍函数,设计了一个求解半正定规划问题的原始-对偶内点算法.这个障碍函数即可以定义算法新的搜索方向,又度量迭代点与中心路径的距离,同时对算法的复杂性分析起着关键的作用.我们计算了算法的迭代界,得出了关于大步校正法和小步校正法的迭代界,它们分别是O(√n log n 10g n/ε)和O(√n log n/ε),这里n是半正定规划问题的维数.最后,我们根据一个算例,说明了算法的有效性以及对核函数的参数的敏感性.     

一种改进的求解矩阵补全问题的原始-对偶算法

低秩矩阵补全问题作为一类在机器学习和图像处理等信息科学领域中都十分重要的问题已被广泛研究.一阶原始-对偶算法是求解该问题的经典算法之一.然而实际应用中处理的数据往往是大规模的.针对大规模矩阵补全问题,本文在原始-对偶算法的框架下,应用变步长校正技术,提出了一种改进的求解矩阵补全问题的原始-对偶算法.该算法在每一步迭代过程中,首先利用原始-对偶算法对原始变量和对偶变量进行更新,然后采用变步长校正技术对这两块变量进行进一步的校正更新.在一定的假设条件下,证明了新算法的全局收敛性.最后通过求解随机低秩矩阵补全问题及图像修复的实例验证新算法的有效性.     

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

在原始对偶内点算法的设计和分析中,障碍函数对算法的搜索方法和复杂性起着重要的作用。本文由核函数来确定障碍函数,设计了一个求解半正定规划问题的原始。对偶内点算法。这个障碍函数即可以定义算法新的搜索方向,又度量迭代点与中心路径的距离,同时对算法的复杂性分析起着关键的作用。我们计算了算法的迭代界,得出了关于大步校正法和小步校正法的迭代界,它们分别是O（√n log n log n/c）和O（√n log n/ε）,这里n是半正定规划问题的维数。最后,我们根据一个算例,说明了算法的有效性以及对核函数的参数的敏感性。     

求解分段常数图象分割模型的一个快速算法

针对Xue-ChengTai等提出的分段常数图象分割模型,我们提出了一个新的快速求解算法。通过引进一个函数来选择模型中的正则化参数β的值,并判断在迭代过程中何时求解不含惩罚项的泛函F。此函数的引入有效地加速了算法的收敛速度。结合原始-对偶Newton方法来求解总变差最小化问题。数值试验表明新算法具有很快的收敛速度与良好的分割效果,且算法对初始值的要求不高。     

0-对偶预同态的一个充要条件

我们对带零逆半群定义了0-对偶预同态的概念,给出并证明了0-对偶预同态的一个等价条件.     

A splitting primal-dual proximity algorithm for solving composite optimization problems

Our work considers the optimization of the sum of a non-smooth convex function and a finite family of composite convex functions, each one of which is composed of a convex function and a bounded linear operator. This type of problem is associated with many interesting challenges encountered in the image restoration and image reconstruction fields. We developed a splitting primal-dual proximity algorithm to solve this problem. Furthermore, we propose a preconditioned method, of which the iterative parameters are obtained without the need to know some particular operator norm in advance. Theoretical convergence theorems are presented. We then apply the proposed methods to solve a total variation regularization model, in which the L2 data error function is added to the L1 data error function. The main advantageous feature of this model is its capability to combine different loss functions. The numerical results obtained for computed tomography (CT) image reconstruction demonstrated the ability of the proposed algorithm to reconstruct an image with few and sparse projection views while maintaining the image quality.     

A relaxed primal-dual path-following algorithm for linear programming

In this paper, we provide an easily satisfied relaxation condition for the primaldual interior path-following algorithm to solve linear programming problems. It is shown that the relaxed algorithm preserves the property of polynomial-time convergence. The computational results obtained by implementing two versions of the relaxed algorithm with slight modifications clearly demonstrate the potential in reducing computational efforts.Partially supported by the North Carolina Supercomputing Center, the 1993 Cray Research Award, and a National Science Council Research Grant of the Republic of China.     

A primal-dual interior-point algorithm for nonlinear least squares constrained problems

This paper extends prior work by the authors on solving nonlinear least squares unconstrained problems using a factorized quasi-Newton technique. With this aim we use a primal-dual interior-point algorithm for nonconvex nonlinear programming. The factorized quasi-Newton technique is now applied to the Hessian of the Lagrangian function for the transformed problem which is based on a logarithmic barrier formulation. We emphasize the importance of establishing and maintaining symmetric quasi-definiteness of the reduced KKT system. The algorithm then tries to choose a step size that reduces a merit function, and to select a penalty parameter that ensures descent directions along the iterative process. Computational results are included for a variety of least squares constrained problems and preliminary numerical testing indicates that the algorithm is robust and efficient in practice.     

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).     

A primal-dual approximation algorithm for stochastic facility location problem with service installation costs

We consider the stochastic version of the facility location problem with service installation costs. Using the primal-dual technique, we obtain a 7-approximation algorithm.     

A primal-dual trust region algorithm for nonlinear optimization

This paper concerns general (nonconvex) nonlinear optimization when first and second derivatives of the objective and constraint functions are available. The proposed method is based on finding an approximate solution of a sequence of unconstrained subproblems parameterized by a scalar parameter. The objective function of each unconstrained subproblem is an augmented penalty-barrier function that involves both primal and dual variables. Each subproblem is solved using a second-derivative Newton-type method that employs a combined trust region and line search strategy to ensure global convergence. It is shown that the trust-region step can be computed by factorizing a sequence of systems with diagonally-modified primal-dual structure, where the inertia of these systems can be determined without recourse to a special factorization method. This has the benefit that off-the-shelf linear system software can be used at all times, allowing the straightforward extension to large-scale problems. Numerical results are given for problems in the COPS test collection.Mathematics Subject Classification (2000): 49M37, 65F05, 65K05, 90C30This paper is dedicated to Roger Fletcher on the occasion of his 65th birthday     

The Newton Bracketing method for the minimization of convex functions subject to affine constraints

The Newton Bracketing method [Y. Levin, A. Ben-Israel, The Newton Bracketing method for convex minimization, Comput. Optimiz. Appl. 21 (2002) 213-229] for the minimization of convex functions f:Rⁿ→R is extended to affinely constrained convex minimization problems. The results are illustrated for affinely constrained Fermat-Weber location problems.     

A new kernel function yielding the best known iteration bounds for primal-dual interior-point algorithms

Kernel functions play an important role in defining new search directions for primal-dual interior-point algorithm for solving linear optimization problems. In this paper we present a new kernel function which yields an algorithm with the best known complexity bound for both large- and small-update methods.