We study the sample complexity of sample average approximation (SAA) and its simple variations, referred to as the regularized SAA (RSAA), in solving convex and strongly convex stochastic programming (SP) problems under heavy-tailed-ness, non-Lipschitz-ness, and/or high dimensionality. The presence of such irregularities underscores critical vacua in the literature. In response, this paper presents three sets of results: First, we show that the (R)SAA is effective even if the objective function is not necessarily Lipschitz and the underlying distribution admits some bounded central moments only at (near-)optimal solutions. Second, when the SP's objective function is the sum of a smooth term and a Lipschitz term, we prove that the (R)SAA's sample complexity is completely independent from any complexity measures (e.g., the covering number) of the feasible region. Third, we explicate the (R)SAA's sample complexities with regard to the dependence on dimensionality $d$: When some $p$th ($p\geq 2$) central moment of the underlying distribution is bounded, we show that the required sample size grows at a rate no worse than $\mathcal O\left(p d^{2/p}\right)$ under any one of the three structural assumptions: (i) strong convexity w.r.t. the $q$-norm ($q\geq 1$); (ii) the combination of restricted strong convexity and sparsity; and (iii) a dimension-insensitive $q$-norm of an optimal solution. In both cases of (i) and (iii), it is further required that $p\leq q/(q-1)$. As a direct implication, the (R)SAA's complexity becomes (poly-)logarithmic in $d$, whenever $p\geq c\cdot \ln d$ is admissible for some constant $c>0$. These new results deviate from the SAA's typical sample complexities that grow polynomially with $d$. Part of our proof is based on the average-replace-one (RO) stability, which appears to be novel for the (R)SAA's analyses.

An autonomous robot with a limited vision range finds a path to the goal in an unknown environment in 2D avoiding polygonal obstacles. In the process of discovering the environmental map, the robot has to return to some positions marked previously, the regions where the robot traverses to return are defined as sequences of bundles of line segments. This paper presents a novel algorithm for finding approximately shortest paths along the sequences of bundles of line segments based on the method of multiple shooting. Three factors of the approach including bundle partition, collinear condition, and update of shooting points are presented. We then show that if the collinear condition holds, the exactly shortest paths of the problems are determined, otherwise, the sequence of paths obtained by the update of the method converges to the shortest path. The algorithm is implemented in Python and some numerical examples show that the running time of path-planning for autonomous robots using our method is faster than that using the rubber band technique of Li and Klette in Euclidean Shortest Paths, Springer, 53-89 (2011).

In this paper, we introduce a new stochastic approximation (SA) type algorithm, namely the randomized stochastic gradient (RSG) method, for solving an important class of nonlinear (possibly nonconvex) stochastic programming (SP) problems. We establish the complexity of this method for computing an approximate stationary point of a nonlinear programming problem. We also show that this method possesses a nearly optimal rate of convergence if the problem is convex. We discuss a variant of the algorithm which consists of applying a post-optimization phase to evaluate a short list of solutions generated by several independent runs of the RSG method, and show that such modification allows to improve significantly the large-deviation properties of the algorithm. These methods are then specialized for solving a class of simulation-based optimization problems in which only stochastic zeroth-order information is available.

We present a formal model to represent and solve the unicast/multicast routing problem in networks with Quality of Service (QoS) requirements. To attain this, first we translate the network adapting it to a weighted graph (unicast) or and-or graph (multicast), where the weight on a connector corresponds to the multidimensional cost of sending a packet on the related network link: each component of the weights vector represents a different QoS metric value (e.g. bandwidth, cost, delay, packet loss). The second step consists in writing this graph as a program in Soft Constraint Logic Programming (SCLP): the engine of this framework is then able to find the best paths/trees by optimizing their costs and solving the constraints imposed on them (e.g. delay < 40msec), thus finding a solution to QoS routing problems. Moreover, c-semiring structures are a convenient tool to model QoS metrics. At last, we provide an implementation of the framework over scale-free networks and we suggest how the performance can be improved.