共查询到20条相似文献,搜索用时 15 毫秒
1.
<正>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. 相似文献
2.
In this paper, a mathematical program with complementarity constraints (MPCC) is reformulated as a nonsmooth constrained mathematical program via the Fischer–Burmeister function. Smooth penalty functions are used to treat this nonsmooth constrained program. Under linear independence constraint qualification, and upper level strict complementarity condition, together with some other mild conditions, we prove that the limit point of stationary points satisfying second-order necessary conditions of unconstrained penalized problems is a strongly stationary point, hence a B-stationary point of the original MPCC. Furthermore, this limit point also satisfies a second-order necessary condition of the original MPCC. Numerical results are presented to test the performance of this method. 相似文献
3.
4.
We consider a mathematical program with complementarity constraints (MPCC). Our purpose is to develop methods that enable
us to compute a solution or a point with some kind of stationarity to MPCC by solving a finite number of nonlinear programs.
We apply an active set identification technique to a smoothing continuation method (Ref. 1) and propose a hybrid algorithm
for solving MPCC. We develop also two modifications: one makes use of an index addition strategy; the other adopts an index
subtraction strategy. We show that, under reasonable assumptions, all the proposed algorithms possess a finite termination
property. Further discussions and numerical experience are given as well
This work was supported in part by the Scientific Research Grant-in-Aid from the Ministry of Education, Science, Sports, and
Culture of Japan. The authors are grateful to Professor Paul Tseng for helpful suggestions on an earlier version of the paper. 相似文献
5.
利用互补问题的Lagrange函数,
将互补约束优化问题(MPCC)转化为含参数的约束优化问题.
给出Lagrange乘子的简单修正公式,
并给出求解互补约束优化问题的部分罚函数法. 无须假设二阶必要条件成立,
只要算法产生的迭代点列的极限点满足互补约束优化问题的线性独立约束规范(MPCC-LICQ),
且极限点是MPCC的可行点, 则算法收敛到原问题的M-稳定点. 另外,
在上水平严格互补(ULSC)成立的条件下, 算法收敛到原问题的B-稳定点. 相似文献
6.
Quasi-Newton methods in conjunction with the piecewise sequential quadratic programming are investigated for solving mathematical programming with equilibrium constraints, in particular for problems with complementarity constraints. Local convergence as well as superlinear convergence of these quasi-Newton methods can be established under suitable assumptions. In particular, several well-known quasi-Newton methods such as BFGS and DFP are proved to exhibit the local and superlinear convergence. 相似文献
7.
Global Optimization Method for Solving Mathematical Programs with Linear Complementarity Constraints
N. V. Thoai Y. Yamamoto A. Yoshise 《Journal of Optimization Theory and Applications》2005,124(2):467-490
We propose a method for finding a global optimal solution of programs with linear complementarity constraints. This problem arises for instance in bilevel programming. The main idea of the method is to generate a sequence of points either ending at a global optimal solution within a finite number of iterations or converging to a global optimal solution. The construction of such sequence is based on branch-and-bound techniques, which have been used successfully in global optimization. Results on a numerical test of the algorithm are reported.The main part of this article was written during the first authors stay as Visiting Professor at the Institute of Policy and Planning Sciences, University of Tsukuba, Tsukuba, Japan. The second and the third authors were supported by Grant-in-Aid for Scientific Research C(2) 13650061 of the Ministry of Education, Culture, Sports, Science, and\break Technology of Japan.The authors thank P. B. Hermanns, Department of Mathematics, University of Trier, for carrying out the numerical test reported in Section 5. The authors also thank the referees and the Associate Editor for comments and suggestions which helped improving the first version of this article. 相似文献
8.
This paper discusses a special class of mathematical programs with nonlinear complementarity constraints, its goal is to present a globally and superlinearly convergent algorithm for the discussed problems. We first reformulate the complementarity constraints as a standard nonlinear equality and inequality constraints by making use of a class of generalized smoothing complementarity functions, then present a new SQP algorithm for the discussed problems. At each iteration, with the help of a pivoting operation, a master search direction is yielded by solving a quadratic program, and a correction search direction for avoiding the Maratos effect is generated by an explicit formula. Under suitable assumptions, without the strict complementarity on the upper-level inequality constraints, the proposed algorithm converges globally to a B-stationary point of the problems, and its convergence rate is superlinear.AMS Subject Classification: 90C, 49MThis work was supported by the National Natural Science Foundation (10261001) and the Guangxi Province Science Foundation (0236001, 0249003) of China. 相似文献
9.
提出了—个求解非线性互补约束均衡问题的滤子SQP算法.借助Fischer-Burmeister函数把均衡约束转化为—个非光滑方程组,然后利用逐步逼近和分裂思想,给出—个与原问题近似的一般的约束优化.引入滤子思想,避免了罚函数法在选择罚因子上的困难.在适当的条件下证明了算法的全局收敛性,部分的数值结果表明算法是有效的. 相似文献
10.
本文提出了一类隐互补约束优化问题的磨光SQP算法.首先,我们给出了这类优化问题的最优性和约束规范性条件.然后,在适当假设条件下,我们证明了算法具有全局收敛性. 相似文献
11.
In this paper, we present a new relaxation method for mathematical programs with complementarity constraints. Based on the fact that a variational inequality problem defined on a simplex can be represented by a finite number of inequalities, we use an expansive simplex instead of the nonnegative orthant involved in the complementarity constraints. We then remove some inequalities and obtain a standard nonlinear program. We show that the linear independence constraint qualification or the Mangasarian–Fromovitz constraint qualification holds for the relaxed problem under some mild conditions. We consider also a limiting behavior of the relaxed problem. We prove that any accumulation point of stationary points of the relaxed problems is a weakly stationary point of the original problem and that, if the function involved in the complementarity constraints does not vanish at this point, it is C-stationary. We obtain also some sufficient conditions of B-stationarity for a feasible point of the original problem. In particular, some conditions described by the eigenvalues of the Hessian matrices of the Lagrangian functions of the relaxed problems are new and can be verified easily. Our limited numerical experience indicates that the proposed approach is promising. 相似文献
12.
Convergence of a Penalty Method for Mathematical Programming with Complementarity Constraints 总被引:5,自引:0,他引:5
We adapt the convergence analysis of the smoothing (Ref. 1) and regularization (Ref. 2) methods to a penalty framework for mathematical programs with complementarity constraints (MPCC); we show that the penalty framework shares convergence properties similar to those of these methods. Moreover, we give sufficient conditions for a sequence generated by the penalty framework to be attracted to a B-stationary point of the MPCC. 相似文献
13.
This paper discusses the convergence properties of a smoothing approach for solving the mathematical programs with second-order
cone complementarity constraints (SOCMPCCs). We first introduce B-stationary, C-stationary, M(orduckhovich)-stationary, S-stationary
point, SOCMPCC-linear independence constraint qualification (denoted by SOCMPCC-LICQ), second-order cone upper level strict
complementarity (denoted by SOC-ULSC) condition at a feasible point of a SOCMPCC problem. With the help of the projection
operator over a second-order cone, we construct a smooth optimization problem to approximate the SOCMPCC. We demonstrate that
any accumulation point of the sequence of stationary points to the sequence of smoothing problems, when smoothing parameters
decrease to zero, is a C-stationary point to the SOCMPCC under SOCMPCC-LICQ at the accumulation point. We also prove that
the accumulation point is an M-stationary point if, in addition, the sequence of stationary points satisfy weak second order
necessary conditions for the sequence of smoothing problems, and moreover it is a B-stationary point if, in addition, the
SOC-ULSC condition holds at the accumulation point. 相似文献
14.
A Robust SQP Method for Mathematical Programs with Linear Complementarity Constraints 总被引:1,自引:0,他引:1
The relationship between the mathematical program with linear complementarity constraints (MPLCC) and its inequality relaxation
is studied. Based on this relationship, a new sequential quadratic programming (SQP) method is presented for solving the MPLCC.
A certain SQP technique is introduced to deal with the possible infeasibility of quadratic programming subproblems. Global
convergence results are derived without assuming the linear independence constraint qualification for MPEC, the nondegeneracy
condition, and any feasibility condition of the quadratic programming subproblems. Preliminary numerical results are reported.
Research is partially supported by Singapore-MIT Alliance and School of Business, National University of Singapore. 相似文献
15.
In this paper, we apply a partial augmented Lagrangian method to mathematical programs with complementarity constraints (MPCC).
Specifically, only the complementarity constraints are incorporated into the objective function of the augmented Lagrangian
problem while the other constraints of the original MPCC are retained as constraints in the augmented Lagrangian problem.
We show that the limit point of a sequence of points that satisfy second-order necessary conditions of the partial augmented
Lagrangian problems is a strongly stationary point (hence a B-stationary point) of the original MPCC if the limit point is feasible to MPCC, the linear independence constraint qualification
for MPCC and the upper level strict complementarity condition hold at the limit point. Furthermore, this limit point also
satisfies a second-order necessary optimality condition of MPCC. Numerical experiments are done to test the computational
performances of several methods for MPCC proposed in the literature.
This research was partially supported by the Research Grants Council (BQ654) of Hong Kong and the Postdoctoral Fellowship
of The Hong Kong Polytechnic University. Dedicated to Alex Rubinov on the occassion of his 65th birthday. 相似文献
16.
提出了求解非线性互补问题的一个逐次逼近拟牛顿算法。在适当的假设下,证明了该算法的全局收敛性和局部超线性收敛性。 相似文献
17.
A Modified Relaxation Scheme for Mathematical Programs with Complementarity Constraints 总被引:3,自引:0,他引:3
In this paper, we consider a mathematical program with complementarity constraints. We present a modified relaxed program
for this problem, which involves less constraints than the relaxation scheme studied by Scholtes (2000). We show that the
linear independence constraint qualification holds for the new relaxed problem under some mild conditions. We also consider
a limiting behavior of the relaxed problem. We prove that any accumulation point of stationary points of the relaxed problems
is C-stationary to the original problem under the MPEC linear independence constraint qualification and, if the Hessian matrices
of the Lagrangian functions of the relaxed problems are uniformly bounded below on the corresponding tangent space, it is
M-stationary. We also obtain some sufficient conditions of B-stationarity for a feasible point of the original problem. In
particular, some conditions described by the eigenvalues of the Hessian matrices mentioned above are new and can be verified
easily.
This work was supported in part by the Scientific Research Grant-in-Aid from the Ministry of Education, Science, Sports, and
Culture of Japan. The authors are grateful to an anonymous referee for critical comments. 相似文献
18.
在本文中,我们提出了一种新的带扰动项的三项记忆梯度混合投影算法.在这种方法中应用了广义Armijo线搜索,并且仅在梯度函数在包含迭代序列的开凸集上一致连续的条件下证明了该算法的全局收敛性.最后给出了几个数值算例. 相似文献
19.
We propose a merit-function piecewise SQP algorithm for mathematical programs with equilibrium constraints (MPEC) formulated
as mathematical programs with complementarity constraints. Under mild conditions, the new algorithm is globally convergent
to a piecewise stationary point. Moreover, if the partial MPEC linear independence constraint qualification (LICQ) is satisfied
at the accumulation point, then the accumulation point is an S-stationary point.
The research of the first author was supported by the National Natural Science Foundation of China under grants 10571177 and
70271014. The research of the second author was partially supported by NSERC. 相似文献
20.
In this paper, we propose an inexact smoothing continuation method for mathematical problem with complementarity constraints. Under suitable conditions, we establish the convergence of the proposed method by showing that any accumulation point of the generated sequence is a B-stationary point of the problem. 相似文献