On local convergence of sequential quadratically-constrained quadratic-programming type methods,with an extension to variational problems

We consider the class of quadratically-constrained quadratic-programming methods in the framework extended from optimization to more general variational problems. Previously, in the optimization case, Anitescu (SIAM J. Optim. 12, 949–978, 2002) showed superlinear convergence of the primal sequence under the Mangasarian-Fromovitz constraint qualification and the quadratic growth condition. Quadratic convergence of the primal-dual sequence was established by Fukushima, Luo and Tseng (SIAM J. Optim. 13, 1098–1119, 2003) under the assumption of convexity, the Slater constraint qualification, and a strong second-order sufficient condition. We obtain a new local convergence result, which complements the above (it is neither stronger nor weaker): we prove primal-dual quadratic convergence under the linear independence constraint qualification, strict complementarity, and a second-order sufficiency condition. Additionally, our results apply to variational problems beyond the optimization case. Finally, we provide a necessary and sufficient condition for superlinear convergence of the primal sequence under a Dennis-Moré type condition. Research of the second author is partially supported by CNPq Grants 300734/95-6 and 471780/2003-0, by PRONEX–Optimization, and by FAPERJ.     

A smoothing projected Newton-type algorithm for semi-infinite programming

This paper presents a smoothing projected Newton-type method for solving the semi-infinite programming (SIP) problem. We first reformulate the KKT system of the SIP problem into a system of constrained nonsmooth equations. Then we solve this system by a smoothing projected Newton-type algorithm. At each iteration only a system of linear equations needs to be solved. The feasibility is ensured via the aggregated constraint under some conditions. Global and local superlinear convergence of this method is established under some standard assumptions. Preliminary numerical results are reported. Qi’s work is supported by the Hong Kong Research Grant Council. Ling’s work was supported by the Zhejiang Provincial National Science Foundation of China (Y606168). Tong’s work was done during her visit to The Hong Kong Polytechnic University. Her work is supported by the NSF of China (60474070) and the Technology Grant of Hunan (06FJ3038). Zhou’s work is supported by Australian Research Council.     

Nonlinear Rescaling as Interior Quadratic Prox Method in Convex Optimization

A class Ψ of strictly concave and twice continuously differentiable functions ψ: R → R with particular properties is used for constraint transformation in the framework of a Nonlinear Rescaling (NR) method with “dynamic” scaling parameter updates. We show that the NR method is equivalent to the Interior Quadratic Prox method for the dual problem in a rescaled dual space. The equivalence is used to prove convergence and to estimate the rate of convergence of the NR method and its dual equivalent under very mild assumptions on the input data for a wide class Ψ of constraint transformations. It is also used to estimate the rate of convergence under strict complementarity and under the standard second order optimality condition. We proved that for any ψ ∈ Ψ, which corresponds to a well-defined dual kernel ϕ = −ψ*, the NR method applied to LP generates a quadratically convergent dual sequence if the dual LP has a unique solution. This paper is dedicated to Professor Elijah Polak on the occasion of his 75th birthday.     

The rate of convergence of the augmented Lagrangian method for nonlinear semidefinite programming

We analyze the rate of local convergence of the augmented Lagrangian method in nonlinear semidefinite optimization. The presence of the positive semidefinite cone constraint requires extensive tools such as the singular value decomposition of matrices, an implicit function theorem for semismooth functions, and variational analysis on the projection operator in the symmetric matrix space. Without requiring strict complementarity, we prove that, under the constraint nondegeneracy condition and the strong second order sufficient condition, the rate of convergence is linear and the ratio constant is proportional to 1/c, where c is the penalty parameter that exceeds a threshold . The research of Defeng Sun is partly supported by the Academic Research Fund from the National University of Singapore. The research of Jie Sun and Liwei Zhang is partly supported by Singapore–MIT Alliance and by Grants RP314000-042/057-112 of the National University of Singapore. The research of Liwei Zhang is also supported by the National Natural Science Foundation of China under project grant no. 10471015 and by the Scientific Research Foundation for the Returned Overseas Chinese Scholars, State Education Ministry, China.     

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.     

