Numerical study of learning algorithms on Stiefel manifold

Convex optimization methods are used for many machine learning models such as support vector machine. However, the requirement of a convex formulation can place limitations on machine learning models. In recent years, a number of machine learning methods not requiring convexity have emerged. In this paper, we study non-convex optimization problems on the Stiefel manifold in which the feasible set consists of a set of rectangular matrices with orthonormal column vectors. We present examples of non-convex optimization problems in machine learning and apply three nonlinear optimization methods for finding a local optimal solution; geometric gradient descent method, augmented Lagrangian method of multipliers, and alternating direction method of multipliers. Although the geometric gradient method is often used to solve non-convex optimization problems on the Stiefel manifold, we show that the alternating direction method of multipliers generally produces higher quality numerical solutions within a reasonable computation time.     

On the existence and uniqueness of pairwise stable networks

In this paper we show how externalities between links affect the existence and uniqueness of pairwise stable (PS) networks. For this we introduce the properties ordinal convexity (concavity) and ordinal strategic complements (substitutes) of utility functions on networks. It is shown that there exists at least one PS network if the profile of utility functions is ordinal convex and satisfies the ordinal strategic complements property. On the other hand, ordinal concavity and ordinal strategic substitutes are sufficient for some uniqueness properties of PS networks. Additionally, we elaborate on the relation of the link externality properties to definitions in the literature.     

Definition and properties of a particular notion of convexity

In an attempt to develop a general theory of nonlinear equations with exactly three solutions in general Hilbert spaces, we have noticed that a particular notion of convexity plays a key role. This paper is devoted to the study of some of its basic properties and we show how it generalizes homogeneous convex functionals on the one hand and some special convex functions of one real variable on the other hand. The important case of functionals associated with Nemytskii's operators is treated as an example.     

On jet-convex functions and their tensor products

In this article, we introduce necessary and sufficient conditions for the tensor product of two convex functions to be convex. For our analysis we introduce the notions of true convexity, jet-convexity, true jet-convexity as well as true log-convexity. The links between jet-convex and log-convex functions are elaborated. As an algebraic tool, we introduce the jet product of two symmetric matrices and study some of its properties. We illustrate our results by an application from global optimization, where a convex underestimator for the tensor product of two functions is constructed as the tensor product of convex underestimators of the single functions.     

Convergence analysis of a proximal point algorithm for minimizing differences of functions

Several optimization schemes have been known for convex optimization problems. However, numerical algorithms for solving nonconvex optimization problems are still underdeveloped. A significant progress to go beyond convexity was made by considering the class of functions representable as differences of convex functions. In this paper, we introduce a generalized proximal point algorithm to minimize the difference of a nonconvex function and a convex function. We also study convergence results of this algorithm under the main assumption that the objective function satisfies the Kurdyka–?ojasiewicz property.     

A Level Set Representation Method for N-Dimensional Convex Shape and Applications

In this work,we present a new method for convex shape representation,which is regardless of the dimension of the concerned objects,using level-set approaches.To the best of our knowledge,the proposed prior is the first one which can work for high dimensional objects.Convexity prior is very useful for object completion in computer vision.It is a very challenging task to represent high dimensional convex objects.In this paper,we first prove that the convexity of the considered object is equivalent to the convexity of the associated signed distance function.Then,the second order condition of convex functions is used to characterize the shape convexity equivalently.We apply this new method to two applications:object segmentation with convexity prior and convex hull problem(especially with outliers).For both applications,the involved problems can be written as a general optimization problem with three constraints.An algorithm based on the alternating direction method of multipliers is presented for the optimization problem.Numerical experiments are conducted to verify the effectiveness of the proposed representation method and algorithm.     

A hybrid LP/NLP paradigm for global optimization relaxations

