A Smoothing SQP Framework for a Class of Composite $ Minimization over Polyhedron
The composite $L_q$ (0
Nonlinear Optimization
Robust Block Coordinate Descent
In this paper we present a novel randomized block coordinate descent method for the minimization of a convex composite objective function. The method uses (approximate) partial second-order (curvature) information, so that the algorithm performance is more robust when applied to highly nonseparable or ill conditioned problems. We call the method Robust Coordinate Descent (RCD). At … Read more
A Feasible Active Set Method with Reoptimization for Convex Quadratic Mixed-Integer Programming
We propose a feasible active set method for convex quadratic programming problems with non-negativity constraints. This method is specifically designed to be embedded into a branch-and-bound algorithm for convex quadratic mixed integer programming problems. The branch-and-bound algorithm generalizes the approach for unconstrained convex quadratic integer programming proposed by Buchheim, Caprara and Lodi to the presence … Read more
Mathematical Programs with Cardinality Constraints: Reformulation by Complementarity-type Constraints and a Regularization Method
Optimization problems with cardinality constraints are very dicult mathematical programs which are typically solved by global techniques from discrete optimization. Here we introduce a mixed-integer formulation whose standard relaxation still has the same solutions (in the sense of global minima) as the underlying cardinality-constrained problem; the relation between the local minima is also discussed in … Read more
Globally Convergent Evolution Strategies for Constrained Optimization.
In this work we propose, analyze, and test algorithms for linearly constrained optimization when no use of derivatives of the objective function is made. The proposed methodology is built upon the globally convergent evolution strategies previously introduced by the authors for unconstrained optimization. Two approaches are encompassed to handle the constraints. In a first approach, … Read more
HIGHER-ORDER METRIC SUBREGULARITY AND ITS APPLICATIONS
This paper is devoted to the study of metric subregularity and strong subregularity of any positive order $q$ for set-valued mappings in finite and infinite dimensions. While these notions have been studied and applied earlier for $q=1$ and—to a much lesser extent—for $q\in(0,1)$, no results are available for the case $q>1$. We derive characterizations of … Read more
An error analysis for polynomial optimization over the simplex based on the multivariate hypergeometric distribution
We study the minimization of fixed-degree polynomials over the simplex. This problem is well-known to be NP-hard, as it contains the maximum stable set problem in graph theory as a special case. In this paper, we consider a rational approximation by taking the minimum over the regular grid, which consists of rational points with denominator … Read more
An Augmented Lagrangian based Algorithm for Distributed Non-Convex Optimization
This paper is about distributed derivative-based algorithms for solving optimization problems with a separable (potentially nonconvex) objective function and coupled affine constraints. A parallelizable method is proposed that combines ideas from the fields of sequential quadratic programming and augmented Lagrangian algorithms. The method negotiates shared dual variables that may be interpreted as prices, a concept … Read more
Directed modified Cholesky factorizations and convex quadratic relaxations
A directed Cholesky factorization of a symmetric interval matrix \A consists of a permuted upper triangular matrix R such that for all symmetric A \in \A, the residual matrix A – R^T R is positive semidefinite with tiny entries. This must holds with full mathematical rigor, although the computations are done in floating-point arithmetic. Similarly, … Read more
A comparison of reduced and unreduced KKT systems arising from Interior Point methods
We address the iterative solution of symmetric KKT systems arising in the solution of convex quadratic programming problems. Two strictly related and well established formulations for such systems are studied with particular emphasis on the effect of preconditioning strategies on their relation. Constraint and augmented preconditioners are considered, and the choice of the augmentation Matrix … Read more