Obtaining an outer approximation of the efficient set of nonlinear biobjective problems

A new method for obtaining an outer approximation of the efficient set of nonlinear biobjective optimization problems is presented. It is based on the well known ‘constraint method’, and obtains a superset of the efficient set by computing the regions of δ-optimality of a finite number of single objective constraint problems. An actual implementation, which makes use of interval tools, shows the applicability of the method and the computational studies on a set of competitive location problems demonstrate its efficiency. An extended version of this paper, with more comments, details, examples, and references, can be found in Fernández and Tóth [5]. This paper has been supported by the Ministry of Education and Science of Spain under the research project SEJ2005-06273/ECON, in part financed by the European Regional Development Fund (ERDF). Boglárka Tóth—On leave from the Research Group on Artificial Intelligence of the Hungarian Academy of Sciences and the University of Szeged, H-6720 Szeged, Aradi vértanúk tere 1., Hungary.     

Non-monotone trust region methods for nonlinear equality constrained optimization without a penalty function

 We propose and analyze a class of penalty-function-free nonmonotone trust-region methods for nonlinear equality constrained optimization problems. The algorithmic framework yields global convergence without using a merit function and allows nonmonotonicity independently for both, the constraint violation and the value of the Lagrangian function. Similar to the Byrd–Omojokun class of algorithms, each step is composed of a quasi-normal and a tangential step. Both steps are required to satisfy a decrease condition for their respective trust-region subproblems. The proposed mechanism for accepting steps combines nonmonotone decrease conditions on the constraint violation and/or the Lagrangian function, which leads to a flexibility and acceptance behavior comparable to filter-based methods. We establish the global convergence of the method. Furthermore, transition to quadratic local convergence is proved. Numerical tests are presented that confirm the robustness and efficiency of the approach. Received: December 14, 2000 / Accepted: August 30, 2001 Published online: September 27, 2002 Key words. nonmonotone trust-region methods – sequential quadratic programming – penalty function – global convergence – equality constraints – local convergence – large-scale optimization Mathematics Subject Classification (2000): 65K05, 90C30     

Convergence of the Augmented Lagrangian Method for Nonlinear Optimization Problems over Second-Order Cones

The paper analyzes the rate of local convergence of the augmented Lagrangian method for nonlinear second-order cone optimization problems. Under the constraint nondegeneracy condition and the strong second order sufficient condition, we demonstrate that the sequence of iterate points generated by the augmented Lagrangian method locally converges to a local minimizer at a linear rate, whose ratio constant is proportional to 1/τ with penalty parameter τ not less than a threshold . Importantly and interestingly enough, the analysis does not require the strict complementarity condition. Supported by the National Natural Science Foundation of China under Project 10771026 and by the Scientific Research Foundation for the Returned Overseas Chinese Scholars, State Education Ministry.     

Newton’s Method for Computing the Nearest Correlation Matrix with a Simple Upper Bound

The standard nearest correlation matrix can be efficiently computed by exploiting a recent development of Newton’s method (Qi and Sun in SIAM J. Matrix Anal. Appl. 28:360–385, 2006). Two key mathematical properties, that ensure the efficiency of the method, are the strong semismoothness of the projection operator onto the positive semidefinite cone and constraint nondegeneracy at every feasible point. In the case where a simple upper bound is enforced in the nearest correlation matrix in order to improve its condition number, it is shown, among other things, that constraint nondegeneracy does not always hold, meaning Newton’s method may lose its quadratic convergence. Despite this, the numerical results show that Newton’s method is still extremely efficient even for large scale problems. Through regularization, the developed method is applied to semidefinite programming problems with simple bounds.     

Constraint identification and algorithm stabilization for degenerate nonlinear programs

 In the vicinity of a solution of a nonlinear programming problem at which both strict complementarity and linear independence of the active constraints may fail to hold, we describe a technique for distinguishing weakly active from strongly active constraints. We show that this information can be used to modify the sequential quadratic programming algorithm so that it exhibits superlinear convergence to the solution under assumptions weaker than those made in previous analyses. Received: December 18, 2000 / Accepted: January 14, 2002 Published online: September 27, 2002 RID="★" ID="★" Research supported by the Mathematical, Information, and Computational Sciences Division subprogram of the Office of Advanced Scientific Computing Research, U.S. Department of Energy, under Contract W-31-109-Eng-38. Key words. nonlinear programming problems – degeneracy – active constraint identification – sequential quadratic programming     

