Block coordinate descent with time perturbation for nonconvex nonsmooth problems in real-world studies

The era of big data in healthcare is here, and this era will significantly improve medicine and especially oncology. However, traditional machine learning algorithms need to be promoted to solve such large-scale real-world problems due to a large amount of data that needs to be analyzed and the difficulty in solving problems with nonconvex nonlinear settings. We aim to minimize the composite of a smooth nonlinear function and a block-separable nonconvex function on a large number of block variables with inequality constraints. We propose a novel parallel first-order optimization method, called asynchronous block coordinate descent with time perturbation (ATP), which adopts a time perturbation technique that escapes from saddle points and sub-optimal local points. The details of the proposed method are presented with analyses of convergence and iteration complexity properties. Experiments conducted on real-world machine learning problems validate the efficacy of our proposed method. The experimental results demonstrate that time perturbation enables ATP to escape from saddle points and sub-optimal points, providing a promising way to handle nonconvex optimization problems with inequality constraints employing asynchronous block coordinate descent. The asynchronous parallel implementation on shared memory multi-core platforms indicates that the proposed algorithm, ATP, has strong scalability.

基于非负张量分解的投资组合策略

有效提取股票价格时间序列中股票对之间的相互依赖关系能够提高投资组合的收益率。采用基于块坐标下降法的非负张量分解技术从股票价格时间序列中提取复杂关系,构建预测距离矩阵来代替原有的相关系数矩阵,提出基于非负张量分解的投资组合策略。选取2019—2021年中证100指数数据进行实证分析,实验结果表明:基于非负张量分解的投资组合策略具有较高的可行性,且在股市动荡时期表现要优于等权重和市值加权投资组合。

智能反射面辅助的无线网络加权和速率优化设计

针对智能反射面(intelligent reflecting surface,IRS)辅助的无线网络传输设计的目标是通过联合设计基站处的发送波束形成向量和IRS的反射系数,在满足基站发射功率和IRS单位模约束的条件下,使多个地面用户的加权和速率最大化。为了求解非凸的目标函数,提出一种交替优化方法,其中采用黎曼流形梯度(Riemannian manifold gradient,RMG)方法来优化反射系数,使用二分搜索法优化发送波束形成向量。此外,为了降低RMG方法的复杂度,设计了一种智能元素块坐标下降方法。仿真结果验证了所提算法的有效性,并且表明通过优化设计反射系数,IRS可显著提高无线网络的频谱效率。

基于块坐标下降法的有砟轨道大机捣固维修经济决策模型及算法

为了更好地利用检修数据指导轨道维修决策计划,在预防性维修理念下提出1种基于块坐标下降法的有砟轨道大机捣固维修经济决策模型及算法。考虑多种捣固模式下不同的捣固效果和相应成本,以轨道质量年末保持值和维修经济成本为决策目标,结合大机养修效率和现场实际条件,建立大机捣固维修经济决策模型;采用块坐标下降算法,以并行计算为主要思路并通过聚类算法调整捣固区段的连续性,实现最佳捣固模式、捣固时机和捣固区段的高效求解。依托某120 km·h~(-1)、50 km试验区段在某年份的实测数据,验证模型及算法有效性。结果表明:依据模型及算法得出的维修计划,采用09-32型捣固车开展单捣、双捣2种捣固模式后,每年可较实际平推捣固计划分别节省18%和15%的费用,改良型大机捣固质量指数MTQI的年末平均值从实际平推捣固计划的6.5 mm分别降低约0.80和1.35 mm;模型及算法能够快捷有效地制定符合线路实际的大机捣固维修计划,不仅实现了大机作业的连续捣固,还较大幅度提升了捣固维修的经济性。

基于块坐标下降法的神经网络学习算法

针对当前一阶优化算法收敛速度慢,对学习率依赖性强和二阶优化方法复杂度高等问题,利用神经网络固有的可分性,提出递归最小二乘与梯度下降的混合算法(Hybrid Recursive Least-Squares with Stochastic Gradient Descent, HRLSGD),将原本复杂的网络模型分解为更易解决的低维优化问题。实验结果表明,HRLSGD的收敛速度优于主流的一阶优化算法,对于学习率的鲁棒性更高。

