Separable nonlinear least squares fitting with linear bound constraints and its application in magnetic resonance spectroscopy data quantification

An application in magnetic resonance spectroscopy quantification models a signal as a linear combination of nonlinear functions. It leads to a separable nonlinear least squares fitting problem, with linear bound constraints on some variables. The variable projection (VARPRO) technique can be applied to this problem, but needs to be adapted in several respects. If only the nonlinear variables are subject to constraints, then the Levenberg–Marquardt minimization algorithm that is classically used by the VARPRO method should be replaced with a version that can incorporate those constraints. If some of the linear variables are also constrained, then they cannot be projected out via a closed-form expression as is the case for the classical VARPRO technique. We show how quadratic programming problems can be solved instead, and we provide details on efficient function and approximate Jacobian evaluations for the inequality constrained VARPRO method.     

一般线性或非线性约束下的共轭投影变尺度方法

梯度投影法是一类有效的约束最优化算法，在最优化领域中占有重要的地位．但是，梯度投影法所采用的投影是正交投影，不包含目标函数和约束函数的二阶导数信息·因而；收敛速度不太令人满意．本文介绍一种共轭投影概念，利用共轭投影构造了一般线性或非线性约束下的共轭投影变尺度算法，并证明了算法在一定条件下具有全局收敛性．由于算法中的共轭投影恰当地包含了目标函数和约束函数的二阶导数信息，因而收敛速度有希望加快．数值试验的结果表明算法是有效的．     

NPTool: a Matlab software for nonnegative image restoration with Newton projection methods

Several image restoration applications require the solution of nonnegatively constrained minimization problems whose objective function is typically constituted by the sum of a data fit function and a regularization function. Newton projection methods are very attractive because of their fast convergence, but they need an efficient implementation to avoid time consuming iterations. In this paper we present NPTool, a set of Matlab functions implementing Newton projection methods for image denoising and deblurring applications. They are specifically thought for two different data fit functions, the Least Squares function and the Kullback–Leibler divergence, and two regularization functions, Tikhonov and Total Variation, giving the opportunity of solving a large variety of restoration problems. The package is easily extensible to other linear or nonlinear data fit and regularization functions. Some examples of its use are included in the package and shown in this paper.     

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.     

Variable projection for nonlinear least squares problems

The variable projection algorithm of Golub and Pereyra (SIAM J. Numer. Anal. 10:413–432, 1973) has proven to be quite valuable in the solution of nonlinear least squares problems in which a substantial number of the parameters are linear. Its advantages are efficiency and, more importantly, a better likelihood of finding a global minimizer rather than a local one. The purpose of our work is to provide a more robust implementation of this algorithm, include constraints on the parameters, more clearly identify key ingredients so that improvements can be made, compute the Jacobian matrix more accurately, and make future implementations in other languages easy.     

求解特征值互补问题的一类ABS算法

ABS算法是20世纪80年代初,由Abaffy,Broyden和Spedicato完成的用于求解线性方程组的含有三个参量的投影算法,是一类有限次迭代直接法。目前,ABS算法不仅可以求解线性与非线性方程组,还可以求解线性规划和具有线性约束的非线性规划等问题。本文即是利用ABS算法求解特征值互补问题的一种尝试,构造了求解特征值互补问题的ABS算法,证明了求解特征值互补问题的ABS算法的收敛性。数值例子充分验证了求解特征值互补问题的ABS算法的有效性。     

Solving the bicriteria traffic equilibrium problem with variable demand and nonlinear path costs

In this paper, we present an algorithm for solving the bicriteria traffic equilibrium problem with variable demand and nonlinear path costs. The path cost function considered is comprised of two attributes, travel time and toll, that are combined into a nonlinear generalized cost. Travel demand is determined endogenously according to a travel disutility function. Travelers choose routes with the minimum overall generalized costs. The algorithm involves two components: a bicriteria shortest path routine to implicitly generate the set of non-dominated paths and a projection and contraction method to solve the nonlinear complementarity problem (NCP) describing the traffic equilibrium problem. Numerical experiments are conducted to demonstrate the feasibility of the algorithm to this class of traffic equilibrium problems.     

Approximating Networks and Extended Ritz Method for the Solution of Functional Optimization Problems

Functional optimization problems can be solved analytically only if special assumptions are verified; otherwise, approximations are needed. The approximate method that we propose is based on two steps. First, the decision functions are constrained to take on the structure of linear combinations of basis functions containing free parameters to be optimized (hence, this step can be considered as an extension to the Ritz method, for which fixed basis functions are used). Then, the functional optimization problem can be approximated by nonlinear programming problems. Linear combinations of basis functions are called approximating networks when they benefit from suitable density properties. We term such networks nonlinear (linear) approximating networks if their basis functions contain (do not contain) free parameters. For certain classes of d-variable functions to be approximated, nonlinear approximating networks may require a number of parameters increasing moderately with d, whereas linear approximating networks may be ruled out by the curse of dimensionality. Since the cost functions of the resulting nonlinear programming problems include complex averaging operations, we minimize such functions by stochastic approximation algorithms. As important special cases, we consider stochastic optimal control and estimation problems. Numerical examples show the effectiveness of the method in solving optimization problems stated in high-dimensional settings, involving for instance several tens of state variables.     

