Hayato Waki

Analytic Formulas for Alternating Projection Sequences for the Positive Semidefinite Cone and an Application to Convergence Analysis

  • Hiroyuki Ochiai
  • Yoshiyuki Sekiguchi
  • Hayato Waki
    • Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , , ,

    \(\) We derive analytic formulas for the alternating projection method applied to the cone \(S^n_+\) of positive semidefinite matrices and an affine subspace. More precisely, we find recursive relations on parameters representing a sequence constructed by the alternating projection method. By applying these formulas, we analyze the alternating projection method in detail and show that … Read more

    Exact Convergence Rates of Alternating Projections for Nontransversal Intersections

  • Hiroyuki Ochiai
  • Yoshiyuki Sekiguchi
  • Hayato Waki
    • Categories Convex Optimization Tags , , , , ,

    We study the exact convergence rate of the alternating projection method for the nontransversal intersection of a semialgebraic set and a linear subspace. If the linear subspace is a line, the exact rates are expressed by multiplicities of the defining polynomials of the semialgebraic set, or related power series. Our methods are also applied to … Read more

    Perturbation Analysis of Singular Semidefinite Program and Its Application to a Control Problem

  • Yoshiyuki Sekiguchi
  • Hayato Waki
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    We consider the sensitivity of semidefinite programs (SDPs) under perturbations. It is well known that the optimal value changes continuously under perturbations on the right hand side in the case where the Slater condition holds in the primal problems. In this manuscript, we observe by investigating a concrete SDP that the optimal value can be … Read more

    Minimization of Akaike’s Information Criterion in Linear Regression Analysis via Mixed Integer Nonlinear Program

  • Keiji Kimura
  • Hayato Waki
    • Categories (Mixed) Integer Nonlinear Programming Tags ,

    Akaike’s information criterion (AIC) is a measure of the quality of a statistical model for a given set of data. We can determine the best statistical model for a particular data set by the minimization of the AIC. Since we need to evaluate exponentially many candidates of the model by the minimization of the AIC, … Read more

    Application of Facial Reduction to \infty$ State Feedback Control Problem

  • Noboru Sebe
  • Hayato Waki
    • Categories Convex Optimization, Semi-definite Programming Tags , , , ,

    One often encounters numerical difficulties in solving linear matrix inequality (LMI) problems obtained from $H_\infty$ control problems. We discuss the reason from the viewpoint of optimization, and provide necessary and sufficient conditions for LMI problem and its dual not to be strongly feasible. Moreover, we interpret them in terms of control system. In this analysis, … Read more

    A Perturbed Sums of Squares Theorem for Polynomial Optimization and its Applications

  • Masakazu Muramatsu
  • Levent Tunçel
  • Hayato Waki
    • Categories Convex Optimization, Quadratic Programming, Semi-definite Programming

    We consider a property of positive polynomials on a compact set with a small perturbation. When applied to a Polynomial Optimization Problem (POP), the property implies that the optimal value of the corresponding SemiDefinite Programming (SDP) relaxation with sufficiently large relaxation order is bounded from below by $(f^¥ast – ¥epsilon)$ and from above by $f^¥ast … Read more

    An extension of the elimination method for a sparse SOS polynomial

  • Masakazu Muramatsu
  • Hayato Waki
    • Categories Convex and Nonsmooth Optimization, Global Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    We propose a method to reduce the sizes of SDP relaxation problems for a given polynomial optimization problem (POP). This method is an extension of the elimination method for a sparse SOS polynomial in [Kojima et al., Mathematical Programming] and exploits sparsity of polynomials involved in a given POP. In addition, we show that this … Read more

    How to generate weakly infeasible semidefinite programs via Lasserre’s relaxations for polynomial optimization

  • Hayato Waki
    • Categories Convex Optimization, Semi-definite Programming Tags , ,

    Examples of weakly infeasible semidefinite programs are useful to test whether semidefinite solvers can detect infeasibility. However, finding non trivial such examples is notoriously difficult. This note shows how to use Lasserre’s semidefinite programming relaxations for polynomial optimization in order to generate examples of weakly infeasible semidefinite programs. Such examples could be used to test … Read more

    A Facial Reduction Algorithm for Finding Sparse SOS Representations

  • Masakazu Muramatsu
  • Hayato Waki
    • Categories Convex Optimization, Global Optimization Theory, Semi-definite Programming Tags , , ,

    Facial reduction algorithm reduces the size of the positive semidefinite cone in SDP. The elimination method for a sparse SOS polynomial ([3]) removes unnecessary monomials for an SOS representation. In this paper, we establish a relationship between a facial reduction algorithm and the elimination method for a sparse SOS polynomial. Citation Technical Report CS-09-02, Department … Read more

    Facial reduction algorithms for conic optimization problems

  • Masakazu Muramatsu
  • Hayato Waki
    • Categories Convex Optimization, Global Optimization Theory, Linear, Cone and Semidefinite Programming Tags ,

    To obtain a primal-dual pair of conic programming problems having zero duality gap, two methods have been proposed: the facial reduction algorithm due to Borwein and Wolkowicz [1,2] and the conic expansion method due to Luo, Sturm, and Zhang [5]. We establish a clear relationship between them. Our results show that although the two methods … Read more