Limiting behavior of the affine scaling continuous trajectories for linear programming problems

We consider the continuous trajectories of the vector field induced by the primal affine scaling algorithm as applied to linear programming problems in standard form. By characterizing these trajectories as solutions of certain parametrized logarithmic barrier families of problems, we show that these trajectories tend to an optimal solution which in general depends on the starting point. By considering the trajectories that arise from the Lagrangian multipliers of the above mentioned logarithmic barrier families of problems, we show that the trajectories of the dual estimates associated with the affine scaling trajectories converge to the so called centered optimal solution of the dual problem. We also present results related to asymptotic direction of the affine scaling trajectories. We briefly discuss how to apply our results to linear programs formulated in formats different from the standard form. Finally, we extend the results to the primal-dual affine scaling algorithm.     

An Interior Point Method for Linear Programming

In this paper we present an interior point method which solves a linear programming problem by using an affine transformation. We prove under certain assumptions that the algorithm converges to an optimal solution even if the dual problem is degenerate as long as the prime is bounded, or to a ray direction if the optimal value of the objective function is unbounded.     

Convergence analysis of the projective scaling algorithm based on a long-step homogeneous affine scaling algorithm

In this paper we give a new convergence analysis of a projective scaling algorithm. We consider a long-step affine scaling algorithm applied to a homogeneous linear programming problem obtained from the original linear programming problem. This algorithm takes a fixed fraction λ≤2/3 of the way towards the boundary of the nonnegative orthant at each iteration. The iteration sequence for the original problem is obtained by pulling back the homogeneous iterates onto the original feasible region with a conical projection, which generates the same search direction as the original projective scaling algorithm at each iterate. The recent convergence results for the long-step affine scaling algorithm by the authors are applied to this algorithm to obtain some convergence results on the projective scaling algorithm. Specifically, we will show (i) polynomiality of the algorithm with complexities of O(nL) and O(n ² L) iterations for λ<2/3 and λ=2/3, respectively; (ii) global covnergence of the algorithm when the optimal face is unbounded; (iii) convergence of the primal iterates to a relative interior point of the optimal face; (iv) convergence of the dual estimates to the analytic center of the dual optimal face; and (v) convergence of the reduction rate of the objective function value to 1−λ.     

一类非单调线性互补问题的高阶仿射尺度算法

In this paper, a new interior point algorithm-high-order atone scaling for a class of nonmonotonic linear complementary problems is developed. On the basis of idea of primal-dual affine scaling method for linear programming , the search direction of our algorithm is obtained by a linear system of equation at each step . We show that, by appropriately choosing the step size, the algorithm has polynomial time complexity. We also give the numberical results of the algorithm for two test problems.     

On the local convergence of adjoint Broyden methods

The numerical solution of nonlinear equation systems is often achieved by so-called quasi-Newton methods. They preserve the rapid local convergence of Newton’s method at a significantly reduced cost per step by successively approximating the system Jacobian though low-rank updates. We analyze two variants of the recently proposed adjoint Broyden update, which for the first time combines the classical least change property with heredity on affine systems. However, the new update does require, the evaluation of so-called adjoint vectors, namely products of the transposed Jacobian with certain dual direction vectors. The resulting quasi-Newton method is linear contravariant in the sense of Deuflhard (Newton methods for nonlinear equations. Springer, Heidelberg, 2006) and it is shown here to be locally and q-superlinearly convergent. Our numerical results on a range of test problems demonstrate that the new method usually outperforms Newton’s and Broyden’s method in terms of runtime and iterations count, respectively. Partially supported by the DFG Research Center Matheon “Mathematics for Key Technologies”, Berlin and the DFG grant WA 1607/2-1.     

水平线性互补问题的广义中心路径跟踪算法

对水平线性互补问题提出了一种广义中心路径跟踪算法.任意的原始-对偶可行内点均可作为算法的初始点.每步迭代选择“仿射步”与“中心步”的凸组合为新的迭代方向,采用使对偶间隙尽可能减小的最大步长.算法的迭代复杂性为O(√nL).     

仿射内点既约投影Hessian算法解非线性约束优化

