Self-organizing maps by difference of convex functions optimization

We offer an efficient approach based on difference of convex functions (DC) optimization for self-organizing maps (SOM). We consider SOM as an optimization problem with a nonsmooth, nonconvex energy function and investigated DC programming and DC algorithm (DCA), an innovative approach in nonconvex optimization framework to effectively solve this problem. Furthermore an appropriate training version of this algorithm is proposed. The numerical results on many real-world datasets show the efficiency of the proposed DCA based algorithms on both quality of solutions and topographic maps.     

基于DC规划的鲁棒模糊核聚类算法

对以径向基核函数和欧拉核函数为代表的鲁棒模糊核聚类算法进行非凸优化,以改善聚类算法目标函数非凸导致的局部解问题.采用凸差规划(DCP)将目标函数转化为2个凸函数之差的形式,减缓局部解的不良性,提高聚类性能.采用凸差算法(DCA)优化求解DCP问题,能快速搜索到相对更优的解,并保持聚类的鲁棒性.在UCI数据集上的实验验证基于DCP的鲁棒模糊核聚类算法对大规模数据集表现出相对更优的聚类性能.     

An Alternating Augmented Lagrangian method for constrained nonconvex optimization

ABSTRACT

We consider the problem of minimizing a smooth nonconvex function over a structured convex feasible set, that is, defined by two sets of constraints that are easy to treat when considered separately. In order to exploit the structure of the problem, we define an equivalent formulation by duplicating the variables and we consider the augmented Lagrangian of this latter formulation. Following the idea of the Alternating Direction Method of Multipliers (ADMM), we propose an algorithm where a two-blocks decomposition method is embedded within an augmented Lagrangian framework. The peculiarities of the proposed algorithm are the following: (1) the computation of the exact solution of a possibly nonconvex subproblem is not required; (2) the penalty parameter is iteratively updated once an approximated stationary point of the augmented Lagrangian is determined. Global convergence results are stated under mild assumptions and without requiring convexity of the objective function. Although the primary aim of the paper is theoretical, we perform numerical experiments on a nonconvex problem arising in machine learning, and the obtained results show the practical advantages of the proposed approach with respect to classical ADMM.     

Globally convergent decomposition methods for nonconvex optimization problems

In this paper we consider nonlinear optimization problems of a separable form with nonconvex objective and convex constraints. A convexification procedure preserving separability is given in order that primal-dual methods are applicable. A globally convergent algorithm observing computational aspects is given. This algorithm was applied to a real world problem with 1007 variables and 4030 constraints for controlling the heads of a hydroenergy power station.     

DC programming and DCA for solving Brugnano–Casulli piecewise linear systems

Piecewise linear optimization is one of the most frequently used optimization models in practice, such as transportation, finance and supply-chain management. In this paper, we investigate a particular piecewise linear optimization that is optimizing the norm of piecewise linear functions (NPLF). Specifically, we are interested in solving a class of Brugnano–Casulli piecewise linear systems (PLS), which can be reformulated as an NPLF problem. Speaking generally, the NPLF is considered as an optimization problem with a nonsmooth, nonconvex objective function. A new and efficient optimization approach based on DC (Difference of Convex functions) programming and DCA (DC Algorithms) is developed. With a suitable DC formulation, we design a DCA scheme, named ℓ₁-DCA, for the problem of optimizing the ℓ₁-norm of NPLF. Thanks to particular properties of the problem, we prove that under some conditions, our proposed algorithm converges to an exact solution after a finite number of iterations. In addition, when a nonglobal solution is found, a numerical procedure is introduced to find a feasible point having a smaller objective value and to restart ℓ₁-DCA at this point. Several numerical experiments illustrate these interesting convergence properties. Moreover, we also present an application to the free-surface hydrodynamic problem, where the correct numerical modeling often requires to have the solution of special PLS, with the aim of showing the efficiency of the proposed method.     

Nonsmooth DC programming approach to clusterwise linear regression: optimality conditions and algorithms

The clusterwise linear regression problem is formulated as a nonsmooth nonconvex optimization problem using the squared regression error function. The objective function in this problem is represented as a difference of convex functions. Optimality conditions are derived, and an algorithm is designed based on such a representation. An incremental approach is proposed to generate starting solutions. The algorithm is tested on small to large data sets.     

DC optimization approach to robust controls: the optimal scaling value problem

The optimal scaling problem (OSP) for constant scaling in output feedback control is an inherently difficult nonconvex problem for which in general existing local search algorithms can at best locate a local solution. However, it can be restated as a problem of globally minimizing a convex function under DC constraints, i.e., constraints that can be expressed in terms of differences of convex functions. A particular structure of this DC optimization problem is that it becomes convex when a relatively small number of "complicating" variables are held fixed. We propose alternative branch and bound algorithms for OSP, which exploit this structure by branching upon the complicating variables and use adaptive sub-division strategies to speed-up the convergence to the global solution.     

Optimized Scheduled Multiple Access Control for Wireless Sensor Networks

