Multistage stochastic programs bring computational complexity which may increase exponentially in real case problems. For this reason approximation techniques which replace the problem by a simpler one and provide lower and upper bounds to the optimal solution are very useful. In this paper we provide monotonic lower and upper bounds for the optimal objective value … Read more
In many network applications, one searches for a connected subset of vertices that exhibits other desirable properties. To this end, this paper studies the connected subgraph polytope of a graph, which is the convex hull of subsets of vertices that induce a connected subgraph. Much of our work is devoted to the study of two … Read more
This paper concerns some practical issues associated with the formulation of sequential quadratic programming (SQP) methods for large-scale nonlinear optimization. SQP methods find an approximate solution of a sequence of quadratic programming (QP) subproblems in which a quadratic model of the objective function is minimized subject to the linearized constraints. Extensive numerical results are given … Read more
In this paper we underline the importance of the parametric subregularity property of set-valued mappings, defined with respect to fixed sets. We show that this property appears naturally for some very simple mappings which play an important role in the theory of metric regularity. We prove a result concerning the preservation of metric subregularity at … Read more
Since the financial crisis of 2007-2009, there has been a renewed interest toward quantifying more appropriately the risks involved in financial positions. Popular risk measures such as variance and value-at-risk have been found inadequate as we now give more importance to properties such as monotonicity, convexity, translation invariance, scale invariance, and law invariance. Unfortunately, the … Read more
We consider the application of mixed-integer linear programming (MILP) solvers to the minimization of submodular functions. We evaluate common large-scale linear-programming (LP) techniques (e.g., column generation, row generation, dual stabilization) for solving a LP reformulation of the submodular minimization (SM) problem. We present heuristics based on the LP framework and a MILP solver. We evaluated … Read more
In this paper, we propose a new step size rule to accelerate Yan et al.’s self-adaptive projection method. Under the new step size strategy, the superiority of modified projection method is verified through theory to numerical experiments. CitationCollege of Communications Engineering, PLA University of Science and Technology, Nanjing, 210007, China 01/29/2015ArticleDownload View PDF
We consider the alternating proximal gradient method (APGM) proposed to solve a convex minimization model with linear constraints and separable objective function which is the sum of two functions without coupled variables. Inspired by Peaceman-Rachford splitting method (PRSM), a nature idea is to extend APGM to the symmetric alternating proximal gradient method (SAPGM), which can … Read more
We consider the Critical Node Problem: given an undirected graph and an integer number K, at most K nodes have to be deleted from the graph in order to minimize a connectivity measure in the residual graph. We combine the basic steps used in common greedy algorithms with some flavour of local search, in order … Read more
In this paper, we propose two block coordinate gradient (BCG) methods for the online convex programming: the BCG method with the cyclic rule and the BCG method with the random rule. The proposed methods solve a low dimensional problem at each iteration, and hence they are efficient for large scale problems. For the proposed methods, … Read more