Computational aspects of minimizing conditional value-at-risk

We consider optimization problems for minimizing conditional value-at-risk (CVaR) from a computational point of view, with an emphasis on financial applications. As a general solution approach, we suggest to reformulate these CVaR optimization problems as two-stage recourse problems of stochastic programming. Specializing the L-shaped method leads to a new algorithm for minimizing conditional value-at-risk. We implemented the algorithm as the solver CVaRMin. For illustrating the performance of this algorithm, we present some comparative computational results with two kinds of test problems. Firstly, we consider portfolio optimization problems with 5 random variables. Such problems involving conditional value at risk play an important role in financial risk management. Therefore, besides testing the performance of the proposed algorithm, we also present computational results of interest in finance. Secondly, with the explicit aim of testing algorithm performance, we also present comparative computational results with randomly generated test problems involving 50 random variables. In all our tests, the experimental solver, based on the new approach, outperformed by at least one order of magnitude all general-purpose solvers, with an accuracy of solution being in the same range as that with the LP solvers. János Mayer: Financial support by the national center of competence in research "Financial Valuation and Risk Management" is gratefully acknowledged. The national centers in research are managed by the Swiss National Science Foundation on behalf of the federal authorities.     

A robust approach based on conditional value-at-risk measure to statistical learning problems

In statistical learning problems, measurement errors in the observed data degrade the reliability of estimation. There exist several approaches to handle those uncertainties in observations. In this paper, we propose to use the conditional value-at-risk (CVaR) measure in order to depress influence of measurement errors, and investigate the relation between the resulting CVaR minimization problems and some existing approaches in the same framework. For the CVaR minimization problems which include the computation of integration, we apply Monte Carlo sampling method and obtain their approximate solutions. The approximation error bound and convergence property of the solution are proved by Vapnik and Chervonenkis theory. Numerical experiments show that the CVaR minimization problem can achieve fairly good estimation results, compared with several support vector machines, in the presence of measurement errors.     

Asymptotic representations for importance-sampling estimators of value-at-risk and conditional value-at-risk

Value-at-risk (VaR) and conditional value-at-risk (CVaR) are important risk measures. They are often estimated by using importance-sampling (IS) techniques. In this paper, we derive the asymptotic representations for IS estimators of VaR and CVaR. Based on these representations, we are able to prove the consistency and asymptotic normality of the estimators and to provide simple conditions under which the IS estimators have smaller asymptotic variances than the ordinary Monte Carlo estimators.     

Deviation inequalities for an estimator of the conditional value-at-risk

In this paper, we present a deviation inequality for a common estimator of the conditional value-at-risk for bounded random variables. The result improves a deviation inequality which is obtained by Brown [D.B. Brown, Large deviations bounds for estimating conditional value-at-risk, Operations Research Letters 35 (2007) 722-730].     

Superquantile regression with applications to buffered reliability,uncertainty quantification,and conditional value-at-risk

The paper presents a generalized regression technique centered on a superquantile (also called conditional value-at-risk) that is consistent with that coherent measure of risk and yields more conservatively fitted curves than classical least-squares and quantile regression. In contrast to other generalized regression techniques that approximate conditional superquantiles by various combinations of conditional quantiles, we directly and in perfect analog to classical regression obtain superquantile regression functions as optimal solutions of certain error minimization problems. We show the existence and possible uniqueness of regression functions, discuss the stability of regression functions under perturbations and approximation of the underlying data, and propose an extension of the coefficient of determination R-squared for assessing the goodness of fit. The paper presents two numerical methods for solving the error minimization problems and illustrates the methodology in several numerical examples in the areas of uncertainty quantification, reliability engineering, and financial risk management.     

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

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

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

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

A maximization method for a class of quasiconcave programs

An implementable linearized method of centers is presented for solving a class of quasiconcave programs of the form (P): maximizef ⁰(x), subject tox B andf ⁱ (x)0, for everyi{1, ...,m}, whereB is a convex polyhedral subset ofR ⁿ (Euclideann-space). Each problem function is a continuous quasiconcave function fromR ⁿ intoR ¹. Also, it is assumed that the feasible region is bounded and there existsx B such thatf _i (x) for everyi {1, ...,m}. For a broad class of continuous quasiconcave problem functions, which may be nonsmooth, it is shown that the method produces a sequence of feasible points whose limit points are optimal for Problem (P). For many programs, no line searches are required. Additionally, the method is equipped with a constraint dropping devise.The author wishes to thank a referee for suggesting the use of generalized gradients and a second referee whose detailed informative comments have enhanced the paper.This work was done while the author was in the Department of Mathematical Sciences at the University of Delaware.     

等式约束优化问题的一类新的简单光滑精确罚函数

