A matrix generation approach for eigenvalue optimization

We study the extension of a column generation technique to nonpolyhedral models. In particular, we study the problem of minimizing the maximum eigenvalue of an affine combination of symmetric matrices. At each step of the algorithm a restricted master problem in the primal space, corresponding to the relaxed dual (original) problem, is formed. A query point is obtained as an approximate analytic center of a bounded set that contains the optimal solution of the dual problem. The original objective function is evaluated at the query point, and depending on its differentiability a column or a matrix is added to the restricted master problem. We discuss the issues of recovering feasibility after the restricted master problem is updated by a column or a matrix. The computational experience of implementing the algorithm on randomly generated problems are reported and the cpu time of the matrix generation algorithm is compared with that of the primal-dual interior point methods on dense and sparse problems using the software SDPT3. Our numerical results illustrate that the matrix generation algorithm outperforms primal-dual interior point methods on dense problems with no structure and also on a class of sparse problems. This work has been completed with the partial support of a summer grant from the College of Business Administration, California State University San Marcos, and the University Professional Development/Research and Creative Activity Grant     

A projective method for structured nonlinear programs

This paper describes a partitioning method for solving a class of structured nonlinear programming problems with block diagonal constraints and a few coupling variables.The special structure of the constraints is used to reduce the given problem by elimination of variables. In variance to other methods proposed previously, this elimination is effected through the use of the general solution to an underdetermined system of linear equations representing the active constraints at a given feasible point. For weakly coupled systems, this arrangement provides a drastic reduction in the number of variables. The solution to the overall problem is obtained by solving a sequence of the reduced nonlinear programs. Primal feasibility is maintained throughout the optimization procedure. Computational experience and results are presented.This paper was presented at the 7 th Mathematical Programming Symposium 1970, The Hague, The Netherlands.This work was supported in part by the National Science Foundation under Research Grant GJ-0362 and in part by the New York Scientific Center, IBM Corporation.     

Determination of optimal vertices from feasible solutions in unimodular linear programming

In this paper we consider a linear programming problem with the underlying matrix unimodular, and the other data integer. Given arbitrary near optimum feasible solutions to the primal and the dual problems, we obtain conditions under which statements can be made about the value of certain variables in optimal vertices. Such results have applications to the problem of determining the stopping criterion in interior point methods like the primal—dual affine scaling method and the path following methods for linear programming.This author's research is partially supported by NSF grant DDM-8921835 and Airforce Grant AFSOR-88-0088.     

Efficient robust optimization for robust control with constraints

This paper proposes an efficient computational technique for the optimal control of linear discrete-time systems subject to bounded disturbances with mixed linear constraints on the states and inputs. The problem of computing an optimal state feedback control policy, given the current state, is non-convex. A recent breakthrough has been the application of robust optimization techniques to reparameterize this problem as a convex program. While the reparameterized problem is theoretically tractable, the number of variables is quadratic in the number of stages or horizon length N and has no apparent exploitable structure, leading to computational time of per iteration of an interior-point method. We focus on the case when the disturbance set is ∞-norm bounded or the linear map of a hypercube, and the cost function involves the minimization of a quadratic cost. Here we make use of state variables to regain a sparse problem structure that is related to the structure of the original problem, that is, the policy optimization problem may be decomposed into a set of coupled finite horizon control problems. This decomposition can then be formulated as a highly structured quadratic program, solvable by primal-dual interior-point methods in which each iteration requires time. This cubic iteration time can be guaranteed using a Riccati-based block factorization technique, which is standard in discrete-time optimal control. Numerical results are presented, using a standard sparse primal-dual interior point solver, that illustrate the efficiency of this approach.     

Exploiting structure in parallel implementation of interior point methods for optimization

OOPS is an object-oriented parallel solver using the primal–dual interior point methods. Its main component is an object-oriented linear algebra library designed to exploit nested block structure that is often present in truly large-scale optimization problems such as those appearing in Stochastic Programming. This is achieved by treating the building blocks of the structured matrices as objects, that can use their inherent linear algebra implementations to efficiently exploit their structure both in a serial and parallel environment. Virtually any nested block-structure can be exploited by representing the matrices defining the problem as a tree build from these objects. OOPS can be run on a wide variety of architectures and has been used to solve a financial planning problem with over 10⁹ decision variables. We give details of supported structures and their implementations. Further we give details of how parallelisation is managed in the object-oriented framework.     

Parallel interior-point solver for structured quadratic programs: Application to financial planning problems