Polyhedral relaxations have been incorporated in a variety of solvers for the global optimization of mixed-integer nonlinear programs. Currently, these relaxations constitute the dominant approach in global optimization practice. In this paper, we introduce a new relaxation paradigm for global optimization. The proposed framework combines polyhedral and convex nonlinear relaxations, along with fail-safe techniques, convexity identification at each node of the branch-and-bound tree, and learning strategies for automatically selecting and switching between polyhedral and nonlinear relaxations and among different local search algorithms in different parts of the search tree. We report computational experiments with the proposed methodology on widely-used test problem collections from the literature, including 369 problems from GlobalLib, 250 problems from MINLPLib, 980 problems from PrincetonLib, and 142 problems from IBMLib. Results show that incorporating the proposed techniques in the BARON software leads to significant reductions in execution time, and increases by 30% the number of problems that are solvable to global optimality within 500 s on a standard workstation.     

Centers of sets with symmetry or cyclicity properties

We introduce an axiomatic formalism for the concept of the center of a set in a Euclidean space. Then we explain how to exploit possible symmetries and possible cyclicities in the set in order to localize its center. Special attention is paid to the determination of centers in cones of matrices. Despite its highly abstract flavor, our work has a strong connection with convex optimization theory. In fact, computing the so-called “incenter” of a solid closed convex cone is a matter of solving a nonsmooth convex optimization program. On the other hand, the concept of the incenter of a solid closed convex cone has a bearing on the complexity analysis and design of algorithms for convex optimization programs under conic constraints.     

面向绿色智能制造的高维多目标动态作业车间调度优化

在当前环境问题日益严峻情况下,绿色智能制造受到广泛关注。在动态柔性作业车间基础上考虑不同机器状态下的能耗情况、机器使用节能方法,构建以极小化总能耗、最大完工时间、机器总负荷和产品质量稳定性为目标的高维多目标绿色动态柔性作业车间调度模型,并设计改进的灰狼优化IMOGWO算法求解该问题。首先,采用反向学习初始化种群策略,以扩大种群多样性;然后,依据多目标问题和标准GWO算法的特点提出多级官员领导机制,并引入POX交叉和逆序变异算子;最后,改进精英保留策略用于多目标优化算法。为证明算法的有效性,设计两组仿真实验分别对三种算法进行比较。实验结果表明,运用本文改进的IMOGWO算法求解多目标问题有更好的收敛性和分布性。     

无线通信系统设计中的两个优化问题和相关优化方法

无线通信系统设计中的许多问题可建模为优化问题.一方面,这些优化问题常常具有高度的非线性性,一般情况下难于求解;另一方面,它们又有自身的特殊结构,例如隐含的凸性、可分性等.利用优化的方法结合问题的特殊结构求解和处理无线通信系统设计问题是近年来学术界研究的热点.本文重点讨论无线通信系统设计中的两个优化问题和相关优化方法,包括多用户干扰信道最大最小准则下的联合传输/接收波束成形设计和多输入多输出(Multi-Input Multi-Output,MIMO)检测问题,主要介绍现代优化技术结合问题的特殊结构在求解和处理上述两个问题的最新进展.     

Uniqueness of solutions of aH ∞ optimization problem and complex geometric convexity

We study uniqueness of an H^∞ optimization problem which is central to the worst case frequency domain system design. It was known that if the so-called sublevel sets are strictly convex inC ^N, then the uniqueness holds. On the other hand, there are examples of non-uniqueness if the sublevel sets are just strictly pseudoconvex. In this paper we prove that uniqueness holds for a type of convexity which is strictly in-between geometric and pseudoconvexity.     

Conjugate duality for multiobjective composed optimization problems

Given a multiobjective optimization problem with the components of the objective function as well as the constraint functions being composed convex functions, we introduce, by using the Fenchel-Moreau conjugate of the functions involved, a suitable dual problem. Under a standard constraint qualification and some convexity as well as monotonicity conditions we prove the existence of strong duality. Finally, some particular cases of this problem are presented.      

Nonlinear optimization and support vector machines

Support Vector Machine (SVM) is one of the most important class of machine learning models and algorithms, and has been successfully applied in various fields. Nonlinear optimization plays a crucial role in SVM methodology, both in defining the machine learning models and in designing convergent and efficient algorithms for large-scale training problems. In this paper we present the convex programming problems underlying SVM focusing on supervised binary classification. We analyze the most important and used optimization methods for SVM training problems, and we discuss how the properties of these problems can be incorporated in designing useful algorithms.     

