The Lagrange method and SAO with bounds on the dual variables

Abstract

We consider the minimization of f₀ (x), x∈ℛⁿ, subject to f_j (x)=0, 1≤j≤m^′, f_j (x)≤0, m^′+1≤j≤m and x∈χ, where χ is compact. For any λ∈ℛ^m, let x (λ) be a minimizer of the Lagrange function , x∈χ, and let φ be the dual function φ (λ)=L (x (λ), λ), λ∈ℛ^m. Assuming only that the functions f_j are continuous, it has been proved that, if x (λ) is unique, then φ has the derivatives d φ (λ)/d λ_j=f_j (x (λ)), 1≤j≤m. Furthermore, if φ (λ*) is the greatest value of φ (λ), λ∈ℛ^m, subject to λ_j≥0, m^′+1≤j≤m, and if x (λ*) is unique, then x=x (λ*) is the solution of the given problem. These properties are illustrated by an example with n=2 and m^′=m=1. The given problem may have no feasible point, however, and then φ may not be bounded above. Therefore the bounded dual method adds the condition | λ |_∞≤Λ for some prescribed Λ>0, and we let λ* be the new maximizer of φ. We find that, if x (λ*) is unique, then now it minimizes the function Ψ (x), x∈χ, which is f₀ (x) plus Λ times the sum of moduli of constraint violations at x. The term SAO stands for Sequential Approximate Optimization. An outermost iteration makes quadratic approximations to the functions f_j, 0≤j≤m, with first order accuracy at x^(k), say, where k is the iteration number. Then using the approximations instead of the original functions, the bounded dual method is applied, giving a new λ* with a unique x (λ*). The choice of x^(k+1) can depend on Ψ (x^(k)) and on the new Ψ (x (λ*)). Thus our theory suggests some useful developments of SAO.

Keywords:

• bounded dual method
• constrained optimization
• derivatives of dual function
• L ₁ penalty terms
• Lagrange method
• sequential approximate optimization

It is mentioned in Section 1 that I was introduced to SAO methods by Albert Groenwold. I cannot thank him enough for renewing my interest in the use of Lagrange functions. I am also very grateful to the Mathematical Sciences Department of the University of Stellenbosch, where I received much support, encouragement and hospitality for 2 months while the given work was begun. Helpful comments on a draft of this paper were made by Pascal Etman and Daniel Robinson. I am indebted to Oleg Burdakov for the references [1,10] and to four referees for a wide range of remarks.

Notes

† Presented at the 8th International Conference on Numerical Optimization and Numerical Linear Algebra (Xiamen, China, 2011).