On the characterization of strong convergence of an iterative algorithm for a class of multi-valued variational inclusions

This paper introduces an Ishikawa type iterative algorithm for finding approximating solutions of a class of multi-valued variational inclusion problems. Characterization of strong convergence of this iterative method is established. L. C. Ceng’s research partially supported by the Teaching and Research Award Fund for Outstanding Young Teachers in Higher Education Institutions of MOE, China and the Dawn Program Foundation in Shanghai. S. Schaible’s research partially supported by the National Science Council of Taiwan. This research was partially supported by the grant NSC 96-2628-E-110-014-MY3.     

The augmented lagrangian method for equality and inequality constraints in hilbert spaces

In this paper we consider an augmented Lagrangian method for the minimization of a nonlinear functional in the presence of an equality constraint whose image space is in a Hilbert space, an inequality constraint whose image space is finite dimensional, and an affine inequality constraint whose image space is in an infinite dimensional Hilbert space. We obtain local convergence of this method without imposing strict complementarity conditions when the equality, as well as the inequality constraint with finite dimensional image space are augmented. To the author's knowledge this result even generalizes the convergence results which are known when all spaces are finite dimensional.This research was supported by the Air Force Office of Scientific Research under Grant AFOSR-84-0398 and AFOSR-85-0303, by the National Aeronautics and Space Administration under Grant NAG-1-517, and by NSF under Grant UINT-8521208.This research was supported in part by the Fonds zur Förderung der wissenschaftichen Forschung under S3206 and P6005 and by AFOSR-84-0398. Part of this work was performed while the author was visiting the Division of Applied Mathematics, Brown University, Providence, RI, USA.     

A convergent adaptive finite element method for an optimal design problem

The optimal design problem for maximal torsion stiffness of an infinite bar of given geometry and unknown distribution of two materials of prescribed amounts is one model example in topology optimisation. It eventually leads to a degenerate convex minimisation problem. The numerical analysis is therefore delicate for possibly multiple primal variables u but unique derivatives σ : = DW(D u). Even fine a posteriori error estimates still suffer from the reliability-efficiency gap. However, it motivates a simple edge-based adaptive mesh-refining algorithm (AFEM) that is not a priori guaranteed to refine everywhere. Its convergence proof is therefore based on energy estimates and some refined convexity control. Numerical experiments illustrate even nearly optimal convergence rates of the proposed AFEM. Supported by the DFG Research Center MATHEON “Mathematics for key technologies” in Berlin.     

Superlinear convergence of the control reduced interior point method for PDE constrained optimization

A thorough convergence analysis of the Control Reduced Interior Point Method in function space is performed. This recently proposed method is a primal interior point pathfollowing scheme with the special feature that the control variable is eliminated from the optimality system. Apart from global linear convergence we show that this method converges locally superlinearly, if the optimal solution satisfies a certain non-degeneracy condition. In numerical experiments we observe that a prototype implementation of our method behaves as predicted by our theoretical results. Supported by the DFG Research Center Matheon “Mathematics for key technologies”.     

Multiobjective optimization problem with variational inequality constraints

 We study a general multiobjective optimization problem with variational inequality, equality, inequality and abstract constraints. Fritz John type necessary optimality conditions involving Mordukhovich coderivatives are derived. They lead to Kuhn-Tucker type necessary optimality conditions under additional constraint qualifications including the calmness condition, the error bound constraint qualification, the no nonzero abnormal multiplier constraint qualification, the generalized Mangasarian-Fromovitz constraint qualification, the strong regularity constraint qualification and the linear constraint qualification. We then apply these results to the multiobjective optimization problem with complementarity constraints and the multiobjective bilevel programming problem. Received: November 2000 / Accepted: October 2001 Published online: December 19, 2002 Key Words. Multiobjective optimization – Variational inequality – Complementarity constraint – Constraint qualification – Bilevel programming problem – Preference – Utility function – Subdifferential calculus – Variational principle Research of this paper was supported by NSERC and a University of Victoria Internal Research Grant Research was supported by the National Science Foundation under grants DMS-9704203 and DMS-0102496 Mathematics Subject Classification (2000): Sub49K24, 90C29     

