Orthogonal and conjugate basis methods for solving equality constrained minimization problems

This paper deals with methods for choosing search directions in the iterative solution of constrained minimization problems. The popular technique of calculating orthogonal components of the search direction (i.e., tangential and normal to the constraints) is discussed and contrasted with the idea of constructing the search direction from two moves which are conjugate with respect to the Hessian of the Lagrangian function. Minimization algorithms which use search directions obtained by these two approaches are described, and their local convergence properties are studied. This analysis, coupled with some numerical results, suggests that the benefits of building steps from conjugate components are well deserving of further investigation.     

Infinite-dimensional convex programming with applications to constrained approximation

In this paper, existence and characterization of solutions and duality aspects of infinite-dimensional convex programming problems are examined. Applications of the results to constrained approximation problems are considered. Various duality properties for constrained interpolation problems over convex sets are established under general regularity conditions. The regularity conditions are shown to hold for many constrained interpolation problems. Characterizations of local proximinal sets and the set of best approximations are also given in normed linear spaces.The author is grateful to the referee for helpful suggestions which have contributed to the final preparation of this paper. This research was partially supported by Grant A68930162 from the Australian Research Council.     

An analysis of reduced Hessian methods for constrained optimization

We study the convergence properties of reduced Hessian successive quadratic programming for equality constrained optimization. The method uses a backtracking line search, and updates an approximation to the reduced Hessian of the Lagrangian by means of the BFGS formula. Two merit functions are considered for the line search: the ₁ function and the Fletcher exact penalty function. We give conditions under which local and superlinear convergence is obtained, and also prove a global convergence result. The analysis allows the initial reduced Hessian approximation to be any positive definite matrix, and does not assume that the iterates converge, or that the matrices are bounded. The effects of a second order correction step, a watchdog procedure and of the choice of null space basis are considered. This work can be seen as an extension to reduced Hessian methods of the well known results of Powell (1976) for unconstrained optimization.This author was supported, in part, by National Science Foundation grant CCR-8702403, Air Force Office of Scientific Research grant AFOSR-85-0251, and Army Research Office contract DAAL03-88-K-0086.This author was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy, under contracts W-31-109-Eng-38 and DE FG02-87ER25047, and by National Science Foundation Grant No. DCR-86-02071.     

Two methods for large-scale nonlinear optimization and their comparison on a case study of hydropower optimization

This paper presents two methods for the optimization of structured large-scale problems: a decomposition method of dual type for nonlinear problems and a sequential quadratic programming based method. Practical details of application of the methods to the case study problem of the hydropower system of an African river are then given. Comparison of results is presented, indicating that both methods are useful and efficient, having however different features from a practical point of view. General remarks concerning the practical differences between a decomposition-based method and a method exploiting the problem structure within the framework of general purpose optimization routines are finally presented.This work was partly supported by the Water Resource Project, IIASA, Laxenburg, Austria.     

Using the KKT matrix in an augmented Lagrangian SQP method for sparse constrained optimization

The augmented Lagrangian SQP subroutine OPALQP was originally designed for small-to-medium sized constrained optimization problems in which the main calculation on each iteration, the solution of a quadratic program, involves dense, rather than sparse, matrices. In this paper, we consider some reformulations of OPALQP which are better able to take advantage of sparsity in the objective function and constraints.The modified versions of OPALQP differ from the original in using sparse data structures for the Jacobian matrix of constraints and in replacing the dense quasi-Newton estimate of the inverse Hessian of the Lagrangian by a sparse approximation to the Hessian. We consider a very simple sparse update for estimating ² L and also investigate the benefits of using exact second derivatives, noting in the latter case that safeguards are needed to ensure that a suitable search direction is obtained when ² L is not positive definite on the null space of the active constraints.The authors are grateful to John Reid and Nick Gould of the Rutherford Appleton Laboratory for a number of helpful and interesting discussions. Thanks are also due to Laurence Dixon for comments which led to the clarification of some parts of the paper.This work has been partly supported by a CAPES Research Studentship funded by the Brazilian Government.     

