Global Convergence of ADMM in Nonconvex Nonsmooth Optimization

In this paper, we analyze the convergence of the alternating direction method of multipliers (ADMM) for minimizing a nonconvex and possibly nonsmooth objective function, $\phi(x_0,\ldots,x_p,y)$, subject to coupled linear equality constraints. Our ADMM updates each of the primal variables $x_0,\ldots,x_p,y$, followed by updating the dual variable. We separate the variable $y$ from $x_i$’s as it … Read more

Efficient solution of quadratically constrained quadratic subproblems within the MADS algorithm

The Mesh Adaptive Direct Search algorithm (MADS) is an iterative method for constrained blackbox optimization problems. One of the optional MADS features is a versatile search step in which quadratic models are built leading to a series of quadratically constrained quadratic subproblems. This work explores different algorithms that exploit the structure of the quadratic models: … Read more

The Rate of Convergence of Augmented Lagrange Method for a Composite Optimization Problem

In this paper we analyze the rate of local convergence of the augmented Lagrange method for solving optimization problems with equality constraints and the objective function expressed as the sum of a convex function and a twice continuously differentiable function. The presence of the non-smoothness of the convex function in the objective requires extensive tools … Read more

Locally weighted regression models for surrogate-assisted design optimization

Locally weighted regression combines the advantages of polynomial regression and kernel smoothing. We present three ideas for appropriate and effective use of LOcally WEighted Scatterplot Smoothing (LOWESS) models for surrogate optimization. First, a method is proposed to reduce the computational cost of LOWESS models. Second, a local scaling coefficient is introduced to adapt LOWESS models … Read more

Extending the ergodic convergence rate of the proximal ADMM

Pointwise and ergodic iteration-complexity results for the proximal alternating direction method of multipliers (ADMM) for any stepsize in $(0,(1+\sqrt{5})/2)$ have been recently established in the literature. In addition to giving alternative proofs of these results, this paper also extends the ergodic iteration-complexity result to include the case in which the stepsize is equal to $(1+\sqrt{5})/2$. … Read more

How to project onto extended second order cones

The extended second order cones were introduced by S. Z. Németh and G. Zhang in [S. Z. Németh and G. Zhang. Extended Lorentz cones and variational inequalities on cylinders. J. Optim. Theory Appl., 168(3):756-768, 2016] for solving mixed complementarity problems and variational inequalities on cylinders. R. Sznajder in [R. Sznajder. The Lyapunov rank of extended … Read more

Homotopy Smoothing for Non-Smooth Problems with Lower Complexity than O(1/epsilon)

In this paper, we develop a novel {\bf ho}moto{\bf p}y {\bf s}moothing (HOPS) algorithm for solving a family of non-smooth problems that is composed of a non-smooth term with an explicit max-structure and a smooth term or a simple non-smooth term whose proximal mapping is easy to compute. The best known iteration complexity for solving … Read more

A general double-proximal gradient algorithm for d.c. programming

The possibilities of exploiting the special structure of d.c. programs, which consist of optimizing the difference of convex functions, are currently more or less limited to variants of the DCA proposed by Pham Dinh Tao and Le Thi Hoai An in 1997. These assume that either the convex or the concave part, or both, are … Read more

Nonsmooth optimization using Taylor-like models: error bounds, convergence, and termination criteria

We consider optimization algorithms that successively minimize simple Taylor-like models of the objective function. Methods of Gauss-Newton type for minimizing the composition of a convex function and a smooth map are common examples. Our main result is an explicit relationship between the step-size of any such algorithm and the slope of the function at a … Read more