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.     

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     

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     

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.