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

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

Global and finite termination of a two-phase augmented Lagrangian filter method for general quadratic programs

We present a two-phase algorithm for solving large-scale quadratic programs (QPs). In the first phase, gradient-projection iterations approximately minimize an augmented Lagrangian function and provide an estimate of the optimal active set. In the second phase, an equality-constrained QP defined by the current inactive variables is approximately minimized in order to generate a second-order search … Read more

The Rate of Convergence of the Augmented Lagrangian Method for Nonlinear Semidefinite Programming

We analyze the rate of local convergence of the augmented Lagrangian method for nonlinear semidefinite optimization. The presence of the positive semidefinite cone constraint requires extensive tools such as the singular value decomposition of matrices, an implicit function theorem for semismooth functions, and certain variational analysis on the projection operator in the symmetric-matrix space. Without … Read more

Blind Source Separation using Relative Newton Method combined with Smoothing Method of Multipliers

We study a relative optimization framework for quasi-maximum likelihood blind source separation and relative Newton method as its particular instance. The structure of the Hessian allows its fast approximate inversion. In the second part we present Smoothing Method of Multipliers (SMOM) for minimization of sum of pairwise maxima of smooth functions, in particular sum of … Read more

On Augmented Lagrangian methods with general lower-level constraints

Augmented Lagrangian methods with general lower-level constraints are considered in the present research. These methods are useful when efficient algorithms exist for solving subproblems where the constraints are only of the lower-level type. Two methods of this class are introduced and analyzed. Inexact resolution of the lower-level constrained subproblems is considered. Global convergence is proved … Read more

Augmented Lagrangian methods under the Constant Positive Linear Dependence constraint qualification

Two Augmented Lagrangian algorithms for solving KKT systems are introduced. The algorithms differ in the way in which penalty parameters are updated. Possibly infeasible accumulation points are characterized. It is proved that feasible limit points that satisfy the Constant Positive Linear Dependence constraint qualification are KKT solutions. Boundedness of the penalty parameters is proved under … Read more

Constrained optimization in seismic reflection tomography: an SQP augmented Lagrangian approach

Seismic reflection tomography is a method for determining a subsurface velocity model from the traveltimes of seismic waves reflecting on geological interfaces. From an optimization viewpoint, the problem consists in minimizing a nonlinear least-squares function measuring the mismatch between observed traveltimes and those calculated by ray tracing in this model. The introduction of a priori … Read more

Solving Lift-and-Project Relaxations of Binary Integer Programs

We propose a method for optimizing the lift-and-project relaxations of binary integer programs introduced by Lov\’asz and Schrijver. In particular, we study both linear and semidefinite relaxations. The key idea is a restructuring of the relaxations, which isolates the complicating constraints and allows for a Lagrangian approach. We detail an enhanced subgradient method and discuss … Read more

Global linear convergence of an augmented Lagrangian algorithm for solving convex quadratic optimization problems

We consider an augmented Lagrangian algorithm for minimizing a convex quadratic function subject to linear inequality constraints. Linear optimization is an important particular instance of this problem. We show that, provided the augmentation parameter is large enough, the constraint value converges {\em globally\/} linearly to zero. This property is viewed as a consequence of the … Read more

Double-Regularization Proximal Methods, with Complementarity Applications

We consider the variational inequality problem formed by a general set-valued maximal monotone operator and a possibly unbounded “box” in $R^n$, and study its solution by proximal methods whose distance regularizations are coercive over the box. We prove convergence for a class of double regularizations generalizing a previously-proposed class of Auslender et al. We apply … Read more