Many practical large-scale optimization problems are not only sparse, but also display some form of block-structure such as primal or dual block angular structure. Often these structures are nested: each block of the coarse top level structure is block-structured itself. Problems with these characteristics appear frequently in stochastic programming but also in other areas such as telecommunication network modelling. We present a linear algebra library tailored for problems with such structure that is used inside an interior point solver for convex quadratic programming problems. Due to its object-oriented design it can be used to exploit virtually any nested block structure arising in practical problems, eliminating the need for highly specialised linear algebra modules needing to be written for every type of problem separately. Through a careful implementation we achieve almost automatic parallelisation of the linear algebra. The efficiency of the approach is illustrated on several problems arising in the financial planning, namely in the asset and liability management. The problems are modelled as multistage decision processes and by nature lead to nested block-structured problems. By taking the variance of the random variables into account the problems become non-separable quadratic programs. A reformulation of the problem is proposed which reduces density of matrices involved and by these means significantly simplifies its solution by an interior point method. The object-oriented parallel solver achieves high efficiency by careful exploitation of the block sparsity of these problems. As a result a problem with over 50 million decision variables is solved in just over 2 hours on a parallel computer with 16 processors. The approach is by nature scalable and the parallel implementation achieves nearly perfect speed-ups on a range of problems. Supported by the Engineering and Physical Sciences Research Council of UK, EPSRC grant GR/R99683/01     

Interior point methods specialized to optimal pump operation costs of water distribution networks

In the water distribution problem the loss is important and the objective function must consider it combined with pump costs. The problem becomes complex because the loss in each branch is as a nonlinear function of water outflow. The objective of this work consists in solving the water distribution problem using interior point methods and to exploit the particular structure of the problem and the specific matrix sparse pattern of the of the resulting linear systems. The interior point methods show to be robust, achieving fast convergence in all instances tested. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Revisiting compressed sensing: exploiting the efficiency of simplex and sparsification methods

We propose two approaches to solve large-scale compressed sensing problems. The first approach uses the parametric simplex method to recover very sparse signals by taking a small number of simplex pivots, while the second approach reformulates the problem using Kronecker products to achieve faster computation via a sparser problem formulation. In particular, we focus on the computational aspects of these methods in compressed sensing. For the first approach, if the true signal is very sparse and we initialize our solution to be the zero vector, then a customized parametric simplex method usually takes a small number of iterations to converge. Our numerical studies show that this approach is 10 times faster than state-of-the-art methods for recovering very sparse signals. The second approach can be used when the sensing matrix is the Kronecker product of two smaller matrices. We show that the best-known sufficient condition for the Kronecker compressed sensing (KCS) strategy to obtain a perfect recovery is more restrictive than the corresponding condition if using the first approach. However, KCS can be formulated as a linear program with a very sparse constraint matrix, whereas the first approach involves a completely dense constraint matrix. Hence, algorithms that benefit from sparse problem representation, such as interior point methods (IPMs), are expected to have computational advantages for the KCS problem. We numerically demonstrate that KCS combined with IPMs is up to 10 times faster than vanilla IPMs and state-of-the-art methods such as \(\ell _1\_\ell _s\) and Mirror Prox regardless of the sparsity level or problem size.     

A control reduced primal interior point method for a class of control constrained optimal control problems

A primal interior point method for control constrained optimal control problems with PDE constraints is considered. Pointwise elimination of the control leads to a homotopy in the remaining state and dual variables, which is addressed by a short step pathfollowing method. The algorithm is applied to the continuous, infinite dimensional problem, where discretization is performed only in the innermost loop when solving linear equations. The a priori elimination of the least regular control permits to obtain the required accuracy with comparatively coarse meshes. Convergence of the method and discretization errors are studied, and the method is illustrated at two numerical examples. Supported by the DFG Research Center Matheon “Mathematics for key technologies” in Berlin. This paper appeared as ZIB Report 04-38.     

Dual multilevel optimization

We study the structure of dual optimization problems associated with linear constraints, bounds on the variables, and separable cost. We show how the separability of the dual cost function is related to the sparsity structure of the linear equations. As a result, techniques for ordering sparse matrices based on nested dissection or graph partitioning can be used to decompose a dual optimization problem into independent subproblems that could be solved in parallel. The performance of a multilevel implementation of the Dual Active Set algorithm is compared with CPLEX Simplex and Barrier codes using Netlib linear programming test problems.      

Local Convergence Behavior of Some Projection-Type Methods for Affine Variational Inequalities

In this paper, we study the local convergence behavior of four projection-type methods for the solution of the affine variational inequality (AVI) problem. It is shown that, if the sequence generated by one of the methods converges to a nondegenerate KKT point of the AVI problem, then after a finite number of iterations, some index sets in the dual variables at each iterative point coincide with the index set of the active constraints in the primal variables at the KKT point. As a consequence, we find that, after finitely many iterations, the four methods need not compute projections and their iterative equations are of reduced dimension.     

Pivot versus interior point methods: Pros and cons

