Solving nested-constraint resource allocation problems with an interior point method

Efficient methods for convex resource allocation problems usually exploit algebraic properties of the objective function. For problems with nested constraints, we show that constraint sparsity structure alone allows rapid solution with a general interior point method. The key is a special-purpose linear system solver requiring only linear time in the problem dimensions. Computational tests show that this approach outperforms the previous best algebraically specialized methods.     

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.     

Using groups in the splitting preconditioner computation for interior point methods

Interior point methods usually rely on iterative methods to solve the linear systems of large scale problems. The paper proposes a hybrid strategy using groups for the preconditioning of these iterative methods. The objective is to solve large scale linear programming problems more efficiently by a faster and robust computation of the preconditioner. In these problems, the coefficient matrix of the linear system becomes ill conditioned during the interior point iterations, causing numerical difficulties to find a solution, mainly with iterative methods. Therefore, the use of preconditioners is a mandatory requirement to achieve successful results. The paper proposes the use of a new columns ordering for the splitting preconditioner computation, exploring the sparsity of the original matrix and the concepts of groups. This new preconditioner is designed specially for the final interior point iterations; a hybrid approach with the controlled Cholesky factorization preconditioner is adopted. Case studies show that the proposed methodology reduces the computational times with the same quality of solutions when compared to previous reference approaches. Furthermore, the benefits are obtained while preserving the sparse structure of the systems. These results highlight the suitability of the proposed approach for large scale problems.     

Application of lower bound direct method to engineering structures

Direct methods provide elegant and efficient approaches for the prediction of the long-term behaviour of engineering structures under arbitrary complex loading independent of the number of loading cycles. The lower bound direct method leads to a constrained non-linear convex problem in conjunction with finite element methods, which necessitates a very large number of optimization variables and a large amount of computer memory. To solve this large-scale optimization problem, we first reformulate it in a simpler equivalent convex program with easily exploitable sparsity structure. The interior point with DC regularization algorithm (IPDCA) using quasi definite matrix techniques is then used for its solution. The numerical results obtained by this algorithm will be compared with those obtained by general standard code Lancelot. They show the robustness, the efficiency of IPDCA and in particular its great superiority with respect to Lancelot.     

An interior point method for quadratic programs based on conjugate projected gradients

We propose an interior point method for large-scale convex quadratic programming where no assumptions are made about the sparsity structure of the quadratic coefficient matrixQ. The interior point method we describe is a doubly iterative algorithm that invokes aconjugate projected gradient procedure to obtain the search direction. The effect is thatQ appears in a conjugate direction routine rather than in a matrix factorization. By doing this, the matrices to be factored have the same nonzero structure as those in linear programming. Further, one variant of this method istheoretically convergent with onlyone matrix factorization throughout the procedure.     

A new long-step interior point algorithm for linear programming based on the algebraic equivalent transformation

In this paper, we investigate a new primal-dual long-step interior point algorithm for linear optimization. Based on the step size, interior point algorithms can be divided into two main groups, short-step, and long-step methods. In practice, long-step variants perform better, but usually, a better theoretical complexity can be achieved for the short-step methods. One of the exceptions is the large-update algorithm of Ai and Zhang. The new wide neighborhood and the main characteristics of the presented algorithm are based on their approach. In addition, we use the algebraic equivalent transformation technique of Darvay to determine new modified search directions for our method. We show that the new long-step algorithm is convergent and has the best known iteration complexity of short-step variants. We present our numerical results and compare the performance of our algorithm with two previously introduced Ai-Zhang type interior point algorithms on a set of linear programming test problems from the Netlib library.

     

A factorization with update procedures for a KKT matrix arising in direct optimal control

Quadratic programs obtained for optimal control problems of dynamic or discrete-time processes usually involve highly block structured Hessian and constraints matrices, to be exploited by efficient numerical methods. In interior point methods, this is elegantly achieved by the widespread availability of advanced sparse symmetric indefinite factorization codes. For active set methods, however, conventional dense matrix techniques suffer from the need to update base matrices in every active set iteration, thereby loosing the sparsity structure after a few updates. This contribution presents a new factorization of a KKT matrix arising in active set methods for optimal control. It fully respects the block structure without any fill-in. For this factorization, matrix updates are derived for all cases of active set changes. This allows for the design of a highly efficient block structured active set method for optimal control and model predictive control problems with long horizons or many control parameters.     

Enumerating a subset of the integer points inside a Minkowski sum

