A proximal cutting plane method using Chebychev center for nonsmooth convex optimization

An algorithm is developed for minimizing nonsmooth convex functions. This algorithm extends Elzinga–Moore cutting plane algorithm by enforcing the search of the next test point not too far from the previous ones, thus removing compactness assumption. Our method is to Elzinga–Moore’s algorithm what a proximal bundle method is to Kelley’s algorithm. Instead of lower approximations used in proximal bundle methods, the present approach is based on some objects regularizing translated functions of the objective function. We propose some variants and using some academic test problems, we conduct a numerical comparative study with Elzinga–Moore algorithm and two other well-known nonsmooth methods.      

Processing second-order stochastic dominance models using cutting-plane representations

Second-order stochastic dominance (SSD) is widely recognised as an important decision criterion in portfolio selection. Unfortunately, stochastic dominance models are known to be very demanding from a computational point of view. In this paper we consider two classes of models which use SSD as a choice criterion. The first, proposed by Dentcheva and Ruszczyński (J Bank Finance 30:433–451, 2006), uses a SSD constraint, which can be expressed as integrated chance constraints (ICCs). The second, proposed by Roman et al. (Math Program, Ser B 108:541–569, 2006) uses SSD through a multi-objective formulation with CVaR objectives. Cutting plane representations and algorithms were proposed by Klein Haneveld and Van der Vlerk (Comput Manage Sci 3:245–269, 2006) for ICCs, and by Künzi-Bay and Mayer (Comput Manage Sci 3:3–27, 2006) for CVaR minimization. These concepts are taken into consideration to propose representations and solution methods for the above class of SSD based models. We describe a cutting plane based solution algorithm and outline implementation details. A computational study is presented, which demonstrates the effectiveness and the scale-up properties of the solution algorithm, as applied to the SSD model of Roman et al. (Math Program, Ser B 108:541–569, 2006).     

Mingling: mixed-integer rounding with bounds

Mixed-integer rounding (MIR) is a simple, yet powerful procedure for generating valid inequalities for mixed-integer programs. When used as cutting planes, MIR inequalities are very effective for mixed-integer programming problems with unbounded integer variables. For problems with bounded integer variables, however, cutting planes based on lifting techniques appear to be more effective. This is not surprising as lifting techniques make explicit use of the bounds on variables, whereas the MIR procedure does not. In this paper we describe a simple procedure, which we call mingling, for incorporating variable bound information into MIR. By explicitly using the variable bounds, the mingling procedure leads to strong inequalities for mixed-integer sets with bounded variables. We show that facets of mixed-integer knapsack sets derived earlier by superadditive lifting techniques can be obtained by the mingling procedure. In particular, the mingling inequalities developed in this paper subsume the continuous cover and reverse continuous cover inequalities of Marchand and Wolsey (Math Program 85:15–33, 1999) as well as the continuous integer knapsack cover and pack inequalities of Atamtürk (Math Program 98:145–175, 2003; Ann Oper Res 139:21–38, 2005). In addition, mingling inequalities give a generalization of the two-step MIR inequalities of Dash and Günlük (Math Program 105:29–53, 2006) under some conditions.     

A criterion for the equivalence of the Euclidean and the geodesic metric on compact subsets of {\mathbb{R}^N}

In (Studia Math 170:89–111, 2005), Bland and Feinstein show in two theorems that a compact plane set with pointwise (uniformly) regular boundary is itself pointwise (uniformly) regular. However, these statements do not cover simple sets as annular-like compact plane sets. In this note we prove that under suitable circumstances the statements keep true if one assumes the boundary to consist of finitely many pointwise (uniformly) regular sets.     

The Stratified Sampling Bootstrap for Measuring the Uncertainty in Mortality Forecasts

In this paper, we propose a procedure for reducing the uncertainty in mortality projections, on the basis of a log bilinear Poisson Lee Carter model (Renshaw and Haberman Appl Stat 52:119–137, 2003a). In the literature, because the non-linear nature of the quantities under consideration has prevented analytical solutions, simulation techniques have been used in order to provide prediction intervals for forecasted quantities (for example, Brouhns et al. Scand Actuar J 3:212–224, 2005, Renshaw and Haberman Insur Math Econ 42:797–816, 2008). In this respect, we adopt the bootstrap simulation approach in order to measure the uncertainty affecting mortality projections. In particular, we propose making the bootstrap procedure more efficient by using a specific variance reducing technique, the so-called Stratified Sampling technique. To this end, we propose a two stage simulation bootstrap procedure where variance reducing techniques are combined with the simple bootstrap of the Poisson Lee Carter version. Numerical applications are shown using the results for some datasets.     

