Convex and Nonsmooth Optimization

Improving an ADMM-like Splitting Method via Positive-Indefinite Proximal Regularization for Three-Block Separable Convex Minimization

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

    The augmented Lagrangian method (ALM) is fundamental for solving convex minimization models with linear constraints. When the objective function is separable such that it can be represented as the sum of more than one function without coupled variables, various splitting versions of the ALM have been well studied in the literature such as the alternating … Read more

    A simple preprocessing algorithm for semidefinite programming

  • Preston Faulk
  • Gabor Pataki
  • Quoc Tran-Dinh
    • Categories Convex Optimization, Optimization Software Benchmark, Semi-definite Programming

    We propose a very simple preprocessing algorithm for semidefinite programming. Our algorithm inspects the constraints of the problem, deletes redundant rows and columns in the constraints, and reduces the size of the variable matrix. It often detects infeasibility. Our algorithm does not rely on any optimization solver: the only subroutine it needs is Cholesky factorization, … Read more

    Constructing New Weighted l1-Algorithms for the Sparsest Points of Polyhedral Sets

  • Zhi-Quan Luo
  • Yun-Bin Zhao
    • Categories Basic Sciences Applications, Convex and Nonsmooth Optimization Tags , , , , , ,

    The l0-minimization problem that seeks the sparsest point of a polyhedral set is a longstanding challenging problem in the fields of signal and image processing, numerical linear algebra and mathematical optimization. The weighted l1-method is one of the most plausible methods for solving this problem. In this paper, we develop a new weighted l1-method through … Read more

    Exploiting Problem Structure in Optimization under Uncertainty via Online Convex Optimization

  • Nam Ho-Nguyen
  • Fatma Kılınç-Karzan
    • Categories Convex and Nonsmooth Optimization, Nonlinear Optimization Tags , ,

    In this paper, we consider two paradigms that are developed to account for uncertainty in optimization models: robust optimization (RO) and joint estimation-optimization (JEO). We examine recent developments on efficient and scalable iterative first-order methods for these problems, and show that these iterative methods can be viewed through the lens of online convex optimization (OCO). … Read more

    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

    A highly efficient semismooth Newton augmented Lagrangian method for solving Lasso problems

  • Xudong Li
  • Defeng Sun
  • Kim-Chuan Toh
    • Categories Nonsmooth Optimization Tags , , , ,

    We develop a fast and robust algorithm for solving large scale convex composite optimization models with an emphasis on the $\ell_1$-regularized least squares regression (Lasso) problems. Despite the fact that there exist a large number of solvers in the literature for the Lasso problems, we found that no solver can efficiently handle difficult large scale … Read more