Superlinear Convergence of a Smooth Approximation Method for Mathematical Programs with Nonlinear Complementarity Constraints

<正>Mathematical programs with complementarity constraints(MPCC) is an important subclass of MPEC.It is a natural way to solve MPCC by constructing a suitable approximation of the primal problem.In this paper,we propose a new smoothing method for MPCC by using the aggregation technique.A new SQP algorithm for solving the MPCC problem is presented.At each iteration,the master direction is computed by solving a quadratic program,and the revised direction for avoiding the Maratos effect is generated by an explicit formula.As the non-degeneracy condition holds and the smoothing parameter tends to zero,the proposed SQP algorithm converges globally to an S-stationary point of the MPEC problem,its convergence rate is superlinear.Some preliminary numerical results are reported.     

NONDESCENT SUBGRADIENT METHOD FOR NONSMOOTH CONSTRAINED MINIMIZATION

A kind of nondecreasing subgradient algorithm with appropriate stopping rule has been proposed for nonsmooth constrained minimization problem. The dual theory is invoked in dealing with the stopping rule and general global minimiizing algorithm is employed as a subroutine of the algorithm. The method is expected to tackle a large class of nonsmooth constrained minimization problem.     

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.     

求解两块可分离凸极小化问题的惯性交替方向乘子法

The alternating direction method of multipliers(ADMM)is a widely used method for solving many convex minimization models arising in signal and image processing.In this paper,we propose an inertial ADMM for solving a two-block separable convex minimization problem with linear equality constraints.This algorithm is obtained by making use of the inertial Douglas-Rachford splitting algorithm to the corresponding dual of the primal problem.We study the convergence analysis of the proposed algorithm in infinite-dimensional Hilbert spaces.Furthermore,we apply the proposed algorithm on the robust principal component analysis problem and also compare it with other state-of-the-art algorithms.Numerical results demonstrate the advantage of the proposed algorithm.     

求解广义线性互补问题的光滑牛顿法(英文)

The extended linear complementarity problem(denoted by ELCP) can be reformulated as the solution of a nonsmooth system of equations. By the symmetrically perturbed CHKS smoothing function, the ELCP is approximated by a family of parameterized smooth equations. A one-step smoothing Newton method is designed for solving the ELCP. The proposed algorithm is proved to be globally convergent under suitable assumptions.     

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.     

A Level Set Representation Method for N-Dimensional Convex Shape and Applications

In this work,we present a new method for convex shape representation,which is regardless of the dimension of the concerned objects,using level-set approaches.To the best of our knowledge,the proposed prior is the first one which can work for high dimensional objects.Convexity prior is very useful for object completion in computer vision.It is a very challenging task to represent high dimensional convex objects.In this paper,we first prove that the convexity of the considered object is equivalent to the convexity of the associated signed distance function.Then,the second order condition of convex functions is used to characterize the shape convexity equivalently.We apply this new method to two applications:object segmentation with convexity prior and convex hull problem(especially with outliers).For both applications,the involved problems can be written as a general optimization problem with three constraints.An algorithm based on the alternating direction method of multipliers is presented for the optimization problem.Numerical experiments are conducted to verify the effectiveness of the proposed representation method and algorithm.     

A projected gradient method with nonmonotonic backtracking technique for solving convex constrained monotone variational inequality problem

Based on a differentiable merit function proposed by Taji, et al in “Mathematical Programming, 1993, 58： 369-383”, a projected gradient trust region method for the monotone variational inequality problem with convex constraints is presented. Theoretical analysis is given which proves that the proposed algorithm is globally convergent and has a local quadratic convergence rate under some reasonable conditions. The results of numerical experiments are reported to show the effectiveness of the proposed algorithm.     

A SUPERLINEARLY CONVERGENT SPLITTING FEASIBLE SEQUENTIAL QUADRATIC OPTIMIZATION METHOD FOR TWO-BLOCK LARGE-SCALE SMOOTH OPTIMIZATION

This paper discusses the two-block large-scale nonconvex optimization problem with general linear constraints.Based on the ideas of splitting and sequential quadratic optimization(SQO),a new feasible descent method for the discussed problem is proposed.First,we consider the problem of quadratic optimal(QO) approximation associated with the current feasible iteration point,and we split the QO into two small-scale QOs which can be solved in parallel.Second,a feasible descent direction for the prob...     

MONOTONIZATION IN GLOBAL OPTIMIZATION

A general monotonization method is proposed for converting a constrained programming problem with non-monotone objective function and monotone constraint functions into a monotone programming problem. An equivalent monotone programming problem with only inequality constraints is obtained via this monotonization method. Then the existing convexification and concavefication methods can be used to convert the monotone programming problem into an equivalent better-structured optimization problem.     