Optimization methods for Dirichlet control problems

We discuss several optimization procedures to solve finite element approximations of linear-quadratic Dirichlet optimal control problems governed by an elliptic partial differential equation posed on a 2D or 3D Lipschitz domain. The control is discretized explicitly using continuous piecewise linear approximations. Unconstrained, control-constrained, state-constrained and control-and-state constrained problems are analysed. A preconditioned conjugate method for a reduced problem in the control variable is proposed to solve the unconstrained problem, whereas semismooth Newton methods are discussed for the solution of constrained problems. State constraints are treated via a Moreau–Yosida penalization. Convergence is studied for both the continuous problems and the finite dimensional approximations. In the finite dimensional case, we are able to show convergence of the optimization procedures even in the absence of Tikhonov regularization parameter. Computational aspects are also treated and several numerical examples are included to illustrate the theoretical results.     

等式约束优化一个新的SQP算法

提出了一个处理等式约束优化问题新的SQP算法,该算法通过求解一个增广Lagrange函数的拟Newton方法推导出一个等式约束二次规划子问题,从而获得下降方向．罚因子具有自动调节性,并能避免趋于无穷．为克服Maratos效应采用增广Lagrange函数作为效益函数并结合二阶步校正方法．在适当的条件下,证明算法是全局收敛的,并且具有超线性收敛速度．     

Primal‐dual active set methods for Allen–Cahn variational inequalities with nonlocal constraints

We propose and analyze a primal‐dual active set method for discretized versions of the local and nonlocal Allen–Cahn variational inequalities. An existence result for the nonlocal variational inequality is shown in a formulation involving Lagrange multipliers for local and nonlocal constraints. Local convergence of the discrete method is shown by interpreting the approach as a semismooth Newton method. Properties of the method are discussed and several numerical simulations demonstrate its efficiency. © 2012 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2013     

Rates of convergence for adaptive Newton methods

We consider Newton-type methods for constrained optimization problems in infinite-dimensional spaces, where at each iteration the first and second derivatives and the feasible set are approximated. The approximations can change at each iteration and conditions are given under which linear and superlinear rates of convergence of the iterates to the optimal point hold. Several applications are discussed.     

ODE versus SQP methods for constrained optimization

In this paper, we review some methods which are designed to solve equality constrained minimization problems by following the trajectory defined by a system of ordinary differential equations. The numerical performance of a number of these methods is compared with that of some popular sequential quadratic programming algorithms. On a set of eighteen difficult test problems, we observe that several of the ODE methods are more successful than any of the SQP techniques. We suggest that these experimental results indicate the need for research both to analyze and develop new ODE techniques and also to strengthen the currently available SQP algorithms.This work was supported by a SERC Research Studentship for the first author. Both authors are indebted to Dr. J. J. McKeown and Dr. K. D. Patel of SCICON Ltd., the collaborating establishment, for their advice and encouragement.     

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.     

New interval methods for constrained global optimization

Interval analysis is a powerful tool which allows to design branch-and-bound algorithms able to solve many global optimization problems. In this paper we present new adaptive multisection rules which enable the algorithm to choose the proper multisection type depending on simple heuristic decision rules. Moreover, for the selection of the next box to be subdivided, we investigate new criteria. Both the adaptive multisection and the subinterval selection rules seem to be specially suitable for being used in inequality constrained global optimization problems. The usefulness of these new techniques is shown by computational studies.     

Generalized Newton methods for crack problems with nonpenetration condition

A class of semismooth Newton methods for unilaterally constrained variational problems modeling cracks under a nonpenetration condition is introduced and investigated. On the continuous level, a penalization technique is applied that allows to argue generalized differentiability of the nonlinear mapping associated to its first‐order optimality characterization. It is shown that the corresponding semismooth Newton method converges locally superlinearly. For the discrete version of the problem, fast local as well as global and monotonous convergence of a discrete semismooth Newton method are proved. A comprehensive report on numerical tests for the two‐dimensional Lamé problem with three collinear cracks under the nonpenetration condition ends the article. © 2004 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2005     

