A quadratically approximate framework for constrained optimization,global and local convergence

This paper presents a quadratically approximate algorithm framework （QAAF） for solving general constrained optimization problems, which solves, at each iteration, a subproblem with quadratic objective function and quadratic equality together with inequality constraints. The global convergence of the algorithm framework is presented under the Mangasarian-Fromovitz constraint qualification （MFCQ）, and the conditions for superlinear and quadratic convergence of the algorithm framework are given under the MFCQ, the constant rank constraint qualification （CRCQ） as well as the strong second-order sufficiency conditions （SSOSC）. As an incidental result, the definition of an approximate KKT point is brought forward, and the global convergence of a sequence of approximate KKT points is analysed.     

AN INTERIOR TRUST REGION ALGORITHM FOR NONLINEAR MINIMIZATION WITH LINEAR CONSTRAINTS

AbstractAn interior trust-region-based algorithm for linearly constrained minimization problems is proposed and analyzed. This algorithm is similar to trust region algorithms for unconstrained minimization: a trust region subproblem on a subspace is solved in each iteration. We establish that the proposed algorithm has convergence properties analogous to those of the trust region algorithms for unconstrained minimization. Namely, every limit point of the generated sequence satisfies the Krush-Kuhn-Tucker (KKT) conditions and at least one limit point satisfies second order necessary optimality conditions. In addition, if one limit point is a strong local minimizer and the Hessian is Lipschitz continuous in a neighborhood of that point, then the generated sequence converges globally to that point in the rate of at least 2-step quadratic. We are mainly concerned with the theoretical properties of the algorithm in this paper. Implementation issues and adaptation to large-scale problems will be addressed in a     

基于增广Lagrange函数的RQP方法

Recursive quadratic programming is a family of techniques developd by Bartholomew-Biggs and other authors for solving nonlinear programming problems.This paperdescribes a new method for constrained optimization which obtains its search di-rections from a quadratic programming subproblem based on the well-known aug-mented Lagrangian function.It avoids the penalty parameter to tend to infinity.We employ the Fletcher‘s exact penalty function as a merit function and the use of an approximate directional derivative of the function that avoids the need toevaluate the second order derivatives of the problem functions.We prove that thealgorithm possesses global and superlinear convergence properties.At the sametime, numerical results are reported.     

On convergence analysis of a derivative-free trust region algorithm for constrained optimization with separable structure

In this paper,we propose a derivative-free trust region algorithm for constrained minimization problems with separable structure,where derivatives of the objective function are not available and cannot be directly approximated.At each iteration,we construct a quadratic interpolation model of the objective function around the current iterate.The new iterates are generated by minimizing the augmented Lagrangian function of this model over the trust region.The filter technique is used to ensure the feasibility and optimality of the iterative sequence.Global convergence of the proposed algorithm is proved under some suitable assumptions.     

SOLVING A CLASS OF INVERSE QP PROBLEMS BY A SMOOTHING NEWTON METHOD

We consider an inverse quadratic programming （IQP） problem in which the parameters in the objective function of a given quadratic programming （QP） problem are adjusted as little as possible so that a known feasible solution becomes the optimal one. This problem can be formulated as a minimization problem with a positive semidefinite cone constraint and its dual （denoted IQD（A, b）） is a semismoothly differentiable （SC^1） convex programming problem with fewer variables than the original one. In this paper a smoothing Newton method is used for getting a Karush-Kuhn-Tucker point of IQD（A, b）. The proposed method needs to solve only one linear system per iteration and achieves quadratic convergence. Numerical experiments are reported to show that the smoothing Newton method is effective for solving this class of inverse quadratic programming problems.     

A NONMONOTONE SECOND-ORDER STEPLENGTH METHOD FOR UNCONSTRAINED MINIMIZATION

In this paper, a nonmonotone method based on McCormick＇s second-order Armijo＇s step-size rule [7] for unconstrained optimization problems is proposed. Every limit point of the sequence generated by using this procedure is proved to be a stationary point with the second-order optimality conditions. Numerical tests on a set of standard test problems are presented and show that the new algorithm is efficient and robust.     

AN EFFECTIVE CONTINUOUS ALGORITHM FOR APPROXIMATE SOLUTIONS OF LARGE SCALE MAX-CUT PROBLEMS

