Linear semi-definite feasibility problems (LSDFPs) are semi-definite programs where either the primal objective function or the dual objective function is zero. Solving linear semi-definite feasibility problems can be applied to find solutions to linear matrix inequalities that arise in various application areas in engineering for example. In this talk, I will focus on an implementable interior point algorithm that solves an LSDFP using known search directions, namely, HKM and NT search directions, found in existing interior point solvers on semi-definite programs, such as, SeDuMi. I consider the local superlinear convergence behavior of the interior point algorithm on LSDFPs, and present a new result that advances what is known in the interior point method literature on this topic. The key that makes this result possible is to consider the interior point algorithm on the homogeneous feasibility model of the LSDFP, instead of the LSDFP itself.

We investigate the following question: Can we verify the feasibility of a given SDP by utilizing an approximate solution that is sufficiently close to an exact solution? Traditional approaches often rely on the existence of rational feasible solutions, employing techniques like rounding and lattice reduction algorithms. However, we propose an alternative method that circumvents this assumption. Specifically, we demonstrate how to construct a system of polynomial equations, guaranteeing that its set of real solutions contains an isolated correct solution (assuming the target exact solution is maximum-rank). This approach enables the utilization of algorithms from real algebraic geometry to solve polynomial equation systems, resulting in a hybrid (or symbolic-numerical) method for SDPs. Notably, this hybrid method has proven effective in certifying the feasibility of numerous SDPs in the instances we tested. We posit that our approach may find applications beyond SDP feasibility certification, such as refining an approximate solution through the application of Newton's method to a system of polynomial equations.

This work investigates efficient solution to two fundamental problems in topology optimization of frame structures. The first one involves minimizing structural compliance under linear-elastic equilibrium and weight constraint, while the second one minimizes the weight under compliance constraints. These problems are non-convex and generally challenging to solve globally, with the non-convexity concentrated in a polynomial matrix inequality. Recently, these problems where tackled using the moment-sum-of-squares (mSOS) hierarchy. However, only smaller instances can be solved globally. Here, we aim to improve the scalability of solution to these problems by using the mSOS hierarchy supplemented with the Term Sparsity Pattern technique (TSP). Due to the unique polynomial structure of our problems in which the objective and constraint functions are separable polynomials, we further improve scalability by adopting a reduced monomial basis containing non-mixed terms only. From extensive numerical testing, we conclude that these techniques allow for a global solution to larger instances and accelerate the solution of the problems significantly.

In this presentation, we study the effects of applying a modified Levenberg-Marquardt regularization
to a nonsmooth Newton method. We expand this application to exact and inexact nonsmooth
Newton methods and apply it to the best approximation constrained to a polyhedral set problem.
We also demonstrate that linear programs can be represented as a best approximation problem,
extending the application of nonsmooth Newton methods to linear programming. This application
provides us with insight into an external path following algorithm that, like the simplex method,
takes a finite number of steps on the boundary of the polyhedral set. However, unlike the simplex
method, these steps do not use basic feasible solutions.