Lorentz Gas with Thermostatted Walls

In a planar periodic Lorentz gas, a point particle (electron) moves freely and collides with fixed round obstacles (ions). If a constant force (induced by an electric field) acts on the particle, the latter will accelerate, and its speed will approach infinity (Chernov and Dolgopyat in J Am Math Soc 22:821–858, 2009; Phys Rev Lett 99, paper 030601, 2007). To keep the kinetic energy bounded one can apply a Gaussian thermostat, which forces the particle’s speed to be constant. Then an electric current sets in and one can prove Ohm’s law and the Einstein relation (Chernov and Dolgopyat in Russian Math Surv 64:73–124, 2009; Chernov et al. Comm Math Phys 154:569–601, 1993; Phys Rev Lett 70:2209–2212, 1993). However, the Gaussian thermostat has been criticized as unrealistic, because it acts all the time, even during the free flights between collisions. We propose a new model, where during the free flights the electron accelerates, but at the collisions with ions its total energy is reset to a fixed level; thus our thermostat is restricted to the surface of the scatterers (the ‘walls’). We rederive all physically interesting facts proven for the Gaussian thermostat in Chernov, Dolgopyat (Russian Math Surv 64:73–124, 2009) and Chernov et al. (Comm Math Phys 154:569–601, 1993; Phys Rev Lett 70:2209–2212, 1993), including Ohm’s law and the Einstein relation. In addition, we investigate the superconductivity phenomenon in the infinite horizon case.     

Robust solutions to uncertain linear complementarity problems

In this paper,we adopt the robust optimization method to consider linear complementarity problems in which the data is not specified exactly or is uncertain,and it is only known to belong to a prescribed uncertainty set.We propose the notion of the p- robust counterpart and the p-robust solution of uncertain linear complementarity problems.We discuss uncertain linear complementarity problems with three different uncertainty sets,respectively,including an unknown-but-bounded uncertainty set,an ellipsoidal uncertainty set and an intersection-of-ellipsoids uncertainty set,and present some sufficient and necessary(or sufficient) conditions which p- robust solutions satisfy.Some special cases are investigated in this paper.     

Primal-dual first-order methods with $${\mathcal {O}(1/\epsilon)}$$ iteration-complexity for cone programming

In this paper we consider the general cone programming problem, and propose primal-dual convex (smooth and/or nonsmooth) minimization reformulations for it. We then discuss first-order methods suitable for solving these reformulations, namely, Nesterov’s optimal method (Nesterov in Doklady AN SSSR 269:543–547, 1983; Math Program 103:127–152, 2005), Nesterov’s smooth approximation scheme (Nesterov in Math Program 103:127–152, 2005), and Nemirovski’s prox-method (Nemirovski in SIAM J Opt 15:229–251, 2005), and propose a variant of Nesterov’s optimal method which has outperformed the latter one in our computational experiments. We also derive iteration-complexity bounds for these first-order methods applied to the proposed primal-dual reformulations of the cone programming problem. The performance of these methods is then compared using a set of randomly generated linear programming and semidefinite programming instances. We also compare the approach based on the variant of Nesterov’s optimal method with the low-rank method proposed by Burer and Monteiro (Math Program Ser B 95:329–357, 2003; Math Program 103:427–444, 2005) for solving a set of randomly generated SDP instances.     

On the extreme inequalities of infinite group problems

