Constraint qualifications for optimality conditions and total Lagrange dualities in convex infinite programming

For an inequality system defined by an infinite family of proper convex functions (not necessarily lower semicontinuous), we introduce some new notions of constraint qualifications. Under the new constraint qualifications, we provide necessary and/or sufficient conditions for the KKT rules to hold. Similarly, we provide characterizations for constrained minimization problems to have total Lagrangian dualities. Several known results in the conic programming problem are extended and improved.     

A General Approach to Convergence Properties of Some Methods for Nonsmooth Convex Optimization

Based on the notion of the ε -subgradient, we present a unified technique to establish convergence properties of several methods for nonsmooth convex minimization problems. Starting from the technical results, we obtain the global convergence of: (i) the variable metric proximal methods presented by Bonnans, Gilbert, Lemaréchal, and Sagastizábal, (ii) some algorithms proposed by Correa and Lemaréchal, and (iii) the proximal point algorithm given by Rockafellar. In particular, we prove that the Rockafellar—Todd phenomenon does not occur for each of the above mentioned methods. Moreover, we explore the convergence rate of {||x _k || } and {f(x _k ) } when {x _k } is unbounded and {f(x _k ) } is bounded for the non\-smooth minimization methods (i), (ii), and (iii). Accepted 15 October 1996     

非线性规划的QP-free方法

该文提出一种QP-free可行域方法用来解满足光滑不等式约束的最优化问题.此方法把QP-free方法和3-1线性互补函数相结合一个等价于原约束问题的一阶KKT条件的方程组,并在此基础上给出解这个方程组的迭代算法. 这个方法的每一步迭代都可以看作是对求KKT条件解的牛顿或拟牛顿迭代的扰动,且在该方法中每一步的迭代均具有可行性. 该方法是可实行的且具有全局性, 且不需要严格互补条件、聚点的孤立性和积极约束函数梯度的线性独立等假设. 在与文献[2]中相同的适当条件下,此方法还具有超线性收敛性. 数值检验结果表示,该文提出的QP-free可行域方法是切实有效的方法.     

新的滤子方法

本文定义了一种新的滤子方法,并提出了求解光滑不等式约束最优化问题的滤子QP-free非可行域方法.通过乘子和分片线性非线性互补函数,构造一个等价于原约束问题一阶KKT条件的非光滑方程组.在此基础上,通过牛顿-拟牛顿迭代得到满足KKT最优条件的解,在迭代中采用了滤子线搜索方法,证明了该算法是可实现,并具有全局收敛性.另外,在较弱条件下可以证明该方法具有超线性收敛性.     

A special complementarity function revisited

ABSTRACT

Recently, a local framework of Newton-type methods for constrained systems of equations has been developed. Applied to the solution of Karush–Kuhn–Tucker (KKT) systems, the framework enables local quadratic convergence under conditions that allow nonisolated and degenerate KKT points. This result is based on a reformulation of the KKT conditions as a constrained piecewise smooth system of equations. It is an open question whether a comparable result can be achieved for other (not piecewise smooth) reformulations. It will be shown that this is possible if the KKT system is reformulated by means of the Fischer–Burmeister complementarity function under conditions that allow degenerate KKT points and nonisolated Lagrange multipliers. To this end, novel constrained Levenberg–Marquardt subproblems are introduced. They allow significantly longer steps for updating the multipliers. Based on this, a convergence rate of at least 1.5 is shown.     

The exact penalty principle

The exact penalty approach aims at replacing a constrained optimization problem by an equivalent unconstrained optimization problem. Most results in the literature of exact penalization are mainly concerned with finding conditions under which a solution of the constrained optimization problem is a solution of an unconstrained penalized optimization problem, and the reverse property is rarely studied. In this paper, we study the reverse property. We give the conditions under which the original constrained (single and/or multiobjective) optimization problem and the unconstrained exact penalized problem are exactly equivalent. The main conditions to ensure the exact penalty principle for optimization problems include the global and local error bound conditions. By using variational analysis, these conditions may be characterized by using generalized differentiation.     

A cut-peak function method for global optimization

