Global Optimization Algorithm Based on Lagrangian Dual

吴慧卓; 张可村

您当前的位置：

首页 >

文章列表页 >

Global Optimization Algorithm Based on Lagrangian Dual

更新时间：2025-12-08

- Global Optimization Algorithm Based on Lagrangian Dual
- Vol. 42, Issue 8, Pages: 1031-1034(2008)
- 作者机构：
  
  西安交通大学理学院,西安,710049
- 作者简介：
- 基金信息：
- DOI：
  CLC： O221.2
- Online First：10 August 2008，
  
  Published：2008
- 稿件说明：
移动端阅览
吴慧卓, 张可村. Global Optimization Algorithm Based on Lagrangian Dual[J]. 2008, 42(8): 1031-1034.
DOI：

吴慧卓, 张可村. Global Optimization Algorithm Based on Lagrangian Dual[J]. 2008, 42(8): 1031-1034. DOI：

摘要

针对带有非凸二次函数约束的非凸二次规划问题(NQP)

提出了一个基于拉格朗日对偶的确定型全局优化算法

这类优化算法可广泛应用于工程设计和非线性系统的鲁棒稳定性分析等实际问题中.为求解此问题

首先

应用拉格朗日对偶对原问题进行下界估计.其次

为克服拉格朗日对偶问题的非凸性

利用线性化方法

得到拉格朗日对偶问题的线性下界估计

并且由此建立了NQP拉格朗日对偶问题的松弛线性规划(RLP).如此通过对RLP可行域的细分和一系列RLP的求解过程

从理论上证明了算法收敛到NQP的全局最优解.数值算例应用结果表明

该方法是可行的.

Abstract

A deterministic global optimization algorithm based on Lagrangian dual is proposed for solving the nonconvex quadratic programming with nonconvex quadratic constraints

which is often encountered in technical design and operational research. By utilizing a linearized method the difficulty that the Lagrangian dual problem is nonconvex is solved and the linearization relaxation of the Lagrangian is obtained. The proposed branch and bound algorithms are convergent to the global minimum via successive refinement of the linear relaxation of the Lagrangian dual problem and the solutions to a series of the relaxation of linear programming. Interval Newton method is used to accelerate the convergence of the algorithm. Numerical experiments are given to verify the feasibility of the proposed algorithm.

关键词

Keywords

references

KHAMMASH M H. Synthesis of globally optimal controllers for robust performance to unstructured uncertainty[J]. IEEE Transactions on Automatic Control,1996, 41(2):189-198.

SALAPAKA M V, KHAMMASH M H, VOORHIS T V.Synthesis of globally optimal controllers in h using the reformulation-linearization technique[C]∥Proceedings of the IEEE Conference on Decision and Control. Piscataway, NJ, USA: IEEE, 1998.

LODWICK W A. Preprocessing nonlinear functional constraints with applications to the pooling problem[J]. ORSA Journal on Computing,1992, 4(1):119-131.

FLOUDAS C A, VISWESWARAN V. Primal-relaxed dual global optimization approach[J]. Journal of Optimization Theory and Applications, 1993, 78:187-225.

QU S J, YIN H Y, ZHANG K C. A global optimization algorithm using linear relaxation[J].Applied Mathematics and Computation, 2006,178:510-518.

VOORHIS T V. A global optimization algorithm using Lagrangian underestimates and the interval Newton method[J]. Journal of Global Optimization, 2002,24:349-370.

PARDLOS P M, ROSEN J B. Constrained global optimization: algorithms and applications[M]. Berlin,Germany:Springer-Verlag, 1987.

AN L T H. An efficient algorithm for globally minimizing a quadratic function under convex quadratic constraints[J]. Math Program: Ser A, 2000, 87(12):401-426.

KEARFOTT R B.Rigorous global search: continuous problems, nonconvex optimization and its applications[M]. Dordrecht,Holland:Kluwer Academic Publishers,1996.

MARANAS C D, FLOUDAS C A. Global optimization in generalized geometric programming[J]. Computers and Chemical Engineering,1997,21(4):351-369.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Pareto Optimality Based Genetic Algorithm in Web Services Composition

Global Optimization Method of the Design for Multi-Layer Planar Inductors

Integrated Intelligent Algorithms for Global Optimization

Profiling Based Optimization Method for CPU-GPU Heterogeneous Parallel Processing System

A Periodical Multi-Installment Scheduling Model and Algorithm for Divisible Loads in Distributed Computing Systems

Related Author

赵晓昳 1

张星 1

符锐 1

董渭清 1

胡焕耀 1

耿莉

邵志标

Related Institution

西安交通大学电子与信息工程学院

中兴通讯股份有限公司上海研发中心

School of Electronics and Information Engineering, Xi'an Jiaotong University

School of Network Engineering, Zhoukou Normal University

School of Computer Science and Technology, Xidian University

⁰