State-Space Regularization: Geometric Theory

Regularization of nonlinear ill-posed inverse problems is analyzed for a class of problems that is characterized by mappings which are the composition of a well-posed nonlinear and an ill-posed linear mapping. Regularization is carried out in the range of the nonlinear mapping. In applications this corresponds to the state-space variable of a partial differential equation or to preconditioning of data. The geometric theory of projection onto quasi-convex sets is used to analyze the stabilizing properties of this regularization technique and to describe its asymptotic behavior as the regularization parameter tends to zero. Accepted 26 April 1996     

A nonlinear Lagrangian for constrained optimization problems

A novel nonlinear Lagrangian is presented for constrained optimization problems with both inequality and equality constraints, which is nonlinear with respect to both functions in problem and Lagrange multipliers. The nonlinear Lagrangian inherits the smoothness of the objective and constraint functions and has positive properties. The algorithm on the nonlinear Lagrangian is demonstrated to possess local and linear convergence when the penalty parameter is less than a threshold (the penalty parameter in the penalty method has to approximate zero) under a set of suitable conditions, and be super-linearly convergent when the penalty parameter is decreased following Lagrange multiplier update. Furthermore, the dual problem based on the nonlinear Lagrangian is discussed and some important properties are proposed, which fail to hold for the dual problem based on the classical Lagrangian. At last, the preliminary and comparing numerical results for several typical test problems by using the new nonlinear Lagrangian algorithm and the other two related nonlinear Lagrangian algorithms, are reported, which show that the given nonlinear Lagrangian is promising.     

A NEW GENERALIZED GRADIENT PROJECTION TYPEALGORITHM FOR LINEARLY CONSTRAINED PROBLEMS

In this paper, we provide a new generalized gradient projection algorithm for nonlinear programming problems with linear constraints. This algorithm has simple structure and is very practical and stable. Under the weaker assumptions, we have proved the global convergence of our algorithm.     

Optimization of the Local Search in the Training for SAMANN Neural Network

In this paper, we discuss the visualization of multidimensional data. A well-known procedure for mapping data from a high-dimensional space onto a lower-dimensional one is Sammon’s mapping. This algorithm preserves as well as possible all interpattern distances. We investigate an unsupervised backpropagation algorithm to train a multilayer feed-forward neural network (SAMANN) to perform the Sammon’s nonlinear projection. Sammon mapping has a disadvantage. It lacks generalization, which means that new points cannot be added to the obtained map without recalculating it. The SAMANN network offers the generalization ability of projecting new data, which is not present in the original Sammon’s projection algorithm. To save computation time without losing the mapping quality, we need to select optimal values of control parameters. In our research the emphasis is put on the optimization of the learning rate. The experiments are carried out both on artificial and real data. Two cases have been analyzed: (1) training of the SAMANN network with full data set, (2) retraining of the network when the new data points appear.     

Visualization of Categorical Response Models: From Data Glyphs to Parameter Glyphs

The multinomial logit model is the most widely used model for nominal multi-category responses. One problem with the model is that many parameters are involved, and another that interpretation of parameters is much harder than for linear models because the model is nonlinear. Both problems can profit from graphical representations. We propose to visualize the effect strengths by star plots, where one star collects all the parameters connected to one term in the linear predictor. In simple models, one star refers to one explanatory variable. In contrast to conventional star plots, which are used to represent data, the plots represent parameters and are considered as parameter glyphs. The set of stars for a fitted model makes the main features of the effects of explanatory variables on the response variable easily accessible. The method is extended to ordinal models and illustrated by several datasets. Supplementary materials are available online.     

A parallel implementation for parameter estimation with implicit models

Parameter estimation and data regression represent special classes of optimization problems. Often, nonlinear programming methods can be tailored to take advantage of the least squares, or more generally, the maximum likelihood, objective function. In previous studies we have developed large-scale nonlinear programming methods that are based on tailored quasi-Newton updating strategies and matrix decomposition of the process model. The resulting algorithms converge in a reduced space of the parameters while simultaneously converging the process model. Moreover, tailoring the method to least squares functions leads to significant improvements in the performance of the algorithm. These approaches can be very efficient for both explicit and implicit models (i.e. problems with small and large degrees of freedom, respectively). In the latter case, degrees of freedom are proportional to a potential large number of data sets. Applications of this case include errors-in-all-variables estimation, data reconciliation and identification of process parameters. To deal with this structure, we apply a decomposition approach that performs a quadratic programming factorization for each data set. Because these are small components of large problems, an efficient and reliable algorithm results. These methods have generally been implemented on standard von Neumann architectures and few studies exist that exploit the parallelism of nonlinear programming algorithms. It is therefore interesting to note that for implicit model parameter estimation and related process applications, this approach can be quite amenable to parallel computation, because the major cost occurs in matrix decompositions for each data set. Here we describe an implementation of this approach on the Alliant FX/8 parallel computer at the Advanced Computing Research Facility at Argone National Laboratory. Special attention is paid to the architecture of this machine and its effect on the performance of the algorithm. This approach is demonstrated on five small, undetermined regression problems as well as a larger process example for simultaneous data reconciliation and parameter estimation.     

