Local convergence analysis for the REQP algorithm using conjugate basis matrices

The REQP algorithm solves constrained minimization problems using a sequential quadratic programming technique based on the properties of penalty functions. The convergence of REQP has been studied elsewhere (Refs. 1, 2). This paper uses a novel approach to the analysis of the method near to the solution, based on the use of conjugate subspaces. The stepp taken by a constrained minimization algorithm can be thought of as having two components,h in the subspace tangential to the constraints andv in the subspace spanned by the constraint normals. It is usual forh andv to be orthogonal components. Recently, Dixon (Ref. 3) has suggested constructingp from components which are not orthogonal. That is, we writep=h + v, whereh is in the subspace tangential to the constraints and wherev andh are conjugate with respect to the Hessian of the Lagrangian function. By looking at the conjugate components of the REQP search directions, it is possible to simplify the analysis of the behavior near the solution and to obtain new results about the local rate of convergence of the method.This work was supported by a SERC Studentship (TTN).     

Quadratic Termination Properties of Minimization Algorithms I. Statement and Discussion of Results

There is a family of gradient algorithms (Broyden, 1970) thatincludes many useful methods for calculating the least valueof a function F(x), and some of these algorithms have been extendedto solve linearly constrained problems (Fletcher, 1971). Somenew and fundamental properties of these algorithms are given,in the case that F(x) is a positive definite quadratic function.In particular these properties are relevant to the case whenonly some of the iterations of an algorithm make a completelinear search. They suggest that Goldfarb's (1969) algorithmfor linearly constrained problems has excellent quadratic terminationproperties, and it is proved that these properties are betterthan has been stated in previously published papers. Also anew technique is identified for unconstrained minimization withoutlinear searches.     

l1 solution of linear inequalities

The numerical solution of a possible inconsistent system oflinear inequalities in the l₁ sense is considered. The non-differentiablel₁ norm minimization problem is approximated by a piecewisequadratic Huber smooth function. A continuation algorithm isdesigned to find an l₁ solution of the inequality system. Inthe case where the linear inequality system is consistent, asolution is obtained by solving any smoothed problem. Otherwise,the algorithm is shown to terminate in a finite number of iterations.We also consider an alternative smoothing scheme which sharessimilar properties with the first one, but results in an improvedcomputational performance of the continuation algorithm on inconsistentsystems. Numerical experiments are conducted to test the efficiencyof the algorithm.     

Numerical examples of the behavior of REQP on nonlinear programming problems involving linear dependence among the constraint normals

This report illustrates, by means of numerical examples, the behavior of the constrained minimization algorithm REQP in situations where the active constraint normals are not linearly independent. The examples are intended to demonstrate that the presence of the penalty parameter in the equations for calculating the Lagrange multiplier estimates enables a useful search direction to be computed. This is shown to be true, whether the dependence among the constraint normals occurs at the solution or in some other region.     

A parameter-free multiplier method for constrained minimization problems

This paper is concerned with the development of a parameter-free method, closely related to penalty function and multiplier methods, for solving constrained minimization problems. The method is developed via the quadratic programming model with equality constraints. The study starts with an investigation into the convergence properties of a so-called “primal-dual differential trajectory”, defined by directions given by the direction of steepest descent with respect to the variables x of the problem, and the direction of steepest ascent with respect to the Lagrangian multipliers λ, associated with the Lagrangian function. It is shown that the trajectory converges to a stationary point (x*, λ*) corresponding to the solution of the equality constrained problem. Subsequently numerical procedures are proposed by means of which practical trajectories may be computed and the convergence of these trajectories are analyzed. A computational algorithm is presented and its application is illustrated by means of simple but representative examples. The extension of the method to inequality constrained problems is discussed and a non-rigorous argument, based on the Kuhn—Tucker necessary conditions for a constrained minimum, is put forward on which a practical procedure for determining the solution is based. The application of the method to inequality constrained problems is illustrated by its application to a couple of simple problems.     

