Joint Bandwidth Allocation and Path Selection in WANs with Path Cardinality Constraints

In this paper,we study the joint bandwidth allocation and path selection problem,which is an extension of the well-known network utility maximization(NUM)problem,via solving a multi-objective minimization problem under path cardinality constraints.Specifically,such a problem formulation captures various types of objectives including proportional fairness,average delay,as well as load balancing.In addition,in order to handle the"unsplittable flows",path cardinality constraints are added,making the resulting optimization problem quite challenging to solve due to intrinsic nonsmoothness and nonconvexity.Almost all existing works deal with such a problem using relaxation techniques to transform it into a convex optimization problem.However,we provide a novel solution framework based on the linearized alternating direction method of multipliers(LADMM)to split the original problem with coupling terms into several subproblems.We then derive that these subproblems,albeit nonconvex nonsmooth,are actually simple to solve and easy to implement,which can be of independent interest.Under some mild assumptions,we prove that any limiting point of the generated sequence of the proposed algorithm is a stationary point.Numerical simulations are performed to demonstrate the advantages of our proposed algorithm compared with various baselines.

Recent Advances in Mathematical Programming with Semi-continuous Variables and Cardinality Constraint

Mathematical programming problems with semi-continuous variables and cardinality constraint have many applications,including production planning,portfolio selection,compressed sensing and subset selection in regression.This class of problems can be modeled as mixed-integer programs with special structures and are in general NP-hard.In the past few years,based on new reformulations,approximation and relaxation techniques,promising exact and approximate methods have been developed.We survey in this paper these recent developments for this challenging class of mathematical programming problems.

A comparative study of heuristic methods for cardinality constrained portfolio optimization

The cardinality constrained mean–variance(CCMV)portfolio selection model aims to identify a subset of the candidate assets such that the constructed portfolio has a guaranteed expected return and minimum variance.By formulating this model as the mixed-integer quadratic program(MIQP),the exact solution can be solved by a branch-and-bound algorithm.However,computational efficiency is the central issue in the time-sensitive portfolio investment due to its NP-hardness properties.To accelerate the solution speeds to CCMV portfolio optimization problems,we develop various heuristic methods based on techniques such as continuous relaxation,l1-norm approximation,integer optimization,and relaxation of semi-definite programming(SDP).We evaluate our heuristic methods by applying them to the US equity market dataset.The experimental results show that our SDP-based method is effective in terms of the computation time and the approximation ratio.Our SDP-based method performs even better than a commercial MIQP solver when the computational time is limited.In addition,several investment companies in China have adopted our methods,gaining good returns.This paper sheds light on the computation optimization for financial investments.

Adaptive Algorithms on Maximizing Monotone Nonsubmodular Functions

Submodular optimization is widely used in large datasets.In order to speed up the problems solving,it is essential to design low-adaptive algorithms to achieve acceleration in parallel.In general,the function values are given by a value oracle,but in practice,the oracle queries may consume a lot of time.Hence,how to strike a balance between optimizing them is important.In this paper,we focus on maximizing a normalized and strictly monotone set function with the diminishing-return ratio under a cardinality constraint,and propose two algorithms to deal with it.We apply the adaptive sequencing technique to devise the first algorithm,whose approximation ratio is arbitrarily close to 1-e^(-γ)in O(logn·log(log k/γ)) adaptive rounds,and requires O(logn^(2)·log(log k/γ)) queries.Then by adding preprocessing and parameter estimation steps to the first algorithm,we get the second one.The second algorithm trades a small sacrifice in adaptive complexity for a significant improvement in query complexity.With the same approximation and adaptive complexity,the query complexity is improved to.To the best of our knowledge,this is the first paper of designing adaptive algorithms for maximizing a monotone function using the diminishing-return ratio.

Streaming Algorithms for Non-Submodular Maximizationon the Integer Lattice

Many practical problems emphasize the importance of not only knowing whether an element is selectedbut also deciding to what extent it is selected,which imposes a challenge on submodule optimization.In this study,we consider the monotone,nondecreasing,and non-submodular maximization on the integer lattice with a cardinalityconstraint.We first design a two-pass streaming algorithm by refining the estimation interval of the optimal value.Foreach element,the algorithm not only decides whether to save the element but also gives the number of reservations.Then,we introduce the binary search as a subroutine to reduce the time complexity.Next,we obtain a one-passstreaming algorithm by dynamically updating the estimation interval of optimal value.Finally,we improve the memorycomplexity of this algorithm.