带自由变量的广义几何规划问题的全局优化

对带自由变量的广义几何规划问题(FGGP)给出一全局优化算法.该算法先利用等价转换把(FGGP)中的自由变量转化为正变量,再通过凸化方案建立了(FGGP)的松弛凸规划(RCP).通过对(RCP)可行域的细分以及一系列(RCP)的求解过程,提出的算法收敛到(FGGP)的全局最优解,且数值例子表明了算法的可行性.     

矫正低秩相关系数矩阵的松弛序列凸近似方法

本文主要讨论带有秩约束以及简单上下界约束的相关系数矩阵矫正问题的求解方法.该问题可以写成一个含有DC(两个凸函数之差)约束的优化问题,于是考虑利用求解DC优化问题的序列凸近似(SCA)方法求解.然而对本文讨论的问题,经典的序列凸近似方法收敛所需的约束规范不成立,于是,本文提出一种松弛的序列凸近似方法.本文证明当松弛参数趋于零时,松弛的DC问题的稳定点趋于原问题的稳定点.另一方面,可以利用序列凸近似方法求解松弛的DC问题.可以证明,序列凸近似方法生成的一系列凸子问题的解的聚点就是该松弛DC问题的稳定点.数值实验验证了该方法的有效性.     

一类线性乘积规划问题的分支定界缩减方法

提出了求解一类线性乘积规划问题的分支定界缩减方法, 并证明了算法的收敛性.在这个方法中, 利用两个变量乘积的凸包络技术, 给出了目标函数与约束函数中乘积的下界, 由此确定原问题的一个松弛凸规划, 从而找到原问题全局最优值的下界和可行解. 为了加快所提算法的收敛速度, 使用了超矩形的缩减策略. 数值结果表明所提出的算法是可行的.     

线性等式与不等式组稀疏解的唯一性条件

近年来,稀疏优化广泛应用在信号处理、机器学习、图像去噪和计算机视觉等方面,得到了深入的研究和快速的发展.本文考虑含有一般线性等式和不等式约束的广义l_(0-)最小化问题.尽管l_(0-)最小化问题是NP-困难的,但已有多种计算方法可以用来克服这一计算上的困难,其中一种常用的方法是,通过一个凸优化问题来近似求解原问题.具体地,用l_(1-)范数代替l_(0-)范数得到l_(0-)最小化问题的一个凸松弛.在这类方法中,研究什么条件可以保证两个问题等价是非常重要的.基于值域空间性质(RSP)的分析方法,本文提出广义l_(0-)最小化问题的RSP性质,并且证明在某些条件下,RSP性质可以保证l_(0-)最小化问题与它的凸松弛l_(1-)最小化问题是等价的.最后,本文对所使用的条件给出一些说明.     

鲁棒凸优化问题拟近似解的刻划

本文研究鲁棒凸优化问题拟近似解的最优性条件和对偶理论.首先利用鲁棒优化方法,在由约束函数的共轭函数的上图给出的闭凸锥约束规格条件下,建立了拟近似解的最优性充要条件.其次给出了鲁棒凸优化问题拟近似解在Wolf型和Mond-weir型对偶模型下的强(弱)对偶定理.最后给出具体实例验证了本文获得的结果.     

一类混合0-1非凸二次约束二次规划问题的近似算法

研究一类混合0-1非凸二次约束二次规划问题的近似算法.该问题是在M个非凸二次约束与一个基数约束下,求解一个n维向量的极小范数,变量包含M个0-1变量与一个n维连续向量.该问题是NP-难的.在求解其半正定规划(SDP)松弛问题的基础上,提出了一种随机舍入算法,能够得到原始的问题的一个可行解.数值仿真实验结果表明该方法是十分有效的.     

求线性比式和问题全局解的输出空间分枝定界算法

基于对p-1维输出空间进行剖分的思想,提出了一种求解线性比式和问题的分枝定界算法.通过一种两阶段转换方法得到原问题的一个等价问题,该问题的非凸性主要体现在新增加的p-1个非线性等式约束上.利用双线性函数的凹凸包络对这些非线性约束进行凸化,这就为等价问题构造了凸松弛子问题.将凸松弛子问题中的冗余约束去掉并进行等价转换,从而获得了一个比凸松弛子问题规模更小、约束更少的线性规划问题.证明了算法的理论收敛性和计算复杂性.数值实验表明该算法是有效可行的.     