Infinite group relaxations of integer programs (IP) were introduced by Gomory and Johnson (Math Program 3:23–85, 1972) to generate cutting planes for general IPs. These valid inequalities correspond to real-valued functions defined over an appropriate infinite group. Among all the valid inequalities of the infinite group relaxation, extreme inequalities are most important since they are the strongest cutting planes that can be obtained within the group-theoretic framework. However, very few properties of extreme inequalities of infinite group relaxations are known. In particular, it is not known if all extreme inequalities are continuous and what their relations are to extreme inequalities of finite group problems. In this paper, we describe new properties of extreme functions of infinite group problems. In particular, we study the behavior of the pointwise limit of a converging sequence of extreme functions as well as the relations between extreme functions of finite and infinite group problems. Using these results, we prove for the first time that a large class of discontinuous functions is extreme for infinite group problems. This class of extreme functions is the generalization of the functions given by Letchford and Lodi (Oper Res Lett 30(2):74–82, 2002), Dash and Günlük (Proceedings 10th conference on integer programming and combinatorial optimization. Springer, Heidelberg, pp 33–45 (2004), Math Program 106:29–53, 2006) and Richard et al. (Math Program 2008, to appear). We also present several other new classes of discontinuous extreme functions. Surprisingly, we prove that the functions defining extreme inequalities for infinite group relaxations of mixed integer programs are continuous. S.S. Dey and J.-P.P. Richard was supported by NSF Grant DMI-03-48611.     

Multi-step nonlinear conjugate gradient methods for unconstrained minimization

Conjugate gradient methods are appealing for large scale nonlinear optimization problems, because they avoid the storage of matrices. Recently, seeking fast convergence of these methods, Dai and Liao (Appl. Math. Optim. 43:87–101, 2001) proposed a conjugate gradient method based on the secant condition of quasi-Newton methods, and later Yabe and Takano (Comput. Optim. Appl. 28:203–225, 2004) proposed another conjugate gradient method based on the modified secant condition. In this paper, we make use of a multi-step secant condition given by Ford and Moghrabi (Optim. Methods Softw. 2:357–370, 1993; J. Comput. Appl. Math. 50:305–323, 1994) and propose two new conjugate gradient methods based on this condition. The methods are shown to be globally convergent under certain assumptions. Numerical results are reported.     

Globally Convergent Cutting Plane Method for Nonconvex Nonsmooth Minimization

Nowadays, solving nonsmooth (not necessarily differentiable) optimization problems plays a very important role in many areas of industrial applications. Most of the algorithms developed so far deal only with nonsmooth convex functions. In this paper, we propose a new algorithm for solving nonsmooth optimization problems that are not assumed to be convex. The algorithm combines the traditional cutting plane method with some features of bundle methods, and the search direction calculation of feasible direction interior point algorithm (Herskovits, J. Optim. Theory Appl. 99(1):121–146, 1998). The algorithm to be presented generates a sequence of interior points to the epigraph of the objective function. The accumulation points of this sequence are solutions to the original problem. We prove the global convergence of the method for locally Lipschitz continuous functions and give some preliminary results from numerical experiments.     

Measures on circle coarse-grained systems of sets

We show that a (non-negative) measure on a circle coarse-grained system of sets can be extended, as a (non-negative) measure, over the collection of all subsets of the circle. This result contributes to quantum logic probability (de Lucia in Colloq Math 80(1):147–154, 1999; Gudder in Quantum Probability, Academic Press, San Diego, 1988; Gudder in SIAM Rev 26(1):71–89, 1984; Harding in Int J Theor Phys 43(10):2149–2168, 2004; Navara and Pták in J Pure Appl Algebra 60:105–111, 1989; Pták in Proc Am Math Soc 126(7):2039–2046, 1998, etc.) and completes the analysis of coarse-grained measures carried on in De Simone and Pták (Bull Pol Acad Sci Math 54(1):1–11, 2006; Czechoslov Math J 57(132) n.2:737–746, 2007), Gudder and Marchand (Bull Pol Acad Sci Math 28(11–12):557–564, 1980) and Ovchinnikov (Construct Theory Funct Funct Anal 8:95–98, 1992).     

Multistars, partial multistars and the capacitated vehicle routing problem

 In an unpublished paper, Araque, Hall and Magnanti considered polyhedra associated with the Capacitated Vehicle Routing Problem (CVRP) in the special case of unit demands. Among the valid and facet-inducing inequalities presented in that paper were the so-called multistar and partial multistar inequalities, each of which came in several versions. Some related inequalities for the case of general demands have appeared subsequently and the result is a rather bewildering array of apparently different classes of inequalities. The main goal of the present paper is to present two relatively simple procedures that can be used to show the validity of all known (and some new) multistar and partial multistar inequalities, in both the unit and general demand cases. The procedures provide a unifying explanation of the inequalities and, perhaps more importantly, ideas that can be exploited in a cutting plane algorithm for the CVRP. Computational results show that the new inequalities can be useful as cutting planes for certain CVRP instances. Received: January 9, 1999 / Accepted: June 17, 2002 Published online: September 27, 2002 Key Words. vehicle routing – valid inequalities – cutting planes     

