Convergence Analysis of the Inexact Infeasible Interior-Point Method for Linear Optimization

We present the convergence analysis of the inexact infeasible path-following (IIPF) interior-point algorithm. In this algorithm, the preconditioned conjugate gradient method is used to solve the reduced KKT system (the augmented system). The augmented system is preconditioned by using a block triangular matrix. The KKT system is solved approximately. Therefore, it becomes necessary to study the convergence of the interior-point method for this specific inexact case. We present the convergence analysis of the inexact infeasible path-following (IIPF) algorithm, prove the global convergence of this method and provide complexity analysis. Communicated by Y. Zhang.     

A New Decomposition Technique in Solving Multistage Stochastic Linear Programs by Infeasible Interior Point Methods

Multistage stochastic linear programming (MSLP) is a powerful tool for making decisions under uncertainty. A deterministic equivalent problem of MSLP is a large-scale linear program with nonanticipativity constraints. Recently developed infeasible interior point methods are used to solve the resulting linear program. Technical problems arising from this approach include rank reduction and computation of search directions. The sparsity of the nonanticipativity constraints and the special structure of the problem are exploited by the interior point method. Preliminary numerical results are reported. The study shows that, by combining the infeasible interior point methods and specific decomposition techniques, it is possible to greatly improve the computability of multistage stochastic linear programs.     

On Superlinear Convergence of Infeasible Interior-Point Algorithms for Linearly Constrained Convex Programs

This note derives bounds on the length of the primal-dual affinescaling directions associated with a linearly constrained convexprogram satisfying the following conditions: 1) the problem has asolution satisfying strict complementarity, 2) the Hessian of theobjective function satisfies a certain invariance property. Weillustrate the usefulness of these bounds by establishing thesuperlinear convergence of the algorithm presented in Wright andRalph [22] for solving the optimality conditions associatedwith a linearly constrained convex program satisfying the aboveconditions.     

A New Complexity Analysis for Full-Newton Step Infeasible Interior-Point Algorithm for Horizontal Linear Complementarity Problems

In this paper, we first present a full-Newton step feasible interior-point algorithm for solving horizontal linear complementarity problems. We prove that the full-Newton step to the central path is quadratically convergent. Then, we generalize an infeasible interior-point method for linear optimization to horizontal linear complementarity problems based on new search directions. This algorithm starts from strictly feasible iterates on the central path of a perturbed problem that is produced by a suitable perturbation in the horizontal linear complementarity problem. We use the so-called feasibility steps that find strictly feasible iterates for the next perturbed problem. By using centering steps for the new perturbed problem, we obtain a strictly feasible iterate close enough to the central path of the new perturbed problem. The complexity of the algorithm coincides with the best known iteration bound for infeasible interior-point methods.     

Validated Infeasible Interior-Point Predictor–Corrector Methods for Linear Programming

Many problems arising in practical applications lead to linear programming problems. Hence, they are fundamentally tractable. Recent interior-point methods can exploit problem structure to solve such problems very efficiently. Infeasible interior-point predictor–corrector methods using floating-point arithmetic sometimes compute an approximate solution with duality gap less than a given tolerance even when the problem may not have a solution. We present an efficient verification method for solving linear programming problems which computes a guaranteed enclosure of the optimal solution and which verifies the existence of the solution within the computed interval.     

On the Optimal Correction of Infeasible Systems of Linear Inequalities

We study the optimum correction of infeasible systems of linear inequalities through making minimal changes in the coefficient matrix and the right-hand side vector by using the Frobenius norm. It leads to a special structured unconstrained nonlinear and nonconvex problem, which can be reformulated as a one-dimensional parametric minimization problem such that each objective function corresponds to a trust region subproblem. We show that, under some assumptions, the parametric function is differentiable and strictly unimodal. We present optimally conditions, propose lower and upper bounds on the optimal value and discuss attainability of the optimal value. To solve the original problem, we propose a binary search method accompanied by a type of Newton–Lagrange method for solving the subproblem. The numerical results illustrate the effectiveness of the suggested method.

     

Problem Specification for Linear Programs

A language for specifying linear programs is proposed. The specificationlanguage is designed so as to enable the user to define theinput for a particular linear program in terms of a given tabulardatabase consisting of multidimensional tables.     