On the convergence of the Newton/log-barrier method

In the Newton/log-barrier method, Newton steps are taken for the log-barrier function for a fixed value of the barrier parameter until a certain convergence criterion is satisfied. The barrier parameter is then decreased and the Newton process is repeated. A naive analysis indicates that Newton’s method does not exhibit superlinear convergence to the minimizer of each instance of the log-barrier function until it reaches a very small neighborhood, namely within O(μ²) of the minimizer, where μ is the barrier parameter. By analyzing the structure of the barrier Hessian and gradient in terms of the subspace of active constraint gradients and the associated null space, we show that this neighborhood is in fact much larger –O(μ^σ) for any σ∈(1,2] – thus explaining why reasonably fast local convergence can be attained in practice. Moreover, we show that the overall convergence rate of the Newton/log-barrier algorithm is superlinear in the number of function/derivative evaluations, provided that the nonlinear program is formulated with a linear objective and that the schedule for decreasing the barrier parameter is related in a certain way to the step length and convergence criteria for each Newton process. Received: October 10, 1997 / Accepted: September 10, 2000?Published online February 22, 2001     

Convergence and efficiency of subgradient methods for quasiconvex minimization

We study a general subgradient projection method for minimizing a quasiconvex objective subject to a convex set constraint in a Hilbert space. Our setting is very general: the objective is only upper semicontinuous on its domain, which need not be open, and various subdifferentials may be used. We extend previous results by proving convergence in objective values and to the generalized solution set for classical stepsizes t _k →0, ∑t _k =∞, and weak or strong convergence of the iterates to a solution for {t _k }∈ℓ₂∖ℓ₁ under mild regularity conditions. For bounded constraint sets and suitable stepsizes, the method finds ε-solutions with an efficiency estimate of O(ε^-2), thus being optimal in the sense of Nemirovskii. Received: October 4, 1998 / Accepted: July 24, 2000?Published online January 17, 2001     

Inexact Josephy–Newton framework for generalized equations and its applications to local analysis of Newtonian methods for constrained optimization

We propose and analyze a perturbed version of the classical Josephy–Newton method for solving generalized equations. This perturbed framework is convenient to treat in a unified way standard sequential quadratic programming, its stabilized version, sequential quadratically constrained quadratic programming, and linearly constrained Lagrangian methods. For the linearly constrained Lagrangian methods, in particular, we obtain superlinear convergence under the second-order sufficient optimality condition and the strict Mangasarian–Fromovitz constraint qualification, while previous results in the literature assume (in addition to second-order sufficiency) the stronger linear independence constraint qualification as well as the strict complementarity condition. For the sequential quadratically constrained quadratic programming methods, we prove primal-dual superlinear/quadratic convergence under the same assumptions as above, which also gives a new result.     

Weighted Hermite-Fejér interpolation on the real line: L ∞ case

We give a weighted Hermite-Fejér-type interpolatory method on the real line, which is a positive operator on “good” matrices. We give an example on “good” interpolatory matrix by weighted Fekete points. To prove the convergence theorem we need the generalization of “Rodrigues’ property”. The present publication was written in the framework of the Hungarian-Spanish Scientific and Technological Governmental Cooperation, no. E-38/04, with the support of the Research and Technological Development Fund of Hungary and the Ministry of Education of Spain, and supported by Hungarian National Foundation for Scientific Research, Grant No. T049301.     

Landweber iterative methods for angle-limited image reconstruction

We introduce a general iterative scheme for angle-limited image reconstruction based on Landwebet＇s method. We derive a representation formula for this scheme and consequently establish its convergence conditions. Our results suggest certain relaxation strategies for an accelerated convergence for angle-limited image reconstruction in L^2-norm comparing with alternative projection methods. The convolution-backprojection algorithm is given for this iterative process.