An Ideal Penalty Function for Constrained Optimization

A well known approach to constrained optimization is via a sequenceof unconstrained minimization calculations applied to a penaltyfunction. This paper shown how it is posiible to generalizePowell's penelty function to solve constrained problems withboth equality and inequality constraints. The resulting methodsare equivalent to the Hestenes' method of multipliers, and ageneralization of this to inequality constraints suggested byRockafellar. Local duality results (not all of which have appearedbefore) for these methods are reviewed, with particular emphasison those of practical importance. It is shown that various strategiesfor varying control parameters are possible, all of which canbe viewed as Newton or Newton-like iterations applied to thedual problem. Practical strategies for guaranteeing convergenceare also discussed. A wide selection of numerical evidence isreported, and the algorithms are compared both amongst themselvesand with other penalty function methods. The new penalty functionis well conditioned, without singularities, and it is not necessaryfor the control parameters to tend to infinity in order to forceconvergence. The rate of convergence is rapid and high accuracyis achieved in few unconstrained minimizations.; furthermorethe computational effort for successive minimizations goes downrapidly. The methods are very easy to program efficiently, usingan established quasi-Newton subroutine for unconstrained minimization.     

A quadratically constrained minimization problem arising from PDE of Monge–Ampère type

This note develops theory and a solution technique for a quadratically constrained eigenvalue minimization problem. This class of problems arises in the numerical solution of fully-nonlinear boundary value problems of Monge–Ampère type. Though it is most important in the three dimensional case, the solution method is directly applicable to systems of arbitrary dimension. The focus here is on solving the minimization subproblem which is part of a method to numerically solve a Monge–Ampère type equation. These subproblems must be evaluated many times in this numerical solution technique and thus efficiency is of utmost importance. A novelty of this minimization algorithm is that it is finite, of complexity O(n³)\mathcal{O}(n^3), with the exception of solving a very simple rational function of one variable. This function is essentially the same for any dimension. This result is quite surprising given the nature of the constrained minimization problem.     

A Simply Constrained Optimization Reformulation of KKT Systems Arising from Variational Inequalities

The Karush—Kuhn—Tucker (KKT) conditions can be regarded as optimality conditions for both variational inequalities and constrained optimization problems. In order to overcome some drawbacks of recently proposed reformulations of KKT systems, we propose casting KKT systems as a minimization problem with nonnegativity constraints on some of the variables. We prove that, under fairly mild assumptions, every stationary point of this constrained minimization problem is a solution of the KKT conditions. Based on this reformulation, a new algorithm for the solution of the KKT conditions is suggested and shown to have some strong global and local convergence properties. Accepted 10 December 1997     

A Fast Direct Method for the Least Squares Solution of Slightly Overdetermined Sets of Linear Equations

Noble (1969) has described a method for the solution of N+Mlinear equations in N unknowns, which is based on an initialpartitioning of the matrix A, and which requires only the solutionof square sets of equations. He assumed rank (A) = N. We describehere an efficient implementation of Noble's method, and showthat it generalizes in a simple way to cover also rank deficientproblems. In the common case that the equation is only slightlyoverdetermined (M << N) the resulting algorithm is muchfaster than the standard methods based on M.G.S. or Householderreduction of A, or on the normal equations, and has a very similaroperation count to the algorithm of Cline (1973). Slightly overdetermined systems arise from Galerkin methodsfor non-Hermitian partial differential equations. In these systems,rank (A) = N and advantage can be taken of the structure ofthe matrix A to yield a least squares solution in (N²) operations.     

Elimination of bounds in optimization problems by transforming variables

