Month: October 2007

Combining segment generation with direct step-and-shoot optimization in intensity-modulated radiation therapy

  • Fredrik Carlsson
    • Categories Biomedical Applications, Constrained Nonlinear Optimization Tags , , ,

    A method for generating a sequence of intensity-modulated radiation therapy step-and-shoot plans with increasing number of segments is presented. The objectives are to generate high-quality plans with few, large and regular segments, and to make the planning process more intuitive. The proposed method combines segment generation with direct step-and-shoot optimization, where leaf positions and segment … Read more

    Sufficient and Necessary Conditions for Semidefinite Representability of Convex Hulls and Sets

  • J. William Helton
  • Jiawang Nie
    • Categories Semi-definite Programming Tags , , , , , , , , , , , ,

    The article proves sufficient conditions and necessary conditions for SDP representability of convex sets and convex hulls by proposing a new approach to construct SDP representations. The contributions of this paper are: (i) For bounded SDP representable sets $W_1,\cdots,W_m$, we give an explicit construction of an SDP representation for $conv(\cup_{k=1}^mW_k)$. This provides a technique for … Read more

    A Numerical Algorithm for Block-Diagonal Decomposition of Matrix *-Algebras, Part I: Proposed Approach and Application to Semidefinite Programming

  • Yoshihiro Kanno
  • Masakazu Kojima
  • Kazuo Murota
  • Sadayoshi Kojima
    • Categories Applications - Science and Engineering, Semi-definite Programming Tags , , , ,

    Motivated by recent interest in group-symmetry in semidefinite programming, we propose a numerical method for finding a finest simultaneous block-diagonalization of a finite number of matrices, or equivalently the irreducible decomposition of the generated matrix *-algebra. The method is composed of numerical-linear algebraic computations such as eigenvalue computation, and automatically makes full use of the … Read more

    Bracketing an Optima in Univariate Optimization

  • Pritibhushan Sinha
    • Categories Unconstrained Optimization Tags ,

    In this article, we consider some problems of bracketing an optimum point for a real-valued, single variable function. We show that, no method, satisfying certain assumptions and requiring a bounded number of function evaluations, can exist to bracket the minimum point of a unimodal function. A similar result is given also for the problem of … Read more

    Regularization methods for semidefinite programming

  • Jérôme Malick
  • Janez Povh
  • Franz Rendl
  • Angelika Wiegele
    • Categories Convex Optimization, Nonlinear Optimization, Semi-definite Programming Tags , , ,

    This paper studies an alternative technique to interior point methods and nonlinear methods for semidefinite programming (SDP). The approach based on classical quadratic regularizations leads to an algorithm, generalizing a recent method called “boundary point method”. We study the theoretical properties of this algorithm and we show that in practice it behaves very well on … Read more

    Properties of a Cutting Plane Method for Semidefinite Programming

  • John E. Mitchell
  • Kartik Krishnan Sivaramakrishnan
    • Categories Linear, Cone and Semidefinite Programming, Nonsmooth Optimization Tags , , , ,

    We analyze the properties of an interior point cutting plane algorithm that is based on a semi-infinite linear formulation of the dual semidefinite program. The cutting plane algorithm approximately solves a linear relaxation of the dual semidefinite program in every iteration and relies on a separation oracle that returns linear cutting planes. We show that … Read more

    A multilevel algorithm for solving the trust-region subproblem

  • Philippe L. Toint
  • Melissa Weber-Mendonca
  • Dimitri Tomanos
    • Categories Infinite Dimensional Optimization, Optimization of Systems modeled by PDEs, Unconstrained Optimization Tags , , ,

    We present a multilevel numerical algorithm for the exact solution of the Euclidean trust-region subproblem. This particular subproblem typically arises when optimizing a nonlinear (possibly non-convex) objective function whose variables are discretized continuous functions, in which case the different levels of discretization provide a natural multilevel context. The trust-region problem is considered at the highest … Read more

    Fast Computation of Optimal Contact Forces

  • Stephen Boyd
  • Ben Wegbreit
    • Categories Convex Optimization, Mechanical Engineering, Second-Order Cone Programming Tags , , ,

    We consider the problem of computing the smallest contact forces, with point-contact friction model, that can hold an object in equilibrium against a known external applied force and torque. It is known that the force optimization problem (FOP) can be formulated as a semidefinite programming problem (SDP), or a second-order cone problem (SOCP), and so … Read more