Lossless convexification of a class of optimal control problems with non-convex control constraints

We consider a class of finite time horizon optimal control problems for continuous time linear systems with a convex cost, convex state constraints and non-convex control constraints. We propose a convex relaxation of the non-convex control constraints, and prove that the optimal solution of the relaxed problem is also an optimal solution for the original problem, which is referred to as the lossless convexification of the optimal control problem. The lossless convexification enables the use of interior point methods of convex optimization to obtain globally optimal solutions of the original non-convex optimal control problem. The solution approach is demonstrated on a number of planetary soft landing optimal control problems.     

The chemical equilibrium problem for a multiphase system formulated as a convex program

We consider the chemical equilibrium problem for a multiphase system: Assuming that the free energies of the individual phases are convex functions, the equilibrium problem is formulated as a convex program. The optimality conditions for this program allow a direct test of the stability of the system's phases relative to a given equilibrium. We then extend our analysis to systems for which the free energies are not necessarily convex. By introducing “convexified” molar free energies we show how the “non-convex” problems can be solved completely in terms of an associated “convex” problem.     

基于智能反射面辅助与无线中继的无人机协作通信系统优化算法

针对采用智能反射面（RIS）辅助与解码转发中继的无人机协作通信系统,研究了RIS反射相位、无人机部署位置和无线中继传输时隙联合优化算法。首先根据协作系统传输协议,建立了以最大化系统端到端信息传输可达速率为目标的资源分配联合优化问题。该问题非凸,为此提出一个交替优化算法,将该非凸问题分解为分别对RIS反射相位、无人机部署位置和协作中继传输时隙进行优化的三个子问题。其中RIS反射相位优化子问题和无人机部署位置优化子问题仍非凸,为此,分别采用半定松弛方法和提出一种基于连续凸逼近的局部区域优化方法进行求解,通过三个子问题的交替和迭代优化得到原问题的次优解。仿真结果验证了提出的联合优化算法获得的系统端到端信息传输可达速率优于其他的基准方案,并发现无人机应部署靠近中继或RIS的上方,其结果与系统的信噪比、RIS的反射元件数量以及RIS和中继所处地理位置等因素有关。     

Truss topology optimization with discrete design variables—Guaranteed global optimality and benchmark examples

This paper considers the problem of optimal truss topology design subject to multiple loading conditions. We minimize a weighted average of the compliances subject to a volume constraint. Based on the ground structure approach, the cross-sectional areas are chosen as the design variables. While this problem is well-studied for continuous bar areas, we consider in this study the case of discrete areas. This problem is of major practical relevance if the truss must be built from pre-produced bars with given areas. As a special case, we consider the design problem for a single available bar area, i.e., a 0/1 problem. In contrast to the heuristic methods considered in many other approaches, our goal is to compute guaranteed globally optimal structures. This is done by a branch-and-bound method for which convergence can be proven. In this branch-and-bound framework, lower bounds of the optimal objective function values are calculated by treating a sequence of continuous but non-convex relaxations of the original mixed-integer problem. The main effect of using this approach lies in the fact that these relaxed problems can be equivalently reformulated as convex problems and, thus, can be solved to global optimality. In addition, these convex problems can be further relaxed to quadratic programs for which very efficient numerical solution procedures exist. By exploiting this special problem structure, much larger problem instances can be solved to global optimality compared to similar mixed-integer problems. The main intention of this paper is to provide optimal solutions for single and multiple load benchmark examples, which can be used for testing and validating other methods or heuristics for the treatment of this discrete topology design problem.     

Evolutionary approach on connectivity-based sensor network localization

The sensor network localization based on connectivity can be modeled as a non-convex optimization problem. It can be argued that the actual problem should be represented as an optimization problem with both convex and non-convex constraints. A two-objective evolutionary algorithm is proposed which utilizes the result of all convex constraints to provide a starting point on the location of the unknown nodes and then searches for a solution to satisfy all the convex and non-convex constraints of the problem. The final solution can reach the most suitable configuration of the unknown nodes because all the information on the constraints (convex and non-convex) related to connectivity have been used. Compared with current models that only consider the nodes that have connections, this method considers not only the connection constraints, but also the disconnection constraints. As a MOEA (Multi-Objective Evolution Algorithm), PAES (Pareto Archived Evolution Strategy) is used to solve the problem. Simulation results have shown that better solution can be obtained through the use of this method when compared with those produced by other methods.     

Optimal motion planning for parallel robots via convex optimization and receding horizon

