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 suitable assumptions. Numerical experiments are presented. The authors were supported by PRONEX - CNPq / FAPERJ E-26 / 171.164/2003 - APQ1, FAPESP (Grants 2001/04597-4, 2002/00094-0, 2003/09169-6, 2002/00832-1 and 2005/56773-1) and CNPq.     

Local Convergence of an Inexact-Restoration Method and Numerical Experiments

Local convergence of an inexact-restoration method for nonlinear programming is proved. Numerical experiments are performed with the objective of evaluating the behavior of the purely local method against a globally convergent nonlinear programming algorithm. This work was supported by PRONEX-CNPq/FAPERJ Grant E-26/171.164/2003-APQ1, FAPESP Grants 03/09169-6 and 01/04597-4, and CNPq. The authors are indebted to Juliano B. Francisco and Yalcin Kaya for their careful reading of the first draft of this paper.     

An inexact-restoration method for nonlinear bilevel programming problems

We present a new algorithm for solving bilevel programming problems without reformulating them as single-level nonlinear programming problems. This strategy allows one to take profit of the structure of the lower level optimization problems without using non-differentiable methods. The algorithm is based on the inexact-restoration technique. Under some assumptions on the problem we prove global convergence to feasible points that satisfy the approximate gradient projection (AGP) optimality condition. Computational experiments are presented that encourage the use of this method for general bilevel problems. This work was supported by PRONEX-Optimization (PRONEX—CNPq/FAPERJ E-26/171.164/2003—APQ1), FAPESP (Grants 06/53768-0 and 05-56773-1) and CNPq.     

Order-Value Optimization: Formulation and solution by means of a primal cauchy method

The Order-Value Optimization (OVO) problem is a generalization of the classical Minimax problem. Instead of the maximum of a set functions, the functional value that ranks in the p-th place is minimized. The problem seeks the application to (non-pessimistic) decision making and to model fitting in the presence of (perhaps systematic) outliers. A Cauchy-type method is introduced that solves the problem in the sense that every limit point satisfies an adequate optimality condition. Numerical examples are given.This author was supported by FAPESP (Grant 01/05492-1) and CNPq (Grant 301115/96-6)This author was supported by PRONEX, FAPESP (PT 2001-04597-4)     

On the Relation between Constant Positive Linear Dependence Condition and Quasinormality Constraint Qualification

The constant positive linear dependence (CPLD) condition for feasible points of nonlinear programming problems was introduced by Qi and Wei (Ref. 1) and used in the analysis of SQP methods. In that paper, the authors conjectured that the CPLD could be a constraint qualification. This conjecture is proven in the present paper. Moreover, it is shown that the CPLD condition implies the quasinormality constraint qualification, but that the reciprocal is not true. Relations with other constraint qualifications are given.This research has been supported by PRONEX-Optimization Grant 76.79.1008-00, by FAPESP Grants 01-04597-4 and 02-00832-1, and by CNPq. The authors are indebted to two anonymous referees for useful comments and to Prof. Liqun Qi for encouragement.     

Quasi-Newton acceleration for equality-constrained minimization

Optimality (or KKT) systems arise as primal-dual stationarity conditions for constrained optimization problems. Under suitable constraint qualifications, local minimizers satisfy KKT equations but, unfortunately, many other stationary points (including, perhaps, maximizers) may solve these nonlinear systems too. For this reason, nonlinear-programming solvers make strong use of the minimization structure and the naive use of nonlinear-system solvers in optimization may lead to spurious solutions. Nevertheless, in the basin of attraction of a minimizer, nonlinear-system solvers may be quite efficient. In this paper quasi-Newton methods for solving nonlinear systems are used as accelerators of nonlinear-programming (augmented Lagrangian) algorithms, with equality constraints. A periodically-restarted memoryless symmetric rank-one (SR1) correction method is introduced for that purpose. Convergence results are given and numerical experiments that confirm that the acceleration is effective are presented. This work was supported by FAPESP, CNPq, PRONEX-Optimization (CNPq / FAPERJ), FAEPEX, UNICAMP.     

Analytic center of spherical shells and its application to analytic center machine

The two-case pattern recognition problem aims to find the best way of linearly separate two different classes of data points with a good generalization performance. In the context of learning machines proposed to solve the pattern recognition problem, the analytic center machine (ACM) uses the analytic center cutting plane method restricted to spherical shells. In this work we prove existence and uniqueness of the analytic center of a spherical surface, which guarantees the well definedness of ACM problem. We also propose and analyze new primal, dual and primal-dual formulations based on interior point methods for the analytic center machine. Further, we provide a complexity bound on the number of iterations for the primal approach. F.M.P. Raupp was partially supported by CNPq Grant 475647/2006-8 and FAPERJ/CNPq through PRONEX-Computational Modeling. B.F. Svaiter was partially supported by CNPq Grants 300755/2005-8, 475647/2006-8 and by FAPERJ/CNPq through PRONEX-Optimization.     

