Convex Optimization

Linearized Alternating Direction Method of Multipliers via Positive-Indefinite Proximal Regularization for Convex Programming

  • Bingsheng He
  • Feng Ma
  • Xiao-Ming Yuan
    • Categories Convex Optimization Tags , , , ,

    The alternating direction method of multipliers (ADMM) is being widely used for various convex minimization models with separable structures arising in a variety of areas. In the literature, the proximalversion of ADMM which allows ADMM’s subproblems to be proximally regularized has been well studied. Particularly the linearized version of ADMM can be yielded when the … Read more

    Convex Relaxations for Quadratic On/Off Constraints and Applications to Optimal Transmission Switching

  • Ksenia Bestuzheva
  • Carleton Coffrin
  • Hassan L. Hijazi
    • Categories (Mixed) Integer Nonlinear Programming, Applications - Science and Engineering, Convex Optimization Tags , , , ,

    This paper studies mixed-integer nonlinear programs featuring disjunctive constraints and trigonometric functions. We first characterize the convex hull of univariate quadratic on/off constraints in the space of original variables using perspective functions. We then introduce new tight quadratic relaxations for trigonometric functions featuring variables with asymmetrical bounds. These results are used to further tighten recent … Read more

    Random permutations fix a worst case for cyclic coordinate descent

  • Stephen Wright
  • Ching-pei Lee
    • Categories Convex Optimization Tags , ,

    Variants of the coordinate descent approach for minimizing a nonlinear function are distinguished in part by the order in which coordinates are considered for relaxation. Three common orderings are cyclic (CCD), in which we cycle through the components of $x$ in order; randomized (RCD), in which the component to update is selected randomly and independently … Read more

    Step lengths in BFGS method for monotone gradients

  • Yunda Dong
    • Categories Convex Optimization, Unconstrained Optimization

    In this paper, we consider how to directly apply the BFGS method to finding a zero point of any given monotone gradient and thus suggest new conditions to locate the corresponding step lengths. The suggested conditions involve curvature condition and merely use gradients’ computations. Furthermore, they can guarantee convergence without any other restrictions. Finally, preliminary … Read more

    Perturbation Analysis of Singular Semidefinite Program and Its Application to a Control Problem

  • Yoshiyuki Sekiguchi
  • Hayato Waki
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    We consider the sensitivity of semidefinite programs (SDPs) under perturbations. It is well known that the optimal value changes continuously under perturbations on the right hand side in the case where the Slater condition holds in the primal problems. In this manuscript, we observe by investigating a concrete SDP that the optimal value can be … Read more

    Faster Alternating Direction Method of Multipliers with a Worst-case O(1/n^2) Convergence Rate

  • Wenyi Tian
  • Xiao-Ming Yuan
    • Categories Convex Optimization Tags , , , ,

    The alternating direction method of multipliers (ADMM) is being widely used for various convex programming models with separable structures arising in specifically many scientific computing areas. The ADMM’s worst-case O(1/n) convergence rate measured by the iteration complexity has been established in the literature when its penalty parameter is a constant, where n is the iteration … Read more

    Multiple cuts in separating plane algorithms

  • Evgeni Alekseevich Nurminski
    • Categories Convex Optimization Tags , , , ,

    This paper presents an extended version of the separation plane algorithms for subgradient-based finite-dimensional nondifferentiable convex blackbox optimization. The extension introduces additional cuts for epigraph of the conjugate of objective function which improve the convergence of the algorithm. The case of affine cuts is considered in more details and it is shown that it requires … Read more

    Steplength thresholds for invariance preserving of discretization methods of dynamical systems on a polyhedron

  • Zoltán Horváth
  • Tamás Terlaky
  • Yunfei Song
    • Categories Convex and Nonsmooth Optimization, Convex Optimization Tags , , , ,

    Steplength thresholds for invariance preserving of three types of discretization methods on a polyhedron are considered. For Taylor approximation type discretization methods we prove that a valid steplength threshold can be obtained by finding the first positive zeros of a finite number of polynomial functions. Further, a simple and efficient algorithm is proposed to numerically … Read more

    Invariance conditions for nonlinear dynamical systems

  • Zoltán Horváth
  • Tamás Terlaky
  • Yunfei Song
    • Categories Convex Optimization Tags , , , ,

    Recently, Horv\’ath, Song, and Terlaky [\emph{A novel unified approach to invariance condition of dynamical system, submitted to Applied Mathematics and Computation}] proposed a novel unified approach to study, i.e., invariance conditions, sufficient and necessary conditions, under which some convex sets are invariant sets for linear dynamical systems. In this paper, by utilizing analogous methodology, we … Read more

    Frechet inequalities via convex optimization

  • Paul Embrechts
  • Paul J. Goulart
  • Bart Paul Gerard Van Parys
    • Categories Convex Optimization, Infinite Dimensional Optimization, Robust Optimization Tags , ,

    Quantifying the risk carried by an aggregate position $S_d\defn\sum_{i=1}^d X_i$ comprising many risk factors $X_i$ is fundamental to both insurance and financial risk management. Frechet inequalities quantify the worst-case risk carried by the aggregate position given distributional information concerning its composing factors but without assuming independence. This marginal factor modeling of the aggregate position in … Read more