本文结合非单调内点回代技术,提供了新的仿射信赖域方法解含有非负变量约束和非线性等式约束的优化问题.为求解大规模问题,采用等式约束的Jacobian矩阵的QR分解和两块校正的双边既约Hessian矩阵投影,将问题分解成零空间和值空间两个信赖域子问题.零空间的子问题为通常二次目标函数只带椭球约束的信赖域子问题,而值空间的子问题使用满足信赖域约束参数的值空间投影向量方向.通过引入Fletcher罚函数作为势函数,将由两个子问题结合信赖域策略构成的合成方向,并使用非单调线搜索技术回代于可接受的非负约束内点步长.在合理的条件下,算法具有整体收敛性且两块校正的双边既约Hessian投影法将保持超线性收敛速率.非单调技术将克服高度非线性情况,加快收敛进展.     

Limited Memory Space Dilation and Reduction Algorithms

In this paper, we present variants of Shor and Zhurbenko's r-algorithm, motivated by the memoryless and limited memory updates for differentiable quasi-Newton methods. This well known r-algorithm, which employs a space dilation strategy in the direction of the difference between two successive subgradients, is recognized as being one of the most effective procedures for solving nondifferentiable optimization problems. However, the method needs to store the space dilation matrix and update it at every iteration, resulting in a substantial computational burden for large-sized problems. To circumvent this difficulty, we first propose a memoryless update scheme, which under a suitable choice of parameters, yields a direction of motion that turns out to be a convex combination of two successive anti-subgradients. Moreover, in the space transformation sense, the new update scheme can be viewed as a combination of space dilation and reduction operations. We prove convergence of this new method, and demonstrate how it can be used in conjunction with a variable target value method that allows a practical, convergent implementation of the method. We also examine a memoryless variant that uses a fixed dilation parameter instead of varying degrees of dilation and/or reduction as in the former algorithm, as well as another variant that examines a two-step limited memory update. These variants are tested along with Shor's r-algorithm and also a modified version of a related algorithm due to Polyak that employs a projection onto a pair of Kelley's cutting planes. We use a set of standard test problems from the literature as well as randomly generated dual transportation and assignment problems in our computational experiments. The results exhibit that the proposed space dilation and reduction method and the modification of Polyak's method are competitive, and offer a substantial advantage over the r-algorithm and over the other tested limited memory variants with respect to accuracy as well as effort.     

Extended dual affine planes

We study a class of diagram geometries, achieve a characterization of extended dual affine planes, and embed extended dual affine planes in extended projective planes. The geometries studied are rank 3 diagram geometries such that the residue of a point is a dual net, and the residue of a plane is linear; the dual of such a geometry has partitions on lines and planes which are reminiscent of parallelism of lines and planes of an affine 3-space. Examples of these geometries (some in dual form) include extended dual affine planes, Laguerre planes, 3-nets, and orthogonal arrays of strength 3. Theorem: Any such finite geometry satisfying Buekenhout's intersection property, and such that any two points are coplanar, is an extended dual affine plane (and has order 2, 4, or 10). Theorem: This geometry may be embedded in an extended projective plane of the same order.This research was partially supported by NSF Grant MCS-8102361.     

伪仿射对偶框架

