A Globally Convergent Primal-Dual Active-Set Framework for Large-Scale Convex Quadratic Optimization

We present a primal-dual active-set framework for solving large-scale convex quadratic optimization problems (QPs). In contrast to classical active-set methods, our framework allows for multiple simultaneous changes in the active- set estimate, which often leads to rapid identification of the optimal active-set regardless of the initial estimate. The iterates of our framework are the active-set … Read more

Coordinate Search Algorithms in Multilevel Optimization

Many optimization problems of practical interest arise from the discretization of continuous problems. Classical examples can be found in calculus of variations, optimal control and image processing. In recent years a number of strategies have been proposed for the solution of such problems, broadly known as multilevel methods. Inspired by classical multigrid schemes for linear … Read more

Deriving robust and globalized robust solutions of uncertain linear programs with general convex uncertainty sets

We propose a new way to derive tractable robust counterparts of a linear program by using the theory of Beck and Ben-Tal (2009) on the duality between the robust (“pessimistic”) primal problem and its “optimistic” dual. First, we obtain a new {\it convex} reformulation of the dual problem of a robust linear program, and then … Read more

Metric regularity of composition set-valued mappings: metric setting and coderivative conditions

The paper concerns a new method to obtain a direct proof of the openness at linear rate/metric regularity of composite set-valued maps on metric spaces by the unification and refinement of several methods developed somehow separately in several works of the authors. In fact, this work is a synthesis and a precise specialization to a … Read more

Robust combinatorial optimization with variable budgeted uncertainty

We introduce a new model for robust combinatorial optimization where the uncertain parameters belong to the image of multifunctions of the problem variables. In particular, we study the variable budgeted uncertainty, an extension of the budgeted uncertainty introduced by Bertsimas and Sim. Variable budgeted uncertainty can provide the same probabilistic guarantee as the budgeted uncertainty … Read more

Chance-constrained binary packing problems

We consider a class of packing problems with uncertain data, which we refer to as the chance-constrained binary packing problem. In this problem, a subset of items is selected that maximizes the total profit so that a generic packing constraint is satisfied with high probability. Interesting special cases of our problem include chance-constrained knapsack and … Read more

Reducing the Number of Function Evaluations in Mesh Adaptive Direct Search Algorithms

The mesh adaptive direct search (MADS) class of algorithms is designed for nonsmooth optimization, where the objective function and constraints are typically computed by launching a time-consuming computer simulation. Each iteration of a MADS algorithm attempts to improve the current best-known solution by launching the simulation at a finite number of trial points. Common implementations … Read more

Minimum Concave Cost Flow Over a Grid Network

The minimum concave cost network flow problem (MCCNFP) is NP-hard, but efficient polynomial-time algorithms exist for some special cases such as the uncapacitated lot-sizing problem and many of its variants. We study the MCCNFP over a grid network with a general nonnegative separable concave cost function. We show that this problem is polynomially solvable when … Read more

On Defining Design Patterns to Generalize and Leverage Automated Constraint Solving

This position paper reflects on the generalization of adaptive methods for Constraint Programming (CP) solving mechanisms, and suggests the use of application-oriented descriptions as a means to broaden CP adoption in the industry. We regard as an adaptive method any procedure that modifies the behavior of the solving process according to previous experience gathered from … Read more

Lowest-rank Solutions of Continuous and Discrete Lyapunov Equations over Symmetric Cone

The low-rank solutions of continuous and discrete Lyapunov equations are of great importance but generally difficult to achieve in control system analysis and design. Fortunately, Mesbahi and Papavassilopoulos [On the rank minimization problems over a positive semidefinite linear matrix inequality, IEEE Trans. Auto. Control, Vol. 42, No. 2 (1997), 239-243] showed that with the semidefinite … Read more