基于最优D.C.分解的单二次约束非凸二次规划精确算法

本文提出一种基于最优D.C.分解的单二次约束非凸二次规划精确算法.本文首先对非凸二次日标函数进行D.C.分解,然后对D.C.分解中凹的部分进行线性下逼近得到一个凸二次松弛问题.本文证明了最优D.C.分解可通过求解一个半定规划问题得到,而原问题的最优解可以通过计算最优凸二次松弛问题的满足某种互补条件的解得到.最后,本文报告了初步数值计算结果.     

一类全局优化问题的线性化方法

本文对带有不定二次约束且目标函数为非凸二次函数的最优化问题提出了一类新的确定型全局优化算法,通过对目标函数和约束函数的线性下界估计,建立了原规划的松弛线性规划,通过对松弛线性规划可行域的细分以及一系列松弛线性规划的求解过程,得到原问题的全局最优解.我们从理论上证明了算法能收敛到原问题的全局最优解.     

一类DC规划问题的分支定界算法

本文针对一类带有箱子和线性不等式约束的特殊DC规划问题,提出了一种分支定界算法.首先将原问题转化为其等价问题,然后利用目标函数的特点将等价问题松弛为凸规划问题,通过求解一系列凸规划问题得到原问题的最优解,最后给出算法的收敛性证明.数值实验表明该算法是可行有效的.     

A new variable reduction technique for convex integer quadratic programs

Convex integer quadratic programming involves minimization of a convex quadratic objective function with affine constraints and is a well-known NP-hard problem with a wide range of applications. We proposed a new variable reduction technique for convex integer quadratic programs (IQP). Based on the optimal values to the continuous relaxation of IQP and a feasible solution to IQP, the proposed technique can be applied to fix some decision variables of an IQP simultaneously at zero without sacrificing optimality. Using this technique, computational effort needed to solve IQP can be greatly reduced. Since a general convex bounded IQP (BIQP) can be transformed to a convex IQP, the proposed technique is also applicable for the convex BIQP. We report a computational study to demonstrate the efficacy of the proposed technique in solving quadratic knapsack problems.     

A Computational Study of the Homogeneous Algorithm for Large-scale Convex Optimization

Recently the authors have proposed a homogeneous and self-dual algorithm for solving the monotone complementarity problem (MCP) [5]. The algorithm is a single phase interior-point type method; nevertheless, it yields either an approximate optimal solution or detects a possible infeasibility of the problem. In this paper we specialize the algorithm to the solution of general smooth convex optimization problems, which also possess nonlinear inequality constraints and free variables. We discuss an implementation of the algorithm for large-scale sparse convex optimization. Moreover, we present computational results for solving quadratically constrained quadratic programming and geometric programming problems, where some of the problems contain more than 100,000 constraints and variables. The results indicate that the proposed algorithm is also practically efficient.     

A Differential Evolution algorithm to deal with box, linear and quadratic-convex constraints for boundary optimization

We both propose and test an implicit strategy that is based on changing the search space from points to directions, which in combination with the Differential Evolution (DE) algorithm, is easily implemented for solving boundary optimization of a generic continuous function. In particular, we see that the DE method can be efficiently implemented to find solutions on the boundary of a convex and bounded feasible set resulting when the constraints are bounds on the variables, linear inequalities and quadratic convex inequalities. The computational results are performed on different classes of boundary minimization problems. The proposed technique is compared with the Generalized Differential Evolution method.     

一类不可微二次规划逆问题

本文求解了一类二次规划的逆问题,具体为目标函数是矩阵谱范数与向量无穷范数之和的最小化问题.首先将该问题转化为目标函数可分离变量的凸优化问题,提出用G-ADMM法求解.并结合奇异值阈值算法,Moreau-Yosida正则化算法,matlab优化工具箱的quadprog函数来精确求解相应的子问题.而对于其中一个子问题的精确求解过程中发现其仍是目标函数可分离变量的凸优化问题,由于其变量都是矩阵,所以采用适合多个矩阵变量的交替方向法求解,通过引入新的变量,使其每个子问题的解都具有显示表达式.最后给出采用的G-ADMM法求解本文问题的数值实验.数据表明,本文所采用的方法能够高效快速地解决该二次规划逆问题.     

