Month: February 2011

Globally Solving Nonconvex Quadratic Programming Problems via Completely Positive Programming

  • Samuel Burer
  • Jieqiu Chen
    • Categories Global Optimization, Optimization Software and Modeling Systems, Quadratic Programming Tags , , , ,

    Nonconvex quadratic programming (QP) is an NP-hard problem that optimizes a general quadratic function over linear constraints. This paper introduces a new global optimization algorithm for this problem, which combines two ideas from the literature—finite branching based on the first-order KKT conditions and polyhedral-semidefinite relaxations of completely positive (or copositive) programs. Through a series of … Read more

    Recoverable Robust Knapsack: the Discrete Scenario Case

  • Christina Büsing
  • Arie M.C.A. Koster
  • Manuel Kutschka
    • Categories Cutting Plane Approaches, Polyhedra, Robust Optimization Tags , , ,

    Admission control problems have been studied extensively in the past. In a typical setting, resources like bandwidth have to be distributed to the different customers according to their demands maximizing the profit of the company. Yet, in real-world applications those demands are deviating and in order to satisfy their service requirements often a robust approach … Read more

    A stabilized model and an efficient solution method for the yearly optimal power management

  • Vincent Guigues
    • Categories Applications - OR and Management Sciences

    We propose a stabilized model for the electricity generation management problem on a yearly scale. We also introduce an original and efficient solution method in a particular case. Our model is compared to other management methods and offers the best average cost while preserving a reasonable standard deviation of the cost over a set of … Read more

    Recoverable Robust Knapsacks: $\GammahBcScenarios

  • Christina Büsing
  • Arie M.C.A. Koster
  • Manuel Kutschka
    • Categories (Mixed) Integer Linear Programming, Robust Optimization Tags , , , ,

    In this paper, we investigate the recoverable robust knapsack problem, where the uncertainty of the item weights follows the approach of Bertsimas and Sim (2003,2004). In contrast to the robust approach, a limited recovery action is allowed, i.e., upto k items may be removed when the actual weights are known. This problem is motivated by … Read more

    Updating the regularization parameter in the adaptive cubic regularization algorithm

  • Nicholas I. M. Gould
  • Margherita Porcelli
  • Philippe L. Toint
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , ,

    The adaptive cubic regularization method [Cartis, Gould, Toint, 2009-2010] has been recently proposed for solving unconstrained minimization problems. At each iteration of this method, the objective function is replaced by a cubic approximation which comprises an adaptive regularization parameter whose role is related to the local Lipschitz constant of the objective’s Hessian. We present new … Read more

    On the convergence of an inexact Gauss-Newton trust-region method for nonlinear least-squares problems with simple bounds

  • Margherita Porcelli
    • Categories Bound-constrained Optimization, Nonlinear Optimization, Nonlinear Systems and Least-Squares Tags , , , ,

    We introduce an inexact Gauss-Newton trust-region method for solving bound-constrained nonlinear least-squares problems where, at each iteration, a trust-region subproblem is approximately solved by the Conjugate Gradient method. Provided a suitable control on the accuracy to which we attempt to solve the subproblems, we prove that the method has global and asymptotic fast convergence properties. … Read more

    Sensitivity analysis and calibration of the covariance matrix for stable portfolio selection

  • Vincent Guigues
    • Categories Quadratic Programming

    We recommend an implementation of the Markowitz problem to generate stable portfolios with respect to perturbations of the problem parameters. The stability is obtained proposing novel calibrations of the covariance matrix between the returns that can be cast as convex or quasiconvex optimization problems. A statistical study as well as a sensitivity analysis of the … Read more

    Robust mid-term power generation management

  • René Aid
  • Vincent Guigues
  • Papa Momar Ndiaye
  • François Oustry
  • François Romanet
    • Categories Robust Optimization

    We consider robust formulations of the mid-term optimal power management problem. For this type of problems, classical approaches minimize the expected generation cost over a horizon of one year, and model the uncertain future by means of scenario trees. In this setting, extreme scenarios -with low probability in the scenario tree- may fail to be … Read more

    A Dual Algorithm For Approximating Pareto Sets in Convex Multi-Criteria Optimization

  • Rasmus Bokrantz
  • Anders Forsgren
    • Categories Biomedical Applications, Multi-Criteria Optimization

    We consider the problem of approximating the Pareto set of convex multi-criteria optimization problems by a discrete set of points and their convex combinations. Finding the scalarization parameters that maximize the improvement in bound on the approximation error when generating a single Pareto optimal solution is a nonconvex optimization problem. This problem is solvable by … Read more

    Robust Production Management

  • Vincent Guigues
    • Categories Robust Optimization

    The problem of production management can often be cast in the form of a linear program with uncertain parameters and risk constraints. Typically, such problems are treated in the framework of multi-stage Stochastic Programming. Recently, a Robust Counterpart (RC) approach has been proposed, in which the decisions are optimized for the worst realizations of problem … Read more