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.     

On the solution of a two ball trust region subproblem

In this paper we investigate the structure of a two ball trust region subproblem arising frequently in nonlinear parameter identification problems and propose a method for its solution. The method decomposes the subproblem and allows the application of efficient, well studied methods for the solution of trust region subproblems arising in unconstrained optimization. In the discussion of the structure we focus on the case where both constraints are active and on the treatment of the unconstrained problem.The research of this author was partially supported bygottlieb-daimler andkarl-benz-stiftung, Ladenburg and NSF, Cooperate of Agreement No. CCR-8809615.     

A method combining norm-relaxed QP subproblems with systems of linear equations for constrained optimization

Based on the ideas of norm-relaxed sequential quadratic programming (SQP) method and the strongly sub-feasible direction method, we propose a new SQP algorithm for the solution of nonlinear inequality constrained optimization. Unlike the previous work, at each iteration, the norm-relaxed quadratic programming subproblem (NRQPS) in our algorithm only consists of the constraints corresponding to an estimate of the active set, and the high-order correction direction (used to avoid the Maratos effect) is obtained by solving a system of linear equations (SLE) which also only consists of such a subset of constraints and gradients. Moreover, the line search technique can effectively combine the initialization process with the optimization process, and therefore (if the starting point is not feasible) the iteration points always get into the feasible set after a finite number of iterations. The global convergence is proved under the Mangasarian–Fromovitz constraint qualification (MFCQ), and the superlinear convergence is obtained without assuming the strict complementarity. Finally, the numerical experiments show that the proposed algorithm is effective and promising for the test problems.     

A globally most violated cutting plane method for complex minimax problems with application to digital filter design

In [4,6], the authors have presented a numerical method for the solution of complex minimax problems, which implicitly solves discretized versions of the equivalent semi-infinite programming problem on increasingly finer grids. While this method only requires the most violated constraint at the current iterate on a finite subset of the infinitely many constraints of the problem, we consider here a related and more direct approach (applicable to general convex semi-infinite programming problems) which makes use of the globally most violated constraint. Numerical examples with up to 500 unknowns, which partially originate from digital filter design problems, are discussed.     

A modified SLP algorithm and its global convergence

This paper concerns a filter technique and its application to the trust region method for nonlinear programming (NLP) problems. We used our filter trust region algorithm to solve NLP problems with equality and inequality constraints, instead of solving NLP problems with just inequality constraints, as was introduced by Fletcher et al. [R. Fletcher, S. Leyffer, Ph.L. Toint, On the global converge of an SLP-filter algorithm, Report NA/183, Department of Mathematics, Dundee University, Dundee, Scotland, 1999]. We incorporate this filter technique into the traditional trust region method such that the new algorithm possesses nonmonotonicity. Unlike the tradition trust region method, our algorithm performs a nonmonotone filter technique to find a new iteration point if a trial step is not accepted. Under mild conditions, we prove that the algorithm is globally convergent.     

一类非光滑广义分式规划的Kuhn-Tucker型最优性必要条件

考虑一类非线性不等式约束的非光滑minimax分式规划问题;目标函数中的分子是可微函数与凸函数之和形式而分母是可微函数与凸函数之差形式,且约束函数是可微的.在Arrow- Hurwicz-Uzawa约束品性下,给出了这类规划的最优解的Kuhn-Tucker型必要条件.所得结果改进和推广了已有文献中的相应结果.     

An exact penalty function method for nonlinear mixed discrete programming problems

In this paper, we consider a general class of nonlinear mixed discrete programming problems. By introducing continuous variables to replace the discrete variables, the problem is first transformed into an equivalent nonlinear continuous optimization problem subject to original constraints and additional linear and quadratic constraints. Then, an exact penalty function is employed to construct a sequence of unconstrained optimization problems, each of which can be solved effectively by unconstrained optimization techniques, such as conjugate gradient or quasi-Newton methods. It is shown that any local optimal solution of the unconstrained optimization problem is a local optimal solution of the transformed nonlinear constrained continuous optimization problem when the penalty parameter is sufficiently large. Numerical experiments are carried out to test the efficiency of the proposed method.     