We consider wireless sensor networks with multiple sensor modalities that capture data to be transported over multiple frequency channels to potentially multiple gateways. We study a general problem of maximizing a utility function of achievable transmission rates between communicating nodes. Decisions involve routing, transmission scheduling, power control, and channel selection, while constraints include physical communication constraints, interference constraints, and fairness constraints. Due to its structure the formulation grows exponentially with the size of the network. Drawing upon large-scale decomposition ideas in mathematical programming, we develop a cutting-plane algorithm and show that it terminates in a finite number of iterations. Every iteration requires the solution of a subproblem which is NP-hard. To solve the subproblem we i) devise a particular relaxation that is solvable in polynomial time and ii) leverage polynomial-time approximation schemes. A combination of both approaches enables an improved decomposition algorithm which is efficient for solving large problem instances.      

A heuristic method for simultaneous tower and pattern-free field optimization on solar power systems

A heuristic method for optimizing a solar power tower system is proposed, in which both heliostat field (heliostat locations and number) and the tower (tower height and receiver size) are simultaneously considered.Maximizing the thermal energy collected per unit cost leads to a difficult optimization problem due to its characteristics: it has a nonconvex black-box objective function with computationally expensive evaluation and nonconvex constraints.The proposed method sequentially optimizes the field layout for a given tower configuration and then, the tower design is optimized for the previously obtained field layout. A greedy-based heuristic algorithm is presented to address the heliostat location problem. This algorithm follows a pattern-free method. The only constraints to be considered are the field region and the nonconvex constraints (which allow heliostats to not collide).The absence of a geometrical pattern to design the field and the simultaneous optimization of the field and the tower designs make this approach different from the existing ones. Our method is compared against other proposals in the literature of heliostat field optimization.     

Nonconvex dynamic spectrum allocation for cognitive radio networks via particle swarm optimization and simulated annealing

Dynamic spectrum access is a promising technique designed to meet the challenge of rapidly growing demands for broadband access in cognitive radio networks. By utilizing the allocated spectrum, cognitive radio devices can provide high throughput and low latency communications. This paper introduces an efficient dynamic spectrum allocation algorithm in cognitive radio networks based on the network utility maximization framework. The objective function in this optimization problem is always nonconvex, which makes the problem difficult to solve. Prior works on network resource optimization always transformed the nonconvex optimization problem into a convex one under some strict assumptions, which do not meet the actual networks. We solve the nonconvex optimization problem directly using an improved particle swarm optimization (PSO) method. Simulated annealing (SA), combined with PSO to form the PSOSA algorithm, overcomes the inherent defects and disadvantages of these two individual components. Simulations show that the proposed solution achieves significant throughput compared with existing approaches, and it is efficient in solving the nonconvex optimization problem.     

A Fully Distributed Approach to Optimal Energy Scheduling of Users and Generators Considering a Novel Combined Neurodynamic Algorithm in Smart Grid

A fully distributed microgrid system model is presented in this paper. In the user side, two types of load and plug-in electric vehicles are considered to schedule energy for more benefits. The charging and discharging states of the electric vehicles are represented by the zero-one variables with more flexibility. To solve the nonconvex optimization problem of the users, a novel neurodynamic algorithm which combines the neural network algorithm with the differential evolution algorithm is designed and its convergence speed is faster. A distributed algorithm with a new approach to deal with the inequality constraints is used to solve the convex optimization problem of the generators which can protect their privacy. Simulation results and comparative experiments show that the model and algorithms are effective.      

On concave constraint functions and duality in predominantly black-and-white topology optimization

We study the ‘classical’ discrete, solid-void or black-and-white topology optimization problem, in which minimum compliance is sought, subject to constraints on the available material resource. We assume that this problem is solved using methods that relax the discreteness requirements during intermediate steps, and that the associated programming problems are solved using sequential approximate optimization (SAO) algorithms based on duality. More specifically, we assume that the advantages of the well-known Falk dual are exploited. Such algorithms represent the state-of-the-art in (large-scale) topology optimization when multiple constraints are present; an important example being the method of moving asymptotes (MMA).We depart by noting that the aforementioned SAO algorithms are invariably formulated using strictly convex subproblems. We then numerically illustrate that strictly concave constraint functions, like those present in volumetric penalization, as recently proposed by Bruns and co-workers, may increase the difficulty of the topology optimization problem when strictly convex approximations are used in the SAO algorithm. In turn, volumetric penalization methods are of notable importance, since they seem to hold much promise for generating predominantly solid-void or discrete designs.We then argue that the nonconvex problems we study may in some instances efficiently be solved using dual SAO methods based on nonconvex (strictly concave) approximations which exhibit monotonicity with respect to the design variables.Indeed, for the topology problem resulting from SIMP-like volumetric penalization, we show explicitly that convex approximations are not necessary. Even though the volumetric penalization constraint is strictly concave, the maximum of the resulting dual subproblem still corresponds to the optimum of the original primal approximate subproblem.     

Inexact proximal stochastic second-order methods for nonconvex composite optimization

ABSTRACT

