关于结构KKT方程组的扰动分析

We discuss the perturbation analysis for the structured KKT systems. The methods and results of forward perturbation analysis all differ from the recent works of Gulliksson and other authors. The optimal backward perturbation results can not be deduced by the corresponding results of Sun about the KKT systems.  

Nonsmooth Equation Based BFGS Method for Solving KKT Systems in Mathematical Programming

In this paper, we present a BFGS method for solving a KKT system in mathematical programming, based on a nonsmooth equation reformulation of the KKT system. We split successively the nonsmooth equation into equivalent equations with a particular structure. Based on the splitting, we develop a BFGS method in which the subproblems are systems of linear equations with symmetric and positive-definite coefficient matrices. A suitable line search is introduced under which the generated iterates exhibit an approximate norm descent property. The method is well defined and, under suitable conditions, converges to a KKT point globally and superlinearly without any convexity assumption on the problem.  

一类KKT系统的结构敏度分析

本文讨论一类KKT系统的敏度分析，这类KKT系统产生于用有限元方法离散Stokes方程，有结构特性．首先给出了最佳向后扰动界，接下来定义了偏条件数并导出了表达式．最后给出了新的扰动界．  

Augmented Lagrangian methods under the constant positive linear dependence constraint qualification

Two Augmented Lagrangian algorithms for solving KKT systems are introduced. The algorithms differ in the way in which penalty parameters are updated. Possibly infeasible accumulation points are characterized. It is proved that feasible limit points that satisfy the Constant Positive Linear Dependence constraint qualification are KKT solutions. Boundedness of the penalty parameters is proved under suitable assumptions. Numerical experiments are presented. The authors were supported by PRONEX - CNPq / FAPERJ E-26 / 171.164/2003 - APQ1, FAPESP (Grants 2001/04597-4, 2002/00094-0, 2003/09169-6, 2002/00832-1 and 2005/56773-1) and CNPq.  

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.  

Second-Order Approach to Optimal Semiconductor Design

Second order methods for optimal semiconductor design based on the standard drift diffusion model are developed. Second–order necessary and sufficient conditions are established. Local quadratic convergence for the Newton method is proved. Numerical results for an unsymmetric (n–p) diode are presented. The first author acknowledges financial support from the Collaborative Research Center 609 funded by the German Research Foundation. The second author was supported by the European network HYKE, funded by the EC under Contract HPRN-CT-2002-00282.  

On the iterative solution of KKT systems in potential reduction software for large-scale quadratic problems

Iterative solvers appear to be very promising in the development of efficient software, based on Interior Point methods, for large-scale nonlinear optimization problems. In this paper we focus on the use of preconditioned iterative techniques to solve the KKT system arising at each iteration of a Potential Reduction method for convex Quadratic Programming. We consider the augmented system approach and analyze the behaviour of the Constraint Preconditioner with the Conjugate Gradient algorithm. Comparisons with a direct solution of the augmented system and with MOSEK show the effectiveness of the iterative approach on large-scale sparse problems. Work partially supported by the Italian MIUR FIRB Project Large Scale Nonlinear Optimization, grant no. RBNE01WBBB.  

Stopping criteria for inner iterations in inexact potential reduction methods: a computational study

We focus on the use of adaptive stopping criteria in iterative methods for KKT systems that arise in Potential Reduction methods for quadratic programming. The aim of these criteria is to relate the accuracy in the solution of the KKT system to the quality of the current iterate, to get computational efficiency. We analyze a stopping criterion deriving from the convergence theory of inexact Potential Reduction methods and investigate the possibility of relaxing it in order to reduce as much as possible the overall computational cost. We also devise computational strategies to face a possible slowdown of convergence when an insufficient accuracy is required.  

Some iterative methods for the solution of a symmetric indefinite KKT system

This paper is concerned with the numerical solution of a Karush–Kuhn–Tucker system. Such symmetric indefinite system arises when we solve a nonlinear programming problem by an Interior-Point (IP) approach. In this framework, we discuss the effectiveness of two inner iterative solvers: the method of multipliers and the preconditioned conjugate gradient method. We discuss the implementation details of these algorithms in an IP scheme and we report the results of a numerical comparison on a set of large scale test-problems arising from the discretization of elliptic control problems. This research was supported by the Italian Ministry for Education, University and Research (MIUR), FIRB Project RBAU01JYPN.  

A practical solution for KKT systems

We consider KKT systems of linear equations with a 2 × 2 block indefinite matrix whose (2, 2) block is zero. Such systems arise in many applications. Treating such matrices would encounter some intricacies, especially when its (1, 1) block, i.e., the stiffness matrix in term of computational mechanics, is rank-deficient. It is the rank-deficiency of the stiffness matrix that leads to the so-called rigid-displacement issue. This is believed to be one of the main reasons that many programmers would unwillingly give up the Lagrange multiplier method but select the penalty method. Based on the Sherman–Morrison formula and the conventional LDL^T decomposition for symmetric positive definite matrices, a robust direct solution is proposed, which is amenable to the conventional finite element codes, competent for both nonsingular and singular stiffness matrices, and particularly suitable to parallel computation. As a paradigm, the application to the element-free Galerkin method (EFGM) with the moving least squares interpolation is illustrated. Funded by the National Natural Science Foundation of China (NSFC), Project no. 90510019.