工件具有任意尺寸的混合分批平行机排序问题的近似算法

本文考虑了工件具有任意尺寸且机器有容量限制的混合分批平行机排序问题。在该问题中, 一个待加工的工件集需在多台平行批处理机上进行加工。每个工件有它的加工时间和尺寸, 每台机器可以同时处理多个工件, 称为一个批, 只要这些工件尺寸之和不超过其容量; 一个批的加工时间等于该批中工件的最大加工时间和总加工时间的加权和; 目标函数是极小化最大完工时间。该问题包含一维装箱问题为其特殊情形, 为强NP-困难的。对此给出了一个$\left( {2 + 2\alpha+\alpha^{2}}\right)$-近似算法, 其中$\alpha$为给定的权重参数, 满足$0\leq\alpha\leq 1$。     

工件可自由下线最小化总完工时间的平行分批排序问题

考虑工件可自由下线最小化总完工时间的有界平行分批排序问题. 在该问题中, 一台平行批机器可以同时处理 b 个工件作为一个平行批, 这里b 是批容量, 一个批的加工时间等于分配给这个批的工件的最大加工时间. 关于可自由下线工件, 每一个工件的完工时间等于包含这个工件的批的开工时间与工件的加工时间的和. 也就是, 如果一个批B 有一个开工时间S, 那么包含在批B 中的每一个工件J_j 的开工时间定义为S, 而它的完工时间定义为S+p_j, 这里p_j 是工件J_j 的加工时间. 对此问题, 首先研究最优排序的一些性质. 然后, 基于这些性质, 给出一个运行时间为O(n^{b (b-1)})的动态规划算法.     

有尺寸的同型机分批排序问题的近似算法

对工件有不同到达时间、不同加工时间和尺寸的同型机分批排序问题寻找近似算法.对于大工件(工件的体积严格大于机器容量的÷)的加工时间不小于小工件(工件的体积小于或等于机器容量的÷)的加工时间的特定情形,利用动态规划的方法和拆分的技巧,我们设计了近似算法并分析了其最差性能比.     

平行机中关于关于同类机近似算法的研究

我们考虑平行机排序问题中的这样一类:机器两台,类型一样,但效率不同.其中n个工件在第一台机器上的加工时间分别为p1,p2,…,Pn,在第二台机器上的加工时间分别为αρ1,αρ2,…,αρn,其中0<α≤1.每台机器上的工件总数不受限制.n个工件的权分别为w1,w2,…,wn,我们的目标是如何在这两台机器上安排这n个工件以及如何确定每台机器上工件加工的先后顺序,使得这n个工件的完工时间的总权和 达到最小.该问题记为 .对于这个问题,我们给出一个1.1755近似算法.     

单位工件的平行机并行分批在线排序问题的算法