The problem of minimizing a nonlinear objective function ofn variables, with continuous first and second partial derivatives, subject to nonnegativity constraints or upper and lower bounds on the variables is studied. The advisability of solving such a constrained optimization problem by making a suitable transformation of its variables in order to change the problem into one of unconstrained minimization is considered. A set of conditions which guarantees that every local minimum of the new unconstrained problem also satisfies the first-order necessary (Kuhn—Tucker) conditions for a local minimum of the original constrained problem is developed. It is shown that there are certain conditions under which the transformed objective function will maintain the convexity of the original objective function in a neighborhood of the solution. A modification of the method of transformations which moves away from extraneous stationary points is introduced and conditions under which the method generates a sequence of points which converges to the solution at a superlinear rate are given.     

A projected newton method forl p norm location problems

This paper is concerned with the numerical solution of continuous minisum multifacility location problems involving thel _p norm, where 1<p<x. This class of problems is potentially difficult to solve because the objective function is not everywhere diflerentiable. After developing conditions that characterize the minimum of the problems under consideration, a second-order algorithm is presented. This algorithm is based on the solution of a finite sequence of linearly constrained subproblems. Descent directions for these subproblems are obtained by projecting the Newton direction onto the corresponding constraint manifold. Univariate minimization is achieved via a specialized linesearch which recognizes the possibility of first derivative discontinuity (and second derivative unboundedness) at points along the search direction. The algorithm, motivated by earlier works of Calamai and Conn, and related to methods recently described by Overton and Dax, is shown to possess both global and quadratic convergence properties. Degeneracy can complicate the numerical solution of the subproblems. This degeneracy is identified, and a method for handling it is outlined. An implementation of the algorithm, that exploits the intrinsic structure of the location problem formulation, is then described along with a discussion of numerical results. The research was supported in part by Natural Sciences and Engineering Research Council of Canada grants A-5671 and A-8639 and by the Applied Mathematical Sciences Research Program (KC-04-02) of the Office of Energy Research of the U.S. Department of Energy under Contract W-31-109-Eng-38. This paper was typeset using software developed at Bell Laboratories and the University of California at Berkeley.     

General iterative methods for equilibrium and constrained convex minimization problem

The gradient-projection algorithm (GPA) plays an important role in solving constrained convex minimization problems. Based on Marino and Xu's method [G. Marino and H.-K. Xu, A general method for nonexpansive mappings in Hilbert space, J. Math. Anal. Appl. 318 (2006), pp. 43–52], we combine GPA and averaged mapping approach to propose implicit and explicit composite iterative algorithms for finding a common solution of an equilibrium and a constrained convex minimization problem for the first time in this article. Under suitable conditions, strong convergence theorems are obtained.     

Stationary Critical Points of the Heat Flow in Spaces of Constant Curvature

The paper considers stationary critical points of the heat flowin sphere S^N and in hyperbolic space H^N, and proves severalresults corresponding to those in Euclidean space R^N which havebeen proved by Magnanini and Sakaguchi. To be precise, it isshown that a solution u of the heat equation has a stationarycritical point, if and only if u satisfies some balance lawwith respect to the point for any time. In Cauchy problems forthe heat equation, it is shown that the solution u has a stationarycritical point if and only if the initial data satisfies thebalance law with respect to the point. Furthermore, one point,say x₀, is fixed and initial-boundary value problems are consideredfor the heat equation on bounded domains containing x₀. It isshown that for any initial data satisfying the balance law withrespect to x₀ (or being centrosymmetric with respect to x₀)the corresponding solution always has x₀ as a stationary criticalpoint, if and only if the domain is a geodesic ball centredat x₀ (or is centrosymmetric with respect to x₀, respectively).     

On the role of continuously differentiable exact penalty functions in constrained global optimization