求解一般界约束优化问题的积极集信赖域方法

本文提出了一种求解一般界约束优化问题的新方法. 每步迭代分为两个阶段. 在第一阶段, 从 当前迭代点x_k 出发, 沿着经过仿射变换后的梯度步, 得到试探点x_k¹, 记录下它的积极集. 这里用到的仿射变换矩阵不仅依赖于变量到边界的距离, 还依赖于当前迭代点的梯度以及该步迭代中的信赖域半 径. 在第二阶段, 从x_k¹ 出发, 通过在积极约束的零空间里面求解一个信赖域子问题得到新的试探点. 然后判断是否接受这个试探点作为下一个迭代点. 文中证明了算法的全局收敛性, 并且迭代点列的每 个聚点都是一阶稳定点. 文中还对国际著名的CUTEr 算例库中所有的界约束优化问题进行了测试. 数值结果表明我们的方法是有效的, 并且可以与L-BFGS-B 方法相媲美.     

On minimax eigenvalue problems via constrained optimization

In this paper, we consider the problem of minimizing the maximum eigenvalues of a matrix. The aim is to show that this optimization problem can be transformed into a standard nonlinearly constrained optimization problem, and hence is solvable by existing software packages. For illustration, two examples are solved by using the proposed method.     

Superlinear convergence theorems for Newton-type methods for nonlinear systems of equations

In this paper, someQ-order convergence theorems are given for the problem of solving nonlinear systems of equations when using very general finitely terminating methods for the solution of the associated linear systems. The theorems differ from those of Dembo, Eisenstat, and Steihaug in the different stopping condition and in their applicability to the nonlinear ABS algorithm.Lecture presented at the University of Bergamo, Bergamo, Italy, October 1989.     

Easy distributions for combinatorial optimization problems with probabilistic constraints

We show how we can linearize individual probabilistic linear constraints with binary variables when all coefficients are independently distributed according to either N(μ_i,λμ_i), for some λ>0 and μ_i>0, or Γ(k_i,θ) for some θ>0 and k_i>0. The constraint can also be linearized when the coefficients are independent and identically distributed and either positive or strictly stable random variables.     

Global convergence without the assumption of linear independence for a trust-region algorithm for constrained optimization

A trust-region algorithm for solving the equality constrained optimization problem is presented. This algorithm uses the Byrd and Omojokun way of computing the trial steps, but it differs from the Byrd and Omojokun algorithm in the way steps are evaluated. A global convergence theory for this new algorithm is presented. The main feature of this theory is that the linear independence assumption on the gradients of the constraints is not assumed.This research was supported in part by the Center for Research on Parallel Computation, by Grant NSF-CCR-91-20008, and by the REDI Foundation.     

Investigating a hybrid simulated annealing and local search algorithm for constrained optimization

Constrained Optimization Problems (COP) often take place in many practical applications such as kinematics, chemical process optimization, power systems and so on. These problems are challenging in terms of identifying feasible solutions when constraints are non-linear and non-convex. Therefore, finding the location of the global optimum in the non-convex COP is more difficult as compared to non-convex bound-constrained global optimization problems. This paper proposes a Hybrid Simulated Annealing method (HSA), for solving the general COP. HSA has features that address both feasibility and optimality issues and here, it is supported by a local search procedure, Feasible Sequential Quadratic Programming (FSQP). We develop two versions of HSA. The first version (HSAP) incorporates penalty methods for constraint handling and the second one (HSAD) eliminates the need for imposing penalties in the objective function by tracing feasible and infeasible solution sequences independently. Numerical experiments show that the second version is more reliable in the worst case performance.     

A Class of penalty functions for optimization problema with bound constraints

In this paper we propose a new class of continuously differentiable globally exact penalty functions for the solution of minimization problems with simple bounds on some (all) of the variables. The penalty functions in this class fully exploit the structure of the problem and are easily computable. Furthermore we introduce a simple updating rule for the penalty parameter that can be used in conjunction with unconstrained minimization techniques to solve the original problem.