Convex Optimization

The kernel average for two convex functions and its application to the extension and representation of monotone operators

  • Heinz Bauschke
  • Xianfu Wang
    • Categories Convex Optimization Tags , , , , , , , , ,

    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

    Two Algorithms for the Minimum Enclosing Ball Problem

  • E. Alper Yildirim
    • Categories Convex Optimization Tags , ,

    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

    An Augmented Primal-Dual Method for Linear Conic Programs

  • Florian Jarre
  • Franz Rendl
    • Categories Convex Optimization Tags , ,

    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

    Approximate Primal Solutions and Rate Analysis in Dual Subgradient Methods

  • Angelia Nedich
  • Asuman Ozdaglar
    • Categories Constrained Nonlinear Optimization, Convex Optimization, Nonsmooth Optimization Tags , , , ,

    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

    Solving the uncapacitated facility location problem with semi-Lagrangian relaxation

  • Antonio Alonso-Ayuso
  • Cesar Beltran-Royo
  • Jean-Philippe Vial
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming, Convex Optimization Tags , ,

    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

    Self-Concordant Barriers for Convex Approximations of Structured Convex Sets

  • Arkadi Nemirovski
  • Levent Tunçel
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    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

    Optimal data fitting: a moment approach

  • Dimitris Bertsimas
  • Xuan Vinh Doan
  • Jean-Bernard Lasserre
    • Categories Convex Optimization Tags , , ,

    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

    Multivariate exponential integral approximations: a moment approach

  • Dimitris Bertsimas
  • Xuan Vinh Doan
  • Jean-Bernard Lasserre
    • Categories Convex Optimization Tags ,

    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

    Polynomial time algorithms to approximate mixed volumes within a simply exponential factor

  • Leonid Gurvits
    • Categories Approximation Algorithms, Convex Optimization Tags , , ,

    We study in this paper randomized algorithms to approximate the mixed volume of well-presented convex compact sets. Our main result is a randomized poly-time algorithm which approximates $V(K_1,…,K_n)$ with multiplicative error $e^n$ and with better rates if the affine dimensions of most of the sets $K_i$ are small.\\ Even such rate is impossible to achieve … Read more

    Constraint Nondegeneracy, Strong Regularity and Nonsingularity in Semidefinite Programming

  • Zi Xian Chan
  • Defeng Sun
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , , ,

    It is known that the Karush-Kuhn-Tucker (KKT) conditions of semidefinite programming can be reformulated as a nonsmooth system via the metric projector over the cone of symmetric and positive semidefinite matrices. We show in this paper that the primal and dual constraint nondegeneracies, the strong regularity, the nonsingularity of the B-subdifferential of this nonsmooth system, … Read more