On an SDP relaxation for kissing number

We demonstrate that an earlier semidefinite-programming relaxation for the kissing-number problem cannot provide good upper bounds. Furthermore, we show the existence of an optimal solution for this relaxation that cannot be used as a basis for establishing a good lower bound.     

An exact Jacobian SDP relaxation for polynomial optimization

Given polynomials f (x), g _i (x), h _j (x), we study how to minimize f (x) on the set $$S = \left\{ x \in \mathbb{R}^n:\, h_1(x) = \cdots = h_{m_1}(x) = 0,\\ g_1(x)\geq 0, \ldots, g_{m_2}(x) \geq 0 \right\}.$$ Let f _min be the minimum of f on S. Suppose S is nonsingular and f _min is achievable on S, which are true generically. This paper proposes a new type semidefinite programming (SDP) relaxation which is the first one for solving this problem exactly. First, we construct new polynomials ${\varphi_1, \ldots, \varphi_r}$ , by using the Jacobian of f, h _i , g _j , such that the above problem is equivalent to $$\begin{gathered}\underset{x\in\mathbb{R}^n}{\min} f(x) \hfill \\ \, \, {\rm s.t.}\; h_i(x) = 0, \, \varphi_j(x) = 0, \, 1\leq i \leq m_1, 1 \leq j \leq r, \hfill \\ \quad \, \, \, g_1(x)^{\nu_1}\cdots g_{m_2}(x)^{\nu_{m_2}}\geq 0, \, \quad\forall\, \nu \,\in \{0,1\}^{m_2} .\hfill \end{gathered}$$ Second, we prove that for all N big enough, the standard N-th order Lasserre’s SDP relaxation is exact for solving this equivalent problem, that is, its optimal value is equal to f _min. Some variations and examples are also shown.     

A SUCCESSIVE QUADRATIC PROGRAMMING ALGORITHM FOR SDP RELAXATION OF MAX-BISECTION

A successive quadratic programming algorithm for solving SDP relaxation of Max- Bisection is provided and its convergence result is given.The step-size in the algorithm is obtained by solving n easy quadratic equations without using the linear search technique.The numerical experiments show that this algorithm is rather faster than the interior-point method.     

Exactness conditions for an SDP relaxation of the extended trust region problem

In this paper we show that a standard SDP relaxation for so called extended trust-region problem is equivalent to a convex quadratic problem, with a linear objective and constraint functions and some additional simple convex quadratic constraints. Through this equivalence, new conditions, generalizing the ones existing in the literature, under which the SDP relaxation is exact, are introduced.     

A New Neighborhood for the QAP

Local search procedures are popular methods to solve combinatorial problems and neighborhood structures are the main part of those algorithms. This paper presents a new neighborhood for the Quadratic Assignment Problem. The proposed neighborhood is compared with the classical 2-exchange neighborhood.     

Minimizing rational functions by exact Jacobian SDP relaxation applicable to finite singularities

This paper considers the optimization problem of minimizing a rational function. We reformulate this problem as a polynomial optimization problem by the technique of homogenization. These two problems are shown to be equivalent under some generic conditions. The exact Jacobian SDP relaxation method proposed by Nie is used to solve the resulting polynomial optimization problem. We also prove that the assumption of nonsingularity in Nie’s method can be weakened to the finiteness of singularities. Some numerical examples are given in the end.     

A general framework for ADMM acceleration

Numerical Algorithms - The Alternating Direction Multipliers Method (ADMM) is a very popular algorithm for computing the solution of convex constrained minimization problems. Such problems are...     

Generalized symmetric ADMM for separable convex optimization

The alternating direction method of multipliers (ADMM) has been proved to be effective for solving separable convex optimization subject to linear constraints. In this paper, we propose a generalized symmetric ADMM (GS-ADMM), which updates the Lagrange multiplier twice with suitable stepsizes, to solve the multi-block separable convex programming. This GS-ADMM partitions the data into two group variables so that one group consists of p block variables while the other has q block variables, where \(p \ge 1\) and \(q \ge 1\) are two integers. The two grouped variables are updated in a Gauss–Seidel scheme, while the variables within each group are updated in a Jacobi scheme, which would make it very attractive for a big data setting. By adding proper proximal terms to the subproblems, we specify the domain of the stepsizes to guarantee that GS-ADMM is globally convergent with a worst-case \({\mathcal {O}}(1/t)\) ergodic convergence rate. It turns out that our convergence domain of the stepsizes is significantly larger than other convergence domains in the literature. Hence, the GS-ADMM is more flexible and attractive on choosing and using larger stepsizes of the dual variable. Besides, two special cases of GS-ADMM, which allows using zero penalty terms, are also discussed and analyzed. Compared with several state-of-the-art methods, preliminary numerical experiments on solving a sparse matrix minimization problem in the statistical learning show that our proposed method is effective and promising.     

A conversion of an SDP having free variables into the standard form SDP

This paper deals with a semidefinite program (SDP) having free variables, which often appears in practice. To apply the primal–dual interior-point method, we usually need to convert our SDP into the standard form having no free variables. One simple way of conversion is to represent each free variable as a difference of two nonnegative variables. But this conversion not only expands the size of the SDP to be solved but also yields some numerical difficulties which are caused by the non-existence of a primal–dual pair of interior-feasible solutions in the resulting standard form SDP and its dual. This paper proposes a new conversion method that eliminates all free variables. The resulting standard form SDP is smaller in its size, and it can be more stably solved in general because the SDP and its dual have interior-feasible solutions whenever the original primal–dual pair of SDPs have interior-feasible solutions. Effectiveness of the new conversion method applied to SDPs having free variables is reported in comparison to some other existing methods.