Exact Convergence Rates of Alternating Projections for Nontransversal Intersections

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

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

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

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

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

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

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

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

SFSDP: a Sparse Version of Full SemiDefinite Programming Relaxation for Sensor Network Localization Problems

SFSDP is a Matlab package for solving a sensor network localization problem. These types of problems arise in monitoring and controlling applications using wireless sensor networks. SFSDP implements the semidefinite programming (SDP) relaxation proposed in Kim et al. [2009] for sensor network localization problems, as a sparse version of the full semidefinite programming relaxation (FSDP) … Read more

Facial reduction algorithms for conic optimization problems

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