Month: April 2012

Solution of monotone complementarity and general convex programming problems using modified potential reduction interior point method

  • Kuo-Ling Huang
  • Sanjay Mehrotra
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Quadratic Programming Tags , , , ,

    We present a homogeneous algorithm equipped with a modified potential function for the monotone complementarity problem. We show that this potential function is reduced by at least a constant amount if a scaled Lipschitz condition is satis ed. A practical algorithm based on this potential function is implemented in a software package named iOptimize. The implementation … Read more

    Complexity of Bilevel Coherent Risk Programming

  • Jonathan Eckstein
    • Categories Stochastic Programming Tags , ,

    This paper considers a bilevel programming approach to applying coherent risk measures to extended two-stage stochastic programming problems. This formulation technique avoids the time-inconsistency issues plaguing naive models and the incomposability issues which cause time-consistent formulations to have complicated, hard-to-explain objective functions. Unfortunately, the analysis here shows that such bilevel formulations, when using the standard … Read more

    On Chubanov’s method for Linear Programming

  • Amitabh Basu
  • Jesús A. De Loera
  • Mark Junod
    • Categories Linear Programming

    We discuss the method recently proposed by S. Chubanov for the linear feasibility problem. We present new, concise proofs and interpretations of some of his results. We then show how our proofs can be used to find strongly polynomial time algorithms for special classes of linear feasibility problems. Under certain conditions, these results provide new … Read more

    A biased random-key genetic algorithm for a 2D and 3D bin packing problem

  • José Fernando Gonçalves
  • Mauricio G.C. Resende
    • Categories Applications - OR and Management Sciences, Meta Heuristics Tags , , , , ,

    We present a novel multi-population biased random-key genetic algorithm (BRKGA) for the 2D and 3D bin packing problem. The approach uses a maximal-space representation to manage the free spaces in the bins. The proposed algorithm uses a decoder based on a novel placement procedure within a multi-population genetic algorithm based on random keys. The BRKGA … Read more

    A class of Fejer convergent algorithms, approximate resolvents and the Hybrid Proximal-Extragradient method

  • Benar Fux Svaiter
    • Categories Complementarity and Variational Inequalities, Infinite Dimensional Optimization, Nonlinear Optimization

    A new framework for analyzing Fejer convergent algorithms is presented. Using this framework we define a very general class of Fejer convergent algorithms and establish its convergence properties. We also introduce a new definition of approximations of resolvents which preserve some useful features of the exact resolvent, and use this concept to present an unifying … Read more

    On the hop-constrained survivable network design problem with reliable edges

  • Quentin Botton
  • Bernard Fortz
  • Luís Gouveia
    • Categories Branch and Cut Algorithms, Cutting Plane Approaches, Network Optimization Tags , , , ,

    In this paper, we study the hop-constrained survivable network design problem with reliable edges. Given a graph with non-negative edge weights and node pairs Q, the hop-constrained survivable network design problem consists of constructing a minimum weight set of edges so that the induced subgraph contains at least K edge-disjoint paths containing at most L … Read more

    Successive Convex Approximations to Cardinality-Constrained Quadratic Programs: A DC Approach

  • Duan Li
  • Jie Sun
  • Xiaoling Sun
  • Xiaojin Zheng
    • Categories Global Optimization, Integer Programming, Nonlinear Optimization

    In this paper we consider a cardinality-constrained quadratic program that minimizes a convex quadratic function subject to a cardinality constraint and linear constraints. This class of problems has found many applications, including portfolio selection, subset selection and compressed sensing. We propose a successive convex approximation method for this class of problems in which the cardinality … Read more

    The optimal harvesting problem under risk aversion

  • Bernardo K. Pagnoncelli
  • Adriana Piazza
    • Categories Applications - OR and Management Sciences, Stochastic Programming Tags , , ,

    We study the exploitation of a one species forest plantation when timber price is uncertain. The work focuses on providing optimality conditions for the optimal harvesting policy in terms of the parameters of the price process and the discount factor. We use risk averse stochastic dynamic programming and use the Conditional Value-at-Risk (CVaR) as our … Read more

    Linear System Identification via Atomic Norm Regularization

  • Badri Narayan Bhaskar
  • Benjamin Recht
  • Parikshit Shah
  • Gongguo Tang
    • Categories Control Applications, Convex Optimization Tags , , ,

    This paper proposes a new algorithm for linear system identification from noisy measurements. The proposed algorithm balances a data fidelity term with a norm induced by the set of single pole filters. We pose a convex optimization problem that approximately solves the atomic norm minimization problem and identifies the unknown system from noisy linear measurements. … Read more