雷达脉冲压缩低旁瓣发射波形和非匹配滤波联合设计方法

为有效抑制雷达波形的脉冲压缩旁瓣水平,提高雷达弱目标检测和成像性能,本文提出了雷达波形和滤波器联合设计抑制脉冲压缩旁瓣水平的方法,建立了雷达波形和滤波器联合设计数学模型,基于分块坐标下降方法分解了联合设计问题,提出了一种联合优化算法,将该方法扩展到了正交波形和滤波器组设计,并提出一种并行优化的联合设计方法 .仿真结果表明,本文方法比传统方法具有更快的运行速度.该方法可有效扩展至正交波形和滤波器组设计问题.

增广拉格朗日函数的两种可分化方法之比较

可分方法用于将一个复杂的大规模优化问题分解成各个子问题进行求解。增广拉格朗日松弛方法的主要缺点是由其引入的二次项是不能分离的。为了处理这种增广拉格朗日函数的不可分离性,可将辅助问题原理方法或分块坐标下降方法应用于增广拉格朗日松弛方法。与已有文献中对带有约束条件x-x-=0的优化问题进行这两种可分方法的比较不同,本文对带有更一般的约束条件——线性约束z=Ax的优化问题进行这两种可分化方法的比较;最后给出的两个算例证实了本文的理论分析结果——在处理不可分离的增广拉格朗日函数的时候,在一定条件下,分块坐标下降法往往比辅助问题原则法更快得到最优值。

自适应步长带回代的邻近分块乘子极小化算法

本文考虑求解带线性约束的多块凸优化问题,其中的目标函数有一项不可分离。对于目标函数中存在不可分离项,晁绵涛等人将块坐标下降法与交替方向乘子法相结合提出了PBMM-MS算法,并通过数值实验验证了其有效性。本文对PBMM-MS算法进行改进,提出了自适应步长带回代的邻近分块乘子极小化算法,该算法结合了步长的自适应调整技术,使步长在迭代过程中自动调整,提高了算法的计算效率。对于提出的算法,我们证明了其收敛性。

基于块坐标下降法的微网群日前联合优化调度

文章顾及微网群调度中心和微电网用户两类主体,建立一类含多个并列下层双层规划结构的微网群联合优化调度模型,上层以微网群调度中心总运行成本最小为优化目标,下层以各微电网用户运行成本最低为优化目标。首先,通过增广拉格朗日松弛法将原双层规划模型松弛;用块坐标下降法将松弛问题分解为多个子问题;然后,通过基于块坐标下降-不精确嵌套乘子法的双层循环求解模型,逐次逼近原问题的全局最优解;采用由松至紧的内循环容限值,以避免内循环计算代价过大的问题。算例的验证结果表明,文章所提的基于块坐标下降-不精确嵌套乘子法的双层循环求解模型,能有效求解微网群双层优化调度模型,为此类优化调度问题提供新的并行求解模式。

基于块稀疏快速重构的MISO活跃用户集与信道联合估计

针对多用户多输入单输出(Multiple input single output,MISO)系统的用户选择与信道估计问题,引入基于用户分布式自选择的信道接入策略,设计一种新的结合该策略的时分双分复用(Time division duplex,TDD)模式数据传输帧结构。利用用户活跃模式自然稀疏性和信道冲激响应时延域稀疏性,将基站接收上行随机导频序列建模为块稀疏线性模型。基于凸松弛的l2/l1模型提出一种快速的块稀疏重构算法求解问题模型。算法首先对目标函数进行变量分裂,然后利用交替方向法对各变量进行交替更新,直至满足收敛条件。交替更新中,对于无法获得闭式解的信号变量项,采取块坐标下降法求解。计算机仿真表明,与块正交匹配追踪和块压缩采样匹配追踪比较,新算法能够在保持高重构精度的前提下获得更快的计算速度。