The aim of this paper is to show that the new continuously differentiable exact penalty functions recently proposed in literature can play an important role in the field of constrained global optimization. In fact they allow us to transfer ideas and results proposed in unconstrained global optimization to the constrained case.First, by drawing our inspiration from the unconstrained case and by using the strong exactness properties of a particular continuously differentiable penalty function, we propose a sufficient condition for a local constrained minimum point to be global.Then we show that every constrained local minimum point satisfying the second order sufficient conditions is an attraction point for a particular implementable minimization algorithm based on the considered penalty function. This result can be used to define new classes of global algorithms for the solution of general constrained global minimization problems. As an example, in this paper we describe a simulated annealing algorithm which produces a sequence of points converging in probability to a global minimum of the original constrained problem.     

New Constrained Optimization Reformulation of Complementarity Problems

We suggest a reformulation of the complementarity problem CP(F) as a minimization problem with nonnegativity constraints. This reformulation is based on a particular unconstrained minimization reformulation of CP(F) introduced by Geiger and Kanzow as well as Facchinei and Soares. This allows us to use nonnegativity constraints for all the variables or only a subset of the variables on which the function F depends. Appropriate regularity conditions ensure that a stationary point of the new reformulation is a solution of the complementarity problem. In particular, stationary points with negative components can be avoided in contrast to the reformulation as unconstrained minimization problem. This advantage will be demonstrated for a class of complementarity problems which arise when the Karush–Kuhn–Tucker conditions of a convex inequality constrained optimization problem are considered.     

Solving nonlinearly constrained global optimization problem via an auxiliary function method

This paper considers the nonlinearly constrained continuous global minimization problem. Based on the idea of the penalty function method, an auxiliary function, which has approximately the same global minimizers as the original problem, is constructed. An algorithm is developed to minimize the auxiliary function to find an approximate constrained global minimizer of the constrained global minimization problem. The algorithm can escape from the previously converged local minimizers, and can converge to an approximate global minimizer of the problem asymptotically with probability one. Numerical experiments show that it is better than some other well known recent methods for constrained global minimization problems.     

Existence of Exact Penalty for Constrained Optimization Problems in Metric Spaces

In this paper we use the penalty approach in order to study constrained minimization problems in a complete metric space with locally Lipschitzian mixed constraints. A penalty function is said to have the exact penalty property if there is a penalty coefficient for which a solution of an unconstrained penalized problem is a solution of the corresponding constrained problem. In this paper we establish sufficient conditions for the exact penalty property.      

Convergence of Fixed-Point Continuation Algorithms for Matrix Rank Minimization

The matrix rank minimization problem has applications in many fields, such as system identification, optimal control, low-dimensional embedding, etc. As this problem is NP-hard in general, its convex relaxation, the nuclear norm minimization problem, is often solved instead. Recently, Ma, Goldfarb and Chen proposed a fixed-point continuation algorithm for solving the nuclear norm minimization problem (Math. Program., doi:, 2009). By incorporating an approximate singular value decomposition technique in this algorithm, the solution to the matrix rank minimization problem is usually obtained. In this paper, we study the convergence/recoverability properties of the fixed-point continuation algorithm and its variants for matrix rank minimization. Heuristics for determining the rank of the matrix when its true rank is not known are also proposed. Some of these algorithms are closely related to greedy algorithms in compressed sensing. Numerical results for these algorithms for solving affinely constrained matrix rank minimization problems are reported.     

Sufficient conditions for exact penalty in constrained optimization

In this paper we use the penalty approach in order to study constrained minimization problems. A penalty function is said to have the exact penalty property if there is a penalty coefficient for which a solution of an unconstrained penalized problem is a solution of the corresponding constrained problem. We discuss very simple sufficient conditions for the exact penalty property. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Locking-free DGFEM for elasticity problems in polygons

The h-version of the discontinuous Galerkin finite element method(h-DGFEM) for nearly incompressible linear elasticity problemsin polygons is analysed. It is proved that the scheme is robust(locking-free) with respect to volume locking, even in the absenceof H²-regularity of the solution. Furthermore, it is shown thatan appropriate choice of the finite element meshes leads torobust and optimal algebraic convergence rates of the DGFEMeven if the exact solutions do not belong to H².