Interaction between financial risk measures and machine learning methods

The purpose of this article is to review the similarity and difference between financial risk minimization and a class of machine learning methods known as support vector machines, which were independently developed. By recognizing their common features, we can understand them in a unified mathematical framework. On the other hand, by recognizing their difference, we can develop new methods. In particular, employing the coherent measures of risk, we develop a generalized criterion for two-class classification. It includes existing criteria, such as the margin maximization and \(\nu \) -SVM, as special cases. This extension can also be applied to the other type of machine learning methods such as multi-class classification, regression and outlier detection. Although the new criterion is first formulated as a nonconvex optimization, it results in a convex optimization by employing the nonnegative \(\ell _1\) -regularization. Numerical examples demonstrate how the developed methods work for bond rating.     

A review on probabilistic graphical models in evolutionary computation

Thanks to their inherent properties, probabilistic graphical models are one of the prime candidates for machine learning and decision making tasks especially in uncertain domains. Their capabilities, like representation, inference and learning, if used effectively, can greatly help to build intelligent systems that are able to act accordingly in different problem domains. Evolutionary algorithms is one such discipline that has employed probabilistic graphical models to improve the search for optimal solutions in complex problems. This paper shows how probabilistic graphical models have been used in evolutionary algorithms to improve their performance in solving complex problems. Specifically, we give a survey of probabilistic model building-based evolutionary algorithms, called estimation of distribution algorithms, and compare different methods for probabilistic modeling in these algorithms.     

关于度量投影的连续性

本文引入的Ｂａｎａｃｈ空间的（Ｃ－Ｉ）、（Ｃ－Ⅱ），（Ｃ－Ⅲ）等几何性质，证明了如下结果。设Ｍ是Ｂａｎａｃｈ空间的逼近凸子集，如果Ｂａｎａｃｈ空间有性质（Ｃ－Ｉ），（Ｃ－Ⅱ）（Ｃ－Ⅲ），则度量投影ＰＭ连续（范数－范数上半连续，范数－弱上半连续）。这些结果推广了文（４，７，８）相应的定理。最近，Ｄ．Ｋｕｔｚａｒｏｖａ，Ｂｏｒ－Ｌｕｈ Ｌｉｎ等引入了一些新的凸性空间，本文还研究了这些凸性空间中度量投影     

On generalized trade-off directions in nonconvex multiobjective optimization

Trade-off information related to Pareto optimal solutions is important in multiobjective optimization problems with conflicting objectives. Recently, the concept of trade-off directions has been introduced for convex problems. These trade-offs are characterized with the help of tangent cones. Generalized trade-off directions for nonconvex problems can be defined by replacing convex tangent cones with nonconvex contingent cones. Here we study how the convex concepts and results can be generalized into a nonconvex case. Giving up convexity naturally means that we need local instead of global analysis. Received: December 2000 / Accepted: October 2001?Published online February 14, 2002     

On Minty variational principle for nonsmooth vector optimization problems with generalized approximate convexity

In this paper, we consider a nonsmooth vector optimization problem involving locally Lipschitz generalized approximate convex functions and find some relations between approximate convexity and generalized approximate convexity. We establish relationships between vector variational inequalities and nonsmooth vector optimization problem using the generalized approximate convexity as a tool.     

Fundamental results for pointfree convex geometry

Inspired by locale theory, we propose “pointfree convex geometry”. We introduce the notion of convexity algebra as a pointfree convexity space. There are two notions of a point for convexity algebra: one is a chain-prime meet-complete filter and the other is a maximal meet-complete filter. In this paper we show the following: (1) the former notion of a point induces a dual equivalence between the category of “spatial” convexity algebras and the category of “sober” convexity spaces as well as a dual adjunction between the category of convexity algebras and the category of convexity spaces; (2) the latter notion of point induces a dual equivalence between the category of “m-spatial” convexity algebras and the category of “m-sober” convexity spaces. We finally argue that the former notion of a point is more useful than the latter one from a category theoretic point of view and that the former notion of a point actually represents a polytope (or generic point) and the latter notion of a point properly represents a point. We also remark on the close relationships between pointfree convex geometry and domain theory.