Multilevel Objective-Function-Free Optimization with an Application to Neural Networks Training
A class of multi-level algorithms for unconstrained nonlinear optimization is presented which does not require the evaluation of the objective function. The class contains the momentum-less AdaGrad method as a particular (single-level) instance. The choice of avoiding the evaluation of the objective function is intended to make the algorithms of the class less sensitive to … Read more
On solving the MAX-SAT using sum of squares
We consider semidefinite programming (SDP) approaches for solving the maximum satisfiabilityproblem (MAX-SAT) and the weighted partial MAX-SAT. It is widely known that SDP is well-suitedto approximate the (MAX-)2-SAT. Our work shows the potential of SDP also for other satisfiabilityproblems, by being competitive with some of the best solvers in the yearly MAX-SAT competition.Our solver combines … Read more
Polynomial argmin for recovery and approximation of multivariate discontinuous functions
We propose to approximate a (possibly discontinuous) multivariate function f(x) on a compact set by the partial minimizer arg min_y p(x,y) of an appropriate polynomial p whose construction can be cast in a univariate sum of squares (SOS) framework, resulting in a highly structured convex semidefinite program. In a number of non-trivial cases (e.g. when … Read more
Bilevel optimization with a multi-objective lower-level problem: Risk-neutral and risk-averse formulations
In this work, we propose different formulations and gradient-based algorithms for deterministic and stochastic bilevel problems with conflicting objectives in the lower level. Such problems have received little attention in the deterministic case and have never been studied from a stochastic approximation viewpoint despite the recent advances in stochastic methods for single-level, bilevel, and multi-objective … Read more
Stochastic programming for an integrated assignment, routing, and scheduling problem
We study a two-stage stochastic combinatorial optimization problem that integrates fleet-sizing, assignment, routing, and scheduling problems. Although this problem has wide applicability, it arises in particular in the home healthcare industry where a service team of caregivers have to be assigned to patients and put in vehicle fleet that have to be routed amongst the … Read more
MGProx: A nonsmooth multigrid proximal gradient method with adaptive restriction for strongly convex optimization
We study the combination of proximal gradient descent with multigrid for solving a class of possibly nonsmooth strongly convex optimization problems. We propose a multigrid proximal gradient method called MG-Prox, which accelerates the proximal gradient method by multigrid, based on using hierarchical information of the optimization problem. MGProx applies a newly introduced adaptive restriction operator … Read more
Projection free methods on product domains
Projection-free block-coordinate methods avoid high computational cost per iteration and at the same time exploit the particular problem structure of product domains. Frank-Wolfe-like approaches rank among the most popular ones of this type. However, as observed in the literature, there was a gap between the classical Frank-Wolfe theory and the block-coordinate case. Moreover, most of … Read more
Cutting plane reusing methods for multiple dual optimizations
We consider solving a group of dual optimization problems that share a core structure: Every primal problem of the group is obtained by the right-hand side variation of constraints in the original primal problem, while the other core part of the original primal problem, such as the objective and the left-hand side of the constraints, … Read more
Robust two-stage combinatorial optimization problems under discrete demand uncertainties and consistent selection constraints
In this paper, we study a robust two-stage concept of combinatorial optimization problems under discrete demand uncertainty. Combinatorial optimization problems are based on a finite set of elements for which we decide whether they are part of a solution. We divide the elements into two types, the so-called fixed and free elements. In a first … Read more