Kantorovich’s majorants principle for Newton’s method

We prove Kantorovich’s theorem on Newton’s method using a convergence analysis which makes clear, with respect to Newton’s method, the relationship of the majorant function and the non-linear operator under consideration. This approach enables us to drop out the assumption of existence of a second root for the majorant function, still guaranteeing Q-quadratic convergence rate and to obtain a new estimate of this rate based on a directional derivative of the derivative of the majorant function. Moreover, the majorant function does not have to be defined beyond its first root for obtaining convergence rate results. The research of O.P. Ferreira was supported in part by FUNAPE/UFG, CNPq Grant 475647/2006-8, CNPq Grant 302618/2005-8, PRONEX–Optimization(FAPERJ/CNPq) and IMPA. The research of B.F. Svaiter was supported in part by CNPq Grant 301200/93-9(RN) and by PRONEX–Optimization(FAPERJ/CNPq).     

Geometric singular perturbation analysis of oxidation heat pulses for two-phase flow in porous media

When air or oxygen is injected into a petroleum reservoir, and oxidation or combustion is induced, a combustion front forms if heat loss to the surrounding rock formation is negligible. Here, we employ a simple model for combustion, which takes into account oil viscosity reduction, but neglects gas density dependence on temperature and uses a simplified oxidation reaction. We show that for small heat loss, this combustion front is actually the lead part of a pulse, while the trailing part of the pulse is a slow cooling process. If the heat loss is too large, we show that such a pulse does not exist. The proofs use geometric singular perturbation theory and center manifold reduction.Dedicated to Constantine Dafermos on his 60^th birthdayThis work was supported in part by: CNPq under Grant 300204/83-3; CNPq/NSF under Grant 91.0011/99-0; MCT under Grant PCI 650009/97-5; FINEP under Grant 77.97.0315.00; FAPERJ under Grants E-26/150.936/99 and E-26/151.893/2000; NSF under Grant DMS-9973105.     

Relations between the Circumference and <Emphasis Type="Italic">e</Emphasis>-Circumference of a Matroid

For a connected matroid with at least two elements, let c be the maximum size of a circuit and let c _e be the maximum size of a circuit that contains an element e. In 2001, Wu prove that . In this note, we characterize the matroids that attain this bound. This characterization is used to generalize another result of Wu. Manol Lemos: The author is partially supported by CNPq (Grants No. 476224/04-7 and 301178/05-4) and FAPESP/CNPq (Grant No. 2003/09925-5). Received: October 13, 2006. Final version received: November 6, 2007.     

Nonlinear leastpth optimization and nonlinear programming

Over the past few years a number of researchers in mathematical programming became very interested in the method of the Augmented Lagrangian to solve the nonlinear programming problem. The main reason being that the Augmented Lagrangian approach overcomes the ill-conditioning problem and the slow convergence of the penalty methods. The purpose of this paper is to present a new method of solving the nonlinear programming problem, which has similar characteristics to the Augmented Lagrangian method. The original nonlinear programming problem is transformed into the minimization of a leastpth objective function which under certain conditions has the same optimum as the original problem. Convergence and rate of convergence of the new method is also proved. Furthermore numerical results are presented which illustrate the usefulness of the new approach to nonlinear programming.This work was supported by the National Research Council of Canada and by the Department of Combinatorics and Optimization of the University of Waterloo.     

Spectral Gradient Methods for Linearly Constrained Optimization

Linearly constrained optimization problems with simple bounds are considered in the present work. First, a preconditioned spectral gradient method is defined for the case in which no simple bounds are present. This algorithm can be viewed as a quasi-Newton method in which the approximate Hessians satisfy a weak secant equation. The spectral choice of steplength is embedded into the Hessian approximation and the whole process is combined with a nonmonotone line search strategy. The simple bounds are then taken into account by placing them in an exponential penalty term that modifies the objective function. The exponential penalty scheme defines the outer iterations of the process. Each outer iteration involves the application of the previously defined preconditioned spectral gradient method for linear equality constrained problems. Therefore, an equality constrained convex quadratic programming problem needs to be solved at every inner iteration. The associated extended KKT matrix remains constant unless the process is reinitiated. In ordinary inner iterations, only the right-hand side of the KKT system changes. Therefore, suitable sparse factorization techniques can be applied and exploited effectively. Encouraging numerical experiments are presented.This research was supported by FAPESP Grant 2001-04597-4 and Grant 903724-6, FINEP and FAEP-UNICAMP, and the Scientific Computing Center of UCV. The authors thank two anonymous referees whose comments helped us to improve the final version of this paper.     

Box-constrained minimization reformulations of complementarity problems in second-order cones