An effective continuous algorithm is proposed to find approximate solutions of NP-hardmax-cut problems.The algorithm relaxes the max-cut problem into a continuous nonlinearprogramming problem by replacing n discrete constraints in the original problem with onesingle continuous constraint.A feasible direction method is designed to solve the resultingnonlinear programming problem.The method employs only the gradient evaluations ofthe objective function,and no any matrix calculations and no line searches are required.This greatly reduces the calculation cost of the method,and is suitable for the solutionof large size max-cut problems.The convergence properties of the proposed method toKKT points of the nonlinear programming are analyzed.If the solution obtained by theproposed method is a global solution of the nonlinear programming problem,the solutionwill provide an upper bound on the max-cut value.Then an approximate solution to themax-cut problem is generated from the solution of the nonlinear programming and providesa lower bound on the max-cut value.Numerical experiments and comparisons on somemax-cut test problems(small and large size)show that the proposed algorithm is efficientto get the exact solutions for all small test problems and well satisfied solutions for mostof the large size test problems with less calculation costs.     

Analysis on a superlinearly convergent augmented Lagrangian method

The augmented Lagrangian method is a classical method for solving constrained optimization.Recently,the augmented Lagrangian method attracts much attention due to its applications to sparse optimization in compressive sensing and low rank matrix optimization problems.However,most Lagrangian methods use first order information to update the Lagrange multipliers,which lead to only linear convergence.In this paper,we study an update technique based on second order information and prove that superlinear convergence can be obtained.Theoretical properties of the update formula are given and some implementation issues regarding the new update are also discussed.     

Superlinearly convergent affine scaling interior trust-region method for linear constrained LC<Superscript>1</Superscript> minimization

We extend the classical affine scaling interior trust region algorithm for the linear constrained smooth minimization problem to the nonsmooth case where the gradient of objective function is only locally Lipschitzian. We propose and analyze a new affine scaling trust-region method in association with nonmonotonic interior backtracking line search technique for solving the linear constrained LC1 optimization where the second-order derivative of the objective function is explicitly required to be locally Lipschitzian. The general trust region subproblem in the proposed algorithm is defined by minimizing an augmented affine scaling quadratic model which requires both first and second order information of the objective function subject only to an affine scaling ellipsoidal constraint in a null subspace of the augmented equality constraints. The global convergence and fast local convergence rate of the proposed algorithm are established under some reasonable conditions where twice smoothness of the objective function is not required. Applications of the algorithm to some nonsmooth optimization problems are discussed.     

CONVERGENCE ANALYSIS ON ITERATIVE METHODS FOR SEMIDEFINITE SYSTEMS

The convergence analysis on the general iterative methods for the symmetric and positive semidefinite problems is presented in this paper. First, formulated are refined necessary and sumcient conditions for the energy norm convergence for iterative methods. Some illustrative examples for the conditions are also provided. The sharp convergence rate identity for the Gauss-Seidel method for the semidefinite system is obtained relying only on the pure matrix manipulations which guides us to obtain the convergence rate identity for the general successive subspace correction methods. The convergence rate identity for the successive subspace correction methods is obtained under the new conditions that the local correction schemes possess the local energy norm convergence. A convergence rate estimate is then derived in terms of the exact subspace solvers and the parameters that appear in the conditions. The uniform convergence of multigrid method for a model problem is proved by the convergence rate identity. The work can be regradled as unified and simplified analysis on the convergence of iteration methods for semidefinite problems [8, 9].     

采用不定Dogleg路径的非单调自适应信赖域算法解无约束极小化(英文)

In this paper, we combine the nonmonotone and adaptive techniques with trust region method for unconstrained minimization problems. We set a new ratio of the actual descent and predicted descent. Then, instead of the monotone sequence, the nonmonotone sequence of function values are employed. With the adaptive technique, the radius of trust region △k can be adjusted automatically to improve the efficiency of trust region methods. By means of the Bunch-Parlett factorization, we construct a method with indefinite dogleg path for solving the trust region subproblem which can handle the indefinite approximate Hessian Bk. The convergence properties of the algorithm are established. Finally, detailed numerical results are reported to show that our algorithm is efficient.     

Unconstrained optimization reformulations of equilibrium problems

We generalize the D-gap function developed in the literature for variational inequalities to a general equilibrium problem （EP）. Through the D-gap function, the equilibrium problem is cast as an unconstrained minimization problem. We give conditions under which any stationary point of the D-gap function is a solution of EP and conditions under which it provides a global error bound for EP. Finally, these results are applied to box-constrained EP and then weaker conditions are established to obtain the desired results for box-constrained EP.     

ROBUST ANALYSIS AND GLOBAL MINIMIZATION OF A CLASS OF DISCONTINUOUS FUNCTIONS (Ⅱ)

In this Paper we continue to investigate global minimization problems. An integral approach is applied to treat a global minimization problem of a discontinuous function. With the help ofthe theory of measure (Q-measure) and integration, optimality conditions of a robust function over arobust set are derived. Algorithms and their implementations for finding global minima are proposed.Numerical tests and applications show that the algorithms are effective.     

