An interior Newton-like method for nonnegative least-squares problems with degenerate solution

  • Stefania Bellavia
  • Benedetta Morini
  • Maria Macconi
    • Categories Nonlinear Optimization Tags , , , ,

    An interior point approach for medium and large nonnegative linear least-squares problems is proposed. Global and locally quadratic convergence is shown even if a degenerate solution is approached. Viable approaches for implementation are discussed and numerical results are provided. CitationTechnical Report 1/2005, Dipartimento di Energetica ‘S. Stecco’, Universita di Firenze, ItaliaArticleDownload View PDF

    Set covering and packing formulations of graph coloring: algorithms and first polyhedral results

  • Pierre Hansen
  • Martine Labbé
  • David Schindl
    • Categories Branch and Cut Algorithms, Graphs and Matroids Tags , , ,

    We consider two (0,1)-linear programming formulations of the graph (vertex-)coloring problem, in which variables are associated to stable sets of the input graph. The first one is a set covering formulation, where the set of vertices has to be covered by a minimum number of stable sets. The second is a set packing formulation, in … Read more

    Prox-Regularity and Stability of the Proximal Mapping

  • Warren Hare
  • R. A. Poliquin
    • Categories Convex and Nonsmooth Optimization, Generalized Convexity/Monoticity, Robust Optimization Tags , , , ,

    Fundamental insights into the properties of a function come from the study of its Moreau envelopes and Proximal point mappings. In this paper we examine the stability of these two objects under several types of perturbations. In the simplest case, we consider tilt-perturbations, i.e. perturbations which correspond to adding a linear term to the objective … Read more

    Comparing Imperfection Ratio and Imperfection Index for Graph Classes

  • Arie M.C.A. Koster
  • Annegret K. Wagler
    • Categories Graphs and Matroids, Polyhedra Tags , ,

    Perfect graphs constitute a well-studied graph class with a rich structure, reflected by many characterizations with respect to different concepts. Perfect graphs are, for instance, precisely those graphs $G$ where the stable set polytope $STAB(G)$ coincides with the fractional stable set polytope $QSTAB(G)$. For all imperfect graphs $G$ it holds that $STAB(G) \subset QSTAB(G)$. It … Read more

    On Ants, Bacteria and Dynamic Environments

  • Carlos Fernandes
  • Vitorino Ramos
  • Agostinho C. Rosa
    • Categories Global Optimization, Meta Heuristics, Robust Optimization Tags , , , ,

    Wasps, bees, ants and termites all make effective use of their environment and resources by displaying collective “swarm” intelligence. Termite colonies – for instance – build nests with a complexity far beyond the comprehension of the individual termite, while ant colonies dynamically allocate labor to various vital tasks such as foraging or defense without any … Read more

    On Self-Regulated Swarms, Societal Memory, Speed and Dynamics

  • Carlos Fernandes
  • Vitorino Ramos
  • Agostinho C. Rosa
    • Categories Control Applications, Nonlinear Optimization, Stochastic Approaches Tags , , , ,

    Wasps, bees, ants and termites all make effective use of their environment and resources by displaying collective “swarm” intelligence. Termite colonies – for instance – build nests with a complexity far beyond the comprehension of the individual termite, while ant colonies dynamically allocate labor to various vital tasks such as foraging or defense without any … Read more

    Stationarity and Regularity of Real-Valued Functions

  • Alexander Y. Kruger
    • Categories Nonsmooth Optimization Tags , , , , , , , ,

    Different stationarity and regularity concepts for extended real-valued functions on metric spaces are considered in the paper. The properties are characterized in terms of certain local constants. A classification scheme for stationarity/regularity constants and corresponding concepts is proposed. The relations between different constants are established. CitationUniversity of Ballarat, School of Information Technology and Mathematical Sciences, … Read more

    Using mixed-integer programming to solve power grid blackout problems

  • Daniel Bienstock
  • Sara Mattia
    • Categories Applications - OR and Management Sciences Tags , ,

    We consider optimization problems related to the prevention of large-scale cascading blackouts in power transmission networks subject to multiple scenarios of externally caused damage. We present computation with networks with up to 600 nodes and 827 edges, and many thousands of damage scenarios. CitationCORC Report TR-2005-07, Columbia UniversityArticleDownload View PDF

    A conic interior point decomposition approach for large scale semidefinite programming

  • Gema Plaza
  • Kartik Krishnan Sivaramakrishnan
  • Tamás Terlaky
    • Categories Nonsmooth Optimization, Semi-definite Programming Tags , , ,

    We describe a conic interior point decomposition approach for solving a large scale semidefinite programs (SDP) whose primal feasible set is bounded. The idea is to solve such an SDP using existing primal-dual interior point methods, in an iterative fashion between a {\em master problem} and a {\em subproblem}. In our case, the master problem … Read more

    An efficient conjugate direction method with orthogonalization for large-scale quadratic optimization problems

  • Edouard Boudinov
  • Arkadiy Manevich
    • Categories Nonlinear Optimization, Unconstrained Optimization Tags , , , ,

    A new conjugate direction method is proposed, which is based on an orthogonalization procedure and does not make use of line searches for the conjugate vector set construction. This procedure prevents the set of conjugate vectors from degeneracy and eliminates high sensitivity to computation errors pertinent to methods of conjugate directions, resulting in an efficient … Read more