We represent the space of linear programs as the space of projection matrices. Projection matrices of the same dimension and rank comprise a Grassmannian, which has rich geometric and algebraic structures. An ordinary differential equation on the space of projection matrices defines a path for each projection matrix associated with a linear programming instance and … Read more
Based on previous explicit computations of universal barrier functions, we describe numerical experiments for solving certain classes of convex optimization problems. The comparison is given of the performance of the classical affine-scaling algorithm with similar algorithm based upon the universal barrier function CitationTo appear in “Computational Optimization and Applications”ArticleDownload View PDF
We consider the conic feasibility problem associated with linear homogeneous systems of inequalities. The complexity of iterative algorithms for solving this problem depends on a condition number. When studying the typical behaviour of algorithms under stochastic input one is therefore naturally led to investigate the fatness of the distribution tails of the random condition number … Read more
Stochastic programming, despite its immense modeling capabilities, is well known to be computationally excruciating. In this paper, we introduce a unified framework of approximating multiperiod stochastic programming from the perspective of robust optimization. Specifically, we propose a framework that integrates multistage modeling with safeguarding constraints. The framework is computationally tractable in the form of second … Read more
The problem of maximizing the sum of linear functional and several weighted logarithmic determinant (logdet) functions under semidefinite constraints is a generalization of the semidefinite programming (SDP) and has a number of applications in statistics and datamining, and other areas of informatics and mathematical sciences. In this paper, we extend the framework of standard primal-dual … Read more
The relationships among central path in the context of semidefinite programming, generalized proximal point method and Cauchy trajectory in Riemannian manifolds is studied in this paper. First it is proved that the central path associated to the general function is well defined. The convergence and characterization of its limit point is established for functions satisfying … Read more
We review complexity results for minimizing polynomials over the standard simplex and unit hypercube. In addition, we show that there exists a polynomial time approximation scheme (PTAS) for minimizing some classes of functions (including Lipschitz continuous functions) over the standard simplex. The main tools used in the analysis are Bernstein approximation and Lagrange interpolation on … Read more
We analyze the rate of local convergence of the augmented Lagrangian method for nonlinear semidefinite optimization. The presence of the positive semidefinite cone constraint requires extensive tools such as the singular value decomposition of matrices, an implicit function theorem for semismooth functions, and certain variational analysis on the projection operator in the symmetric-matrix space. Without … Read more
Linear Programming, LP, problems with finite optimal value have a zero duality gap and a primal-dual strictly complementary optimal solution pair. On the other hand, there exists Semidefinite Programming, SDP, problems which have a nonzero duality gap (different primal and dual optimal values; not both infinite). The duality gap is assured to be zero if … Read more
This short note extends the sparse SOS (sum of squares) and SDP (semidefinite programming) relaxation proposed by Waki, Kim, Kojima and Muramatsu for normal POPs (polynomial optimization problems) to POPs over symmetric cones, and establishes its theoretical convergence based on the recent convergence result by Lasserre on the sparse SOS and SDP relaxation for normal … Read more