Aiming at a fast and robust simulation of large multibody systems with contacts and friction, this work presents a novel method for solving large cone complementarity problems by means of a fixed-point iteration. The method is an extension of the Gauss-Seidel and Gauss-Jacobi method with overrelaxation for symmetric convex linear complementarity problems. The method is … Read more
A common method for constructing a function from a finite set of moments is to solve a constrained minimization problem. The idea is to find, among all functions with the given moments, that function which minimizes a physically motivated, strictly convex functional. In the kinetic theory of gases, this functional is the kinetic entropy; the … Read more
We provide and analyze a based average for two convex functions, based on a kernel function. It covers several known averages such as the arithmetic average, epigraphical average, and the proximal average. When applied to the Fitzpatrick function and the conjugate of Fitzpatrick function associated with a monotone operator, our average produces an autoconjugate (also … Read more
Given $\cA := \{a^1,\ldots,a^m\} \subset \R^n$ and $\eps > 0$, we propose and analyze two algorithms for the problem of computing a $(1 + \eps)$-approximation to the radius of the minimum enclosing ball of $\cA$. The first algorithm is closely related to the Frank-Wolfe algorithm with a proper initialization applied to the dual formulation of … Read more
We propose a new iterative approach for solving linear programs over convex cones. Assuming that Slaters condition is satisfied, the conic problem is transformed to the minimization of a convex differentiable function. This “agumented primal-dual function” or “apd-function” is restricted to an affine set in the primal-dual space. The evaluation of the function and its … Read more
We study primal solutions obtained as a by-product of subgradient methods when solving the Lagrangian dual of a primal convex constrained optimization problem (possibly nonsmooth). The existing literature on the use of subgradient methods for generating primal optimal solutions is limited to the methods producing such solutions only asymptotically (i.e., in the limit as the … Read more
The semi-Lagrangian Relaxation (SLR) method has been introduced in Beltran et al. (2006) to solve the p-median problem. In this paper we apply the method to the Uncapacitated Facility Location (UFL) problem. We perform computational experiments on two main collections of UFL problems with unknown optimal values. On one collection, we manage to solve to … Read more
We show how to approximate the feasible region of structured convex optimization problems by a family of convex sets with explicitly given and efficient (if the accuracy of the approximation is moderate) self-concordant barriers. This approach extends the reach of the modern theory of interior-point methods, and lays the foundation for new ways to treat … Read more
We propose a moment relaxation for two problems, the separation and covering problem with semi-algebraic sets generated by a polynomial of degree d. We show that (a) the optimal value of the relaxation finitely converges to the optimal value of the original problem, when the moment order r increases and (b) there exist probability measures … Read more
We propose a method to approximate a class of exponential multivariate integrals using moment relaxations. Using this approach, both lower and upper bounds of the integrals are obtained and we show that these bound values asymptotically converge to the real value of the integrals when the moment degree r increases. We further demonstrate the method … Read more