QPECgen, a MATLAB Generator for Mathematical Programs with Quadratic Objectives and Affine Variational Inequality Constraints

We describe a technique for generating a special class, called QPEC, of mathematical programs with equilibrium constraints, MPEC. A QPEC is a quadratic MPEC, that is an optimization problem whose objective function is quadratic, first-level constraints are linear, and second-level (equilibrium) constraints are given by a parametric affine variational inequality or one of its specialisations. The generator, written in MATLAB, allows the user to control different properties of the QPEC and its solution. Options include the proportion of degenerate constraints in both the first and second level, ill-conditioning, convexity of the objective, monotonicity and symmetry of the second-level problem, and so on. We believe these properties may substantially effect efficiency of existing methods for MPEC, and illustrate this numerically by applying several methods to generator test problems. Documentation and relevant codes can be found by visiting http://www.ms.unimelb.edu.au/danny/qpecgendoc.html.     

A primal-dual interior-point algorithm for quadratic programming

In this paper we propose a primal-dual interior-point method for large, sparse, quadratic programming problems. The method is based on a reduction presented by Gonzalez-Lima, Wei, and Wolkowicz [14] in order to solve the linear systems arising in the primal-dual methods for linear programming. The main features of this reduction is that it is well defined at the solution set and it preserves sparsity. These properties add robustness and stability to the algorithm and very accurate solutions can be obtained. We describe the method and we consider different reductions using the same framework. We discuss the relationship of our proposals and the one used in the LOQO code. We compare and study the different approaches by performing numerical experimentation using problems from the Maros and Meszaros collection. We also include a brief discussion on the meaning and effect of ill-conditioning when solving linear systems.This work was partially supported by DID-USB (GID-001).     

Stabilization of Interior-Point Methods for Linear Programming

The paper studies numerical stability problems arising in the application of interior-point methods to primal degenerate linear programs. A stabilization procedure based on Gaussian elimination is proposed and it is shown that it stabilizes all path following methods, original and modified Dikin's method, Karmarkar's method, etc.     

荧光光谱解析中矩阵病态对检测结果的影响

在工程数据处理中,经常要进行矩阵变换,矩阵病态性影响计算结果的稳定性,而矩阵的条件数与矩阵病态性密切相关.针对荧光光谱原始信号,通过分析解谱矩阵的条件数,给出通过解谱矩阵进行信号解谱时,解谱矩阵病态性对解谱数据结果的影响以及在提取解谱矩阵时如何减少矩阵病态性的方法.实验结果表明,数据突变会导致矩阵病态性增加,同时带来荧光光谱结果失真,在实际解谱矩阵提取及数据处理过程中,需重视并增强荧光染料谱图的平滑性.     

A class of generalized variable penalty methods for nonlinear programming

A class of generalized variable penalty formulations for solving nonlinear programming problems is presented. The method poses a sequence of unconstrained optimization problems with mechanisms to control the quality of the approximation for the Hessian matrix, which is expressed in terms of the constraint functions and their first derivatives. The unconstrained problems are solved using a modified Newton's algorithm. The method is particularly applicable to solution techniques where an approximate analysis step has to be used (e.g., constraint approximations, etc.), which often results in the violation of the constraints. The generalized penalty formulation contains two floating parameters, which are used to meet the penalty requirements and to control the errors in the approximation of the Hessian matrix. A third parameter is used to vary the class of standard barrier or quasibarrier functions, forming a branch of the variable penalty formulation. Several possibilities for choosing such floating parameters are discussed. The numerical effectiveness of this algorithm is demonstrated on a relatively large set of test examples.The author is thankful for the constructive suggestions of the referees.     

REGULARIZATION TOOLS: A Matlab package for analysis and solution of discrete ill-posed problems

The package REGULARIZATION TOOLS consists of 54 Matlab routines for analysis and solution of discrete ill-posed problems, i.e., systems of linear equations whose coefficient matrix has the properties that its condition number is very large, and its singular values decay gradually to zero. Such problems typically arise in connection with discretization of Fredholm integral equations of the first kind, and similar ill-posed problems. Some form of regularization is always required in order to compute a stabilized solution to discrete ill-posed problems. The purpose of REGULARIZATION TOOLS is to provide the user with easy-to-use routines, based on numerical robust and efficient algorithms, for doing experiments with regularization of discrete ill-posed problems. By means of this package, the user can experiment with different regularization strategies, compare them, and draw conclusions from these experiments that would otherwise require a major programming effert. For discrete ill-posed problems, which are indeed difficult to treat numerically, such an approach is certainly superior to a single black-box routine. This paper describes the underlying theory gives an overview of the package; a complete manual is also available.This work was supported by grants from Augustinus Fonden, Knud Højgaards Fond, and Civ. Ing. Frants Allings Legat.