Log-Sigmoid nonlinear Lagrange method for nonlinear optimization problems over second-order cones

This paper analyzes the rate of local convergence of the Log-Sigmoid nonlinear Lagrange method for nonconvex nonlinear second-order cone programming. Under the componentwise strict complementarity condition, the constraint nondegeneracy condition and the second-order sufficient condition, we show that the sequence of iteration points generated by the proposed method locally converges to a local solution when the penalty parameter is less than a threshold and the error bound of solution is proportional to the penalty parameter. Finally, we report numerical results to show the efficiency of the method.     

A superlinearly convergent strongly sub-feasible SSLE-type algorithm with working set for nonlinearly constrained optimization

In this paper, by means of a new efficient identification technique of active constraints and the method of strongly sub-feasible direction, we propose a new sequential system of linear equations (SSLE) algorithm for solving inequality constrained optimization problems, in which the initial point is arbitrary. At each iteration, we first yield the working set by a pivoting operation and a generalized projection; then, three or four reduced linear equations with a same coefficient are solved to obtain the search direction. After a finite number of iterations, the algorithm can produced a feasible iteration point, and it becomes the method of feasible directions. Moreover, after finitely many iterations, the working set becomes independent of the iterates and is essentially the same as the active set of the KKT point. Under some mild conditions, the proposed algorithm is proved to be globally, strongly and superlinearly convergent. Finally, some preliminary numerical experiments are reported to show that the algorithm is practicable and effective.     

Detecting embedded pure network structures in LP problems

Recently, linear programming problems with special structures have assumed growing importance in mathematical programming. It is well known that exploiting network structures within linear programs can lead to considerable improvement of the computational solution of large-scale linear programming problems. A linear program is said to contain an embedded network structure provided that some subset of its constraints can be interpreted as specifying conservation of flow. If a column of the constraint matrix has at most two non-zeros, then it leads to embedded generalized network structure and if these non-zeros are unit elements and of opposite signs, then it leads to embedded pure network structure. In this paper, we are concerned with algorithms for detecting embedded pure network structures within linear programs. The network extraction methods are presented in two groups. The first group covers deletion and addition based algorithms and the second group covers GUB based algorithms. We have extended the GUB based algorithm appearing in the second group by introducing Markowitz merit count approach for exploiting matrix non zeros. A set of well known test problems has been used to carry out computational experiments which show that our extensions to the GUB based algorithms give better results than the algorithms reported earlier.     

A filled function method applied to nonsmooth constrained global optimization

The filled function method is an effective approach to find a global minimizer. In this paper, based on a new definition of the filled function for nonsmooth constrained programming problems, a one-parameter filled function is constructed to improve the efficiency of numerical computation. Then a corresponding algorithm is presented. It is a global optimization method which modify the objective function as a filled function, and which find a better local minimizer gradually by optimizing the filled function constructed on the minimizer previously found. Illustrative examples are provided to demonstrate the efficiency and reliability of the proposed filled function method.     

Feasible generalized monotone line search SQP algorithm for nonlinear minimax problems with inequality constraints

In this paper, the nonlinear minimax problems with inequality constraints are discussed, and a sequential quadratic programming (SQP) algorithm with a generalized monotone line search is presented. At each iteration, a feasible direction of descent is obtained by solving a quadratic programming (QP). To avoid the Maratos effect, a high order correction direction is achieved by solving another QP. As a result, the proposed algorithm has global and superlinear convergence. Especially, the global convergence is obtained under a weak Mangasarian–Fromovitz constraint qualification (MFCQ) instead of the linearly independent constraint qualification (LICQ). At last, its numerical effectiveness is demonstrated with test examples.     

A globally convergent trust region algorithm for optimization with general constraints and simple bounds