Fractal interpolation: a sequential approach

Fractal interpolation is a modern technique to fit and analyze scientific data. We develop a new class of fractal interpolation functions which converge to a data generating(original) function for any choice of the scaling factors. Consequently, our method offers an alternative to the existing fractal interpolation functions(FIFs). We construct a sequence of α-FIFs using a suitable sequence of iterated function systems(IFSs). Without imposing any condition on the scaling vector, we establish constrained interpolation by using fractal functions. In particular,the constrained interpolation discussed herein includes a method to obtain fractal functions that preserve positivity inherent in the given data. The existence of Cr-α-FIFs is investigated. We identify suitable conditions on the associated scaling factors so that α-FIFs preserve r-convexity in addition to the C~r-smoothness of original function.     

APPROXIMATE CONTROLLABILITY OF FRACTIONAL IMPULSIVE NEUTRAL STOCHASTIC INTEGRO-DIFFERENTIAL EQUATIONS WITH NONLOCAL CONDITIONS AND INFINITE DELAY

This paper is concerned with the approximate controllability of nonlinear fractional impulsive neutral stochastic integro-differential equations with nonlocal conditions and infinite delay in Hilbert spaces under the assumptions that the corresponding linear system is approximately controllable. By the Krasnoselskii-Schaefer-type fixed point theorem and stochastic analysis theory, some sufficient conditions are given for the approximate controllability of the system. At the end, an example is given to illustrate the application of our result.     

SEQUENTIAL QUADRATIC PROGRAMMING METHODS FOR OPTIMAL CONTROL PROBLEMS WITH STATE CONSTRAINTS

A Kind of direct methods is presented for the solution of optimal control problems with state constraints.These methods are sequential quadratic programming methods.At every iteration a quadratic programming which is obtained by quadratic approximation to Lagrangian function and Linear approximations to constraints is solved to get a search direction for a merit function.The merit function is formulated by augmenting the Lagrangian funetion with a penalty term.A line search is carried out along the search direction to determine a step length such that the merit function is decreased.The methods presented in this paper include continuous sequential quadratic programming methods and discreate sequential quadrade programming methods.     

Robust estimation in inverse problems via quantile coupling

In this article we consider a sequence of hierarchical space model of inverse problems.The underlying function is estimated from indirect observations over a variety of error distributions including those that are heavy-tailed and may not even possess variances or means.The main contribution of this paper is that we establish some oracle inequalities for the inverse problems by using quantile coupling technique that gives a tight bound for the quantile coupling between an arbitrary sample p-quantile and a normal variable,and an automatic selection principle for the nonrandom filters.This leads to the data-driven choice of weights.We also give an algorithm for its implementation.The quantile coupling inequality developed in this paper is of independent interest,because it includes the median coupling inequality in literature as a special case.     

具有V-不变凸的多目标规划的另一种方法

In this paper, optimality conditions for multiobjective programming problems having V-invex objective and constraint functions are considered. An equivalent multiobjective programming problem is constructed by a modification of the objective function.Furthermore, a (α, η)-Lagrange function is introduced for a constructed multiobjective programming problem, and a new type of saddle point is introduced. Some results for the new type of saddle point are given.     

本刊英文版Vol．23(2007)，No．12论文摘要(英文)

<正>Classification of Flat Lagrangian Surfaces in Complex Lorentzian Plane Bang-Yen CHEN Johan FASTENAKELS One of the most fundamental problems in the study of Lagrangian submanifolds from Riemannian geometric point of view is to classify Lagrangian immersions of real space forms into complex space forms.The main purpose of this paper is thus to classify fiat Lagrangian surfaces in the Lorentzian complex plane C_1~2.Our main result states that there are thirty-eight families of fiat Lagrangian surfaces in C_1~2.Conversely,every fiat Lagrangian surface in C_1~2 is locally congruent to one of the thirty-eight families.     

A dual-relax penalty function approach for solving nonlinear bilevel programming with linear lower level problem

The penalty function method, presented many years ago, is an important numerical method for the mathematical programming problems. In this article, we propose a dual-relax penalty function approach, which is significantly different from penalty function approach existing for solving the bilevel programming, to solve the nonlinear bilevel programming with linear lower level problem. Our algorithm will redound to the error analysis for computing an approximate solution to the bilevel programming. The error estimate is obtained among the optimal objective function value of the dual-relax penalty problem and of the original bilevel programming problem. An example is illustrated to show the feasibility of the proposed approach.