对于给定冗余的仿射框架X（Ф）={Ф1,…,ФL）,存在对偶Y（ψ）={ψ1,…,ψL）,这个对偶可能不是仿射框架,因为它不满足Bessel条件．这样的对偶我们称为伪仿射对偶,并给出伪仿射对偶框架的一种构造公式．     

中约化子空间上的仿射与伪仿射对偶小波标架

本文讨论中约化子空间上的仿射(伪仿射)对偶小波标架.我们建立了仿射系与伪仿射系之间的一个标架 和对偶标架保持定理,并且在没有任何衰减性假设的条件下获得了仿射(伪仿射)对偶小波标架在傅立叶域上的一个刻画.进一步, 我们也给出了仿射Parseval标架在傅立叶域上的刻画.       

一类非单调线性互补问题的高阶Dikin型仿射尺度算法

对于一类非单调线性互补问题提出了一个新算法：高阶Dikin型仿射尺度算法，算法的每步迭代．基于线性规划Dikin原始-对偶算法思想来求解一个线性方程组得到迭代方向，再适当选取步长，得到了算法的多项式复杂性。     

A method for convex minimization based on translated first-order approximations

We describe an algorithm for minimizing convex, not necessarily smooth, functions of several variables, based on a descent direction finding procedure that inherits some characteristics both of standard bundle method and of Wolfe’s conjugate subgradient method. This is obtained by allowing appropriate upward shifting of the affine approximations of the objective function which contribute to the classic definition of the cutting plane function. The algorithm embeds a proximity control strategy. Finite termination is proved at a point satisfying an approximate optimality condition and some numerical results are provided.     

An implementation of Karmarkar's algorithm for linear programming

This paper describes the implementation of power series dual affine scaling variants of Karmarkar's algorithm for linear programming. Based on a continuous version of Karmarkar's algorithm, two variants resulting from first and second order approximations of the continuous trajectory are implemented and tested. Linear programs are expressed in an inequality form, which allows for the inexact computation of the algorithm's direction of improvement, resulting in a significant computational advantage. Implementation issues particular to this family of algorithms, such as treatment of dense columns, are discussed. The code is tested on several standard linear programming problems and compares favorably with the simplex codeMinos 4.0.     

多项式空间的对偶及其在多元插值中的应用

本文通过把域Ｋ上ｎ元多项式环看成域Ｋ上的无限维向量空间Ａ，把ｎ维仿射空间Ｋ＾ｎ中的每一点看成Ａ上的线性泛函，从而Ｋ＾ｎ为对偶空间Ａ＾＊的子集，利用对偶空间的理论得到了一些有趣的理论结果，弄清了Ｋ＾ｎ上点有限拓扑的结构，给出了判定给定结点组是否是给定多项式空间的适定结点组的判定准则，最后还给出了构造理想对偶基的一种算法。     

A characterization of special laguerre planes and extended dual affine planes

A special Laguerre plane is a nondegenerate transversal 3-design such that the residue of each point is a dual affine plane. A special Laguerre plane is equivalent to an optimal code with three information digits and maximal length. An extended dual affine plane is an incidence structure (whose objects will be called points and blocks) such that the residue of each point is a dual affine plane, and each pair of points is in at least one block. Finite extended dual affine planes exist only of order 2, 4, and (dubiously) 10. We show that any finite incidence structure having the residue of each point a dual affine plane either is a transversal 3-design or has a block through each pair of points. Hence theorem: If a finite nondegenerate connected incidence structure has the residue of each point a dual affine plane, then is either an extended dual affine plane or a special Laguerre plane. This research was partially supported by NSF Grant MCS-8102361.     

Dual decomposition of a single-machine scheduling problem

We design a fast ascent direction algorithm for the Lagrangian dual problem of the single-machine scheduling problem of minimizing total weighted completion time subject to precedence constraints. We show that designing such an algorithm is relatively simple if a scheduling problem is formulated in terms of the job completion times rather than as an 0–1 linear program. Also, we show that upon termination of such an ascent direction algorithm we get a dual decomposition of the original problem, which can be exploited to develop approximative and enumerative approaches for it. Computational results exhibit that in our application the ascent direction leads to good Lagrangian lower and upper bounds.     

A least-squares minimum-cost network flow algorithm

Node-arc incidence matrices in network flow problems exhibit several special least-squares properties. We show how these properties can be leveraged in a least-squares primal-dual algorithm for solving minimum-cost network flow problems quickly. Computational results show that the performance of an upper-bounded version of the least-squares minimum-cost network flow algorithm with a special dual update operation is comparable to CPLEX Network and Dual Optimizers for solving a wide range of minimum-cost network flow problems.     

Partial affine system–based frames and dual frames

In this paper, we introduce the notion of partial affine system that is a subset of an affine system. It has potential applications in signal analysis. A general affine system has been extensively studied; however, the partial one has not. The main focus of this paper is on partial affine system–based frames and dual frames. We obtain a necessary condition and a sufficient condition for a partial affine system to be a frame and present a characterization of partial affine system–based dual frames. Some examples are also provided.     

Generalization of Primal—Dual Interior-Point Methods to Convex Optimization Problems in Conic Form

We generalize primal—dual interior-point methods for linear programming (LP) problems to the convex optimization problems in conic form. Previously, the most comprehensive theory of symmetric primal—dual interior-point algorithms was given by Nesterov and Todd for feasible regions expressed as the intersection of a symmetric cone with an affine subspace. In our setting, we allow an arbitrary convex cone in place of the symmetric cone. Even though some of the impressive properties attained by Nesterov—Todd algorithms are impossible in this general setting of convex optimization problems, we show that essentially all primal—dual interior-point algorithms for LP can be extended easily to the general setting. We provide three frameworks for primal—dual algorithms, each framework corresponding to a different level of sophistication in the algorithms. As the level of sophistication increases, we demand better formulations of the feasible solution sets. Our algorithms, in return, attain provably better theoretical properties. We also make a very strong connection to quasi-Newton methods by expressing the square of the symmetric primal—dual linear transformation (the so-called scaling) as a quasi-Newton update in the case of the least sophisticated framework. August 25, 1999. Final version received: March 7, 2001.