Sparse elimination exploits the structure of algebraic equations in order to obtain tighter bounds on the number of roots and better complexity in numerically approximating them. The model of sparsity is of combinatorial nature, thus leading to certain problems in general-dimensional convex geometry. This work addresses one such problem, namely the computation of a certain subset of integer points in the interior of integer convex polytopes. These polytopes are Minkowski sums, but avoiding their explicit construction is precisely one of the main features of the algorithm. Complexity bounds for our algorithm are derived under certain hypotheses, in terms of output-size and the sparsity parameters. A public domain implementation is described and its performance studied. Linear optimization lies at the inner loop of the algorithm, hence we analyze the structure of the linear programs and compare different implementations.     

Overlapping Domain Decomposition Algorithms for General Sparse Matrices

Domain decomposition methods for finite element problems using a partition based on the underlying finite element mesh have been extensively studied. In this paper, we discuss algebraic extensions of the class of overlapping domain decomposition algorithms for general sparse matrices. The subproblems are created with an overlapping partition of the graph corresponding to the sparsity structure of the matrix. These algebraic domain decomposition methods are especially useful for unstructured mesh problems. We also discuss some difficulties encountered in the algebraic extension, particularly the issues related to the coarse solver.     

Product-form Cholesky factorization in interior point methods for second-order cone programming

Second-order cone programming (SOCP) problems are typically solved by interior point methods. As in linear programming (LP), interior point methods can, in theory, solve SOCPs in polynomial time and can, in practice, exploit sparsity in the problem data. Specifically, when cones of large dimension are present, the density that results in the normal equations that are solved at each iteration can be remedied in a manner similar to the treatment of dense columns in an LP. Here we propose a product-form Cholesky factorization (PFCF) approach, and show that it is more numerically stable than the alternative Sherman-Morrison-Woodbury approach. We derive several PFCF variants and compare their theoretical perfomance. Finally, we prove that the elements of L in the Cholesky factorizations LDL^T that arise in interior point methods for SOCP are uniformly bounded as the duality gap tends to zero as long as the iterates remain is some conic neighborhood of the cental path.Mathematics Subject Classification (1991): 90C25, 90C51, 15A23Research supported in part by NSF Grants CDA 97-26385, DMS 01-04282, ONR Grant N000140310514 and DOE Grant GE-FG01-92ER-25126     

A specialized primal-dual interior point method for the plastic truss layout optimization

We are concerned with solving linear programming problems arising in the plastic truss layout optimization. We follow the ground structure approach with all possible connections between the nodal points. For very dense ground structures, the solutions of such problems converge to the so-called generalized Michell trusses. Clearly, solving the problems for large nodal densities can be computationally prohibitive due to the resulting huge size of the optimization problems. A technique called member adding that has correspondence to column generation is used to produce a sequence of smaller sub-problems that ultimately approximate the original problem. Although these sub-problems are significantly smaller than the full formulation, they still remain large and require computationally efficient solution techniques. In this article, we present a special purpose primal-dual interior point method tuned to such problems. It exploits the algebraic structure of the problems to reduce the normal equations originating from the algorithm to much smaller linear equation systems. Moreover, these systems are solved using iterative methods. Finally, due to high degree of similarity among the sub-problems after preforming few member adding iterations, the method uses a warm-start strategy and achieves convergence within fewer interior point iterations. The efficiency and robustness of the method are demonstrated with several numerical experiments.     

An implementation of a parallel primal-dual interior point method for block-structured linear programs

An implementation of the primal-dual predictor-corrector interior point method is specialized to solve block-structured linear programs with side constraints. The block structure of the constraint matrix is exploited via parallel computation. The side constraints require the Cholesky factorization of a dense matrix, where a method that exploits parallelism for the dense Cholesky factorization is used. For testing, multicommodity flow problems were used. The resulting implementation is 65%–90% efficient, depending on the problem instance. For a problem with K commodities, an approximate speedup for the interior point method of 0.8K is realized.     

Convergence and round-off errors in a two-dimensional eigenvalue problem using spectral methods and Arnoldi–Chebyshev algorithm

An efficient way of solving 2D stability problems in fluid mechanics is to use, after discretization of the equations that cast the problem in the form of a generalized eigenvalue problem, the incomplete Arnoldi–Chebyshev method. This method preserves the banded structure sparsity of matrices of the algebraic eigenvalue problem and thus decreases memory use and CPU time consumption.     

Feasible Interior Methods Using Slacks for Nonlinear Optimization