A new method is proposed for solving box constrained global optimization problems. The basic idea of the method is described as follows: Constructing a so-called cut-peak function and a choice function for each present minimizer, the original problem of finding a global solution is converted into an auxiliary minimization problem of finding local minimizers of the choice function, whose objective function values are smaller than the previous ones. For a local minimum solution of auxiliary problems this procedure is repeated until no new minimizer with a smaller objective function value could be found for the last minimizer. Construction of auxiliary problems and choice of parameters are relatively simple, so the algorithm is relatively easy to implement, and the results of the numerical tests are satisfactory compared to other methods.     

A Variant of the Topkis—Veinott Method for Solving Inequality Constrained Optimization Problems

In this paper we give a variant of the Topkis—Veinott method for solving inequality constrained optimization problems. This method uses a linearly constrained positive semidefinite quadratic problem to generate a feasible descent direction at each iteration. Under mild assumptions, the algorithm is shown to be globally convergent in the sense that every accumulation point of the sequence generated by the algorithm is a Fritz—John point of the problem. We introduce a Fritz—John (FJ) function, an FJ1 strong second-order sufficiency condition (FJ1-SSOSC), and an FJ2 strong second-order sufficiency condition (FJ2-SSOSC), and then show, without any constraint qualification (CQ), that (i) if an FJ point z satisfies the FJ1-SSOSC, then there exists a neighborhood N(z) of z such that, for any FJ point y ∈ N(z) \ {z } , f ₀ (y) ≠ f ₀ (z) , where f ₀ is the objective function of the problem; (ii) if an FJ point z satisfies the FJ2-SSOSC, then z is a strict local minimum of the problem. The result (i) implies that the entire iteration point sequence generated by the method converges to an FJ point. We also show that if the parameters are chosen large enough, a unit step length can be accepted by the proposed algorithm. Accepted 21 September 1998     

Generalization of Primal—Dual Interior-Point Methods to Convex Optimization Problems in Conic Form

We generalize primal—dual interior-point methods for linear programming (LP) problems to the convex optimization problems in conic form. Previously, the most comprehensive theory of symmetric primal—dual interior-point algorithms was given by Nesterov and Todd for feasible regions expressed as the intersection of a symmetric cone with an affine subspace. In our setting, we allow an arbitrary convex cone in place of the symmetric cone. Even though some of the impressive properties attained by Nesterov—Todd algorithms are impossible in this general setting of convex optimization problems, we show that essentially all primal—dual interior-point algorithms for LP can be extended easily to the general setting. We provide three frameworks for primal—dual algorithms, each framework corresponding to a different level of sophistication in the algorithms. As the level of sophistication increases, we demand better formulations of the feasible solution sets. Our algorithms, in return, attain provably better theoretical properties. We also make a very strong connection to quasi-Newton methods by expressing the square of the symmetric primal—dual linear transformation (the so-called scaling) as a quasi-Newton update in the case of the least sophisticated framework. August 25, 1999. Final version received: March 7, 2001.     

分片线性NCP函数滤子QP-free算法

本文定义了分片线性NCP函数,并对非线性约束优化问题,提出了带有这分片NCP函数的QP-free非可行域算法.利用优化问题的一阶KKT条件,乘子和NCP函数,得到对应的非光滑方程组.本文给出解这非光滑方程组算法,它包含原始-对偶变量,在局部意义下,可看成关扰动牛顿-拟牛顿迭代算法.在线性搜索时,这算法采用滤子方法.本文给出的算法是可实现的并具有全局收敛性,在适当假设下算法具有超线性收敛性.     

无罚函数和滤子的QP-free非可行域方法

提出了求解光滑不等式约束最优化问题的无罚函数和无滤子QP-free非可行域方法. 通过乘子和非线性互补函数, 构造一个等价于原约束问题一阶KKT条件的非光滑方程组. 在此基础上, 通过牛顿-拟牛顿迭代得到满足KKT最优性条件的解, 在迭代中采用了无罚函数和无滤子线搜索方法, 并证明该算法是可实现,具有全局收敛性. 另外, 在较弱条件下可以证明该方法具有超线性收敛性.     

3-分片线性NCP函数的滤子QP-free算法

本文定义一个3-分片线性的NCP函数,并对非线性约束优化问题,提出了带有这分片NCP函数的QP-free非可行域算法.根据优化问题的一阶KKT条件,利用乘子和NCP函数,得到非光滑方程,本文给出一个非光滑方程的迭代算法.这算法包含原始-对偶变量,在局部意义下,可看成关于一阶KKT最优条件的的扰动拟牛顿迭代算法.在线性搜索时,这算法采用滤子方法.本文给出的算法是可实现的并具有全局收敛性,且在适当假设下具有超线性收敛性.     

