Month: October 2012

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

  • Frank E. Curtis
  • Daniel P. Robinson
  • Zheng Han
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , , ,

    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

  • Emanuele Frandi
  • Alessandra Papini
    • Categories Unconstrained 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

  • Aharon Ben-Tal
  • Dick den Hertog
  • Bram L. Gorissen
  • Hans Blanc
    • Categories Robust Optimization

    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

  • Marius Durea
  • Van Ngai Huynh
  • Huu Tron Nguyen
  • Radu Strugariu
    • Categories Convex and Nonsmooth Optimization

    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

  • Michael Poss
    • Categories Robust Optimization

    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

  • Simge Küçükyavuz
  • James R. Luedtke
  • Yongjia Song
    • Categories Integer Programming, Stochastic Programming Tags ,

    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

  • Charles Audet
  • Sébastien Le Digabel
  • Christophe Tribes
  • Andrea Ianni
    • Categories Constrained Nonlinear Optimization, Nonsmooth Optimization Tags , , ,

    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

  • Shabbir Ahmed
  • Qie He
  • George L. Nemhauser
    • Categories Combinatorial Optimization, Network Optimization, Production and Logistics Tags , ,

    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

  • Thiago Serra
    • Categories Combinatorial Optimization, Integer Programming, Optimization Software Design Principles Tags , ,

    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

  • Ziyan Luo
  • Jiyuan Tao
  • Naihua Xiu
    • Categories Control Applications, Linear, Cone and Semidefinite Programming Tags , , , ,

    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