带基数约束的次模+超模(BP)函数最大化问题的流算法

本文研究在基数约束下具有单调性的次模+超模函数最大化问题的流模型。该问题在数据处理、机器学习和人工智能等方面都有广泛应用。借助于目标函数的收益递减率（$\gamma$）,我们设计了单轮读取数据的过滤-流算法,并结合次模、超模函数的全局曲率（$\kappa^{g}$）得到算法的近似比为$\min\left\{\frac{（1-\varepsilon）\gamma}{2^{\gamma}},1-\frac{\gamma}{2^{\gamma}（1-\kappa^{g}）^{2}}\right\}$。数值实验验证了过滤-流算法对BP最大化问题的有效性并且得出：次模函数和超模函数在同量级条件下,能保证在较少的时间内得到与贪婪算法相同的最优值。     

次模函数最大化的流算法综述

次模函数优化在计算机科学、数学、经济学等学科得到广泛研究.大数据环境下的次模优化是相对较新的研究领域,受到更多关注.特别地,考虑基于流模型的次模最大化问题.在该问题中,数据以流的形式呈现,其目的是从数据流中抽取满足某些特性的稀疏子集,最大化次模收益函数值.介绍了基于流模型的次模最大化问题的阈值和优先权方法,同时也介绍了若干次模最大化变形的流算法进展.     

带模糊约束的最大流问题

首次提出带模糊约束的最大流问题,并根据网络中的弧容量限制是否带有模糊性,分别建立数学模型,给出求解这两个模型的相应算法和有关实例。     

一般约束优化基于识别函数的模松弛算法

借助于半罚函数和产生工作集的识别函数以及模松弛SQP算法思想, 本文建立了求解带等式及不等式约束优化的一个新算法. 每次迭代中, 算法的搜索方向由一个简化的二次规划子问题及一个简化的线性方程组产生. 算法在不包含严格互补性的温和条件下具有全局收敛性和超线性收敛性. 最后给出了算法初步的数值试验报告.     

约束优化问题的单参数填充函数算法

本文研究约束优化问题的全局优化确定性方法.基于填充函数的定义,具体构造出了一个新的单参数填充函数并做了相关理论证明.结合SQP和BFGS局部极小化算法设计了新的填充函数全局优化算法.数值实验表明,该算法可行有效,具有良好的全局寻优能力.     

求解带箱式约束全局优化问题的滤子填充函数方法

提出一个基于滤子技术的填充函数算法, 用于求解带箱式约束的非凸全局优化问题. 填充函数算法是求解全局优化问题的有效方法之一, 而滤子技术以其良好的数值效果广泛应用于局部优化算法中. 为优化填充函数方法, 应用滤子来监控迭代过程. 首先给出一个新的填充函数并讨论了其特性, 在此基础上提出了理论算法及算法性质. 最后列出数值实验结果以说明算法的有效性.     

带模糊约束的最小费用流问题

本文首次提出了带模糊约束的最小费用流问题,建立了相应的数学模型并给出了求解这一模型的有关算法。最后,给出了一个具体实例。     

利用Fisher函数解非线性不等式约束优化问题的梯度投影算法

本文将利用梯度投影与Fisher函数提出一个新的二阶段搜索方向,给出相应的解非线性不等式约束优化问题的梯度投影算法,并证明了该算法具有全局收敛性.     

线性约束三次规划问题的全局最优性必要条件和最优化算法

讨论了带线性不等式约束三次规划问题的最优性条件和最优化算法. 首先, 讨论了带有线性不等式约束三次规划问题的 全局最优性必要条件. 然后, 利用全局最优性必要条件, 设计了解线性约束三次规划问题的一个新的局部最优化算法(强局部最优化算法). 再利用辅助函数和所给出的新的局部最优化算法, 设计了带有线性不等式约束三 规划问题的全局最优化算法. 最后, 数值算例说明给出的最优化算法是可行的、有效的.     

一类求解约束全局优化问题的填充函数

本文构造了一类求解约束全局优化问题的填充函数,并在适当的假设条件下, 证明了其填充性质及其它分析性质; 此外,根据所构造的填充函数设计了相应的算法, 并给出了数值试验结果, 以说明所构造填充函数方法的有效性.     

Maximizing DR-submodular+supermodular functions on the integer lattice subject to a cardinality constraint

Journal of Global Optimization - Arising from practical problems such as in sensor placement and influence maximization in social network, submodular and non-submodular maximization on the integer...     

An exact method for constrained maximization of the conditional value-at-risk of a class of stochastic submodular functions

We consider a class of risk-averse submodular maximization problems (RASM) where the objective is the conditional value-at-risk (CVaR) of a random nondecreasing submodular function at a given risk level. We propose valid inequalities and an exact general method for solving RASM under the assumption that we have an efficient oracle that computes the CVaR of the random function. We demonstrate the proposed method on a stochastic set covering problem that admits an efficient CVaR oracle for the random coverage function.     

Approximation bounds for quadratic maximization and max-cut problems with semidefinite programming relaxation

In this paper,we consider a class of quadratic maximization problems.For a subclass of the problems,we show that the SDP relaxation approach yields an approximation solution with the ratio is dependent on the data of the problem with α being a uniform lower bound.In light of this new bound,we show that the actual worst-case performance ratio of the SDP relaxation approach (with the triangle inequalities added) is at least α δd if every weight is strictly positive,where δd ＞ 0 is a constant depending on the problem dimension and data.     

Utility maximization under risk constraints and incomplete information for a market with a change point

In this article, we consider an optimization problem of expected utility maximization of continuous-time trading in a financial market. This trading is constrained by a benchmark for a utility-based shortfall risk measure. The market consists of one asset whose price process is modelled by a Geometric Brownian motion where the market parameters change at a random time. The information flow is modelled by initially and progressively enlarged filtrations which represent the knowledge about the price process, the Brownian motion and the random time. We solve the maximization problem and give the optimal terminal wealth depending on these different filtrations for general utility functions by using martingale representation results for the corresponding filtration.     

带次模惩罚的优先设施选址问题的近似算法

研究带次模惩罚的优先设施选址问题, 每个顾客都有一定的服务水平要求, 开设的设施只有满足了顾客的服务水平要求, 才能为顾客提供服务, 没被服务的顾客对应一定的次模惩罚费用. 目标是使得开设费用、连接费用与次模惩罚费用之和最小. 给出该问题的整数规划、 线性规划松弛及其对偶规划. 基于原始对偶和贪婪增广技巧, 给出该问题的两个近似算法, 得到的近似比分别为3和2.375.     

Competitive strategies for an online generalized assignment problem with a service consecution constraint

This work studies a variant of the online generalized assignment problem, where there are m ? 2 heterogeneous servers to process n requests which arrive one by one over time. Each request must either be assigned to one of the servers or be rejected upon its arrival, before knowing any information of future requests. There is a corresponding weight (or revenue) for assigning each request to a server, and the objective is to maximize the total weights obtained from all the requests. We study the above problem with a service consecution constraint, such that at any time each server is only allowed to process up to d consecutive requests.     

Extended formulations for the cardinality constrained subtree of a tree problem

Given a tree with n nodes, we consider the problem of finding the most profitable subtree of that tree with at most K nodes which is known as the Cardinality Subtree of a Tree Problem. We present a new exact linear extended formulation with O(nK) two-indexed variables and O(nK) constraints.