A slack-based feasible interior point method is described which can be derived as a modification of infeasible methods. The modification is minor for most line search methods, but trust region methods require special attention. It is shown how the Cauchy point, which is often computed in trust region methods, must be modified so that the feasible method is effective for problems containing both equality and inequality constraints. The relationship between slack-based methods and traditional feasible methods is discussed. Numerical results using the KNITRO package show the relative performance of feasible versus infeasible interior point methods.     

Interior point methods for optimal control of discrete time systems

We show that recently developed interior point methods for quadratic programming and linear complementarity problems can be put to use in solving discrete-time optimal control problems, with general pointwise constraints on states and controls. We describe interior point algorithms for a discrete-time linear-quadratic regulator problem with mixed state/control constraints and show how they can be efficiently-incorporated into an inexact sequential quadratic programming algorithm for nonlinear problems. The key to the efficiency of the interior-point method is the narrow-banded structure of the coefficient matrix which is factorized at each iteration.This research was supported by the Applied Mathematical Sciences Subprogram of the Office of Energy Research, US Department of Energy, under Contract W-31-109-Eng-38.     

基于代数等价变换下的凸二次规划不可行内点算法

基于代数等价变换和在KMM算法的框架基础上,在原始-对偶内点方法的牛顿方程里嵌入一种自调节功能.从而对凸二次规划提出了一种新的迭代方向的不可行内点算法,并证明了算法的全局收敛性.     

Interior‐point methods and preconditioning for PDE‐constrained optimization problems involving sparsity terms

Partial differential equation (PDE)–constrained optimization problems with control or state constraints are challenging from an analytical and numerical perspective. The combination of these constraints with a sparsity‐promoting L¹ term within the objective function requires sophisticated optimization methods. We propose the use of an interior‐point scheme applied to a smoothed reformulation of the discretized problem and illustrate that such a scheme exhibits robust performance with respect to parameter changes. To increase the potency of this method, we introduce fast and efficient preconditioners that enable us to solve problems from a number of PDE applications in low iteration numbers and CPU times, even when the parameters involved are altered dramatically.     

Efficient Management of Multiple Sets to Extract Complex Structures from Mathematical Programs

Most of the applied models written with an algebraic modeling language involve simultaneously several dimensions such as materials, location, time or uncertainty. The information about dimensions available in the algebraic formulation is usually sufficient to retrieve different block structures from mathematical programs. These structured problems can then be solved by adequate solution techniques. To illustrate this idea we focus on stochastic programming problems with recourse. Taking into account both time and uncertainty dimensions of these problems, we are able to retrieve different customized structures in their constraint matrices. We applied the Structure Exploiting Tool to retrieve the structure from models built with the GAMS modeling language. The underlying mathematical programs are solved with the decomposition algorithm that applies interior point methods. The optimization algorithm is run in a sequential and in a parallel computing environment.     

First- and second-order methods for semidefinite programming

 In this paper, we survey the most recent methods that have been developed for the solution of semidefinite programs. We first concentrate on the methods that have been primarily motivated by the interior point (IP) algorithms for linear programming, putting special emphasis in the class of primal-dual path-following algorithms. We also survey methods that have been developed for solving large-scale SDP problems. These include first-order nonlinear programming (NLP) methods and more specialized path-following IP methods which use the (preconditioned) conjugate gradient or residual scheme to compute the Newton direction and the notion of matrix completion to exploit data sparsity. Received: December 16, 2002 / Accepted: May 5, 2003 Published online: May 28, 2003 Key words. semidefinite programming – interior-point methods – polynomial complexity – path-following methods – primal-dual methods – nonlinear programming – Newton method – first-order methods – bundle method – matrix completion The author's research presented in this survey article has been supported in part by NSF through grants INT-9600343, INT-9910084, CCR-9700448, CCR-9902010, CCR-0203113 and ONR through grants N00014-93-1-0234, N00014-94-1-0340 and N00014-03-1-0401. Mathematics Subject Classification (2000): 65K05, 90C06, 90C22, 90C25, 90C30, 90C51     

Efficient Algorithms for Large‐Scale Quadratic Matrix Equations

Quadratic matrix equations and in particular symmetric algebraic Riccati equations play a fundamental role in systems and control theory. Classically, they are solved via methods using their connection to Hamiltonian eigenproblems. Due to the ever‐increasing complexity of the models describing the underlying control problems, new methods are needed that can be used for large‐scale problems. In particular, sparsity of the coefficient matrices, obtained, e.g., from semi‐discretizing partial differential equations to describe the physical process to be controlled, need to be addressed. We briefly review recent approaches based on Krylov subspace methods and discuss a new approach employing a sparse implementation of Newton's method for algebraic Riccati equations.