Global optimization of signomial mixed-integer nonlinear programming problems with free variables

Mixed-integer nonlinear programming (MINLP) problems involving general constraints and objective functions with continuous and integer variables occur frequently in engineering design, chemical process industry and management. Although many optimization approaches have been developed for MINLP problems, these methods can only handle signomial terms with positive variables or find a local solution. Therefore, this study proposes a novel method for solving a signomial MINLP problem with free variables to obtain a global optimal solution. The signomial MINLP problem is first transformed into another one containing only positive variables. Then the transformed problem is reformulated as a convex mixed-integer program by the convexification strategies and piecewise linearization techniques. A global optimum of the signomial MINLP problem can finally be found within the tolerable error. Numerical examples are also presented to demonstrate the effectiveness of the proposed method.     

A one-layer recurrent neural network for non-smooth convex optimization subject to linear inequality constraints

In this paper, a one-layer recurrent network is proposed for solving a non-smooth convex optimization subject to linear inequality constraints. Compared with the existing neural networks for optimization, the proposed neural network is capable of solving more general convex optimization with linear inequality constraints. The convergence of the state variables of the proposed neural network to achieve solution optimality is guaranteed as long as the designed parameters in the model are larger than the derived lower bounds.     

Accelerated primal–dual proximal block coordinate updating methods for constrained convex optimization

Block coordinate update (BCU) methods enjoy low per-update computational complexity because every time only one or a few block variables would need to be updated among possibly a large number of blocks. They are also easily parallelized and thus have been particularly popular for solving problems involving large-scale dataset and/or variables. In this paper, we propose a primal–dual BCU method for solving linearly constrained convex program with multi-block variables. The method is an accelerated version of a primal–dual algorithm proposed by the authors, which applies randomization in selecting block variables to update and establishes an O(1 / t) convergence rate under convexity assumption. We show that the rate can be accelerated to \(O(1/t^2)\) if the objective is strongly convex. In addition, if one block variable is independent of the others in the objective, we then show that the algorithm can be modified to achieve a linear rate of convergence. The numerical experiments show that the accelerated method performs stably with a single set of parameters while the original method needs to tune the parameters for different datasets in order to achieve a comparable level of performance.     

求解非凸区域上凸函数比式和问题的全局优化方法

针对非凸区域上的凸函数比式和问题,给出一种求其全局最优解的确定性方法.该方法基于分支定界框架.首先通过引入变量,将原问题等价转化为d.c.规划问题,然后利用次梯度和凸包络构造松弛线性规划问题,从而将关键的估计下界问题转化为一系列线性规划问题,这些线性规划易于求解而且规模不变,更容易编程实现和应用到实际中;分支采用单纯形对分不但保证其穷举性,而且使得线性规划规模更小.理论分析和数值实验表明所提出的算法可行有效.     

An outer approximation method for minimizing the product of several convex functions on a convex set

This paper addresses the minimization of the product ofp convex functions on a convex set. It is shown that this nonconvex problem can be converted to a concave minimization problem withp variables, whose objective function value is determined by solving a convex minimization problem. An outer approximation method is proposed for obtaining a global minimum of the resulting problem. Computational experiments indicate that this algorithm is reasonable efficient whenp is less than 4.This research was partly supported by Grant-in-Aid for Scientific Research of the Ministry of Education, Science and Culture, Grant No. (C)03832018 and (C)04832010.     

On nonconvex optimization problems with separated nonconvex variables

A mathematical programming problem is said to have separated nonconvex variables when the variables can be divided into two groups: x=(x ₁,...,x _n ) and y=( y ₁,...,y _n ), such that the objective function and any constraint function is a sum of a convex function of (x, y) jointly and a nonconvex function of x alone. A method is proposed for solving a class of such problems which includes Lipschitz optimization, reverse convex programming problems and also more general nonconvex optimization problems.