Linear optimization (LO) is the fundamental problem of mathematical optimization. It admits an enormous number of applications in economics, engineering, science and many other fields. The three most significant classes of algorithms for solving LO problems are: pivot, ellipsoid and interior point methods. Because ellipsoid methods are not efficient in practice we will concentrate on the computationally successful simplex and primal–dual interior point methods only, and summarize the pros and cons of these algorithm classes.     

Superlinear and quadratic convergence of some primal-dual interior point methods for constrained optimization

This paper proves local convergence rates of primal-dual interior point methods for general nonlinearly constrained optimization problems. Conditions to be satisfied at a solution are those given by the usual Jacobian uniqueness conditions. Proofs about convergence rates are given for three kinds of step size rules. They are: (i) the step size rule adopted by Zhang et al. in their convergence analysis of a primal-dual interior point method for linear programs, in which they used single step size for primal and dual variables; (ii) the step size rule used in the software package OB1, which uses different step sizes for primal and dual variables; and (iii) the step size rule used by Yamashita for his globally convergent primal-dual interior point method for general constrained optimization problems, which also uses different step sizes for primal and dual variables. Conditions to the barrier parameter and parameters in step size rules are given for each case. For these step size rules, local and quadratic convergence of the Newton method and local and superlinear convergence of the quasi-Newton method are proved. A preliminary version of this paper was presented at the conference “Optimization-Models and Algorithms” held at the Institute of Statistical Mathematics, Tokyo, March 1993.     

相邻多个浅圆弧凹陷地形对平面SH波散射的级数解

本文采用解析法研究相邻多个线圆弧凹陷地形对平面SH波散射问题。文中由分离变量法把相邻多个圆弧凹陷对平面SH波的多重散射表示为各局部坐标中的级数之和,再利用Graf加法公式的内域和外域表达式进一步表示某个局部坐标中的双重无穷级数形式。问题最后可归结为求解一组无穷型的线性代数方程。文末给出了相邻两个等直径浅圆弧凹陷地形的多种深宽比对地面运动的影响的计算结果,并讨论了浅圆凹陷地形对波的屏蔽及它们之间的相互作用。     

Synthesis of a control in the problem of the time-optimal transfer of a point mass to a specified position with zero velocity

The problem of the time-optimal control of the motion of a point mass by means of a force of bounded modulus is considered. It is required that the point be transferred from an arbitrary state of motion to the origin of the system of coordinates with zero velocity. By introducing self-similar conjugate variables, the solution of the two-point problem can be successfully reduced to a search for the optimal root of a certain function, specified analytically. A complete solution of the control problem in the form of a synthesis is obtained using mathematical modelling methods. The feedback coefficients along the unit vectors of the position and velocity vectors are found and a control algorithm and a Bellman function are constructed. Examples using practical initial data are presented.     

A Riccati-based primal interior point solver for multistage stochastic programming

We propose a new method for certain multistage stochastic programs with linear or nonlinear objective function, combining a primal interior point approach with a linear-quadratic control problem over the scenario tree. The latter problem, which is the direction finding problem for the barrier subproblem is solved through dynamic programming using Riccati equations. In this way we combine the low iteration count of interior point methods with an efficient solver for the subproblems. The computational results are promising. We have solved a financial problem with 1,000,000 scenarios, 15,777,740 variables and 16,888,850 constraints in 20 hours on a moderate computer.     

An Exact Solution to Linear Programming Using an Interior Point Method

This paper presents sufficient conditions for optimality of the Linear programming (LP) problem in the neighborhood of an optimal solution, and applies them to an interior point method for solving the LP problem. We show that after a finite number of iterations, an exact solution to the LP problem is obtained by solving a linear system of equations under the assumptions that the primal and dual problems are both nondegenerate, and that the minimum value is bounded. If necessary, the dual solution can also be found.     

Interior dual proximal point algorithm using preconditioned conjugate gradient †

Serial and parallel implementations of the interior dual proximal point algorithm for the solution of large linear programs are described. A preconditioned conjugate gradient method is used to solve the linear system of equations that arises at each interior point interation. Numerical results for a set of multicommodity network flow problems are given. For larger problem preconditioned conjugate gradient method outperforms direct methods of solution. In fact it is impossible to handle very large problems by direct methods     

A warm-start approach for large-scale stochastic linear programs

We describe a way of generating a warm-start point for interior point methods in the context of stochastic programming. Our approach exploits the structural information of the stochastic problem so that it can be seen as a structure-exploiting initial point generator. We solve a small-scale version of the problem corresponding to a reduced event tree and use the solution to generate an advanced starting point for the complete problem. The way we produce a reduced tree tries to capture the important information in the scenario space while keeping the dimension of the corresponding (reduced) deterministic equivalent small. We derive conditions which should be satisfied by the reduced tree to guarantee a successful warm-start of the complete problem. The implementation within the HOPDM and OOPS interior point solvers shows remarkable advantages.