Reformulations of a generalization of a second-order cone complementarity problem (GSOCCP) as optimization problems are introduced, which preserve differentiability. Equivalence results are proved in the sense that the global minimizers of the reformulations with zero objective value are solutions to the GSOCCP and vice versa. Since the optimization problems involved include only simple constraints, a whole range of minimization algorithms may be used to solve the equivalent problems. Taking into account that optimization algorithms usually seek stationary points, a theoretical result is established that ensures equivalence between stationary points of the reformulation and solutions to the GSOCCP. Numerical experiments are presented that illustrate the advantages and disadvantages of the reformulations. Supported by FAPESP (01/04597-4), CNPq, PRONEX-Optimization, FAEPEX-Unicamp.     

Solution of linear complementarity problems using minimization with simple bounds

We define a minimization problem with simple bounds associated to the horizontal linear complementarity problem (HLCP). When the HLCP is solvable, its solutions are the global minimizers of the associated problem. When the HLCP is feasible, we are able to prove a number of properties of the stationary points of the associated problem. In many cases, the stationary points are solutions of the HLCP. The theoretical results allow us to conjecture that local methods for box constrained optimization applied to the associated problem are efficient tools for solving linear complementarity problems. Numerical experiments seem to confirm this conjecture.This work was supported by FAPESP (grants 90-3724-6 and 91-2441-3), CNPq and FAEP (UNICAMP).     

Examples of dual behaviour of Newton-type methods on optimization problems with degenerate constraints

We discuss possible scenarios of behaviour of the dual part of sequences generated by primal-dual Newton-type methods when applied to optimization problems with nonunique multipliers associated to a solution. Those scenarios are: (a) failure of convergence of the dual sequence; (b) convergence to a so-called critical multiplier (which, in particular, violates some second-order sufficient conditions for optimality), the latter appearing to be a typical scenario when critical multipliers exist; (c) convergence to a noncritical multiplier. The case of mathematical programs with complementarity constraints is also discussed. We illustrate those scenarios with examples, and discuss consequences for the speed of convergence. We also put together a collection of examples of optimization problems with constraints violating some standard constraint qualifications, intended for preliminary testing of existing algorithms on degenerate problems, or for developing special new algorithms designed to deal with constraints degeneracy. Research of the first author is supported by the Russian Foundation for Basic Research Grants 07-01-00270, 07-01-00416 and 07-01-90102-Mong, and by RF President’s Grant NS-9344.2006.1 for the support of leading scientific schools. The second author is supported in part by CNPq Grants 301508/2005-4, 490200/2005-2 and 550317/2005-8, by PRONEX–Optimization, and by FAPERJ Grant E-26/151.942/2004.     

Multiperiod Mean-Variance Optimization with Intertemporal Restrictions

We investigate mean-variance optimization problems that arise in portfolio selection. Restrictions on intermediate expected values or variances of the portfolio are considered. Some explicit procedures for obtaining the solution are presented. The main advantage of this technique is that it is possible to control the intermediate behavior of a portfolio’s return or variance. Some examples illustrating these situations are presented. The first author received financial support from CNPq (Brazilian National Research Council) Grants 472920/03-0 and 304866/03-2, FAPESP (Research Council of the State of S?o Paulo) Grant 03/06736-7, PRONEX Grant 015/98, and IM-AGIMB.     

Weight Distribution of the Bases of a Matroid

Given a weighted graph, let w₁, w₂, . . . ,w_n denote the increasing sequence of all possible distinct spanning tree weights. In 1992, Mayr and Plaxton proved the following conjecture proposed by Kano: every spanning tree of weight w₁ is at most k−1 edge swaps away from some spanning tree of weight w_k. In this paper, we extend this result for matroids. We also prove that all the four conjectures due to Kano hold for matroids provided one partitions the bases of a matroid by the weight distribution of its elements instead of their weight. The author was partially supported by CNPq (Grant No. 302195/02-5) and ProNEx/CNPq (Grant No. 664107/97-4)     

Continuous optimization methods for structure alignments

Structural Alignment is an important tool for fold identification of proteins, structural screening on ligand databases, pharmacophore identification and other applications. In the general case, the optimization problem of superimposing two structures is nonsmooth and nonconvex, so that most popular methods are heuristic and do not employ derivative information. Usually, these methods do not admit convergence theories of practical significance. In this work it is shown that the optimization of the superposition of two structures may be addressed using continuous smooth minimization. It is proved that, using a Low Order-Value Optimization approach, the nonsmoothness may be essentially ignored and classical optimization algorithms may be used. Within this context, a Gauss–Newton method is introduced for structural alignments incorporating (or not) transformations (as flexibility) on the structures. Convergence theorems are provided and practical aspects of implementation are described. Numerical experiments suggest that the Gauss–Newton methodology is competitive with state-of-the-art algorithms for protein alignment both in terms of quality and speed. Additional experiments on binding site identification, ligand and cofactor alignments illustrate the generality of this approach. The softwares containing the methods presented here are available at http://www.ime.unicamp.br/∼martinez/lovoalign. This work was supported by PRONEX-Optimization 76.79.1008-00, FAPESP (Grants 01-04597-4 - 02-14203-6 and 05-56773-1) and CNPq