Global minimization using an Augmented Lagrangian method with variable lower-level constraints

Categories Global Optimization Tags , , ,

A novel global optimization method based on an Augmented Lagrangian framework is introduced for continuous constrained nonlinear optimization problems. At each outer iteration the method requires the $\varepsilon$-global minimization of the Augmented Lagrangian with simple constraints. Global convergence to an $\varepsilon$-global minimizer of the original problem is proved. The subproblems are solved using the $\alpha$BB … Read more

Primal-dual first-order methods with ${\cal O}(1/\epsilon)$ iteration-complexity for cone programming

Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , , , , ,

In this paper we consider the general cone programming problem, and propose primal-dual convex (smooth and/or nonsmooth) minimization reformulations for it. We then discuss first-order methods suitable for solving these reformulations, namely, Nesterov’s optimal method \cite{Nest83-1,Nest05-1}, Nesterov’s smooth approximation scheme \cite{Nest05-1}, and Nemirovski’s prox-method \cite{Nem05-1}, and propose a variant of Nesterov’s optimal method which has … Read more

A PARALLEL interior point decomposition algorithm for block-angular semidefinite programs

Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , ,

We present a two phase interior point decomposition framework for solving semidefinite (SDP) relaxations of sparse maxcut, stable set, and box constrained quadratic programs. In phase 1, we suitably modify the {\em matrix completion} scheme of Fukuda et al. \cite{fukuda_et_al} to preprocess an existing SDP into an equivalent SDP in the block-angular form. In phase … Read more

Approximation algorithms for metric tree cover and generalized tour and tree covers

Categories Approximation Algorithms, Network Optimization, Polyhedra Tags , , , ,

Given a weighted undirected graph $G=(V,E)$, a tree (respectively tour) cover of an edge-weighted graph is a set of edges which forms a tree (resp. closed walk) and covers every other edge in the graph. The tree (resp. tour) cover problem is of finding a minimum weight tree (resp. tour) cover of $G$. Arkin, Halld\’orsson … Read more

SPECTRAL STOCHASTIC FINITE-ELEMENT METHODS FOR PARAMETRIC CONSTRAINED OPTIMIZATION PROBLEMS

Categories Constrained Nonlinear Optimization, Mechanical Engineering, Stochastic Programming Tags , , , ,

We present a method to approximate the solution mapping of parametric constrained optimization problems. The approximation, which is of the spectral stochastic finite element type, is represented as a linear combination of orthogonal polynomials. Its coefficients are determined by solving an appropriate finite-dimensional constrained optimization problem. We show that, under certain conditions, the latter problem … Read more

A T-algebraic approach to primal-dual interior-point algorithms

Categories Convex Optimization, Linear, Cone and Semidefinite Programming

Three primal-dual interior-point algorithms for homogeneous cone programming are presented. They are a short-step algorithm, a large-update algorithm, and a predictor-corrector algorithm. These algorithms are described and analyzed based on a characterization of homogeneous cone via T-algebra. The analysis show that the algorithms have polynomial iteration complexity. CitationDivision of Mathematical Sciences, Nanyang Technological University, December … Read more

CONVERGENCE OF A CLASS OF SEMI-IMPLICIT TIME-STEPPING SCHEMES FOR NONSMOOTH RIGID MULTIBODY DYNAMICS

Categories Complementarity and Variational Inequalities, Mechanical Engineering, Other Topics Tags , , , ,

In this work we present a framework for the convergence analysis in a measure differential inclusion sense of a class of time-stepping schemes for multibody dynamics with contacts, joints, and friction. This class of methods solves one linear complementarity problem per step and contains the semi-implicit Euler method, as well as trapezoidallike methods for which … Read more

Selective Gram-Schmidt orthonormalization for conic cutting surface algorithms

Categories Linear, Cone and Semidefinite Programming, Nonsmooth Optimization Tags , , ,

It is not straightforward to find a new feasible solution when several conic constraints are added to a conic optimization problem. Examples of conic constraints include semidefinite constraints and second order cone constraints. In this paper, a method to slightly modify the constraints is proposed. Because of this modification, a simple procedure to generate strictly … Read more

Exact regularization of convex programs

Categories Convex Optimization Tags , , , , , , , ,

The regularization of a convex program is exact if all solutions of the regularized problem are also solutions of the original problem for all values of the regularization parameter below some positive threshold. For a general convex program, we show that the regularization is exact if and only if a certain selection problem has a … Read more

A Unified Theorem on SDP Rank Reduction

Categories Approximation Algorithms, Semi-definite Programming Tags ,

We consider the problem of finding a low-rank approximate solution to a system of linear equations in symmetric, positive semidefinite matrices. Specifically, let $A_1,\ldots,A_m \in \R^{n\times n}$ be symmetric, positive semidefinite matrices, and let $b_1,\ldots,b_m \ge 0$. We show that if there exists a symmetric, positive semidefinite matrix $X$ to the system $A_i \bullet X … Read more