1.IntroductionInthispaper,weconsiderthefollowingnonlinearprogr~ngproblemwherec(x)=(c,(x),c2(2),',We(.))',i(x)andci(x)(i=1,2,',m)arerealfunctions*ThisworkissupPOrtedbytheNationalNaturalScienceFOundationofChinaandtheManagement,DecisionandinformationSystemLab,theChineseAcademyofSciences.definedinD={xEReIISx5u}.Weassumethath相似文献   

A simplex social spider algorithm for solving integer programming and minimax problems

In this paper, we propose a new hybrid social spider algorithm with simplex Nelder-Mead method in order to solve integer programming and minimax problems. We call the proposed algorithm a Simplex Social Spider optimization (SSSO) algorithm. In the the proposed SSSO algorithm, we combine the social spider algorithm with its powerful capability of performing exploration, exploitation, and the Nelder-Mead method in order to refine the best obtained solution from the standard social spider algorithm. In order to investigate the general performance of the proposed SSSO algorithm, we test it on 7 integer programming problems and 10 minimax problems and compare against 10 algorithms for solving integer programming problems and 9 algorithms for solving minimax problems. The experiments results show the efficiency of the proposed algorithm and its ability to solve integer and minimax optimization problems in reasonable time.     

Smoothing Newton method for NCP with the identification of degenerate indices

We present a new smoothing Newton method for nonlinear complementarity problems (NCP(F)) by using an NCP function to reformulate the problem to its equivalent form. Compared with most current smoothing methods, our method contains an estimating technique based on the active-set strategy. This technique focuses on the identification of the degenerate set for a solution x^∗ of the NCP(F). The proposed method has the global convergence, each accumulation point is a solution of the problem. The introduction of the active-set strategy effectively reduces the scale of the problem. Under some regularity assumption, the degenerate set can be identified correctly near the solution and local superlinear convergence is obtained as well.     

极大熵方法与二次规划子问题的显式解

本文对混合约束极大极小问题的目标函数与约束分别用熵函数来逼近,讨论了逼近问题的二次规划子问题的搜索方向的显式形式,并给出了极大极小问题和多目标规划的二次规划予问题的显式解。将所得结果用于相应的算法中,可提高算法的有效性。     

A cutting plane method for solving minimax problems in the complex plane

It is shown how the combined discretization and cutting plane method for general convex semi-infinite programming problems recently presented in [40] can be effectively implemented for the solution of minimax problems in the complex plane. In contrast to other approaches, the minimax problem does not have to be linearized. The performance of the algorithm is demonstrated by a number of highly accurate numerical examples.     

Projected gradient methods for linearly constrained problems

The aim of this paper is to study the convergence properties of the gradient projection method and to apply these results to algorithms for linearly constrained problems. The main convergence result is obtained by defining a projected gradient, and proving that the gradient projection method forces the sequence of projected gradients to zero. A consequence of this result is that if the gradient projection method converges to a nondegenerate point of a linearly constrained problem, then the active and binding constraints are identified in a finite number of iterations. As an application of our theory, we develop quadratic programming algorithms that iteratively explore a subspace defined by the active constraints. These algorithms are able to drop and add many constraints from the active set, and can either compute an accurate minimizer by a direct method, or an approximate minimizer by an iterative method of the conjugate gradient type. Thus, these algorithms are attractive for large scale problems. We show that it is possible to develop a finite terminating quadratic programming algorithm without non-degeneracy assumptions. Work supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research of the U.S. Department of Energy under Contract W-31-109-Eng-38. Work supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research of the U.S. Department of Energy under Contract W-31-109-Eng-38.     

On diagonally preconditioning the truncated Newton method for super-scale linearly constrained nonlinear programming

We present an algorithm for super-scale linearly constrained nonlinear programming (LCNP) based on Newton's method. In large-scale programming solving the Newton equation at each iteration can be expensive and may not be justified when far from a local solution. For super-scale problems, the truncated Newton method (where an inaccurate solution is computed by using the conjugate-gradient method) is recommended; a diagonal BFGS preconditioning of the gradient is used, so that the number of iterations to solve the equation is reduced. The procedure for updating that preconditioning is described for LCNP when the set of active constraints or the partition of basic, superbasic and nonbasic (structural) variables have been changed.