Abstract:
A branch and bound algorithm is developed for global optimization. Branching in the algorithm is accomplished by subdividing the feasible set using ellipses. Lower bounds are obtained by replacing the concave part of the objective function by an affine underestimate. A ball approximation algorithm, obtained by generalizing of a scheme of Lin and Han, is used to solve the convex relaxation of the original problem. The ball approximation algorithm is compared to SEDUMI as well as to gradient projection algorithms using randomly generated test problems with a quadratic objective and ellipsoidal constraints.

Abstract:
We consider concave minimization problems over non-convex sets.Optimization problems with this structure arise in sparse principal component analysis. We analyze both a gradient projection algorithm and an approximate Newton algorithm where the Hessian approximation is a multiple of the identity. Convergence results are established. In numerical experiments arising in sparse principal component analysis, it is seen that the performance of the gradient projection algorithm is very similar to that of the truncated power method and the generalized power method. In some cases, the approximate Newton algorithm with a Barzilai-Borwein (BB) Hessian approximation can be substantially faster than the other algorithms, and can converge to a better solution.

Abstract:
The convergence rate is analyzed for the SpaSRA algorithm (Sparse Reconstruction by Separable Approximation) for minimizing a sum $f (\m{x}) + \psi (\m{x})$ where $f$ is smooth and $\psi$ is convex, but possibly nonsmooth. It is shown that if $f$ is convex, then the error in the objective function at iteration $k$, for $k$ sufficiently large, is bounded by $a/(b+k)$ for suitable choices of $a$ and $b$. Moreover, if the objective function is strongly convex, then the convergence is $R$-linear. An improved version of the algorithm based on a cycle version of the BB iteration and an adaptive line search is given. The performance of the algorithm is investigated using applications in the areas of signal processing and image reconstruction.

Abstract:
An exact algorithm is presented for solving edge weighted graph partitioning problems. The algorithm is based on a branch and bound method applied to a continuous quadratic programming formulation of the problem. Lower bounds are obtained by decomposing the objective function into convex and concave parts and replacing the concave part by an affine underestimate. It is shown that the best affine underestimate can be expressed in terms of the center and the radius of the smallest sphere containing the feasible set. The concave term is obtained either by a constant diagonal shift associated with the smallest eigenvalue of the objective function Hessian, or by a diagonal shift obtained by solving a semidefinite programming problem. Numerical results show that the proposed algorithm is competitive with state-of-the-art graph partitioning codes.

Abstract:
We consider demand-side primary frequency control in the power grid provided by smart and flexible loads: loads change consumption to match generation and help the grid while minimizing disutility for consumers incurred by consumption changes. The dual formulation of this problem has been solved previously by Zhao et al. in a decentralized manner for consumer disutilities that are twice continuously differentiable with respect to consumption changes. In this work, we propose a decentralized multi-block alternating-direction-method-of-multipliers (DM-ADMM) algorithm to solve this problem. In contrast to the dual ascent algorithm of Zhao et al., the proposed DM-ADMM algorithm does not require the disutilities to be continuously differentiable; this allows disutility functions that model consumer behavior that may be quite common. In this work, we prove convergence of the DM-ADMM algorithm in the deterministic setting (i.e., when loads may estimate the consumption-generation mismatch from frequency measurements exactly). We test the performance of the DM-ADMM algorithm in simulations, and we compare (when applicable) with the previously proposed solution for the dual formulation. We also present numerical results for a previously proposed ADMM algorithm, whose results were not previously reported.

Abstract:
The Vertex Separator Problem (VSP) on a graph is the problem of finding the smallest collection of vertices whose removal separates the graph into two disjoint subsets of roughly equal size. Recently, Hager and Hungerford [1] developed a continuous bilinear programming formulation of the VSP. In this paper, we reinforce the bilinear programming approach with a multilevel scheme for learning the structure of the graph.

Abstract:
A local convergence rate is established for an orthogonal collocation method based on Gauss quadrature applied to an unconstrained optimal control problem. If the continuous problem has a sufficiently smooth solution and the Hamiltonian satisfies a strong convexity condition, then the discrete problem possesses a local minimizer in a neighborhood of the continuous solution, and as the number of collocation points increases, the discrete solution convergences exponentially fast in the sup-norm to the continuous solution. This is the first convergence rate result for an orthogonal collocation method based on global polynomials applied to an optimal control problem.

Abstract:
Estimates are obtained for the Lebesgue constants associated with the Gauss quadrature points on $(-1, +1)$ augmented by the point $-1$ and with the Radau quadrature points on either $(-1, +1]$ or $[-1, +1)$. It is shown that the Lebesgue constants are $O(\sqrt{N})$, where $N$ is the number of quadrature points. These point sets arise in the estimation of the residual associated with recently developed orthogonal collocation schemes for optimal control problems. For problems with smooth solutions, the estimates for the Lebesgue constants can imply an exponential decay of the residual in the collocated problem as a function of the number of quadrature points.

Abstract:
A local convergence rate is established for an orthogonal collocation method based on Radau quadrature applied to an unconstrained optimal control problem. If the continuous problem has a sufficiently smooth solution and the Hamiltonian satisfies a strong convexity condition, then the discrete problem possesses a local minimizer in a neighborhood of the continuous solution, and as the number of collocation points increases, the discrete solution convergences exponentially fast in the sup-norm to the continuous solution. An earlier paper analyzes an orthogonal collocation method based on Gauss quadrature, where neither end point of the problem domain is a collocation point. For the Radau quadrature scheme, one end point is a collocation point.

Abstract:
The Vertex Separator Problem for a graph is to find the smallest collection of vertices whose removal breaks the graph into two disconnected subsets that satisfy specified size constraints. In the paper 10.1016/j.ejor.2014.05.042, the Vertex Separator Problem was formulated as a continuous (non-concave/non-convex) bilinear quadratic program. In this paper, we develop a more general continuous bilinear program which incorporates vertex weights, and which applies to the coarse graphs that are generated in a multilevel compression of the original Vertex Separator Problem. A Mountain Climbing Algorithm is used to find a stationary point of the continuous bilinear quadratic program, while second-order optimality conditions and perturbation techniques are used to escape from either a stationary point or a local maximizer. The algorithms for solving the continuous bilinear program are employed during the solution and refinement phases in a multilevel scheme. Computational results and comparisons demonstrate the advantage of the proposed algorithm.