Random Skew Plane Partitions with a Piecewise Periodic Back Wall

Random skew plane partitions of large size distributed according to an appropriately scaled Schur process develop limit shapes. In the present work, we consider the limit of large random skew plane partitions where the inner boundary approaches a piecewise linear curve with non-lattice slopes, describing the limit shape and the local fluctuations in various regions. This analysis is fairly similar to that in Okounkov and Reshetikhin (Commun Math Phys 269:571–609, 2007), but we do find some new behavior. For instance, the boundary of the limit shape is now a single smooth (not algebraic) curve, whereas the boundary in Okounkov and Reshetikhin (Commun Math Phys 269:571–609, 2007) is singular. We also observe the bead process introduced in Boutillier (Ann Probab 37(1):107–142, 2009) appearing in the asymptotics at the top of the limit shape.     

q-expansions of vector-valued modular forms of negative weight

In this paper, we determine the q-expansions of vector-valued modular forms (Knopp and Mason in Ill. J. Math. 48:1345–1366, 2004; Acta Arith. 110(2): 117–124, 2003) of large negative weight on the full modular group where we allow poles in the upper half plane and at infinity.     

Globally Convergent Three-Term Conjugate Gradient Methods that Use Secant Conditions and Generate Descent Search Directions for Unconstrained Optimization

In this paper, we propose a three-term conjugate gradient method based on secant conditions for unconstrained optimization problems. Specifically, we apply the idea of Dai and Liao (in Appl. Math. Optim. 43: 87–101, 2001) to the three-term conjugate gradient method proposed by Narushima et al. (in SIAM J. Optim. 21: 212–230, 2011). Moreover, we derive a special-purpose three-term conjugate gradient method for a problem, whose objective function has a special structure, and apply it to nonlinear least squares problems. We prove the global convergence properties of the proposed methods. Finally, some numerical results are given to show the performance of our methods.     

Antispecial cycles on the Drinfeld upper half plane and degenerate Hirzebruch–Zagier cycles

We define the notion of antispecial cycles on the Drinfeld upper half plane in analogy to the notion of special cycles in Kudla and Rapoport (Invent Math 142:153–223, 2000). We determine equations for antispecial cycles and calculate the intersection multiplicity of two antispecial cycles. The result is applied to calculate the intersection multiplicity of certain degenerate Hirzebruch–Zagier cycles. Finally we compare this intersection multiplicity to certain representation densities.     

Maximum stable set formulations and heuristics based on continuous optimization

 The stability number α(G) for a given graph G is the size of a maximum stable set in G. The Lovász theta number provides an upper bound on α(G) and can be computed in polynomial time as the optimal value of the Lovász semidefinite program. In this paper, we show that restricting the matrix variable in the Lovász semidefinite program to be rank-one and rank-two, respectively, yields a pair of continuous, nonlinear optimization problems each having the global optimal value α(G). We propose heuristics for obtaining large stable sets in G based on these new formulations and present computational results indicating the effectiveness of the heuristics. Received: December 13, 2000 / Accepted: September 3, 2002 Published online: December 19, 2002 RID="★" ID="★" Computational results reported in this paper were obtained on an SGI Origin2000 computer at Rice University acquired in part with support from NSF Grant DMS-9872009. Key Words. maximum stable set – maximum clique – minimum vertex cover – semidefinite program – semidefinite relaxation – continuous optimization heuristics – nonlinear programming Mathematics Subject Classification (2000): 90C06, 90C27, 90C30     

Iterative algorithms for variational inequality and equilibrium problems with applications

In this paper, we introduce an iterative method for finding a common element of the set of solutions of equilibrium problems, of the set of variational inequalities and of the set of common fixed points of an infinite family of nonexpansive mappings in the framework of real Hilbert spaces. Strong convergence of the proposed iterative algorithm is obtained. As an application, we utilize the main results which improve the corresponding results announced in Chang et al. (Nonlinear Anal, 70:3307–3319, 2009), Colao et al. (J Math Anal Appl, 344:340–352, 2008), Plubtieng and Punpaeng (Appl Math Comput, 197:548–558, 2008) to study the optimization problem.