权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

Successive Convex Relaxation Methods for Nonconvex Optimization Problems

非凸优化问题的连续凸松弛方法

基本信息

批准号：
11680441
负责人：
KOJIMA Masakazu
金额：
$ 2.11万
依托单位：
Tokyo Institute of Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
1999
资助国家：
日本
起止时间：
1999 至 2000
项目状态：
已结题

项目摘要

In this research project, we studied a general Quadratic Optimization Problem(QOP)having a linear objective function c^Tx to be maximized over a compact subset F of the n-dimensional Euclidean space R^n represented by(finitely or infinitely many)quadratic inequalities. There are two viriants of successive convex relaxation method, the SSDP(Successive Semidefinite Programming)Relaxation Method and the SSILP(Successive Semi-Infinite Linear Programming)Relaxation Method. Each of the methods generates a sequence of compact convex subsets C_k(k=1,2, ...)of R^n which monotonically converges to the convex hull of F.To implements the SSDP and SSILP Relaxation Methods, we introduced two new techniques, "discretization " and "localization." The discretization technique makes it possible to approximate an infinite number of semi-infinite SDPs(or semi-infinite LPs)which appeared at each iteration of the original methods by a finite number of standard SDPs(or standard LPs)with a finite number of linear inequality constraints. The localization technique is for the cases where we are only interested in upper bounds on the optimal objective value(for a fixed objective function vector c)but not in a global approximation of the convex hull of F.This technique allows us to generate a convex relaxation of F that is accurate only in certain directions in a neighborhood of the objective direction c. This cuts off redundant work to make the convex relaxation accurate in unnecessary directions. Through numerical experiments, we confirmed that these two techniques worked effectively for large scale QOPs.

在这个研究项目中，我们研究了一个一般的二次优化问题（QOP），它具有一个线性目标函数c^Tx在n维欧几里德空间R^n的紧子集F上最大化，该空间由（有限或无限多个）二次不等式表示。连续凸松弛法有两种类型，即连续半定规划松弛法和连续半无限线性规划松弛法。每一种方法都生成一个R^n的紧凸子集C_k（k=1,2，…）序列，该序列单调收敛于f的凸包。为了实现SSDP和SSILP松弛方法，我们引入了两种新技术，“离散化”和“局部化”。离散化技术可以用有限数量的标准sdp（或标准lp）和有限数量的线性不等式约束来近似原方法每次迭代中出现的无限数量的半无限sdp（或半无限lp）。定位技术适用于我们只对最优目标值的上界感兴趣的情况（对于固定的目标函数向量c），而不是对F的凸包的全局逼近感兴趣。这种技术允许我们生成F的凸松弛，它只在目标方向c附近的某些方向上准确。这减少了多余的工作，使凸松弛在不必要的方向上准确。通过数值实验，我们证实了这两种技术在大规模QOPs中是有效的。