In this paper, the problem of motion planning for parallel robots in the presence of static and dynamic obstacles has been investigated. The proposed algorithm can be regarded as a synergy of convex optimization with discrete optimization and receding horizon. This algorithm has several advantages, including absence of trapping in local optimums and a high computational speed. This problem has been fully analyzed for two three-DOF parallel robots, ie 3s-RPR parallel mechanism and the so-called Tripteron, while the shortest path is selected as the objective function. It should be noted that the first case study is a parallel mechanism with complex singularity loci expression from a convex optimization problem standpoint, while the second case is a parallel manipulator for which each limb has two links, an issue which increases the complexity of the optimization problem. Since some of the constraints are non-convex, two approaches are introduced in order to convexify them: (1) A McCormick-based relaxation merged with a branch-and-prune algorithm to prevent it from becoming too loose and (2) a first-order approximation which linearizes the non-convex quadratic constraints. The computational time for the approaches presented in this paper is considerably low, which will pave the way for online applications.     

Strength-based topology optimisation of plastic isotropic von Mises materials

Conventionally, topology optimisation is formulated as a non-linear optimisation problem, where the material is distributed in a manner which maximises the stiffness of the structure. Due to the nature of non-linear, non-convex optimisation problems, a multitude of local optima will exist and the solution will depend on the starting point. Moreover, while stress is an essential consideration in topology optimisation, accounting for the stress locally requires a large number of constraints to be considered in the optimisation problem; therefore, global methods are often deployed to alleviate this with less control of the stress field as a consequence. In the present work, a strength-based formulation with stress-based elements is introduced for plastic isotropic von Mises materials. The formulation results in a convex optimisation problem which ensures that any local optimum is the global optimum, and the problems can be solved efficiently using interior point methods. Four plane stress elements are introduced and several examples illustrate the strength of the convex stress-based formulation including mesh independence, rapid convergence and near-linear time complexity.

     

基于凸松弛方法的医学 B 超图像快速分割

利用活动轮廓线方法进行图像分割的一个重要缺陷是目标函数是非凸的, 这不仅使得分割结果容易陷于局部极小, 而且还使得一些快速算法无法开展.本文首先从贝叶斯风险估计的方法出发,针对B超幅度图像, 给出一种基于Rayleigh分布的活动轮廓线模型. 然后结合凸松弛的方法,得到一个新的放松的凸模型.原有模型和放松后模型的关系可由定理1给出. 最后结合分裂Bregman算法, 给出基于B超分割模型的快速算法.与传统梯度下降法相比较,本文提出的算法不仅能得到全局最优解,而且在算法收敛速度上也 大大优于梯度下降法.     

Some symmetry results for optimal solutions in structural optimization

In the present paper, some symmetry results for optimal solutions in structural optimization have been proposed and proven. It is found that under some invariant assumptions, for many structural optimization problems that can be formulated as convex programs, there exists at least one symmetric global optimal solution if the prescribed loading and support conditions are symmetric. Furthermore, for some specific non-convex cases, a weaker result is also presented.     

A Parallel Proximal Splitting Method for Disparity Estimation from Multicomponent Images Under Illumination Variation

Proximal splitting algorithms play a central role in finding the numerical solution of convex optimization problems. This paper addresses the problem of stereo matching of multi-component images by jointly estimating the disparity and the illumination variation. The global formulation being non-convex, the problem is addressed by solving a sequence of convex relaxations. Each convex relaxation is non trivial and involves many constraints aiming at imposing some regularity on the solution. Experiments demonstrate that the method is efficient and provides better results compared with other approaches.     

Variation-based approach to image segmentation

A new approach to image segmentation is presented using a variation framework. Re-garding the edge points as interpolating points and minimizing an energy functional to interpolate a smooth threshold surface it carries out the image segmentation. In order to preserve the edge informa-tion of the original image in the threshold surface, without unduly sharping the edge of the image, a non-convex energy functional is adopted. A relaxation algorithm with the property of global conver-gence, for solving the optimization problem, is proposed by introducing a binary energy. As a result the non-convex optimization problem is transformed into a series of convex optimization problems, and the problem of slow convergence or nonconvergence is solved. The presented method is also tested experimentally. Finally the method of determining the parameters in optimizing is also explored.     

Variation-based approach to image segmentation Variation-based approach to image segmentation

A new approach to image segmentation is presented using a variation framework. Regarding the edge points as interpolating points and minimizing an energy functional to interpolate a smooth threshold surface it carries out the image segmentation. In order to preserve the edge information of the original image in the threshold surface, without unduly sharping the edge of the image, a non-convex energy functional is adopted. A relaxation algorithm with the property of global convergence, for solving the optimization problem, is proposed by introducing a binary energy. As a result the non-convex optimization problem is transformed into a series of convex optimization problems, and the problem of slow convergence or nonconvergence is solved. The presented method is also tested experimentally. Finally the method of determining the parameters in optimizing is also explored.     

A location–inventory supply chain problem: Reformulation and piecewise linearization