精确罚函数方法是求解优化问题的一类经典方法,传统的精确罚函数不可能既是简单的又是光滑的,这里简单的是指罚函数中不包含目标函数和约束函数的梯度信息。针对等式约束问题提出了不同与传统罚函数的一类新的简单光滑罚函数并证明了它是精确的。给出了以新的罚函数为基础的罚函数方法并用数值例子说明算法是可行的。     

The exact measures of a class of self-similar sets on the plane

Let S (C) R2 be the attractor of the iterated function system{f1,f2,f3}iterating on the unit equilateral triangle So,where fi(x)=λix bi,I=1,2,3,x=(x1,x2),b1=(0,0),62=(1-λ2,0),63=(1-λ3/2,√3/2(1-λ3)).This paper determines the exact Hausdorff measure,centred covering measure and packing measure of S under some conditions relating to the ontraction parameter.     

An RQP algorithm using a differentiable exact penalty function for inequality constrained problems

In this paper we propose a recursive quadratic programming algorithm for nonlinear programming problems with inequality constraints that uses as merit function a differentiable exact penalty function. The algorithm incorporates an automatic adjustment rule for the selection of the penalty parameter and makes use of an Armijo-type line search procedure that avoids the need to evaluate second order derivatives of the problem functions. We prove that the algorithm possesses global and superlinear convergence properties. Numerical results are reported.     

ISTMO: An interval reference point-based method for stochastic multiobjective programming problems

In this paper, we present an interactive algorithm (ISTMO) for stochastic multiobjective problems with continuous random variables. This method combines the concept of probability efficiency for stochastic problems with the reference point philosophy for deterministic multiobjective problems. The decision maker expresses her/his references by dividing the variation range of each objective into intervals, and by setting the desired probability for each objective to achieve values belonging to each interval. These intervals may also be redefined during the process. This interactive procedure helps the decision maker to understand the stochastic nature of the problem, to discover the risk level (s)he is willing to assume for each objective, and to learn about the trade-offs among the objectives.     

The use of stochastic analytic center for yield maximization of systems with general distributions of component values

This paper presents a new method for maximizing manufacturing yield when the realizations of system components are dependent random variables with general distributions. The method uses a new concept of stochastic analytic center introduced herein to design the unknown parameters of component values. Design specifications define a feasible region which, in the nonlinear case, is linearized using a first-order approximation. The resulting problem becomes a convex optimization problem. Monte Carlo simulation is used to evaluate the actual yield of the optimal designs of a tutorial example.     

Penalty method for solving a class of stochastic differential variational inequalities with an application

The aim of this paper is to study the penalty method for solving a class of stochastic differential variational inequalities (SDVIs). The penalty problem for solving SDVIs is first constructed and the convergence of the sequences generated by the penalty problem is proved under some mild conditions. As an application, the convergence of the sequences generated by the penalty problem is obtained for solving a stochastic migration equilibrium problem with movement cost.     

带等式约束的光滑优化问题的一类新的精确罚函数

罚函数方法是将约束优化问题转化为无约束优化问题的主要方法之一. 不包含目标函数和约束函数梯度信息的罚函数, 称为简单罚函数. 对传统精确罚函数而言, 如果它是简单的就一定是非光滑的; 如果它是光滑的, 就一定不是简单的. 针对等式约束优化问题, 提出一类新的简单罚函数, 该罚函数通过增加一个新的变量来控制罚项. 证明了此罚函数的光滑性和精确性, 并给出了一种解决等式约束优化问题的罚函数算法. 数值结果表明, 该算法对于求解等式约束优化问题是可行的.     

An efficient computational method for a stochastic dynamic lot-sizing problem under service-level constraints

We provide an efficient computational approach to solve the mixed integer programming (MIP) model developed by Tarim and Kingsman [8] for solving a stochastic lot-sizing problem with service level constraints under the static-dynamic uncertainty strategy. The effectiveness of the proposed method hinges on three novelties: (i) the proposed relaxation is computationally efficient and provides an optimal solution most of the time, (ii) if the relaxation produces an infeasible solution, then this solution yields a tight lower bound for the optimal cost, and (iii) it can be modified easily to obtain a feasible solution, which yields an upper bound. In case of infeasibility, the relaxation approach is implemented at each node of the search tree in a branch-and-bound procedure to efficiently search for an optimal solution. Extensive numerical tests show that our method dominates the MIP solution approach and can handle real-life size problems in trivial time.     

Convergence of the constrained gradient method for a class of nonconvex functions

Translated from Issledovaniya po Prikladnoi Matematike, Kazan', No. 14, pp. 15–25, 1987.     

A method of stochastic subgradients with complete feedback stepsize rule for convex stochastic approximation problems

A stochastic subgradient algorithm for solving convex stochastic approximation problems is considered. In the algorithm, the stepsize coefficients are controlled on-line on the basis of information gathered in the course of computations according to a new, complete feedback rule derived from the concept of regularized improvement function. Convergence with probability 1 of the method is established.This work was supported by Project No. CPBP/02.15.