Exact Solutions of Some Nonconvex Quadratic Optimization Problems via SDP and SOCP Relaxations

  • Sunyoung Kim
  • Masakazu Kojima
    • Categories Second-Order Cone Programming, Semi-definite Programming Tags , , ,

    We show that SDP (semidefinite programming) and SOCP (second order cone programming) relaxations provide exact optimal solutions for a class of nonconvex quadratic optimization problems. It is a generalization of the results by S.~Zhang for a subclass of quadratic maximization problems that have nonnegative off-diagonal coefficient matrices of objective quadratic functions and diagonal coefficient matrices … Read more

    Relations between divergence of multipliers and convergence to infeasible points in primal-dual interior methods for nonconvex nonlinear programming

  • Anders Forsgren
  • Göran Sporre
    • Categories Constrained Nonlinear Optimization Tags , , ,

    Recently, infeasibility issues in interior methods for nonconvex nonlinear programming have been studied. In particular, it has been shown how many line-search interior methods may converge to an infeasible point which is on the boundary of the feasible region with respect to the inequality constraints. The convergence is such that the search direction does not … Read more

    Solving Stability Problems on a Superclass of Interval Graphs

  • Carlo Mannino
  • Gianpaolo Oriolo
    • Categories Dynamic Programming, Graphs and Matroids, Telecommunications Tags , , ,

    We introduce a graph invariant, called thinness, and show that a maximum weighted stable set on a graph $G(V, E)$ with thinness $k$ may be found in $O(\frac{|V|}{k})^k$-time, if a certain representation is given. We show that a graph has thinness 1 if and only if it is an interval graph, while a graph with … Read more

    A characterization of the distance to infeasibility under block-structured perturbations

  • Javier F. Peña
    • Categories Convex Optimization Tags , , , ,

    We discuss several generalizations of the classical Eckart and Young identity. We show that a natural extension of this identity holds for rectangular matrices defining conic systems of constraints, and for perturbations restricted to a particular block structure, such as those determined by a sparsity pattern. Our results extend and unify the classical Eckart and … Read more

    A binary LP model to the facility layout problem

  • Christos Papahristodoulou
    • Categories 0-1 Programming, Applications - OR and Management Sciences, Facility Planning and Design Tags , , , ,

    In facility layout problems, a major concern is the optimal design or remodeling of the facilities of an organization. The decision-maker’s objective is to arrange the facility in an optimal way, so that the interaction among functions (i.e. machines, inventories, persons) and places (i.e. offices, work locations, depots) is efficient. A simple pure-binary LP model … Read more

    DSDP4 Software User Guide

  • Steven Benson
  • Yinyu Ye
    • Categories Semi-definite Programming Tags

    DSDP4 is an implementation of the dual-scaling algorithm for semidefinite program ming. New features in this version include a Lanczos procedure for determining the step size, more precise primal solutions, a parallel solver, and improved performance on the standard test suites. CitationANL/MCS-TM-255; Mathematics and Computer Science Division; Argonne National Laboratory; Argonne, IL; March 2002ArticleDownload View … Read more

    The least-intensity feasible solution for aperture-based inverse planning in radiation therapy.

  • Yair Censor
  • James M. Galvin
  • Darek Michalski
  • Ying Xiao
    • Categories Biomedical Applications, Convex Optimization, Nonlinear Systems and Least-Squares Tags , , , , ,

    Aperture-based inverse planning (ABIP) for intensity modulated radiation therapy (IMRT) treatment planning starts with external radiation fields (beams) that fully conform to the target(s) and then superimposes sub-fields called segments to achieve complex shaping of 3D dose distributions. The segments’ intensities are determined by solving a feasibility problem. The least-intensity feasible (LIF) solution, proposed and … Read more

    Parallel Computing on Semidefinite Programs

  • Steven Benson
    • Categories Parallel Algorithms, Semi-definite Programming Tags , , ,

    This paper demonstrates how interior-point methods can use multiple processors efficiently to solve large semidefinite programs that arise in VLSI design, control theory, and graph coloring. Previous implementations of these methods have been restricted to a single processor. By computing and solving the Schur complement matrix in parallel, multiple processors enable the faster solution of … Read more

    CUTEr (and SifDec), a Constrained and Unconstrained Testing Environment, revisited

  • Nicholas I. M. Gould
  • Dominique Orban
  • Philippe L. Toint
    • Categories Nonlinear Optimization, Optimization Software Benchmark, Problem Solving Environments Tags , , , ,

    The initial release of CUTE, a widely used testing environment for optimization software was described by Bongartz, Conn, Gould and Toint. The latest version, now known as CUTEr, is presented. New features include reorganisation of the environment to allow simultaneous multi-platform installation, new tools for, and interfaces to, optimization packages, and a considerably simplified and … Read more

    Reduntant axioms in the definitionof Bregman functions

  • Dan Butnariu
  • Charles Byrne
  • Yair Censor
    • Categories Constrained Nonlinear Optimization Tags , , , , ,

    The definition of a Bregman function, given by Censor and Lent in 1981 on the basis of Bregman’s seminal 1967 paper, was subsequently used in a plethora of research works as a tool for building sequential and inherently parallel feasibility and optimization algorithms. Solodov and Svaiter have recently shown that it is not CitationJournal of … Read more