In this paper we present a new iteration-complexity bound for the Mizuno-Todd-Ye predictor-corrector (MTY P-C) primal-dual interior-point algorithm for linear programming. The analysis of the paper is based on the important notion of crossover events introduced by Vavasis and Ye. For a standard form linear program $\min\{c^Tx : Ax=b, \, x \ge 0\}$ with decision … Read more
Consider the problem of finding optimal bounds on the expected value of piece-wise polynomials over all measures with a given set of moments. We show that this problem can be studied within the framework of conic programming. Relying on a key approximation result for conic programming, we show that these bounds can be numerically computed … Read more
This is the user’s guide for version 5.0 of CSDP, a C library for semidefinite programming. The code is available at http://www.nmt.edu/~borchers/csdp.html ArticleDownload View PDF
The classical Quadratic Programming formulation of the well known portfolio selection problem, is cumbersome, time consuming and relies on two important assumptions: (a) the expected return is multivariate normally distributed; (b) the investor is risk averter. This paper formulates two alternative models, (i) maximin, and (ii) minimization of absolute deviation. Data from a very simple … Read more
Abstract: The SDPA (SemiDefinite Programming Algorithm) is known as efficient computer software based on primal-dual interior-point method for solving SDPs (Semidefinite Programs). In many applications, however, some SDPs become larger and larger, too large for the SDPA to solve on a single processor. In execution of the SDPA applied to large scale SDPs, the computation … Read more
This thesis is about mathematical optimization. Mathematical optimization involves the construction of methods to solve optimization problems, which can arise from real-life problems in applied science, when they are mathematically modeled. Examples come from electrical design, engineering, control theory, telecommunication, environment, finance, and logistics. This thesis deals especially with semidefinite optimization problems. Semidefinite programming is … Read more
This paper attempts to extend the notion of duality for convex cones, by basing it on a pre-described conic ordering and a fixed bilinear mapping. This is an extension of the standard definition of dual cones, in the sense that the {\em nonnegativity}\/ of the inner-product is replaced by a pre-specified conic ordering, defined by … Read more
The SDPA (SemiDefinite Programming Algorithm) is a software package for solving general SDPs(SemiDefinite Programs). It is written in C++ with the help of {\it LAPACK} for numerical linear algebra for dense matrix computation. The purpose of this paper is to present a brief description of the latest version of the SDPA and its high performance … Read more
The trust region subproblem (the minimization of a quadratic objective subject to one quadratic constraint and denoted TRS) has many applications in diverse areas, e.g. function minimization, sequential quadratic programming, regularization, ridge regression, and discrete optimization. In particular, it determines the step in trust region algorithms for function minimization. Trust region algorithms are popular for … Read more
Semidefinite Programming (SDP) provides strong bounds for many NP-hard combinatorial problems. Arguably the most popular/efficient search direction for solving SDPs using a primal-dual interior point (p-d i-p) framework is the {\em HKM direction}. This direction is a Newton direction found from the linearization of a symmetrized version of the optimality conditions. For many of the … Read more