增广拉格朗日函数的两种分解方法比较

分解方法是一种把复杂的大规模优化问题分解成各个子问题来求解的方法。增广拉格朗日松弛方法的一个主要缺点是它的二次项是不可分离的。可将辅助问题原理方法或分块坐标下降方法应用于增广拉格朗日松弛,来处理增广拉格朗日函数的不可分离性。通过线性约束Ax+By=z的优化问题对这两种分解方法进行比较。

交替方向块稀疏信号快速重构算法

研究模型压缩感知中的块稀疏信号重构问题.在l2/l1模型基础上,提出一种基于交替方向法的块稀疏信号重构算法.在该算法中,首先对目标函数进行变量分裂,然后利用交替方向法对各变量进行交替更新,直至满足收敛条件.仿真实验中,将该算法与块正交匹配追踪和块压缩采样匹配追踪算法进行比较,结果表明该算法能够在保持高重构精度的前提下获得更快的计算速度.

D2D毫米波通信中基于多变量联合优化的吞吐量提升算法

为了提升设备直连(device-to-device, D2D)的毫米波通信系统的吞吐量,提出基于多变量联合优化的吞吐量提升(multi-variable joint optimization-based throughput improvement, MJTI)算法。MJTI算法将共享同一子信道的D2D对形成一个联盟,以最大化联盟速率之和为联盟收益。先构建关于联盟形成、定向天线波束转向角设置和最佳传输功率的目标问题。然后,采用块坐标下降法将目标问题分解成3个子问题。再分别利用联盟博弈、拉格朗日乘法和内点法求解。最后,通过仿真数据分析联盟数、D2D对数和天线增益对吞吐量的影响。仿真数据表明,相比于随机方式形成联盟,MJTI算法的吞吐量平均提升约15%。

A Parallel Line Search Subspace Correction Method for Composite Convex Optimization

In this paper,we investigate a parallel subspace correction framework for composite convex optimization.The variables are first divided into a few blocks based on certain rules.At each iteration,the algorithms solve a suitable subproblem on each block simultaneously,construct a search direction by combining their solutions on all blocks,then identify a new point along this direction using a step size satisfying the Armijo line search condition.They are called PSCLN and PSCLO,respectively,depending on whether there are overlapping regions between two imme-diately adjacent blocks of variables.Their convergence is established under mild assumptions.We compare PSCLN and PSCLO with the parallel version of the fast iterative thresholding algorithm and the fixed-point continuation method using the Barzilai-Borwein step size and the greedy coordinate block descent method for solving the l1-regularized minimization problems.Our numerical results showthatPSCLN andPSCLOcan run fast and return solutions notworse than those from the state-of-theart algorithms on most test problems.It is also observed that the overlapping domain decomposition scheme is helpful when the data of the problem has certain special structures.

On the Linear Convergence of the Approximate Proximal Splitting Method for Non-smooth Convex Optimization

Consider the problem of minimizing the sum of two convex functions,one being smooth and the other non-smooth.In this paper,we introduce a general class of approximate proximal splitting(APS)methods for solving such minimization problems.Methods in the APS class include many well-known algorithms such as the proximal splitting method,the block coordinate descent method(BCD),and the approximate gradient projection methods for smooth convex optimization.We establish the linear convergence of APS methods under a local error bound assumption.Since the latter is known to hold for compressive sensing and sparse group LASSO problems,our analysis implies the linear convergence of the BCD method for these problems without strong convexity assumption.

An Improved Robust Sparse Convex Clustering

Convex clustering,turning clustering into a convex optimization problem,has drawn wide attention.It overcomes the shortcomings of traditional clustering methods such as K-means,Density-Based Spatial Clustring of Applications with Noise(DBSCAN)and hierarchical clustering that can easily fall into the local optimal solution.However,convex clustering is vulnerable to the occurrence of outlier features,as it uses the Frobenius norm to measure the distance between data points and their corresponding cluster centers and evaluate clusters.To accurately identify outlier features,this paper decomposes data into a clustering structure component and a normalized component that captures outlier features.Different from existing convex clustering evaluating features with the exact measurement,the proposed model can overcome the vast difference in the magnitude of different features and the outlier features can be efficiently identified and removed.To solve the proposed model,we design an efficient algorithm and prove the global convergence of the algorithm.Experiments on both synthetic datasets and UCI datasets demonstrate that the proposed method outperforms the compared approaches in convex clustering.

