Search

In this paper, we present a long-step infeasible primal-dual path-following algorithm for convex quadratic programming (CQP) whose search directions are computed by means of a preconditioned iterative linear solver. In contrast to the authors' previous paper [Z. Lu, R.D.C. Monteiro, and J.W. O'Neal. An iterative solver-based infeasible primal-dual path-following algorithm for convex quadratic programming, SIAM J. Optim. 17(1) (2006), pp. 287-310], we propose a new linear system, which we refer to as the hybrid augmented normal equation (HANE), to determine the primal-dual search directions. Since the iterative linear solver can only generate an approximate solution to the HANE, this solution does not yield a primal-dual search direction satisfying all equations of the primal-dual Newton system. We propose a recipe to compute an inexact primal-dual search direction, based on a suitable approximate solution to the HANE. The second difference between this paper and [Z. Lu, R.D.C. Monteiro, and J.W. O'Neal. An iterative solver-based infeasible primal-dual path-following algorithm for convex quadratic programming, SIAM J. Optim. 17(1)(2006), pp. 287-310] is that, instead of using the maximum weight basis (MWB) preconditioner in the aforesaid recipe for constructing the inexact search direction, this paper proposes the use of any member of a whole class of preconditioners, of which the MWB preconditioner is just a special case. The proposed recipe allows us to: (i) establish a polynomial bound on the number of iterations performed by our path-following algorithm and (ii) establish a uniform bound, depending on the quality of the preconditioner, on the number of iterations performed by the iterative solver. [ABSTRACT FROM AUTHOR]

The contribution of this article is to describe a general technique to solve some classes of large but sparse semidefinite problems via a robust primal-dual interior-point technique, which uses an inexact Gauss-Newton approach with a matrix free preconditioned conjugate gradient method. This approach avoids the ill-conditioning pitfalls that result from symmetrization and from forming the so-called normal equations, while maintaining the primal-dual framework. First, we apply a preprocessing step that reduces the optimality conditions before linearization and results in a single, well-conditioned, overdetermined bilinear operator equation. We then use preconditioned conjugate-gradients to approximately solve the linearization at every step of a path-following approach. We do not form the matrix representation of the linearization. In addition, once close to the optimal solution, we apply a crossover technique after which the iterates are no longer forced to be positive definite. In the experimental part of this article, we use Max-Cut to illustrate the technique. We describe preconditioners that exploit the operator structure of the constraints and show how the crossover can be effective in practice and how it allows for warm starts. In all cases we obtain high-accuracy solutions. * Research Report CORR 2001-49 a preliminary version of this paper, Semidefinite Programming and Some Closest Matrix Approximation Problems , was presented at the 1st Annual McMaster Optimization Conference (MOPTA 01), August 2-4, 2001 Hamilton, Ontario. URL for paper and MATLAB programs: http://orion.math.uwaterloo.ca/∼hwolkowi/henry/reports/ABSTRACTS.html. [ABSTRACT FROM AUTHOR]

This paper presents a projection-based approach for solving conic feasibility problems. To find a point in the intersection of a cone and an affine subspace, we simply project a point onto this intersection. This projection is computed by dual algorithms operating a sequence of projections onto the cone and generalizing the alternating projection method. We release an easy-to-use Matlab package implementing an elementary dual-projection algorithm. Numerical experiments show that, for solving some semidefinite feasibility problems, the package is competitive with sophisticated conic programming software. We also provide a particular treatment for semidefinite feasibility problems modelling polynomial sum-of-squares decomposition problems. [ABSTRACT FROM AUTHOR]

Derivative-based solution algorithms for optimal control problems of time-dependent nonlinear PDE systems require multiple solutions of backward-in-time adjoint systems. Since these adjoint systems, in general, depend on the primal state, and thus on forward information, the storage requirement for such solution algorithms is very large. This paper proposes stable and memory-efficient checkpointing techniques for evaluating gradients and Hessian times increment for such solution algorithms, and presents numerical tests with the instationary Navier-Stokes system which demonstrate that huge memory savings are achieved by the proposed approach while the increase in runtime is moderate. More precisely, a memory reduction of two orders of magnitude causes only a slow down factor of two in run-time. [ABSTRACT FROM AUTHOR]

In this paper we propose a filter-trust-region algorithm for solving nonlinear optimization problems with simple bounds. It extends the technique of Gould et al. [Gould, N.I.M. Sainvitu, C. and Toint, Ph.L., 2005, A filter-trust-region method for unconstrained optimization. SIAM Journal on Optimization, 16(2), 341-357.] designed for unconstrained optimization problems. The two main ingredients of the method are a filter-trust-region algorithm and a gradient-projection method. The algorithm is shown to be globally convergent to at least one first-order critical point. Numerical experiments on a large set of problems are also reported. [ABSTRACT FROM AUTHOR]

SDP (SemiDefinite Programming) is one of the most attractive optimization models. It has many applications from various fields such as control theory, combinatorial and robust optimization, and quantum chemistry. The SDPA (SemiDefinite Programming Algorithm) is a software package for solving general SDPs based on primal--dual interior-point methods with the HRVW/KSH/M search direction. It is written in C with the help of LAPACK for numerical linear algebra for dense matrix computation. The purpose of this paper is to present a brief description of the latest version of the SDPA and its high performance for large scale problems through numerical experiments and comparisons with some other major software packages for general SDPs. [ABSTRACT FROM AUTHOR]

Computational algebraic approaches using Gröbner bases or standard pairs of toric ideals to integer programming problems have been studied in recent years. In combinatorial optimization problems, matrices of Lawrence type arise in many situations as capacitated integer programming problems and some multidimensional transportation problems. While the reduced Gröbner basis of the toric ideal for the Lawrence lifting Λ(A) of A relates a set of circuits of the vector matroid defined by a matrix A, a relation of the vector matroid with a standard pair decomposition for Λ(A) is not well-known. In this paper, we show a bijection between the set of bases of a matrix A and the set of standard pairs Λ(A) which relates with the dual feasible bases for a linear programming problem with a coefficient matrix Λ(A). This relation gives a matroidal structure of standard pairs in a sense that an adjacency of standard pairs corresponds to that of vertices in a base polyhedron of a vector matroid. As applications to Lawrence type integer programming problems, we analyze the number of dual feasible bases for minimum cost flow problems and for multidimensional transportation problems of type 2 × … × 2 × M × N. [ABSTRACT FROM AUTHOR]