Recently Tseng (Math Program 83:159185, 1998) extended a class of merit functions, proposed by Luo and Tseng (<i>A new class of merit functions for the nonlinear complementarity problem</i>, in Complementarity and Variational Problems: State of the Art, pp. 204225, 1997), for the nonlinear complementarity problem (NCP) to the semidefinite complementarity problem (SDCP) and showed several related properties. In this paper, we extend this class of merit functions to the second-order cone complementarity problem (SOCCP) and show analogous properties as in NCP and SDCP cases. In addition, we study another class of merit functions which are based on a slight modification of the aforementioned class of merit functions. Both classes of merit functions provide an error bound for the SOCCP and have bounded level sets.

Many iterative methods in optimization are fixed-point iterations with averaged operators. As such methods converge at an O(1/k) rate with the constant determined by the averagedness coefficient, establishing small averagedness coefficients for operators is of broad interest. In this paper, we show that the averagedness coefficients of the composition of averaged operators by Ogura and Yamada (Numer Func Anal Opt 32(1–2):113–137, 2002) and the threeoperator splitting by Davis and Yin (Set Valued Var Anal 25(4):829–858, 2017) are tight. The analysis relies on the scaled relative graph, a geometric tool recently proposed by Ryu, Hannah, and Yin (arXiv:1902.09788, 2019).

We study correlation bounds under pairwise independent distributions for functions with no large Fourier coefficients. Functions in which all Fourier coefficients are bounded by$δ$are called$δ$-$uniform$. The search for such bounds is motivated by their potential applicability to hardness of approximation, derandomization, and additive combinatorics.

No abstract uploaded!

First-order methods have been popularly used for solving large-scale problems. However, many existing works only consider unconstrained problems or those with simple constraint. In this paper, we develop two first-order methods for constrained convex programs, for which the constraint set is represented by affine equations and smooth nonlinear inequalities. Both methods are based on the classic augmented Lagrangian function. They update the multipliers in the same way as the augmented Lagrangian method (ALM) but employ different primal variable updates. The first method, at each iteration, performs a single proximal gradient step to the primal variable, and the second method is a block update version of the first one.