Successive Convex Relaxation Methods for Nonconvex Optimization Problems

在这个研究项目中，我们研究了一个一般的二次优化问题（QOP），其线性目标函数c^Tx在n维欧氏空间R^n的一个由（无穷多个或无穷多个）二次不等式表示的紧致子集F上被最大化。逐次凸松弛法有两种形式，SSDP（逐次半定规划）松弛法和SSLP（逐次半无限线性规划）松弛法。每种方法都生成一列紧凸子集C_k（k= 1，2，.）为了实现SSDP和SSLP松弛方法，我们引入了两种新的技术，“离散化“和“局部化”。“离散化技术使得有可能通过有限数量的标准SDP（或标准LP）与有限数量的线性不等式约束来近似在原始方法的每次迭代中出现的无限数量的半无限SDP（或半无限LP）。局部化技术适用于我们只对最优目标值的上界（对于固定的目标函数向量c）感兴趣而不对F的凸船体的全局近似感兴趣的情况。这种技术允许我们生成F的凸松弛，其仅在目标方向c的邻域中的某些方向上是准确的。这就切断了多余的工作，使凸松弛在不必要的方向上精确。通过数值实验，我们证实了这两种方法对大尺度QOP的有效性。

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.