In this paper, we study a two-echelon inventory management problem with multiple warehouses and retailers. The problem is a natural extension to the well-known one-warehouse multi-retailer inventory problem. The problem is formulated as a mixed integer non-linear program such that its continuous relaxation is non-convex. We propose an equivalent formulation with fewer non-linear terms in the objective function so that the continuous relaxation of the new model is a convex optimization problem. We use piecewise linearization to transform the resulting MINLP to a mixed integer program and we solve it using CPLEX. Through numerical experiments, we compare the solutions obtained by solving the new formulation using CPLEX with two previously published Lagrangian relaxation based heuristics to solve the original mixed integer non-linear program. We demonstrate that the new approach is capable of providing almost the same solutions without the need of using specialized algorithms. This important contribution further implies that additional variants of the problem, such as multiple products, capacitated warehouses and routing, can be added to result in a problem that will again be solvable by commercial optimization software, while the respective Lagrangian heuristics will fail to solve such variants or extended problems.     

Scalable anomaly detection in large homogeneous populations

Anomaly detection in large populations is a challenging but highly relevant problem. It is essentially a multi-hypothesis problem, with a hypothesis for every division of the systems into normal and anomalous systems. The number of hypothesis grows rapidly with the number of systems and approximate solutions become a necessity for any problem of practical interest. In this paper we take an optimization approach to this multi-hypothesis problem. It is first shown to be equivalent to a non-convex combinatorial optimization problem and then is relaxed to a convex optimization problem that can be solved distributively on the systems and that stays computationally tractable as the number of systems increase. An interesting property of the proposed method is that it can under certain conditions be shown to give exactly the same result as the combinatorial multi-hypothesis problem and the relaxation is hence tight.     

一类线性离散时滞大系统的分散镇定

用一组线性矩阵不等式给出一类线性离散时滞大系统分散能镇定的一个充分条件,进而,通过建立和求解一个凸优化问题,提出了具有较反馈增益参数的分散稳定化状态反馈控制律的设计方法,所得到的控制器不仅使得闭环境系统是稳定的,而且还可以使得闭环系统状态具有给定的衰减度。     

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.     

Asymptotic Stability of Cohen–Grossberg BAM Neutral Type Neural Networks with Distributed Time Varying Delays

This paper is concerned with the problem of asymptotic stability of neutral type Cohen–Grossberg BAM neural networks with discrete and distributed time-varying delays. By constructing a suitable Lyapunov–Krasovskii functional (LKF), reciprocal convex technique and Jensen’s inequality are used to delay-dependent conditions are established to analysis the asymptotic stability of Cohen–Grossberg BAM neural networks with discrete and distributed time-varying delays. These stability conditions are formulated as linear matrix inequalities (LMIs) which can be easily solved by various convex optimization algorithms. Finally numerical examples are given to illustrate the usefulness of our proposed method.     

Energy-efficient joint path-following for attitude-fixed space manipulators with bounds on completion time and motor voltage/current

This paper investigates the minimum-energy joint path-following problem for space manipulators whose base attitude is stabilized by reaction wheels. In the problem, manipulator joint path is specified for rest-to-rest motion and constraints are imposed as the upper bound on both motion completion time and the voltage/current limits of DC motors in manipulator joints and reaction wheels. We suggest a simple two-stage algorithm to address this problem. The algorithm first tries to find a global optimal solution by solving a relaxed convex problem. If the convex relaxation is not successful, then the algorithm solves subproblems iteratively to find a suboptimal solution. Since both problems are formulated as second-order cone programming (SOCP) form, they can be solved efficiently using dedicated SOCP solvers. The effectiveness of the proposed method is verified by numerical experiments.     

一种基于混合NOMA的IRS-MEC系统能量效率优化方案

在移动边缘计算系统（MEC）中结合智能反射面（IRS）和资源分配策略以提高系统能量效率是当前国内外研究的热点。基于混合非正交多址（NOMA）传输模式,通过对用户的本地运算频率、传输功率、传输时间和智能反射面离散相移的联合优化,实现智能反射面辅助的移动边缘计算系统能量效率最大化。由于优化过程涉及难以求解的非凸分式规划问题,提出了Dinkelbach-SCA的两步迭代算法：首先利用Dinkelbach方法将初始问题转换成易于求解的形式,通过分离变量对智能反射面离散相移进行优化;其次为了解耦传输功率与时间之间的耦合关系,引入辅助变量,并结合逐次凸逼近（SCA）方法将非凸问题转换成凸问题,求出优化解。仿真结果表明采用的系统方案的能量效率优于其他对比方案,并发现系统的能量效率随用户2的最小计算数据量减少而提升。     

不确定离散系统的最优保性能控制*

对一类具有范数有界时变参数不确定性的离散时间线性系统和一个二次型性能指标,研究其最优保性能状态反馈控制律的设计问题。