Volumetric path following algorithms for linear programming

We consider the construction of small step path following algorithms using volumetric, and mixed volumetric-logarithmic, barriers. We establish quadratic convergence of a volumetric centering measure using pure Newton steps, enabling us to use relatively standard proof techniques for several subsequently needed results. Using a mixed volumetric-logarithmic barrier we obtain an O(n ^1/4 m ^1/4 L) iteration algorithm for linear programs withn variables andm inequality constraints, providing an alternative derivation for results first obtained by Vaidya and Atkinson. In addition, we show that the same iteration complexity can be attained while holding the work per iteration to O(n ² m), as opposed to O(nm ²), operations, by avoiding use of the true Hessian of the volumetric barrier. Our analysis also provides a simplified proof of self-concordancy of the volumetric and mixed volumetric-logarithmic barriers, originally due to Nesterov and Nemirovskii. This paper was first presented at the 1994 Faculty Research Seminar “Optimization in Theory and Practice”, at the University of Iowa Center for Advanced Studies.     

A Modified SQP Method and Its Global Convergence

The sequential quadratic programming method developed by Wilson, Han andPowell may fail if the quadratic programming subproblems become infeasibleor if the associated sequence of search directions is unbounded. In [1], Hanand Burke give a modification to this method wherein the QP subproblem isaltered in a way which guarantees that the associated constraint region isnonempty and for which a robust convergence theory is established. In thispaper, we give a modification to the QP subproblem and provide a modifiedSQP method. Under some conditions, we prove that the algorithm eitherterminates at a Kuhn–Tucker point within finite steps or generates aninfinite sequence whose every cluster is a Kuhn–Tucker point.Finally, we give some numerical examples.     

Fractional programming and characterization of some vertices of the feasible region

This paper considers a problem of nonlinear programming in which the objective function is the ratio of two linear functions and the constraints define a bounded and connected feasible region. Using a coordinate transformation, this problem is transformed into a simpler one, whose geometric interpretation is of particular significance. The transformation leads to a characterization of some special vertices of the feasible region from both the theoretical and operational points of view.     

A globally convergent Newton method for solving strongly monotone variational inequalities

Variational inequality problems have been used to formulate and study equilibrium problems, which arise in many fields including economics, operations research and regional sciences. For solving variational inequality problems, various iterative methods such as projection methods and the nonlinear Jacobi method have been developed. These methods are convergent to a solution under certain conditions, but their rates of convergence are typically linear. In this paper we propose to modify the Newton method for variational inequality problems by using a certain differentiable merit function to determine a suitable step length. The purpose of introducing this merit function is to provide some measure of the discrepancy between the solution and the current iterate. It is then shown that, under the strong monotonicity assumption, the method is globally convergent and, under some additional assumptions, the rate of convergence is quadratic. Limited computational experience indicates the high efficiency of the proposed method.     

Balance constraints reduction of large-scale linear programming problems

This paper describes a method and the corresponding algorithms for simplification of large-scale linear programming models. It consists of the elimination of the balance constraints (i.e. constraints with zero RHS term). The idea is to apply some linear transformations to the original problem in order to nullify the balance constraints. These transformations are able to simultaneously eliminate more balance rows. The core of this contribution is the introduction of the reduction matrix and the associated theorems on the equivalent linear programs (original and reduced). The numerical experiments with this method of simplification proved this approach to be beneficial for a large class of LP problems.This research work was done while the first author was at Duisburg University, Mess-, Steuer und Regelungstechnik, Germany, under the greatly appreciated financial assistance given by the Alexander-von-Humboldt Foundation.     

Extended convergence results for the method of multipliers for nonstrictly binding inequality constraints

In this paper, we extend the classical convergence and rate of convergence results for the method of multipliers for equality constrained problems to general inequality constrained problems, without assuming the strict complementarity hypothesis at the local optimal solution. Instead, we consider an alternative second-order sufficient condition for a strict local minimum, which coincides with the standard one in the case of strict complementary slackness. As a consequence, new stopping rules are derived in order to guarantee a local linear rate of convergence for the method, even if the current Lagrangian is only asymptotically minimized in this more general setting. These extended results allow us to broaden the scope of applicability of the method of multipliers, in order to cover all those problems admitting loosely binding constraints at some optimal solution. This fact is not meaningless, since in practice this kind of problem seems to be more the rule rather than the exception.In proving the different results, we follow the classical primaldual approach to the method of multipliers, considering the approximate minimizers for the original augmented Lagrangian as the exact solutions for some adequate approximate augmented Lagrangian. In particular, we prove a general uniform continuity property concerning both their primal and their dual optimal solution set maps, a property that could be useful beyond the scope of this paper. This approach leads to very simple proofs of the preliminary results and to a straight-forward proof of the main results.The author gratefully acknowledges the referees for their helpful comments and remarks. This research was supported by FONDECYT (Fondo Nacional de Desarrollo Científico y Technológico de Chile).     

Determination of the portfolio selection for a property-liability insurance company

This paper presents an analysis of a portfolio model which can be used to assist a property-liability insurance company in determining the optimal composition of the insurance and investment portfolios. By introducing insurer's threshold risk and relaxing some non-realistic assumptions made in traditional chance constraint insurance and investment portfolio models, we propose a method for an insurer to maximize his return threshold for a given threshold risk level. This proposed model can be used to optimize the composition of underwriting and investment portfolios regarding the insurer's threshold risk level, as well as to generate the efficient frontier by adjusting insurer's threshold risk levels. A numerical example is given based on the industry's aggregated data for a sixteen year period.     

RANDOM EDGE can be exponential on abstract cubes

We prove that RANDOM EDGE, the simplex algorithm that always chooses a random improving edge to proceed on, can take a mildly exponential number of steps in the model of abstract objective functions (introduced by Williamson Hoke [Completely unimodal numberings of a simple polytope, Discrete Appl. Math. 20 (1988) 69-81.] and by Kalai [A simple way to tell a simple polytope from its graph, J. Combin. Theory Ser. A 49(2) (1988) 381-383.] under different names). We define an abstract objective function on the n-dimensional cube for which the algorithm, started at a random vertex, needs at least exp(const·n^1/3) steps with high probability. The best previous lower bound was quadratic. So in order for RANDOM EDGE to succeed in polynomial time, geometry must help.     

基于几何不变量的蛋白质三维分子结构比对

为了解决蛋白质三维结构比对需要处理大量的旋转、平移变换，直接用动态规划将变得十分繁琐这一问题，在保留蛋白质空间结构属性特征的基础上，对蛋白质三维数据进行了预先的处理．通过计算蛋白质结构在旋转和平移下的几何不变量，将蛋白质的三维结构坐标变换为具有旋转、平移不变性的一维序列．进一步给出了“距离”以及“相似得分”的定义．在此基础上采用动态规划方法给出了新的蛋白质结构比对算法．对专家分类的蛋白质结构数据库进行测试，结果显示准确、快速．     

A constructive characterization of the split closure of a mixed integer linear program

Two independent proofs of the polyhedrality of the split closure of mixed integer linear program have been previously presented. Unfortunately neither of these proofs is constructive. In this paper, we present a constructive version of this proof. We also show that split cuts dominate a family of inequalities introduced by Köppe and Weismantel.