研究论文

求不定二次规划问题全局解的单调化方法

  • 申培萍 ,
  • 李卫敏 ,
  • 唐冲
展开
  • 河南师范大学数学与信息科学学院, 新乡 453007
申培萍,教授,研究方向为最优化理论与应用,电子信箱:shenpp@htu.cn

收稿日期: 2014-01-18

  修回日期: 2014-04-22

  网络出版日期: 2014-07-02

基金资助

国家自然科学基金项目(11171094,11171368)

A Monotonic Optimization Approach for Solving Globally Generalized Quadratic Programming

  • SHEN Peiping ,
  • LI Weimin ,
  • TANG Chong
Expand
  • College of Mathematics and Information Science, Henan Normal University, Xinxiang 453007, China

Received date: 2014-01-18

  Revised date: 2014-04-22

  Online published: 2014-07-02

摘要

不定二次规划是全局优化的一类重要问题,在金融、统计、工程设计等实际问题中有广泛应用。但此类问题可能存在多个非全局最优的局部极值点,所以求其全局最优解变得十分困难。运用单调优化理论提出一种求不定二次规划问题全局最优解的新方法:通过引入新变量将问题等价转化为单调优化问题,然后利用问题的单调结构进行缩减、分割、辅助问题最优值的定界等过程获得近似全局最优解。该解不仅可行且能充分接近真实的全局最优解,数值结果表明方法可行有效。

本文引用格式

申培萍 , 李卫敏 , 唐冲 . 求不定二次规划问题全局解的单调化方法[J]. 科技导报, 2014 , 32(18) : 58 -61 . DOI: 10.3981/j.issn.1000-7857.2014.18.009

Abstract

The generalized quadratic programming (GQP) is an important class of global optimization problems with wide applications in the fields of financial management, statistics and design engineering, with multiple local optimal solutions differing from the global solution. Thus, it is very difficult to obtain a global optimal solution for the GQP. Many solution methods were developed for globally solving the GQPs in a special form and the general form. However, these approaches may sometimes provide an infeasible solution, or one far from the true optimum. To overcome these limitations, a monotonic optimization approach is proposed for the GQP. In the approach, the original problem is first converted into an equivalent monotonic optimization problem, whose objective function is just a simple univariate by exploiting the particular features of this problem. Then, a range division and compression approach is used to reduce the range of each variable. Tightening variable bounds iteratively allows the proposed method to reach an approximate solution within an acceptable error by using monotonic functions, in which such solution is adequately guaranteed to be feasible and to be close to the actual global optimal solution. At last, several numerical examples are given to illustrate the feasibility and efficiency of the present algorithm.

参考文献

[1] Horst R, Pardalos P M. Handbook of global optimization[M]. Boston: Kluwer Academic Publisher, 1975.
[2] Kedem G, Watanabe H. Graph-optimization techniques for IC layout and compaction[J]. Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, 1984, 3(1): 12-20.
[3] Stern R J, Wolkowicz H. Indefinite trust region subproblems and nonsymmetric eigenvalue perturbations[J]. SIAM Journal on Optimization, 1995, 5(2): 286-313.
[4] Cambini R, Sodini C. Decomposition methods for solving nonconvex quadratic programs via branch and bound[J]. Journal of Global Optimization, 2005, 33(3): 313-336.
[5] Li H M, Zhang K C. A decomposition algorithm for solving large-scale quadratic programming problems[J]. Applied Mathematics and Computation, 2006, 173(1): 394-403.
[6] Qu S J, Yin H Y, Zhang K C. A global optimization algorithm using linear relaxation[J]. Applied Mathematics and Computation, 2006, 178(2): 510-518.
[7] Gao Y L, Xue H G, Shen P P. A new rectangle branch and reduce approach for solving nonconvex quadratic programming problems[J]. Applied Mathematics and Computation, 2005, 168(2): 1409-1418.
[8] Anstreicher K M. Semidefinite programming versus the reformulationlinearization technique for nonconvex quadratically constrained quadratic programming[J]. Journal of Global Optimization, 2009, 43(2-3): 471-484.
[9] Lu C, Fang S C, Jin Q, et al. KKT solution and conic relaxation for solving quadratically constrained quadratic programming problems[J]. SIAM Journal on Optimization, 2011, 21(4): 1475-1490.
[10] Shi Z Y, Jin Q W. Second order optimality conditions and reformulations for nonconvex quadratically constrained quadratic programming problems[J]. Journal of Industrial and Management Optimization, 2014, 10(3): 871-882
[11] 汪春峰, 刘三阳, 张建科. 不定二次规划全局解的一个新算法[J]. 工程 数学学报, 2011, 28(3): 300-306. Wang Chunfeng, Liu Sanyang, Zhang Jianke. A new global optimization algorithm for indefinite quadratic programs[J]. Chinese Journal of Engineering Mathematics, 2011, 28(3): 300-306.
[12] 申培萍, 刘利敏. 带非凸二次约束的二次规划问题的全局优化方法[J]. 工程数学学报, 2008, 25(5): 923-926. Shen Peiping, Liu Liming. A global optimization approach to quadratic programming problems with nonconvex quadratic constraints[J]. Chinese Journal of Engineering Mathematics, 2008, 25(5): 923-926.
[13] Jiao H W, Chen Y Q. A global optimization algorithm for generalized quadratic programming[J]. Journal of Applied Mathematics, 2013, 2013: 1-9.
[14] Linderoth J. A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs[J]. Mathematical Programming, 2005, 103(2): 251-282.
[15] Benson H P. Decomposition branch-and-bound based algorithm for linear programs with additional multiplicative constraints[J]. Journal of Optimization Theory and Applications, 2005, 126(1): 41-61.
[16] Shen P P, Chen Y Q, Ma Y. A nonisolated optimal solution for special reverse convex programming problems[J]. Journal of Computational and Applied Mathematics, 2009, 224(1): 219-229.
[17] Shen P P, Ma Y, Chen Y Q. A robust algorithm for generalized geometric programming[J]. Journal of Global Optimization, 2008, 41(4): 593-612.
[18] Shen P P, Chen Y Q, Ma Y. Global optimization for the generalized polynomial sum of ratios problem[J]. Journal of Global Optimization, 2011, 50(3): 439-455.
[19] Shen P P, Li X A. Branch-reduction-bound algorithm for generalized geometric programming[J]. Journal of Global Optimization, 2013, 56(3): 1123-1142.
[20] Pörn R, Björk K M, Westerlund T. Global solution of optimization problems with signomial parts[J]. Discrete optimization, 2008, 5(1): 108-120.
文章导航

/