共查询到20条相似文献,搜索用时 0 毫秒
1.
We apply a linearization technique for nonconvex quadratic problems with box constraints. We show that cutting plane algorithms can be designed to solve the equivalent problems which minimize a linear function over a convex region. We propose several classes of valid inequalities of the convex region which are closely related to the Boolean quadric polytope. We also describe heuristic procedures for generating cutting planes. Results of preliminary computational experiments show that our inequalities generate a polytope which is a fairly tight approximation of the convex region. 相似文献
2.
本文提出了一种求解带二次约束和线性约束的二次规划的分支定界算法.在算法中,我们运用Lipschitz条件来确定目标函数和约束函数的在每个n矩形上的上下界,对于n矩形的分割,我们采用选择n矩形最长边的二分法,同时我们采用了一些矩形删除技术,在不大幅增加计算量的前提下,起到了加速算法收敛的效果.从理论上我们证明了算法的收敛性,同时数值实验表明该算法是有效的. 相似文献
3.
4.
Zi-Luan Wei 《计算数学(英文版)》2002,20(6):643-652
A regular splitting and potential reduction method is presented for solving a quadratic programming problem with box constraints (QPB) in this paper. A general algorithm is designed to solve the QPB problem and generate a sequence of iterative points. We show that the number of iterations to generate an e-minimum solution or an e-KKT solution by the algorithm is bounded by O( nlog(1 )), and the total running time is bounded by O(n2(n logn log1/ε)(n/εlog1/ε logn)) arithmetic operations. 相似文献
5.
边界约束非凸二次规划问题的分枝定界方法 总被引:2,自引:0,他引:2
本文是研究带有边界约束非凸二次规划问题,我们把球约束二次规划问题和线性约束凸二次规划问题作为子问题,分明引用了它们的一个求整体最优解的有效算法,我们提出几种定界的紧、松驰策略,给出了求解原问题整体最优解的分枝定界算法,并证明了该算法的收敛性,不同的定界组合就可以产生不同的分枝定界算法,最后我们简单讨论了一般有界凸域上非凸二次规划问题求整体最优解的分枝与定界思想。 相似文献
6.
Zhu Wang 《Journal of computational and graphical statistics》2018,27(3):491-502
Classical robust statistical methods dealing with noisy data are often based on modifications of convex loss functions. In recent years, nonconvex loss-based robust methods have been increasingly popular. A nonconvex loss can provide robust estimation for data contaminated with outliers. The significant challenge is that a nonconvex loss can be numerically difficult to optimize. This article proposes quadratic majorization algorithm for nonconvex (QManc) loss. The QManc can decompose a nonconvex loss into a sequence of simpler optimization problems. Subsequently, the QManc is applied to a powerful machine learning algorithm: quadratic majorization boosting algorithm (QMBA). We develop QMBA for robust classification (binary and multi-category) and regression. In high-dimensional cancer genetics data and simulations, the QMBA is comparable with convex loss-based boosting algorithms for clean data, and outperforms the latter for data contaminated with outliers. The QMBA is also superior to boosting when directly implemented to optimize nonconvex loss functions. Supplementary material for this article is available online. 相似文献
7.
1IntroductionWeconsiderastrictlyconvex(i.e.,positivedefinite)quadraticprogrammingproblemsubjecttoboxconstraints:t-iereA=[aij]isannxnsymmetricpositivedefinitematrix,andb,canddaren-vectors.Letg(x)bethegradient,Ax b,off(x)atx.Withoutlossofgeneralityweassumebothcianddiarefinitenumbers,ci相似文献
8.
9.
Z. Y. Wu V. Jeyakumar A. M. Rubinov 《Journal of Optimization Theory and Applications》2007,133(1):123-130
We present sufficient conditions for the global optimality of bivalent nonconvex quadratic programs involving quadratic inequality
constraints as well as equality constraints. By employing the Lagrangian function, we extend the global subdifferential approach,
developed recently in Jeyakumar et al. (J. Glob. Optim., 2007, to appear; Math. Program. Ser. A, 2007, to appear) for studying bivalent quadratic programs without quadratic constraints, and derive global optimality conditions.
The authors are grateful to the referees for constructive comments and suggestions which have contributed to the final preparation
of the paper.
Z.Y. Wu’s current address: School of Information Technology and Mathematical Sciences, University of Ballarat, Ballarat, Victoria,
Australia. The work of this author was completed while at the Department of Applied Mathematics, University of New South Wales,
Sydney, Australia. 相似文献
10.
Jin-bao Jian Qing-jie Hu Chun-ming Tang Hai-yan Zheng 《Applied Mathematics and Optimization》2007,56(3):343-363
In this paper, a sequential quadratically constrained quadratic programming method of feasible directions is proposed for
the optimization problems with nonlinear inequality constraints. At each iteration of the proposed algorithm, a feasible direction
of descent is obtained by solving only one subproblem which consist of a convex quadratic objective function and simple quadratic
inequality constraints without the second derivatives of the functions of the discussed problems, and such a subproblem can
be formulated as a second-order cone programming which can be solved by interior point methods. To overcome the Maratos effect,
an efficient higher-order correction direction is obtained by only one explicit computation formula. The algorithm is proved
to be globally convergent and superlinearly convergent under some mild conditions without the strict complementarity. Finally, some preliminary numerical results are reported.
Project supported by the National Natural Science Foundation (No. 10261001), Guangxi Science Foundation (Nos. 0236001, 064001),
and Guangxi University Key Program for Science and Technology Research (No. 2005ZD02) of China. 相似文献
11.
12.
Duality Bound Method for the General Quadratic Programming Problem with Quadratic Constraints 总被引:4,自引:0,他引:4
N. V. Thoai 《Journal of Optimization Theory and Applications》2000,107(2):331-354
The purpose of this article is to develop a branch-and-bound algorithm using duality bounds for the general quadratically-constrained quadratic programming problem and having the following properties: (i) duality bounds are computed by solving ordinary linear programs; (ii) they are at least as good as the lower bounds obtained by solving relaxed problems, in which each nonconvex function is replaced by its convex envelope; (iii) standard convergence properties of branch-and-bound algorithms for nonconvex global optimization problems are guaranteed. Numerical results of preliminary computational experiments for the case of one quadratic constraint are reported. 相似文献
13.
14.
对框式凸二次规划问题提出了一种非精确不可行内点算法 ,该算法使用的迭代方向仅需要达到一个相对的精度 .在初始点位于中心线的某邻域内的假设下 ,证明了算法的全局收敛性 相似文献
15.
Hiroshi Yamashita 《Mathematical Programming》1982,23(1):75-86
The recently proposed quasi-Newton method for constrained optimization has very attractive local convergence properties. To force global convergnce of the method, a descent method which uses Zangwill's penalty function and an exact line search has been proposed by Han. In this paper a new method which adopts a differentiable penalty function and an approximate line is presented. The proposed penalty function has the form of the augmented Lagrangian function. An algorithm for updating parameters which appear in the penalty function is described. Global convergence of the given method is proved. 相似文献
16.
In this paper we propose a new branch and bound algorithm using a rectangular partition and ellipsoidal technique for minimizing a nonconvex quadratic function with box constraints. The bounding procedures are investigated by d.c. (difference of convex functions) optimization algorithms, called DCA. This is based upon the fact that the application of the DCA to the problems of minimizing a quadratic form over an ellipsoid and/or over a box is efficient. Some details of computational aspects of the algorithm are reported. Finally, numerical experiments on a lot of test problems showing the efficiency of our algorithm are presented. 相似文献
17.
基于模糊结构元方法构建并讨论了一类含有直觉模糊弹性约束的多目标模糊线性规划问题.通过引入模糊数的加权特征数,定义了一种序关系并拓展了Verdegay的模糊线性规划方法,将上述多目标模糊线性规划问题转化成两个等价含参数约束条件的清晰多目标线性规划模型,并应用一种线性加权函数法给出了此类线性规划模型的对比最优可行解.最后通过一个数值实例来说明此类问题的一般求解方法. 相似文献
18.
Patrice Marcotte 《Mathematical Programming》1985,33(3):339-351
The variational inequality problem in Euclidian space is formulated as a nonconvex, nondifferentiable optimization problem. We show that any stationary point is optimal, and we propose a solution algorithm that decreases the nondifferential objective monotonically. Application to the asymmetric traffic assignment problem is considered.Research supported by C.R.S.H. (Canada) grant #410-81-0722-RL and F.C.A.C. (Québec) grant # 83-AS-0026. 相似文献
19.
20.
A Non-Interior Path Following Method for Convex Quadratic Programming Problems with Bound Constraints 总被引:2,自引:1,他引:1
Song Xu 《Computational Optimization and Applications》2004,27(3):285-303
We propose a non-interior path following algorithm for convex quadratic programming problems with bound constraints based on Chen-Harker-Kanzow-Smale smoothing technique. Conditions are given under which the algorithm is globally convergent or globally linearly convergent. Preliminary numerical experiments indicate that the method is promising. 相似文献