Reformulation in mathematical programming: An application to quantum chemistry

This paper concerns the application of reformulation techniques in mathematical programming to a specific problem arising in quantum chemistry, namely the solution of Hartree-Fock systems of equations, which describe atomic and molecular electronic wave functions based on the minimization of a functional of the energy. Their traditional solution method does not provide a guarantee of global optimality and its output depends on a provided initial starting point. We formulate this problem as a multi-extremal nonconvex polynomial programming problem, and solve it with a spatial Branch-and-Bound algorithm for global optimization. The lower bounds at each node are provided by reformulating the problem in such a way that its convex relaxation is tight. The validity of the proposed approach was established by successfully computing the ground-state of the helium and beryllium atoms.     

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.     

Unconstrained minimization approaches to nonlinear complementarity problems

The nonlinear complementarity problem can be reformulated as unconstrained minimization problems by introducing merit functions. Under some assumptions, the solution set of the nonlinear complementarity problem coincides with the set of local minima of the corresponding minimization problem. These results were presented by Mangasarian and Solodov, Yamashita and Fukushima, and Geiger and Kanzow. In this note, we generalize some results of Mangasarian and Solodov, Yamashita and Fukushima, and Geiger and Kanzow to the case where the considered function is only directionally differentiable. Some results are strengthened in the smooth case. For example, it is shown that the strong monotonicity condition can be replaced by the P-uniform property for ensuring a stationary point of the reformulated unconstrained minimization problems to be a solution of the nonlinear complementarity problem. We also present a descent algorithm for solving the nonlinear complementarity problem in the smooth case. Any accumulation point generated by this algorithm is proved to be a solution of the nonlinear complementarity under the monotonicity condition.     

Neural networks for solving second-order cone constrained variational inequality problem

In this paper, we consider using the neural networks to efficiently solve the second-order cone constrained variational inequality (SOCCVI) problem. More specifically, two kinds of neural networks are proposed to deal with the Karush-Kuhn-Tucker (KKT) conditions of the SOCCVI problem. The first neural network uses the Fischer-Burmeister (FB) function to achieve an unconstrained minimization which is a merit function of the Karush-Kuhn-Tucker equation. We show that the merit function is a Lyapunov function and this neural network is asymptotically stable. The second neural network is introduced for solving a projection formulation whose solutions coincide with the KKT triples of SOCCVI problem. Its Lyapunov stability and global convergence are proved under some conditions. Simulations are provided to show effectiveness of the proposed neural networks.     

A Spectral Conjugate Gradient Method for Unconstrained Optimization

A family of scaled conjugate gradient algorithms for large-scale unconstrained minimization is defined. The Perry, the Polak—Ribière and the Fletcher—Reeves formulae are compared using a spectral scaling derived from Raydan's spectral gradient optimization method. The best combination of formula, scaling and initial choice of step-length is compared against well known algorithms using a classical set of problems. An additional comparison involving an ill-conditioned estimation problem in Optics is presented. Accepted 22 August 2000. Online publication 26 February 2001.     

Convergence Properties of Projection and Contraction Methods for Variational Inequality Problems

In this paper we develop the convergence theory of a general class of projection and contraction algorithms (PC method), where an extended stepsize rule is used, for solving variational inequality (VI) problems. It is shown that, by defining a scaled projection residue, the PC method forces the sequence of the residues to zero. It is also shown that, by defining a projected function, the PC method forces the sequence of projected functions to zero. A consequence of this result is that if the PC method converges to a nondegenerate solution of the VI problem, then after a finite number of iterations, the optimal face is identified. Finally, we study local convergence behavior of the extragradient algorithm for solving the KKT system of the inequality constrained VI problem. \keywords{Variational inequality, Projection and contraction method, Predictor-corrector stepsize, Convergence property.} \amsclass{90C30, 90C33, 65K05.} Accepted 5 September 2000. Online publication 16 January 2001.     

解非线性约束优化问题的依赖域算法

本文对一般非线性约束优化问题提出了一个信赖域算法,导出了等价的KKT条件.在试探步满足适当条件下,证明了算法的全局收敛性,并进行了数值试验.