We review several (and provide new) results on the theory of moments, sums of squares and basic semi-algebraic sets when convexity is present. In particular, we show that under convexity, the hierarchy of semidefinite relaxations for polynomial optimization simplifies and has finite convergence, a highly desirable feature as convex problems are in principle easier to … Read more
In this paper, we extend the Ai-Zhang direction to the class of semidefinite optimization problems. We define a new wide neighborhood $\N(\tau_1,\tau_2,\eta)$ and, as usual, we utilize symmetric directions by scaling the Newton equation with special matrices. After defining the “positive part” and the “negative part” of a symmetric matrix, we solve the Newton equation … Read more
We give an elementary proof of optimality conditions for linear programming. The proof is direct, built on a straightforward classical perturbation of the constraints, and does not require either the use of Farkas’ lemma or the use of the simplex method. CitationTechnical Report TRITA-MAT-2008-OS6, Department of Mathematics, Royal Institute of Technology (KTH), SE-100 44 Stockholm, … Read more
In many applications in statistics, finance, and insurance/reinsurance, one seeks a solution of finding a covariance matrix satisfying a large number of given linear equality and inequality constraints in a way that it deviates the least from a given symmetric matrix. The difficulty in finding an efficient method for solving this problem is due to … Read more
Euclidean Jordan-algebra is a commonly used tool in designing interior point algorithms for symmetric cone programs. T-algebra, on the other hand, has rarely been used in symmetric cone programming. In this paper, we use both algebraic characterizations of symmetric cones to extend the target-following framework of linear programming to symmetric cone programming. Within this framework, … Read more
The space of linear programs (LP) can be partitioned into a finite number of sets, each corresponding to a basis. This partition is thus called the basis partition. The closed-form solution on the space of LP can be determined with the basis partition if we can characterize the basis partition. A differential equation on the … Read more
Linear programming is arguably one of the most basic forms of optimization. Its theory and algorithms can not only be applied to linear optimization problems but also to relaxations of nonlinear problems and branch-and-bound methods for mixed-integer and global optimization problems. Recent research shows that against intuition bad condition numbers frequently occur in linear programming. … Read more
The problem of approximately factoring a real or complex multivariate polynomial $f$ seeks minimal perturbations $\Delta f$ to the coefficients of the input polynomial $f$ so that the deformed polynomial $f + \Delta f$ has the desired factorization properties. Efficient algorithms exist that compute the nearest real or complex polynomials that has non-trivial factors. (see … Read more
In this paper, we analyze the limiting behavior of the weighted least squares problem $\min_{x\in\Re^n}\sum_{i=1}^p\|D_i(A_ix-b_i)\|^2$, where each $D_i$ is a positive definite diagonal matrix. We consider the situation where the magnitude of the weights are drastically different block-wisely so that $\max(D_1)\geq\min(D_1) \gg \max(D_2) \geq \min(D_2) \gg \max(D_3) \geq \ldots \gg \max(D_{p-1}) \geq \min(D_{p-1}) \gg \max(D_p)$. … Read more
The convex cone of $n \times n$ completely positive (CPP) matrices and its dual cone of copositive matrices arise in several areas of applied mathematics, including optimization. Every CPP matrix is doubly nonnegative (DNN), i.e., positive semidefinite and component-wise nonnegative, and it is known that, for $n \le 4$ only, every DNN matrix is CPP. … Read more