We propose a perturbed gradient algorithm with stochastic noises to solve a general class of optimization problems. We provide a convergence proof for this algorithm, under classical assumptions on the descent direction, and new assumptions on the stochastic noises. Instead of requiring the stochastic noises to correspond to martingale increments, we only require these noises … Read more
In this paper, we study wavelength assignment problems in multi-fiber WDM networks. We focus on the special case that all lightpaths have at most two links. This in particular holds in case the network topology is a star. As the links incident to a specific node in a meshed topology form a star subnetwork, results … Read more
The Semidefinite Program (SDP) is a fundamental problem in mathematical programming. It covers a wide range of applications, such as combinatorial optimization, control theory, polynomial optimization, and quantum chemistry. Solving extremely large-scale SDPs which could not be solved before is a significant work to open up a new vista of future applications of SDPs. Our … Read more
We propose a primal-dual path-following Mehrotra-type predictor-corrector method for solving convex quadratic semidefinite programming (QSDP) problems. For the special case when the quadratic term has the form $\frac{1}{2} X \bul (UXU)$, we compute the search direction at each iteration from the Schur complement equation. We are able to solve the Schur complement equation efficiently via … Read more
SparesPOP is a MATLAB implementation of a sparse semidefinite programming (SDP) relaxation method proposed for polynomial optimization problems (POPs) in the recent paper by Waki et al. The sparse SDP relaxation is based on a hierarchy of LMI relaxations of increasing dimensions by Lasserre, and exploits a sparsity structure of polynomials in POPs. The efficiency … Read more
We describe an approach to the parallel and distributed solution of large-scale, block structured semidefinite programs using the spectral bundle method. Various elements of this approach (such as data distribution, an implicitly restarted Lanczos method tailored to handle block diagonal structure, a mixed polyhedral-semidefinite subdifferential model, and other aspects related to parallelism) are combined in … Read more
This paper considers strategies for selecting the barrier parameter at every iteration of an interior-point method for nonlinear programming. Numerical experiments suggest that adaptive choices, such as Mehrotra’s probing procedure, outperform static strategies that hold the barrier parameter fixed until a barrier optimality test is satisfied. A new adaptive strategy is proposed based on the … Read more
The problem of finding the optimal placement of $N$ identical, non overlapping, circles with maximum radius in the unit square is a well known challenge both in classical geometry and in optimization. A database of putative optima is currently maintained at \url{www.packomania.com}. Recently, through clever use of an extremely simple global optimization method, we succeeded … Read more
Augmented Lagrangian methods with general lower-level constraints are considered in the present research. These methods are useful when efficient algorithms exist for solving subproblems where the constraints are only of the lower-level type. Two methods of this class are introduced and analyzed. Inexact resolution of the lower-level constrained subproblems is considered. Global convergence is proved … Read more
The problem of minimizing a quadratic form over the standard simplex is known as the standard quadratic optimization problem (SQO). It is NP-hard, and contains the maximum stable set problem in graphs as a special case. In this note we show that the SQO problem may be reformulated as an (exponentially sized) linear program. Citation … Read more