求广义几何规划全局最优解的线性化方法

对广义几何规划问题(GGP)提出了一个确定型全局优化算法，这类优化问题能广泛应用于工程设计和非线性系统的鲁棒稳定性分析等实际问题中，使用指数变换及对目标函数和约束函数的线性下界估计，建立了GGP的松弛线性规划(RLP)，通过对RLP可行域的细分以及一系列RLP的求解过程，从理论上证明了算法能收敛到GGP的全局最优解，对一个化学工程设计问题应用本文算法，数值实验表明本文方法是可行的。     

An implicit least squares algorithm for nonlinear rational model parameter estimation

In this study a new insight into least squares regression is identified and immediately applied to estimating the parameters of nonlinear rational models. From the beginning the ordinary explicit expression for linear in the parameters model is expanded into an implicit expression. Then a generic algorithm in terms of least squares error is developed for the model parameter estimation. It has been proved that a nonlinear rational model can be expressed as an implicit linear in the parameters model, therefore, the developed algorithm can be comfortably revised for estimating the parameters of the rational models. The major advancement of the generic algorithm is its conciseness and efficiency in dealing with the parameter estimation problems associated with nonlinear in the parameters models. Further, the algorithm can be used to deal with those regression terms which are subject to noise. The algorithm is reduced to an ordinary least square algorithm in the case of linear or linear in the parameters models. Three simulated examples plus a realistic case study are used to test and illustrate the performance of the algorithm.     

A New Step-Size Skill for Solving a Class of Nonlinear Projection Equations

1.IntroductionIn[11],aniterativeprojectionandcontraction(PC)methodforlinearcomplemen-taxityproblemswasproposed.Inpractice,thealgorithmbehaveseffectively,butintheorythesteP-sizecannotbeprovedtobeboundedawayfromzero.Sonostatementcanbemadeabouttherateofconvergence.AlthoughavariantoftheprimePCal-gorithmwithconstantstepsizeforlineaJrprogrammminghasalinearconvergence['1,itconvergesmuchslowerinparctice.In[1o],HeproposedanewsteVsizerulefortheprimePCalgorithmforthelinearprogrammingsuchthattheresul…     

一般单调变分不等式的一个改进的预估-校正算法

最近何炳生等提出了解大规模单调变分不等式的一种预估-校正算法,然而,这个方法在计算每一个试验点时需要一次投影运算,因而计算量较大．为了克服这个缺点,我们提出了一个解一般大规模g-单调变分不等式的新的预估-校正算法,该方法使用了一个非常有效的预估步长准则,每个步长的选取只需要计算一次投影,这将大大减少计算量．数值试验说明我们的算法比最新文献中出现的投影类方法有效．     

Finding all solutions of affine generalized Nash equilibrium problems with one-dimensional strategy sets

We consider a class of generalized Nash equilibrium problems with quadratic cost functions and common linear constraints for all players. Further we focus on the case where every player has a single strategy variable within a bounded set. For this problem class we present an algorithm that is able to compute all solutions and that terminates finitely. Our method is based on a representation of the solution set as a finite union of polyhedral sets using sign conditions for the derivatives of the cost and constraint functions. The effectiveness of the algorithm is shown in various examples from literature.     

Valid inequalities for separable concave constraints with indicator variables

We study valid inequalities for optimization models that contain both binary indicator variables and separable concave constraints. These models reduce to a mixed-integer linear program (MILP) when the concave constraints are ignored, or to a nonconvex global optimization problem when the binary restrictions are ignored. In algorithms designed to solve these problems to global optimality, cutting planes to strengthen the relaxation are traditionally obtained using valid inequalities for the MILP only. We propose a technique to obtain valid inequalities that are based on both the MILP constraints and the concave constraints. We begin by characterizing the convex hull of a four-dimensional set consisting of a single binary indicator variable, a single concave constraint, and two linear inequalities. Using this analysis, we demonstrate how valid inequalities for the single node flow set and for the lot-sizing polyhedron can be “tilted” to give valid inequalities that also account for separable concave functions of the arc flows. We present computational results demonstrating the utility of the new inequalities for nonlinear transportation problems and for lot-sizing problems with concave costs. To our knowledge, this is one of the first works that simultaneously convexifies both nonconvex functions and binary variables to strengthen the relaxations of practical mixed-integer nonlinear programs.