An Extension Theorem for Linear Codes

One of the first results one meets in coding theory is that a binary linear [n,k,d] code, whose minimum distance is odd, can be extended to an [n + 1, k, d + 1] code. This is one of the few elementary results about binary codes which does not obviously generalise to q-ary codes. The aim of this paper is to give a simple sufficient condition for a q-ary [n, k, d] code to be extendable to an [n + 1, k, d + 1] code. Applications will be given to the construction and classification of good codes, to proving the non- existence of certain codes, and also an application in finite geometry.     

A Full-Newton Step Infeasible Interior-Point Method for the Special Weighted Linear Complementarity Problem

Journal of Optimization Theory and Applications - As an extension of the complementarity problem (CP), the weighted complementarity problem (wCP) is a large class of equilibrium problems with wide...     

基于半光滑方程的线性规划问题局部灵敏度分析

本文考虑线性规划的局部灵敏度问题.首先用非线性互补函数将线性规翊I问题的KKT系统转化为一个半光滑的方程组,然后利用半光滑函数的性质,得到一个能同时求所有变量(包括对偶变量)关于价值系数c,资源向量b,技术消耗系数aij的局部灵敏度的计算公式.该方法能处理任意特性的最优解(包括严格互补解和退化解)的局部灵敏度分析.具体算例说明了分析方法的应用.     

On the Extendability of Linear Codes

R. Hill and P. Lizak (1995, in “Proc. IEEE Int. Symposium on Inform. Theory, Whistler, Canada,” pp. 345) proved that every [n, k, d]_q code with gcd(d, q)=1 and with all weights congruent to 0 or d (modulo q) is extendable to an [n+1, k, d+1]_q code with all weights congruent to 0 or d+1 (modulo q). We give another elementary geometrical proof of this theorem, which also yields the uniqueness of the extension.     

Z_(p~m)-线性码

给出了含非零码字的任一 Zpm-线性码的生成矩阵形式 (其中 p为素数 ,m为正整数 ) ,推广了文 [1 ]的结论     

Convergence Analysis of an Infeasible Interior Point Algorithm Based on a Regularized Central Path for Linear Complementarity Problems

Most existing interior-point methods for a linear complementarity problem (LCP) require the existence of a strictly feasible point to guarantee that the iterates are bounded. Based on a regularized central path, we present an infeasible interior-point algorithm for LCPs without requiring the strict feasibility condition. The iterates generated by the algorithm are bounded when the problem is a P _* LCP and has a solution. Moreover, when the problem is a monotone LCP and has a solution, we prove that the convergence rate is globally linear and it achieves `-feasibility and `-complementarity in at most O(n ² ln(1/`)) iterations with a properly chosen starting point.     

Linear Programming Bounds for Codes of Small Size

Combining linear programming with the Plotkin–Johnson argument for constant weight codes, we derive upper bounds on the size of codes of lengthnand minimum distanced=(n − j) /2, 0<j<n^1/3.Forj=o(n^1/3)these bounds practically coincide with (are slightly better than) the Tietäväinen bound. Forjfixed and forjproportional ton^1/3, j<n^1/3-(2 /9)ln n,it improves on the earlier known results.     

Extendability of Ternary Linear Codes

There are four diversities for which ternary linear codes of dimension k 3, minimum distance d with gcd(3,d) = 1 are always extendable. Moreover, three of them yield double extendability when d 1 (mod 3). All the diversities are found for ternary linear codes of dimension 3 k 6. An algorithm how to find an extension from a generator matrix is also given.This research has been partially supported by Grant-in-Aid for Scientific Research of the Ministry of Education under Contract Number 304-4508-12640137     

Intersection of Isomorphic Linear Codes

Given an (n, k) linear code over GF(q), the intersection of with a codeπ( ), whereπS_n, is an (n, k₁) code, where max{0, 2k−n}k₁k. The intersection problem is to determine which integers in this range are attainable for a given code . We show that, depending on the structure of the generator matrix of the code, some of the values in this range are attainable. As a consequence we give a complete solution to the intersection problem for most of the interesting linear codes, e.g. cyclic codes, Reed–Muller codes, and most MDS codes.