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]

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]

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]

We present software for investigations with cut-generating functions in the Gomory-Johnson model and extensions, implemented in the computer algebra system SageMath. [ABSTRACT FROM AUTHOR]

Constructing a feasible solution, where the focus is on 'hard' constraints only, is an important part of solving timetabling problems. For the University Course Timetabling Problem, we propose a heuristic algorithm to schedule events to timeslots based on cliques, each representing a set of events that could be scheduled in the same timeslot, which the algorithm constructs. Our algorithm has been tested on a set of well-known instances, and the experimental results show that our algorithm is efficient and can compete with other effective algorithms. [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]

Based on the pivot selection rule [Anstreicher, K.M. and Terlaky, T., 1994, A monotonic build-up simplex algorithm for linear programming. Operations Research, 42, 556-561.] we define a new monotonic build-up (MBU) simplex algorithm for linear feasibility problems. An mK upper bound for the iteration bound of our algorithm is given under a weak non-degeneracy assumption, where K is determined by the input data of the problem and m is the number of constraints. The constant K cannot be bounded in general by a polynomial of the bit length of the input data since it is related to the determinants (of the pivot tableau) with the highest absolute value. An interesting local property of degeneracy led us to construct a new recursive procedure to handle strongly degenerate problems as well. Analogous complexity bounds for the linear programming versions of MBU and the first phase of the simplex method can be proved under our weak non-degeneracy assumption. [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]

We present a nonlinear least-square formulation for the second-order cone complementarity problem based on the Fischer-Burmeister (FB) function and the plus function. This formulation has two-fold advantages. First, the operator involved in the over-determined system of equations inherits the favourable properties of the FB function for local convergence, for example, the (strong) semi-smoothness; second, the natural merit function of the over-determined system of equations share all the nice features of the class of merit functions fYF studied in [J.-S. Chen and P. Tseng, An unconstrained smooth minimization reformulation of the second-order cone complementarity problem, Math. Program. 104 (2005), pp. 293-327] for global convergence. We propose a semi-smooth Levenberg-Marquardt method to solve the arising over-determined system of equations, and establish the global and local convergence results. Among others, the superlinear (quadratic) rate of convergence is obtained under strict complementarity of the solution and a local error bound assumption, respectively. Numerical results verify the advantages of the least-square reformulation for difficult problems. [ABSTRACT FROM AUTHOR]

The Levenberg-Marquardt method is a popular method for both optimization problems and equilibrium problems in dynamical systems. In this article, we study the convergence properties of the Levenberg-Marquardt method with the standard matrix update scheme. In our global convergence proof, we relax the condition that update matrices be bounded, and only require that their norms increase at most linearly. Furthermore, we analyze its local convergence for the uniformly convex function. In this case, the Levenberg-Marquardt method has superlinear convergence, and the initial matrix can be chosen arbitrarily for the Broyden-Fletcher-Goldfarb-Shanno (BFGS) formula. [ABSTRACT FROM AUTHOR]

Interior point (IP) algorithms for Min Cost Flow (MCF) problems have been shown to be competitive with combinatorial approaches, at least on some problem classes and for very large instances. This is in part due to availability of specialized crossover routines for MCF; these allow early termination of the IP approach, sparing it with the final iterations where the Karush Kuhn-Tucker (KKT) systems become more difficult to solve. As the crossover procedures are nothing but combinatorial approaches to MCF that are only allowed to perform few iterations, the IP algorithm can be seen as a complex 'multiple crash start' routine for the combinatorial ones. We report our experiments of allowing one primal-dual combinatorial algorithm to MCF to perform as many iterations as required to solve the problem after being warm-started by an IP approach. Our results show that the efficiency of the combined approach critically depends on the accurate selection of a set of parameters among very many possible ones, for which designing accurate guidelines appears not to be an easy task; however, they also show that the combined approach can be competitive with the original combinatorial algorithm, at least on some 'difficult' instances. [ABSTRACT FROM AUTHOR]

On-board model predictive control of a nonlinear dynamical system often involves linearizing the nonlinear dynamics and posing a quadratic program to stay close to a desired profile of outputs. As on-board control requires computing a reliable solution in a robust manner in real time, the quadratic programming algorithm needs to use linear algebra optimally. This article describes an active set algorithm which exploits a ‘hot start’ for the set of binding constraints at optimality along with efficient linear algebra to make rapid progress towards the solution. Furthermore, the linear algebra is designed to deal with degenerate constraints, because the required factorizations are performed and because degeneracy emerges, and not via a mostly unnecessary pre-process step. Computational results are presented for controlling the deceleration of a large commercial aircraft engine. [ABSTRACT FROM AUTHOR]

We propose a pivoting procedure for a class of second-order cone programming (SOCP) problems having one second-order cone, but possibly with additional non-negative variables. We introduce a dictionary, basic variables, nonbasic variables, and other necessary concepts to define a pivot for this class of SOCP problems. In a pivot, two-dimensional SOCP subproblems are solved to decide which variables should be entering or leaving the basis. Under a nondegeneracy assumption, we prove that the objective function value is strictly decreasing by a pivot unless the current basic solution is optimal. We also propose an algorithm using the pivoting procedure which has a global convergence property. [ABSTRACT FROM AUTHOR]

A new ‘matrix-free’ algorithm for the solution of linear inequality constrained, large-scale trust-region subproblems is presented. The matrix-free nature of the algorithm eliminates the need for any matrix factorizations and only requires matrix–vector products. Numerical results that demonstrate the viability of the approach are included. [ABSTRACT FROM AUTHOR]

We address numerical optimization algorithms for solving nonlinear least squares problems that lack well-defined solutions, in particular discrete parameter estimation problems. We present algorithms based on the Gauss-Newton method for both exactly and almost rank-deficient problems. Merit functions proposed have good global convergence properties. Numerical results that confirm local convergence results are presented. [ABSTRACT FROM AUTHOR]

The trust region (TR) subproblem (the minimization of a quadratic objective subject to one quadratic constraint and denoted TRS) has many applications in diverse areas, e.g., function minimization, sequential quadratic programming, regularization, ridge regression, and discrete optimization. In particular, it determines the step in TR algorithms for function minimization. Trust region algorithms are popular for their strong convergence properties. However, a drawback has been the inability to exploit sparsity as well as the difficulty in dealing with the so-called hard case. These concerns have been addressed by recent advances in the theory and algorithmic development. In particular, this has allowed Lanczos techniques to replace Cholesky factorizations. This article provides an in depth study of TRS and its properties as well as a survey of recent advances. We emphasize large scale problems and robustness. This is done using semidefinite programming (SDP) and the modern primal-dual approaches as a unifying framework. The SDP framework arises naturally and solves TRS efficiently. In addition, it shows that TRS is always a well-posed problem, i.e., the optimal value and an optimum can be calculated to a given tolerance. We provide both theoretical and empirical evidence to illustrate the strength of the SDP and duality approach. In particular, this includes new insights and techniques for handling the hard case, as well as numerical results on large test problems. [ABSTRACT FROM AUTHOR]