Makoto Yamashita

An infeasible interior-point arc-search method with Nesterov’s restarting strategy for linear programming problems

  • Einosuke Iida
  • Makoto Yamashita
    • Categories Linear Programming Tags , , ,

    An arc-search interior-point method is a type of interior-point methods that approximates the central path by an ellipsoidal arc, and it can often reduce the number of iterations. In this work, to further reduce the number of iterations and computation time for solving linear programming problems, we propose two arc-search interior-point methods using Nesterov’s restarting … Read more

    Exact SDP relaxations for quadratic programs with bipartite graph structures

  • Godai Azuma
  • Mituhiro Fukuda
  • Sunyoung Kim
  • Makoto Yamashita
    • Categories Semi-definite Programming Tags , , , ,

    For nonconvex quadratically constrained quadratic programs (QCQPs), we first show that, under certain feasibility conditions, the standard semidefinite (SDP) relaxation is exact for QCQPs with bipartite graph structures. The exact optimal solutions are obtained by examining the dual SDP relaxation and the rank of the optimal solution of this dual SDP relaxation under strong duality. … Read more

    A Robust Optimization Method with Successive Linear Programming for Intensity Modulated Radiation Therapy

  • Masaaki Tamai
  • Makoto Yamashita
    • Categories Applications - OR and Management Sciences, Linear Programming, Robust Optimization Tags , , , ,

    Intensity modulated radiation therapy (IMRT) is one of radiation therapies for cancers, and it is considered to be effective for complicated shapes of tumors, since dose distributions from each irradiation can be modulated arbitrary. Fluence map optimization (FMO), which optimizes beam intensities with given beam angles, is often formulated as an optimization problem with dose … Read more

    Exact SDP relaxations of quadratically constrained quadratic programs with forest structures

  • Godai Azuma
  • Mituhiro Fukuda
  • Sunyoung Kim
  • Makoto Yamashita
    • Categories Global Optimization, Semi-definite Programming Tags , , ,

    We study the exactness of the semidefinite programming (SDP) relaxation of quadratically constrained quadratic programs (QCQPs). With the aggregate sparsity matrix from the data matrices of a QCQP with $n$ variables, the rank and positive semidefiniteness of the matrix are examined. We prove that if the rank of the aggregate sparsity matrix is not less … Read more

    Exploiting Aggregate Sparsity in Second Order Cone Relaxations for Quadratic Constrained Quadratic Programming Problems

  • Heejune Sheen
  • Makoto Yamashita
    • Categories Quadratic Programming, Second-Order Cone Programming, Semi-definite Programming Tags , , , ,

    Among many approaches to increase the computational efficiency of semidefinite programming (SDP) relaxation for quadratic constrained quadratic programming problems (QCQPs), exploiting the aggregate sparsity of the data matrices in the SDP by Fukuda et al. (2001) and second-order cone programming (SOCP) relaxation have been popular. In this paper, we exploit the aggregate sparsity of SOCP … Read more

    An Infeasible Interior-point Arc-search Algorithm for Nonlinear Constrained Optimization

  • Einosuke Iida
  • Yaguang Yang
  • Makoto Yamashita
    • Categories Constrained Nonlinear Optimization Tags , , , ,

    In this paper, we propose an infeasible arc-search interior-point algorithm for solving nonlinear programming problems. Most algorithms based on interior-point methods are categorized as line search in the sense that they compute a next iterate on a straight line determined by a search direction which approximates the central path. The proposed arc-search interior-point algorithm uses … Read more

    A dual spectral projected gradient method for log-determinant semidefinite problems

  • Mituhiro Fukuda
  • Sunyoung Kim
  • Takashi Nakagaki
  • Makoto Yamashita
    • Categories Convex Optimization, Semi-definite Programming Tags , , , ,

    We extend the result on the spectral projected gradient method by Birgin et al in 2000 to a log-determinant semidefinite problem (SDP) with linear constraints and propose a spectral projected gradient method for the dual problem. Our method is based on alternate projections on the intersection of two convex sets, which first projects onto the … Read more

    Polyhedral-based Methods for Mixed-Integer SOCP in Tree Breeding

  • Tim J. Mullin
  • Sena Safarina
  • Makoto Yamashita
    • Categories (Mixed) Integer Linear Programming, Second-Order Cone Programming

    Optimal contribution selection (OCS) is a mathematical optimization problem that aims to maximize the total benefit from selecting a group of individuals under a constraint on genetic diversity. We are specifically focused on OCS as applied to forest tree breeding, when selected individuals will contribute equally to the gene pool. Since the diversity constraint in … Read more

    Solving Pooling Problems by LP and SOCP Relaxations and Rescheduling Methods

  • Sunyoung Kim
  • Masaki Kimizuka
  • Makoto Yamashita
    • Categories Applications - Science and Engineering, Linear, Cone and Semidefinite Programming Tags , , , , ,

    The pooling problem is an important industrial problem in the class of network flow problems for allocating gas flow in pipeline transportation networks. For P-formulation of the pooling problem with time discretization, we propose second order cone programming (SOCP) and linear programming (LP) relaxations and prove that they obtain the same optimal value as the … Read more

    Conic relaxation approaches for equal deployment problems

  • Safia Kedad-Sidhoum
  • Tim J. Mullin
  • Satoko Moriguchi
  • Makoto Yamashita
    • Categories (Mixed) Integer Nonlinear Programming, Linear, Cone and Semidefinite Programming

    An important problem in the breeding of livestock, crops, and forest trees is the optimum of selection of genotypes that maximizes genetic gain. The key constraint in the optimal selection is a convex quadratic constraint that ensures genetic diversity, therefore, the optimal selection can be cast as a second-order cone programming (SOCP) problem. Yamashita et … Read more