Optimality conditions for nonsmooth mathematical programs with equilibrium constraints,using convexificators

In this paper, we deal with constraint qualifications, stationary concepts and optimality conditions for a nonsmooth mathematical program with equilibrium constraints (MPEC). The main tool in our study is the notion of convexificator. Using this notion, standard and MPEC Abadie and several other constraint qualifications are proposed and a comparison between them is presented. We also define nonsmooth stationary conditions based on the convexificators. In particular, we show that GS-stationary is the first-order optimality condition under generalized standard Abadie constraint qualification. Finally, sufficient conditions for global or local optimality are derived under some MPEC generalized convexity assumptions.     

求解含平衡约束数学规划的熵函数法

提出求解含平衡约束数学规划问题(简记为MPEC问题)的熵函数法，在将原问题等价改写为单层非光滑优化问题的基础上，通过熵函数逼近，给出求解MPEC问题的序列光滑优化方法，证明了熵函数逼近问题解的存在性和算法的全局收敛性，数值算例表明了算法的有效性。     

Optimality Conditions for Nonsmooth Equilibrium Problems via Hadamard Directional Derivative

In this paper, we consider a mathematical program with equilibrium constraints (MPEC) formulated as a mathematical program with complementarity constraints. We obtain necessary conditions of Fritz John (FJ) and Karush-Kuhn-Tucker (KKT) types for a nonsmooth (MPEC) problem in terms of the lower Hadamard directional derivative. In particular sufficient conditions for MPECs are given where the involved functions have pseudoconvex sublevel sets. The functions with pseudoconvex sublevel sets is a class of generalized convex functions that include quasiconvex functions.     

Complementarity Active-Set Algorithm for Mathematical Programming Problems with Equilibrium Constraints

In this paper, an algorithm for solving a mathematical programming problem with complementarity (or equilibrium) constraints (MPEC) is introduced, which uses the active-set methodology while maintaining the complementarity restrictions throughout the procedure. Finite convergence of the algorithm to a strongly stationary point of the MPEC is established under reasonable hypotheses. The algorithm can be easily implemented by adopting any active-set code for nonlinear programming. Computational experience is included to highlight the efficacy of the proposed method in practice.     

Necessary and sufficient conditions for nonsmooth mathematical programs with equilibrium constraints

In this paper we consider a mathematical program with equilibrium constraints (MPEC) formulated as a mathematical program with complementarity constraints. Then, we derive a necessary optimality result for nonsmooth MPEC on any Asplund space. Also, under generalized convexity assumptions, we establish sufficient optimality conditions for this program in Banach spaces.     

支持向量机中一种参数优化选取方法

本文给出一种支持向量机中的参数优化选取方法. 它是通过遗传算法和确定性算法相结合解平衡约束优化问题,求出二分类支持向量机(SVM)中的正则参数C,本文将C作为优化问题中的变量来处理.遗传算法用来求解以C为变量的优化问题, 而确定性算法对每一个C值求解约束.数值计算的结果表明,用文中所述的方法求得的C值能明显提高支持向量机的泛化性能.     

非线性互补约束规划问题的一个新的QP-free算法

本文研究了非线性互补约束均衡问题.利用互补函数以及光滑近似法,把非线性互补约束均衡问题转化为一个光滑非线性规划问题,得到了超线性收敛速度,数值实验结果表明本文提出的算法是可行的.     

互补约束均衡问题一个新的磨光技术

研究了一类带非线性互补约束的均衡问题．借助于逐步逼近思想,构造了一个在求解意义上与原问题等价的磨光非线性规划．从而保证一些经典的标准优化算法可以应用到该类优化问题上．最后提出了两个算法模型并分析了其全局收敛性．     

Partial Exact Penalty for Mathematical Programs with Equilibrium Constraints

It is well known that mathematical programs with equilibrium constraints (MPEC) violate the standard constraint qualifications such as Mangasarian–Fromovitz constraint qualification (MFCQ) and hence the usual Karush–Kuhn–Tucker conditions cannot be used as stationary conditions unless relatively strong assumptions are satisfied. This observation has led to a number of weaker stationary conditions, with Mordukhovich stationary (M-stationary) condition being the strongest among the weaker conditions. In nonlinear programming, it is known that MFCQ leads to an exact penalization. In this paper we show that MPEC GMFCQ, an MPEC variant of MFCQ, leads to a partial exact penalty where all the constraints except a simple linear complementarity constraint are moved to the objective function. The partial exact penalty function, however, is nonsmooth. By smoothing the partial exact penalty function, we design an algorithm which is shown to be globally convergent to an M-stationary point under an extended version of the MPEC GMFCQ.     

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.