解约束非凸规划问题的同伦方法的收敛性定理

本文在利用组合内点同伦方法求解约束非凸规划问题时,得到了一些新的收敛性定理.证明了同伦映射为正则映射的条件下,选取合适的同伦方程,用此同伦方法得到的K-K-T点一定是问题局部最优解.     

同伦方法求解无界域上非凸规划问题的收敛性定理

利用同伦方法求解非凸规划时,一般只能得到问题的K-K-T点.本文得到无界域上同伦方法求解非凸规划的几个收敛性定理,证明在一定条件下,通过构造合适的同伦方程,同伦算法收敛到问题的局部最优解.     

解一类函数极值问题的动约束同伦算法

本文对可行域为不等式约束构成的带洞非凸域上光滑优化问题,通过添加动约束函数的形式,将带洞非凸可行域分割为两个非凸不带洞可行域,讨论了带洞非凸域上优化问题与不带洞两个非凸优化问题KKT点的关系;在非凸不带洞的可行域上,给出了初始点方便选取的动约束同伦算法,证明了同伦路径的存在性,有界性和收敛性,通过数值算例表明该算法是可行的,有效的.     

无界区域上非凸规划的同伦方法

In the past few years, much and much attention has been paid to the method for solving non-convex programming. Many convergence results are obtained for bounded sets. In this paper, we get global convergence results for non-convex programming in unbounded sets under suitable conditions.     

连续化方法求解约束凸规划问题

1．引言大型规划问题数值求解一直是计算数学工作者感兴趣的课题之一．针对大型约束规划问题,1991年李兴斯山提出凝聚函数法,该方法用光滑的凝聚函数逼近非光滑的极大值函数,从而把多个约束函数转化为带参数的单个光滑函数约束,从而降低了问题的规模．近年来,K3］研究了凸规划问题的凝聚函数法的收敛性,在目标函数强凸性及对一般凸规划研究了收敛性质．向讨论了可行解集有界的线性规划问题的凝聚函数求解算法并证明了收效性定理．上述文章均预先把凝聚参数取得充分小,然后对固定参数的单约束近似问题进行求解．一般地,凝聚参数取得…     

关于非线性规划的同伦算法与罚函数法

本文揭示了关于非线性规划问题的同伦算法与外点罚函数法的关系，并讨论了有关同伦算法的收敛条件，给出了一些典型的检验问题的计算结果以表明利用结构的分段线性同伦算法的有效性。     

无界区域非凸优化问题的组合同伦方法

考虑带有不等式约束的优化问题,对此问题建立组合同伦方程,给出同伦路径存在的一个条件,此条件不需要可行域满足法锥条件,获得了优化问题的K-K-T点.     

同伦方法求解非凸区域Brouwer不动点问题

本文构造了一个新的求解非凸区域上不动点问题的内点同伦算法,并在弱法锥(见定义2．1(2))和适当的条件下,证明了算法的全局收敛性．本文所给的条件比外法锥条件更加一般．     

解非凸规划问题的一种连续化方法

针对一类非线性规划问题的解存在的新等价性条件,给出了大范围收敛的连续化方法及证明了收敛性的结论．     

内点同伦方法求解更一般非凸集上的不动点问题(英文)

In this paper,we are mainly devoted to solving fixed point problems in more general nonconvex sets via an interior point homotopy method.Under suitable conditions,a constructive proof is given to prove the existence of fixed points,which can lead to an implementable globally convergent algorithm.     

Convergence of a Tuy-type algorithm for concave minimization subject to linear inequality constraints

A modification of Tuy's cone splitting algorithm for minimizing a concave function subject to linear inequality constraints is shown to be convergent by demonstrating that the limit of a sequence of constructed convex polytopes contains the feasible region. No geometric tolerance parameters are required.Research supported by National Science Foundation Grant ENG 76-12250     

Solving a Class of Brouwer Fixed-point Problems via a Modified Aggregate Constraint Homotopy Method

In this paper, we provide an aggregate function homotopy interior point method to solve a class of Brouwer fixed-point problems. Compared with the homotopy method （proposed by Yu and Lin, Appl. Math. Comput., 74（1996）, 65）, the main adavantages of this method are as foUows： on the one hand, it can solve the Brouwer fixed-point problems in a broader class of nonconvex subsets Ω in R^n （in this paper, we let Ω={x∈ R^n ： gi（x） ≤0, i= 1,... , m}）; on the other hand, it can also deal with the subsets Ω with larger amount of constraints more effectively.     

用改进的凝聚约束同伦方法求解一类Brouwer不动点问题

In this paper, we provide an aggregate function homotopy interior point method to solve a class of Brouwer fixed-point problems. Compared with the homotopy method (proposed by Yu and Lin, Appl. Math. Comput., 74(1996), 65), the main adavantages of this method are as follows: on the one hand, it can solve the Brouwer fixed-point problems in a broader class of nonconvex subsets Ω in Rn (in this paper, we let Ω = [x ∈ Rn: gi(x) ≤ 0, i = 1,… ,m]); on the other hand, it can also deal with the subsets Ω with larger amount of constraints more effectively.     

求解Brouwer不动点问题的改进同伦方法

In this paper,we modify the homotopy method(proposed by Yu and Lin,Appl.Math.Comput.,74(1996),65)and hence make the modified method be able to solve Brouwer fixed-point problems in a broader class of nonconvex subsets in R~n.In addition,a simple example is given to show the effectiveness of the modified method.     

关于非线性规划问题的组合同伦内点法

文[1]在条件(C1)、(C2)和(C3)之下，利用组合同伦内点法讨论了非凸非线性规划问题K—K—T点的存在性，本文对条件(C2)和(C3)进行了改进和处理。     

弱拟法锥条件下非凸优化问题的同伦算法

本文给出弱拟法锥条件的定义,并针对非线性组合同伦方程,得到在弱拟法锥条件下求解约束非凸优化问题的同伦内点算法.证明了该算法对于可行域的某个子集中几乎所有的点,同伦路径存在,并且同伦路径收敛于问题的K-K-T点,通过数值例子验证了该算法是有效的.     

On bilevel programming,Part I: General nonlinear cases

This paper is concerned with general nonlinear nonconvex bilevel programming problems (BLPP). We derive necessary and sufficient conditions at a local solution and investigate the stability and sensitivity analysis at a local solution in the BLPP. We then explore an approach in which a bundle method is used in the upper-level problem with subgradient information from the lower-level problem. Two algorithms are proposed to solve the general nonlinear BLPP and are shown to converge to regular points of the BLPP under appropriate conditions. The theoretical analysis conducted in this paper seems to indicate that a sensitivity-based approach is rather promising for solving general nonlinear BLPP.This research is sponsored by the Office of Naval Research under contract N00014-89-J-1537.