Conic relaxation approaches for equal deployment problems

An important problem in the breeding of livestock, crops, and forest trees is the optimum of selection of genotypes that maximizes genetic gain. The key constraint in the optimal selection is a convex quadratic constraint that ensures genetic diversity, therefore, the optimal selection can be cast as a second-order cone programming (SOCP) problem. Yamashita et … Read more

Solving sparse polynomial optimization problems with chordal structure using the sparse, bounded-degree sum-of-squares hierarchy

The sparse bounded degree sum-of-squares (sparse-BSOS) hierarchy of Weisser, Lasserre and Toh [arXiv:1607.01151,2016] constructs a sequence of lower bounds for a sparse polynomial optimization problem. Under some assumptions, it is proven by the authors that the sequence converges to the optimal value. In this paper, we modify the hierarchy to deal with problems containing equality … Read more

A semi-analytical approach for the positive semidefinite Procrustes problem

The positive semidefinite Procrustes (PSDP) problem is the following: given rectangular matrices $X$ and $B$, find the symmetric positive semidefinite matrix $A$ that minimizes the Frobenius norm of $AX-B$. No general procedure is known that gives an exact solution. In this paper, we present a semi-analytical approach to solve the PSDP problem. First, we characterize … Read more

Comparison of Lasserre’s measure–based bounds for polynomial optimization to bounds obtained by simulated annealing

We consider the problem of minimizing a continuous function f over a compact set K. We compare the hierarchy of upper bounds proposed by Lasserre in [SIAM J. Optim. 21(3) (2011), pp. 864-885] to bounds that may be obtained from simulated annealing. We show that, when f is a polynomial and K a convex body, … Read more

Computing Weighted Analytic Center for Linear Matrix Inequalities Using Infeasible Newton’s Method

We study the problem of computing weighted analytic center for system of linear matrix inequality constraints. The problem can be solved using the Standard Newton’s method. However, this approach requires that a starting point in the interior point of the feasible region be given or a Phase I problem be solved. We address the problem … Read more

Statistical Inference of Semidefinite Programming

In this paper we consider covariance structural models with which we associate semidefinite programming problems. We discuss statistical properties of estimates of the respective optimal value and optimal solutions when the `true’ covariance matrix is estimated by its sample counterpart. The analysis is based on perturbation theory of semidefinite programming. As an example we consider … Read more

Geometry of 3D Environments and Sum of Squares Polynomials

Motivated by applications in robotics and computer vision, we study problems related to spatial reasoning of a 3D environment using sublevel sets of polynomials. These include: tightly containing a cloud of points (e.g., representing an obstacle) with convex or nearly-convex basic semialgebraic sets, computation of Euclidean distance between two such sets, separation of two convex … Read more

On the Fermat point of a triangle

For a given triangle $\triangle ABC$, Pierre de Fermat posed around 1640 the problem of finding a point $P$ minimizing the sum $s_P$ of the Euclidean distances from $P$ to the vertices $A$, $B$, $C$. Based on geometrical arguments this problem was first solved by Torricelli shortly after, by Simpson in 1750, and by several … Read more

A polynomial algorithm for linear feasibility problems given by separation oracles

The algorithm proposed in this paper runs in a polynomial oracle time, i.e., in a number of arithmetic operations and calls to the separation oracle bounded by a polynomial in the number of variables and in the maximum binary size of an entry of the coefficient matrix. This algorithm is much simpler than traditional polynomial … Read more

Semidefinite Programming Approach to Russell Measure Model

Throughout its evolution, data envelopment analysis (DEA) has mostly relied on linear programming, particularly because of simple primal-dual relations and the existence of standard software for solving linear programs. Although also non-linear models, such as Russell measure or hyperbolic measure models, have been introduced, their use in applications has been limited mainly because of their … Read more