Robust optimization – methodology and applications

Robust Optimization (RO) is a modeling methodology, combined with computational tools, to process optimization problems in which the data are uncertain and is only known to belong to some uncertainty set. The paper surveys the main results of RO as applied to uncertain linear, conic quadratic and semidefinite programming. For these cases, computationally tractable robust counterparts of uncertain problems are explicitly obtained, or good approximations of these counterparts are proposed, making RO a useful tool for real-world applications. We discuss some of these applications, specifically: antenna design, truss topology design and stability analysis/synthesis in uncertain dynamic systems. We also describe a case study of 90 LPs from the NETLIB collection. The study reveals that the feasibility properties of the usual solutions of real world LPs can be severely affected by small perturbations of the data and that the RO methodology can be successfully used to overcome this phenomenon. Received: May 24, 2000 / Accepted: September 12, 2001?Published online February 14, 2002     

Stochastic functional differential equations on manifolds

In this paper, we study stochastic functional differential equations (sfde's) whose solutions are constrained to live on a smooth compact Riemannian manifold. We prove the existence and uniqueness of solutions to such sfde's. We consider examples of geometrical sfde's and establish the smooth dependence of the solution on finite-dimensional parameters. Received: 6 July 1999 / Revised version: 19 April 2000 /?Published online: 14 June 2001     

Ginzburg-Landau vortex analogues

We consider a static one-dimensional Ginzburg-Landau equation (on a line segment or a circle) involving a large parameter λ. We show that as λ→∞, there exist solutions whose asymptotic behavior resembles the behavior of the two-dimensional vortex solutions. Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 124, No. 1, pp. 18–35, July, 2000.     

Comments on Global convergence of the method of shortest residuals by Y. Dai and Y. Yuan

Summary. We show that the example given in [Dai, Y., Yuan, Y. (1999): Global convergence of the method of shortest residuals, Numerische Mathematik 83, 581–598] does not contradict the results of [Pytlak, R. (1994): On the convergence of conjugate gradient algorithms, IMA J. Numerical Analysis 14, 443–460]. Received September 9, 2000 / Revised version received November 28, 2000 / Published online July 25, 2001     

Discretization and localization in successive convex relaxation methods for nonconvex quadratic optimization

Based on the authors’ previous work which established theoretical foundations of two, conceptual, successive convex relaxation methods, i.e., the SSDP (Successive Semidefinite Programming) Relaxation Method and the SSILP (Successive Semi-Infinite Linear Programming) Relaxation Method, this paper proposes their implementable variants for general quadratic optimization problems. These problems have a linear objective function c ^T x to be maximized over a nonconvex compact feasible region F described by a finite number of quadratic inequalities. We introduce two new techniques, “discretization” and “localization,” into the SSDP and SSILP Relaxation Methods. The discretization technique makes it possible to approximate an infinite number of semi-infinite SDPs (or semi-infinite LPs) which appeared at each iteration of the original methods by a finite number of standard SDPs (or standard LPs) with a finite number of linear inequality constraints. We establish:?•Given any open convex set U containing F, there is an implementable discretization of the SSDP (or SSILP) Relaxation Method which generates a compact convex set C such that F⊆C⊆U in a finite number of iterations.?The localization technique is for the cases where we are only interested in upper bounds on the optimal objective value (for a fixed objective function vector c) but not in a global approximation of the convex hull of F. This technique allows us to generate a convex relaxation of F that is accurate only in certain directions in a neighborhood of the objective direction c. This cuts off redundant work to make the convex relaxation accurate in unnecessary directions. We establish:?•Given any positive number ε, there is an implementable localization-discretization of the SSDP (or SSILP) Relaxation Method which generates an upper bound of the objective value within ε of its maximum in a finite number of iterations. Received: June 30, 1998 / Accepted: May 18, 2000?Published online September 20, 2000     

Existence and Structure of Optimal Solutions of Infinite-Dimensional Control Problems

In this work we analyze the structure of optimal solutions for a class of infinite-dimensional control systems. We are concerned with the existence of an overtaking optimal trajectory over an infinite horizon. The existence result that we obtain extends the result of Carlson, Haurie, and Jabrane to a situation where the trajectories are not necessarily bounded. Also, we show that an optimal trajectory defined on an interval [0,τ] is contained in a small neighborhood of the optimal steady-state in the weak topology for all t ∈ [0,τ] \backslash E , where E \subset [0,τ] is a measurable set such that the Lebesgue measure of E does not exceed a constant which depends only on the neighborhood of the optimal steady-state and does not depend on τ . Accepted 26 July 2000. Online publication 13 November 2000.     

Transcendental divisors and their critical functions

 In this paper we try to generalize the notion of a minimal polynomial of an algebraic number to a class of transcendental elements from where is the completion of the algebraic closure of ℚ in ℂ, relative to the spectral norm on : ([PPP], [PPZ1], [PPZ2], [PPZ3]). Received: 2 July 2002 / Revised version: 13 January 2003 Published online: 20 March 2003 Mathematics Subject Classification (2000): 11R99     

How fast are the particles of super-Brownian motion?

In this paper we investigate fast particles in the range and support ofsuper-Brownian motion in the historical setting. In this setting eachparticle of super-Brownian motion alive at time t is represented by apath w:[0,t]→ℝ ^d and the state of historical super-Brownian motionis a measure on the set of paths. Typical particles have Brownian paths,however in the uncountable collection of particles in the range of asuper-Brownian motion there are some which at exceptional times movefaster than Brownian motion. We determine the maximal speed of allparticles during a given time period E, which turns out to be afunction of the packing dimension of E. A path w in the support ofhistorical super-Brownian motion at time t is called a-fast if . Wecalculate the Hausdorff dimension of the set of a-fast paths in thesupport and the range of historical super-Brownian motion. A valuabletool in the proofs is a uniform dimension formula for the Browniansnake, which reduces dimension problems in the space of stopped paths to dimension problems on the line. Received: 27 January 2000 / Revised version: 28 August 2000 / Published online: 24 July 2001     

The final NETLIB-LP results

With standard linear programming solvers there is always some uncertainty about the precise values of the optimal solutions. We implemented a program using exact rational arithmetic to compute proofs for the feasibility and optimality of an LP solution. This paper reports the exact optimal objective values for all NETLIB problems.     

The multiplicity of solutions in non-homogeneous boundary value problems

We use a method recently devised by Bolle to establish the existence of an infinite number of solutions for various non-homogeneous boundary value problems. In particular, we consider second order systems, Hamiltonian systems as well as semi-linear partial differential equations. The non-homogeneity can originate in the equation but also from the boundary conditions. The results are more satisfactory than those obtained by the standard “Perturbation from Symmetry” method that was developed – in various forms – in the early eighties by Bahri–Berestycki, Struwe and Rabinowitz. Received: 13 August 1998 / Revised version: 6 July 1999     

An augmented Lagrangian interior-point method using directions of negative curvature

 We describe an efficient implementation of an interior-point algorithm for non-convex problems that uses directions of negative curvature. These directions should ensure convergence to second-order KKT points and improve the computational efficiency of the procedure. Some relevant aspects of the implementation are the strategy to combine a direction of negative curvature and a modified Newton direction, and the conditions to ensure feasibility of the iterates with respect to the simple bounds. The use of multivariate barrier and penalty parameters is also discussed, as well as the update rules for these parameters. We analyze the convergence of the procedure; both the linesearch and the update rule for the barrier parameter behave appropriately. As the main goal of the paper is the practical usage of negative curvature, a set of numerical results on small test problems is presented. Based on these results, the relevance of using directions of negative curvature is discussed. Received: July 2000 / Accepted: October 2002 Published online: December 19, 2002 Key words. Primal-dual methods – Nonconvex optimization – Linesearches Research supported by Spanish MEC grant BEC2000-0167 Mathematics Subject Classification (1991): 49M37, 65K05, 90C30     

Inequality averse multi-utilitarian bargaining solutions

This paper introduces and analyzes the class of inequality averse multi-utilitarian solutions for cooperative bargaining problems. We show that generalized Gini solutions and inequality averse Choquet solutions are particular cases of this new multi-valued solution concept and provide a complete characterization in which an invariance property, consisting of a weakening of both the linear invariance axiom in Blackorby et al. (Econometrica 62:1161–1178, 1994) and the restricted invariance axiom in Ok and Zhou (Games Econ Behav 33:249–264, 2000), plays an important role. Moreover, by relaxing the assumptions involved in the characterization, the class is extended to include inequality loving multi-utilitarian solutions which are also studied in the paper.     

Non-existence of certain semistable abelian varieties

We show that there is no semistable abelian variety defined over ℚ with bad reduction at exactly one prime p≤ 7. Received: 7 November 2000 / Revised version: 13 July 2001     

Nonlinear elliptic equations with natural growth in general domains

We prove the existence of solutions of nonlinear elliptic equations with first-order terms having “natural growth” with respect to the gradient. The assumptions on the source terms lead to the existence of possibly unbounded solutions (though with exponential integrability). The domain Ω is allowed to have infinite Lebesgue measure. Received: April 13, 2001; in final form: September 29, 2001?Published online: July 9, 2002     

Lifschitz tail in a magnetic field: coexistence of classical and quantum behavior in the borderline case

We establish the exact low-energy asymptotics of the integrated density of states (Lifschitz tail) in a homogeneous magnetic field and Poissonian impurities with a repulsive single-site potential of Gaussian decay. It has been known that the Gaussian potential tail discriminates between the so-called “classical” and “quantum” regimes, and precise asymptotics are known in these cases. For the borderline case, the coexistence of the classical and quantum regimes was conjectured. Here we settle this last remaining open case to complete the full picture of the magnetic Lifschitz tails. Received: 28 March 2000 / Revised version: 22 December 2000 / Published online: 24 July 2001     

A general non-convex large deviation result with applications to stochastic equations

We prove an abstract large deviation result for a sequence of random elements of a vector space satisfying an “abstract exponential martingale condition”. The framework naturally generates non-convex rate functions. We apply the result to solutions of It? stochastic equations in R ^d driven by Brownian motion and a Poisson random measure. Received: 23 June 1999 / Revised version: 17 February 2000 / Published online: 22 November 2000