In this paper, we propose a framework of Inexact Proximal Stochastic Second-order (IPSS) method for solving nonconvex optimization problems, whose objective function consists of an average of finitely many, possibly weakly, smooth functions and a convex but possibly nonsmooth function. At each iteration, IPSS inexactly solves a proximal subproblem constructed by using some positive definite matrix which could capture the second-order information of original problem. Proper tolerances are given for the subproblem solution in order to maintain global convergence and the desired overall complexity of the algorithm. Under mild conditions, we analyse the computational complexity related to the evaluations on the component gradient of the smooth function. We also investigate the number of evaluations of subgradient when using an iterative subgradient method to solve the subproblem. In addition, based on IPSS, we propose a linearly convergent algorithm under the proximal Polyak–?ojasiewicz condition. Finally, we extend the analysis to problems with weakly smooth function and obtain the computational complexity accordingly.     

Mixed coordination method for long-horizon optimal control problems

We present a new approach to solving long-horizon, discrete-time optimal control problems using the mixed coordination method. The idea is to decompose a long-horizon problem into subproblems along the time axis. The requirement that the initial state of a subproblem equal the terminal state of the preceding subproblem is relaxed by using Lagrange multipliers. The Lagrange multipliers and initial state of each subproblem are then selected as high-level variables. The equivalence of the two-level formulation and the original problem is proved for both convex and non-convex cases. The low-level subproblems are solved in parallel using extended differential dynamic programming (DDP). An efficient way to find the gradient and hessian of a low-level objective function with respect to high-level variables is developed. The high-level problem is solved using the modified Newton method. An effective procedure is developed to select initial values of multipliers based on the initial trajectory. The method can convexify the high-level problem while maintaining the separability of an originally non-convex problem. The method performs better and faster than one-level DDP for both convex and non-convex test problems.     

NOMA网络中考虑回程约束的联合资源分配算法

针对应用非正交多址接入（NOMA）技术的异构蜂窝网络,提出了一种具有回程容量约束的能效最大化的功率和带宽分配算法。首先,考虑小蜂窝发射功率约束、小蜂窝速率约束和回程链路容量约束,构建了功率和带宽分配模型。然后,对于功率分配,利用凸差（DC）规划和函数的拟凹性将原问题转换为等价的凸问题,并使用凸差迭代法和二分法求得全局最优解;对于回程链路带宽分配,将其转换为可行性问题并给出了解析解。仿真结果显示,该方案的能量效率高于相同场景中的已有方案。     

基于lP范数的非凸低秩张量最小化

在低秩矩阵、张量最小化问题中,凸函数容易求得最优解,而非凸函数可以得到更低秩的局部解.文中基于非凸替换函数的低秩张量恢复问题,提出基于l_p范数的非凸张量模型.采用迭代加权核范数算法求解模型,实现低秩张量最小化.在合成数据和真实图像上的大量实验验证文中方法的恢复性能.     

蜂窝网络下基于max-min公平性的D2D功率分配

针对多个终端直通通信（D2D）用户共享多个蜂窝用户资源的公平性问题,在保证蜂窝用户速率的前提下,提出了基于最大最小公平性（max-min fairness）的功率分配算法。该算法首先将非凸优化问题转化为含凸函数的差（DC）规划问题,然后采用凸近似的全局优化算法和对分算法对D2D实现功率优化。仿真结果表明,与只采用凸近似的全局优化算法相比,所提算法收敛性更优,同时最大化了瓶颈用户的速率。     

Successive Chebyshev pseudospectral convex optimization method for nonlinear optimal control problems

This article aims at proposing a successive Chebyshev pseudospectral convex optimization method for solving general nonlinear optimal control problems (OCPs). First, Chebyshev pseudospectral discrete scheme is used to discretize a general nonlinear OCP. At the same time, a convex subproblem is formulated by using the first-order Taylor expansion to convexify the discretized nonlinear dynamic constraints. Second, a trust-region penalty term is added to the performance index of the subproblem, and a successive convex optimization algorithm is proposed to solve the subproblem iteratively. Noted that the trust-region penalty parameters can be adjusted according to the linearization error in iterative process, which improves convergence rate. Third, the Karush–Kuhn–Tucker conditions of the subproblem are derived, and furthermore, a proof is given to show that the algorithm will iteratively converge to the subproblem. Additionally, the global convergence of the algorithm is analyzed and proved, which is based on three key lemmas. Finally, the orbit transfer problem of spacecraft is used to test the performance of the proposed method. The simulation results demonstrate the optimal control is bang-bang form, which is consistent with the result of theoretical proof. Also, the algorithm is of efficiency, fast convergence rate, and high accuracy. Therefore, the proposed method provides a new approach for solving nonlinear OCPs online and has great potential in engineering practice.     

应用突函数差异算法进行癌症分类的基因选择(英文)

研究了有关癌症分类的基因选择问题。开发了集成的基于平滑剪切绝对偏差罚分的SVM—特征选择方法,直接最小化分类器的性能。为解决优化问题,应用了突函数差异算法(difference of convex functionsal-gorithms,DCA)这一进行非突连续优化的通用框架,致使连续线性规划算法有限收敛。真实数据集上的先验实验表明算法达到了预想目标:在压缩大量属性的同时,保持了较小分类差错。