带有隐式反馈的SVD推荐模型高效求解算法

作为推荐系统的重要组成部分,协同过滤已成为了当今主流的推荐方法之一.其中基于潜在因子的协同过滤常采用SVD推荐模型分析用户喜好.近年来,随着SVD推荐模型研究的深入,SVD++,TrustSVD等一类带有隐式反馈的SVD推荐模型被相继提出.此类模型能更有效地从有限的数据源中挖掘有用信息并取得了较好的效果,因此受到了人们广泛关注.然而,现有文献大多关注于模型设计,缺乏专门针对带有隐式反馈的SVD推荐模型的高效求解算法.为此,本文首先研究了一般性的SVD推荐模型梯度求解框架,然后以SVD++推荐模型为突破口,基于块梯度下降方法设计了高效求解算法BCDSVD++并解决了容量矩阵求逆、稀疏数据优化处理等两个关键问题.实验表明,本文所设计的BCDSVD++算法具有比传统的并行梯度下降法更高效的求解效率及收敛能力.

Energy-efficient data collection for UAV-assisted IoT: Joint trajectory and resource optimization

Internet of Things(IoT) can be conveniently deployed while empowering various applications, where the IoT nodes can form clusters to finish certain missions collectively. As energyefficient operations are critical to prolong the lifetime of the energy-constrained IoT devices, the Unmanned Aerial Vehicle(UAV) can be dispatched to geographically approach the IoT clusters towards energy-efficient IoT transmissions. This paper intends to maximize the system energy efficiency by considering both the IoT transmission energy and UAV propulsion energy, where the UAV trajectory and IoT communication resources are jointly optimized. By applying largesystem analysis and Dinkelbach method, the original fractional optimization is approximated and reformulated in the form of subtraction, and further a block coordinate descent framework is employed to update the UAV trajectory and IoT communication resources iteratively. Extensive simulation results are provided to corroborate the effectiveness of the proposed method.

A Two-stage Adaptive Robust Model for Residential Micro-CHP Expansion Planning

This paper addresses the planning problem of residential micro combined heat and power (micro-CHP) systems (including micro-generation units, auxiliary boilers, and thermal storage tanks) considering the associated technical and economic factors. Since the accurate values of the thermal and electrical loads of this system cannot be exactly predicted for the planning horizon, the thermal and electrical load uncertainties are modeled using a two-stage adaptive robust optimization method based on a polyhedral uncertainty set. A solution method, which is composed of column-and-constraint generation (C&CG) algorithm and block coordinate descent (BCD) method, is proposed to efficiently solve this adaptive robust optimization model. Numerical results from a practical case study show the effective performance of the proposed adaptive robust model for residential micro-CHP planning and its solution method.

Aerial intelligent reflecting surface for secure wireless networks:Secrecy capacity and optimal trajectory strategy

This work investigates the potential of the aerial intelligent reflecting surface(AIRS)in secure communication,where an intelligent reflecting surface(IRS)carried by an unmanned aerial vehicle(UAV)is utilized to help the communication between the ground nodes.Specifically,we formulate the joint design of the AIRS’s deployment and the phase shift to maximize the secrecy rate.To solve the non-convex objective,we develop an alternating optimization(AO)approach,where the phase shift optimization is solved by the Riemannian manifold optimization(RMO)method,while the deployment optimization is handled by the successive convex approximation(SCA)technique.Furthermore,to reduce the computational complexity of the RMO method,an element-wise block coordinate descent(EBCD)based method is employed.Simulation results verify the effect of AIRS in improving the communication security,as well as the importance of designing the deployment and phase shift properly.