本文研究一类批容量有界的并行分批、平行机在线排序问题。模型中有n个相互独立的工件J={J₁,…,J_n}要在m台批处理机上加工。批处理机每次可同时加工至多B(Bj(1≤j≤n)的到达时间为r_j,加工时间为1,工件是否会到达事先未知,而只有等到工件的到达时间才能获知它的到达。目标为最小化工件的最大完工时间。针对该排序问题,本文设计了两个竞争比均达到最好可能的在线算法。     

平行机上带有前瞻区间的不相容工件组在线排序问题

研究当不相容工件组的个数与机器数相等时,具有前瞻区间的单位工件平行机无界平行分批在线排序问题.工件按时在线到达, 目标是最小化 最大完工时间. 具有前瞻区间是指在时刻t, 在线算法能预见到时间区间(t,t+\beta) 内到达的所有工件的信息.不可相容的工件组是指属于不同组的工件不能被安排在同一批中加工. \beta\geq 1 时, 提供了一个最优的在线算法; 当0\leq \beta < 1时, 提供了一个竞争比为1+\alpha 的最好可能的在线算法, 其中\alpha是方程\alpha^{2}+(1+\beta) \alpha+\beta-1=0的一个正根.最后, 给出了当\beta =0 时稠密算法竞争比的下界,并提供了达到该下界的最好可能的稠密算法.     

工作有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法

考虑了工件有到达时间且拒绝工件总个数不超过某个给定值的单机平行分批排序问题.在该问题中,给定一个工件集和一台可以进行批处理加工的机器.每个工件有它的到达时间和加工时间;对于每个工件来说要么被拒绝要么被接受安排在机器的某一个批次里进行加工;一个工件如果被拒绝,则需支付该工件对应的拒绝费用.为了保证一定的服务水平,要求拒绝工件的总个数不超过给定值.目标是如何安排被接受工件的加工批次和加工次序使得其最大完工时间与被拒绝工件的总拒绝费用之和最小.该问题是NP-难的,对此给出了伪多项式时间动态规划精确算法,2-近似算法和完全多项式时间近似方案.     

具有前瞻区间的两个工件组单机在线排序问题

研究具有前瞻区间的两个不相容工件组单位工件单机无界平行分批在线排序问题.工件按时在线到达, 目标是最小化最大完工时间. 在无界平行分批排序中, 一台容量无限制机器可将多个工件形成一批同时加工, 每一批的加工时间等于该批中最长工件的加工时间. 具有前瞻区间是指在时刻t, 在线算法能预见到时间区间(t,t+\beta]内到达的所有工件的信息.不可相容的工件组是指属于不同组的工件不能安排在同一批中加工.对该问题提供了一个竞争比为\ 1+\alpha 的最好可能的在线算法,其中\ \alpha 是方程2\alpha^{2}+(\beta +1)\alpha +\beta -2=0的一个正根, 这里0\leq \beta <1.     

工件有到达时间及可拒绝下的同类平行机排序问题的近似算法

本文研究工件有到达时间且可拒绝下的同类平行机排序问题。在该问题中, 给定一个待加工工件集, 每个工件在到达之后, 可以被选择安排到$m$台同类平行机器中的某一台机器上进行加工, 也可以被选择拒绝加工, 但需支付一定的拒绝惩罚费用。目标函数是最小化接受工件集的最大完工时间与拒绝工件集的总拒绝费用之和。当$m$为固定常数时, 设计了一个伪多项式时间动态规划精确算法; 当$m$为任意输入时, 设计了一个近似算法, 当接受工件个数大于$(m-1)$时, 该算法近似比为3, 当接受工件个数小于$(m-1)$时, 该算法近似比为$(2+\rho)$, 其中$\rho$为机器加工速度最大值和最小值的比值。最后通过算例演示了算法的运行。     

工件有到达时间及可拒绝下的同类平行机排序问题的近似算法

本文研究工件有到达时间且可拒绝下的同类平行机排序问题。在该问题中, 给定一个待加工工件集, 每个工件在到达之后, 可以被选择安排到$m$台同类平行机器中的某一台机器上进行加工, 也可以被选择拒绝加工, 但需支付一定的拒绝惩罚费用。目标函数是最小化接受工件集的最大完工时间与拒绝工件集的总拒绝费用之和。当$m$为固定常数时, 设计了一个伪多项式时间动态规划精确算法; 当$m$为任意输入时, 设计了一个近似算法, 当接受工件个数大于$(m-1)$时, 该算法近似比为3, 当接受工件个数小于$(m-1)$时, 该算法近似比为$(2+\rho)$, 其中$\rho$为机器加工速度最大值和最小值的比值。最后通过算例演示了算法的运行。     

Robust model selection in regression

A robust version of Akaike's model selection procedure for regression models is introduced and its relationship with robust testing procedures is discussed.     

Robust global optimization with polynomials

We consider the optimization problems max_z∈Ω min_x∈K p(z, x) and min_{x ∈ K} max_{z ∈ Ω} p(z, x) where the criterion p is a polynomial, linear in the variables z, the set Ω can be described by LMIs, and K is a basic closed semi-algebraic set. The first problem is a robust analogue of the generic SDP problem max_{z ∈ Ω} p(z), whereas the second problem is a robust analogue of the generic problem min_{x ∈ K} p(x) of minimizing a polynomial over a semi-algebraic set. We show that the optimal values of both robust optimization problems can be approximated as closely as desired, by solving a hierarchy of SDP relaxations. We also relate and compare the SDP relaxations associated with the max-min and the min-max robust optimization problems.     

Robust mean variance portfolio selection model in the jump-diffusion financial market with an intractable claim

In this paper, a continuous-time robust mean variance model in the jump-diffusion financial market with an intractable claim is considered, in which the price processes of the assets not only are driven by the Brownian motion, but also have the Poisson jumps. By combining the martingale representation theorem and the quantile formulation method, an explicit closed-form solution of the robust mean-variance portfolio selection model is given under some suitable assumptions.     

Robust portfolio selection based on a multi-stage scenario tree

The aim of this paper is to apply the concept of robust optimization introduced by Bel-Tal and Nemirovski to the portfolio selection problems based on multi-stage scenario trees. The objective of our portfolio selection is to maximize an expected utility function value (or equivalently, to minimize an expected disutility function value) as in a classical stochastic programming problem, except that we allow for ambiguities to exist in the probability distributions along the scenario tree. We show that such a problem can be formulated as a finite convex program in the conic form, on which general convex optimization techniques can be applied. In particular, if there is no short-selling, and the disutility function takes the form of semi-variance downside risk, and all the parameter ambiguity sets are ellipsoidal, then the problem becomes a second order cone program, thus tractable. We use SeDuMi to solve the resulting robust portfolio selection problem, and the simulation results show that the robust consideration helps to reduce the variability of the optimal values caused by the parameter ambiguity.     

鲁棒投资组合选择优化问题的研究进展

对近年来投资组合研究优化研究的热点问题——鲁棒投资组合优化研究的现状和发展趋势作了综述性研究．在投资组合选择优化的均值-方差模型的基础上,回顾了鲁棒投资组合选择优化问题的发展历史;详细地介绍了鲁棒投资组合选择优化的研究热点及国内外研究现状,就鲁棒投资组合选择优化问题的未来发展方向和主要研究内容,提出了新的观点,以期为相关领域的研究工作提供参考依据．     

Robust portfolio optimization with copulas

Conditional Value at Risk (CVaR) is widely used in portfolio optimization as a measure of risk. CVaR is clearly dependent on the underlying probability distribution of the portfolio. We show how copulas can be introduced to any problem that involves distributions and how they can provide solutions for the modeling of the portfolio. We use this to provide the copula formulation of the CVaR of a portfolio. Given the critical dependence of CVaR on the underlying distribution, we use a robust framework to extend our approach to Worst Case CVaR (WCVaR). WCVaR is achieved through the use of rival copulas. These rival copulas have the advantage of exploiting a variety of dependence structures, symmetric and not. We compare our model against two other models, Gaussian CVaR and Worst Case Markowitz. Our empirical analysis shows that WCVaR can asses the risk more adequately than the two competitive models during periods of crisis.     

Robust portfolio selection based on asymmetric measures of variability of stock returns

This paper addresses a new uncertainty set—interval random uncertainty set for robust optimization. The form of interval random uncertainty set makes it suitable for capturing the downside and upside deviations of real-world data. These deviation measures capture distributional asymmetry and lead to better optimization results. We also apply our interval random chance-constrained programming to robust mean-variance portfolio selection under interval random uncertainty sets in the elements of mean vector and covariance matrix. Numerical experiments with real market data indicate that our approach results in better portfolio performance.     

Robust ranking and portfolio optimization

The portfolio optimization problem has attracted researchers from many disciplines to resolve the issue of poor out-of-sample performance due to estimation errors in the expected returns. A practical method for portfolio construction is to use assets’ ordering information, expressed in the form of preferences over the stocks, instead of the exact expected returns. Due to the fact that the ranking itself is often described with uncertainty, we introduce a generic robust ranking model and apply it to portfolio optimization. In this problem, there are n objects whose ranking is in a discrete uncertainty set. We want to find a weight vector that maximizes some generic objective function for the worst realization of the ranking. This robust ranking problem is a mixed integer minimax problem and is very difficult to solve in general. To solve this robust ranking problem, we apply the constraint generation method, where constraints are efficiently generated by solving a network flow problem. For empirical tests, we use post-earnings-announcement drifts to obtain ranking uncertainty sets for the stocks in the DJIA index. We demonstrate that our robust portfolios produce smaller risk compared to their non-robust counterparts.     

Asymptotically optimal selection of a piecewise polynomial estimator of a regression function

Let (X, Y) be a pair of random variables such that X = (X₁,…, X_d) ranges over a nondegenerate compact d-dimensional interval C and Y is real-valued. Let the conditional distribution of Y given X have mean θ(X) and satisfy an appropriate moment condition. It is assumed that the distribution of X is absolutely continuous and its density is bounded away from zero and infinity on C. Without loss of generality let C be the unit cube. Consider an estimator of θ having the form of a piecewise polynomial of degree k_n based on m_n^d cubes of length 1/m_n, where the m_n^d(_d^k_n+d) coefficients are chosen by the method of least squares based on a random sample of size n from the distribution of (X, Y). Let (k_n, m_n) be chosen by the FPE procedure. It is shown that the indicated estimator has an asymptotically minimal squared error of prediction if θ is not of the form of piecewise polynomial.     

Mean-chance model for portfolio selection based on uncertain measure

This paper discusses a portfolio selection problem in which security returns are given by experts’ evaluations instead of historical data. A factor method for evaluating security returns based on experts’ judgment is proposed and a mean-chance model for optimal portfolio selection is developed taking transaction costs and investors’ preference on diversification and investment limitations on certain securities into account. The factor method of evaluation can make good use of experts’ knowledge on the effects of economic environment and the companies’ unique characteristics on security returns and incorporate the contemporary relationship of security returns in the portfolio. The use of chance of portfolio return failing to reach the threshold can help investors easily tell their tolerance toward risk and thus facilitate a decision making. To solve the proposed nonlinear programming problem, a genetic algorithm is provided. To illustrate the application of the proposed method, a numerical example is also presented.