Convex and Nonsmooth 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

    The Speed of Shor’s R-Algorithm

  • James V. Burke
  • Adrian Lewis
  • Michael L. Overton
    • Categories Nonsmooth Optimization, Unconstrained Optimization Tags , , , ,

    Shor’s r-algorithm is an iterative method for unconstrained optimization, designed for minimizing nonsmooth functions, for which its reported success has been considerable. Although some limited convergence results are known, nothing seems to be known about the algorithm’s rate of convergence, even in the smooth case. We study how the method behaves on convex quadratics, proving … 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

    A Coordinate Gradient Descent Method for Nonsmooth Separable Minimization

  • Paul Tseng
  • Sangwoon Yun
    • Categories Bound-constrained Optimization, Convex and Nonsmooth Optimization Tags

    We consider the problem of minimizing the sum of a smooth function and a separable convex function. This problem includes as special cases bound-constrained optimization and smooth optimization with l_1-regularization. We propose a (block) coordinate gradient descent method for solving this class of nonsmooth separable problems. We establish global convergence and, under a local Lipschitzian … Read more

    Monotonicity of L”{o}wner Operators and Its Applications to Symmetric Cone Complementarity Problems

  • Lingchen Kong
  • Levent Tunçel
  • Naihua Xiu
    • Categories Complementarity and Variational Inequalities, Generalized Convexity/Monoticity, Semi-definite Programming Tags , , , ,

    This paper focuses on monotone L\”{o}wner operators in Euclidean Jordan algebras and their applications to the symmetric cone complementarity problem (SCCP). We prove necessary and sufficient conditions for locally Lipschitz L\”{o}wner operators to be monotone, strictly monotone and strongly monotone. We also study the relationship between monotonicity and operator-monotonicity of L\”{o}wner operators. As a by-product … Read more

    Accuracy Certificates for Computational Problems with Convex Structure

  • Arkadi Nemirovski
  • Shmuel Onn
  • Uriel Rothblum
    • Categories Convex and Nonsmooth Optimization Tags , ,

    The goal of the current paper is to introduce the notion of certificates which verify the accuracy of solutions of computational problems with convex structure; such problems include minimizing convex functions, variational inequalities corresponding to monotone operators, computing saddle points of convex-concave functions and solving convex Nash equilibrium problems. We demonstrate how the implementation 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

    One Class Nonsmooth Dyscrete Step Control Problem

  • Shahlar Maharramov
    • Categories Nonsmooth Optimization Tags , , , ,

    In this paper a survey and refinement of its recent results in the discrete optimal control theory are presented. The step control problem depending on a parameter is investigated. No smoothness of the cost function is assumed and new versions of the discrete maximum principle for the step control problem are derived Citationsubmited to the … Read more

    Separation of convex polyhedral sets with uncertain data

  • Milan Hladik
    • Categories Convex and Nonsmooth Optimization, Robust Optimization Tags , , , ,

    This paper is a contribution to the interval analysis and separability of convex sets. Separation is a familiar principle and is often used not only in optimization theory, but in many economic applications as well. In real problems input data are usually not known exactly. For the purpose of this paper we assume that data … Read more