Another greedy heuristic for the constrained forest problem

The constrained forest problem seeks a minimum-weight spanning forest in an undirected edge-weighted graph such that each tree spans at least a specified number of vertices. We present a greedy heuristic for this NP-hard problem, whose solutions are at least as good as, and often better than, those produced by the best-known 2-approximate heuristic.     

Necessary conditions for constrained optimization problems with semicontinuous and continuous data

We consider nonsmooth constrained optimization problems with semicontinuous and continuous data in Banach space and derive necessary conditions without constraint qualification in terms of smooth subderivatives and normal cones. These results, in different versions, are set in reflexive and smooth Banach spaces.

     

Separation of sets and Wolfe duality

Lagrangian duality can be derived from separation in the Image Space, namely the space where the images of the objective and constraining functions of the given extremum problem run. By exploiting such a result, we analyse the relationships between Wolfe and Mond-Weir duality and prove their equivalence in the Image Space under suitable generalized convexity assumptions.      

A polynomially bounded algorithm for a singly constrained quadratic program

This paper presents a characterization of the solutions of a singly constrained quadratic program. This characterization is then used in the development of a polynomially bounded algorithm for this class of problems.     

An only 2-step Q-superlinear convergence example for some algorithms that use reduced hessian approximations

It is shown by example that the reduced Hessian method for constrained optimization that is known to give 2-stepQ-superlinear convergence may not convergeQ-superlinearly.     

Newton's method for constrained optimization

We derive a quadratically convergent algorithm for minimizing a nonlinear function subject to nonlinear equality constraints. We show, following Kaufman [4], how to compute efficiently the derivative of a basis of the subspace tangent to the feasible surface. The derivation minimizes the use of Lagrange multipliers, producing multiplier estimates as a by-product of other calculations. An extension of Kantorovich's theorem shows that the algorithm maintains quadratic convergence even if the basis of the tangent space changes abruptly from iteration to iteration. The algorithm and its quadratic convergence are known but the drivation is new, simple, and suggests several new modifications of the algorithm.     

Enlarging the region of convergence of Newton's method for constrained optimization

In this paper, we consider Newton's method for solving the system of necessary optimality conditions of optimization problems with equality and inequality constraints. The principal drawbacks of the method are the need for a good starting point, the inability to distinguish between local maxima and local minima, and, when inequality constraints are present, the necessity to solve a quadratic programming problem at each iteration. We show that all these drawbacks can be overcome to a great extent without sacrificing the superlinear convergence rate by making use of exact differentiable penalty functions introduced by Di Pillo and Grippo (Ref. 1). We also show that there is a close relationship between the class of penalty functions of Di Pillo and Grippo and the class of Fletcher (Ref. 2), and that the region of convergence of a variation of Newton's method can be enlarged by making use of one of Fletcher's penalty functions.This work was supported by the National Science Foundation, Grant No. ENG-79-06332.     

A quadratic assignment formulation of the molecular conformation problem

The molecular conformation problem is discussed, and a concave quadratic global minimization approach for solving it is described. This approach is based on a quadratic assignment formulation of a discrete approximation to the original problem.     

A constrained min‐max algorithm for rival models of the same economic system

There are well established rival theories about the economy. These have, in turn, led to the development of rival models purporting to represent the economic system. The models are large systems of discrete-time nonlinear dynamic equations. Observed data of the real system does not, in general, provide sufficient information for statistical methods to invalidate all but one of the rival models. In such a circumstance, there is uncertainty about which model to use in the formulation of policy. Prudent policy design would suggest that a model-based policy should take into account all the rival models. This is achieved as a pooling of the models. The pooling that yields the policy which is robust to model choice is formulated as a constrained min-max problem. The minimization is over the decision variables and the maximization is over the rival models. Only equality constraints are considered.A successive quadratic programming algorithm is discussed for the solution of the min-max problem. The algorithm uses a stepsize strategy based on a differentiable penalty function for the constraints. Two alternative quadratic subproblems can be used. One is a quadratic min-max and the other a quadratic programming problem. The objective function of either subproblem includes a linear term which is dependent on the penalty function. The penalty parameter is determined at every iteration, using a strategy that ensures a descent property as well as the boundedness of the penalty term. The boundedness follows since the strategy is always satisfied for finite values of the parameter which needs to be increased a finite number of times.The global and local convergence of the algorithm is established. The conditions, involving projected Hessian approximations, are discussed under which the algorithm achieves unit stepsizes and subsequently Q-superlinear convergence.     

Exploiting additional structure in equality constrained optimization by structured SQP secant algorithms

In 1988, Tapia (Ref. 1) developed and analyzed SQP secant methods in equality constrained optimization taking explicitly the additive structure of the problem setting into account. In this paper, we extend Tapia's augmented scale Lagrangian secant method to the case where additional structure coming from the objective function is available. Using the example of nonlinear least squares with equality constraints, we demonstrate these ideas and develop a convergence theory proving local and q-superlinear convergence for this kind of structured SQP-algorithms.This research was supported by the Studienstiftung des Deutschen Volkes.