User’s Manual for SparseCoLO: Conversion Methods for Sparse Conic-form Linear Optimization Problems

SparseCoLO is a Matlab package for implementing the four conversion methods, proposed by Kim, Kojima, Mevissen, and Yamashita, via positive semidefinite matrix completion for an optimization problem with matrix inequalities satisfying a sparse chordal graph structure. It is based on quite a general description of optimization problem including both primal and dual form of linear, … Read more

An Active Set Strategy for Solving Optimization Problems with up to 200,000,000 Nonlinear Constraints

We propose a numerical algorithm for solving smooth nonlinear programming problems with a large number of constraints, but a moderate number of variables. The active set method proceeds from a given bound mw for the maximum number of expected violated constraints, where mw is a user-provided parameter less than the total number of constraints. A … Read more

On solving trust-region and other regularised subproblems in optimization

The solution of trust-region and regularisation subproblems which arise in unconstrained optimization is considered. Building on the pioneering work of Gay, More’ and Sorensen, methods which obtain the solution of a sequence of parametrized linear systems by factorization are used. Enhancements using high-order polynomial approximation and inverse iteration ensure that the resulting method is both … Read more

Decomposition of large-scale stochastic optimal control problems

In this paper, we present an Uzawa-based heuristic that is adapted to some type of stochastic optimal control problems. More precisely, we consider dynamical systems that can be divided into small-scale independent subsystems, though linked through a static almost sure coupling constraint at each time step. This type of problem is common in production/portfolio management … Read more

The Constant Rank Condition and Second Order Constraint Qualifications

The Constant Rank condition for feasible points of nonlinear programming problems was defined by Janin in Ref. 1. In that paper the author proved that the condition was a first order constraint qualification. In this work we prove that the Janin Constant Rank condition is, in addition, a second order constraint qualification. We also define … Read more

A GSS method for oblique l_1 Procrustes problems

We propose a Generating Search Set method for solving the oblique l_1 Procrustes problem. Implementative details, algorithmic choices and theoretical properties of the method are discussed. The results of some numerical experiments are reported. Citation in Applied and Industrial Mathematics in Italy III – Proceedings of the 9th Conference SIMAI, De Bernardis et. Al. (eds), … Read more

High accuracy semidefinite programming bounds for kissing numbers

The kissing number in n-dimensional Euclidean space is the maximal number of non-overlapping unit spheres which simultaneously can touch a central unit sphere. Bachoc and Vallentin developed a method to find upper bounds for the kissing number based on semidefinite programming. This paper is a report on high accuracy calculations of these upper bounds for … Read more

An Interior-Point Algorithm for Large-Scale Nonlinear Optimization with Inexact Step Computations

We present a line-search algorithm for large-scale continuous optimization. The algorithm is matrix-free in that it does not require the factorization of derivative matrices. Instead, it uses iterative linear system solvers. Inexact step computations are supported in order to save computational expense during each iteration. The algorithm is an interior-point approach derived from an inexact … Read more

Improved algorithms for convex minimization in relative scale

In this paper we propose two modifications to Nesterov’s algorithms for minimizing convex functions in relative scale. The first is based on a bisection technique and leads to improved theoretical iteration complexity, and the second is a heuristic for avoiding restarting behavior. The fastest of our algorithms produces a solution within relative error O(1/k) of … Read more

Equivalence of Convex Problem Geometry and Computational Complexity in the Separation Oracle Model

Consider the following supposedly-simple problem: “compute x \in S” where S is a convex set conveyed by a separation oracle, with no further information (e.g., no bounding ball containing or intersecting S, etc.). Our interest in this problem stems from fundamental issues involving the interplay of computational complexity, the geometry of S, and the stability … Read more