No abstract uploaded!

The trust-region problem,which minimizes a nonconvex quadratic function over a ball, is a key subproblem in trust-region methods for solving nonlinear optimization problems. It enjoys many attractive properties such as an exact semi-definite linear programming relaxation (SDP-relaxation) and strong duality. Unfortunately, such properties do not, in general, hold for an extended trust-region problem having extra linear constraints. This paper shows that two useful and powerful features of the classical trust-region problem continue to hold for an extended trust-region problem with linear inequality constraints under a new dimension condition. First, we establish that the class of extended trust-region problems has an exact SDP-relaxation, which holds without the Slater constraint qualification. This is achieved by proving that a system of quadratic and affine functions involved in the model satisfies a range-convexity whenever the dimension condition is fulfilled. Second, we show that the dimension condition together with the Slater condition ensures that a set of combined first and second-order Lagrange multiplier conditions is necessary and sufficient for global optimality of the extended trust-region problem and consequently for strong duality. Through simple examples we also provide an insightful account of our development from SDP-relaxation to strong duality. Finally, we show that the dimension condition is easily satisfied for the extended trust-region model that arises from the reformulation of a robust least squares problem (LSP) as well as a robust second order cone programming model problem (SOCP) as an equivalent semi-definite linear programming problem. This leads us to conclude that, under mild assumptions, solving a robust LSP or SOCP under matrix-norm uncertainty or polyhedral uncertainty is equivalent to solving a semi-definite linear programming problem and so, their solutions can be validated in polynomial time.

In this paper, we study the rate of convergence of the cyclic projection algorithm applied to finitely many basic semialgebraic convex sets. We establish an explicit convergence rate estimate which relies on the maximum degree of the polynomials that generate the basic semialgebraic convex sets and the dimension of the underlying space. We achieve our results by exploiting the algebraic structure of the basic semialgebraic convex sets.

A fourth order finite difference method is presented for the 2D unsteady viscous incompressible Boussinesq equations in vorticity-stream function formulation. The method is especially suitable for moderate to large Reynolds number flows. The momentum equation is discretized by a compact fourth order scheme with the no-slip boundary condition enforced using a local vorticity boundary condition. Fourth order long-stencil discretizations are used for the temperature transport equation with one-sided extrapolation applied near the boundary. The time stepping scheme for both equations is classical fourth order Runge–Kutta. The method is highly efficient. The main computation consists of the solution of two Poisson-like equations at each Runge–Kutta time stage for which standard FFT based fast Poisson solvers are used. An example of Lorenz flow is presented, in which the full fourth order accuracy is checked. The numerical simulation of a strong shear flow induced by a temperature jump, is resolved by two perfectly matching resolutions. Additionally, we present benchmark quality simulations of a differentially-heated cavity problem. This flow was the focus of a special session at the first MIT conference on Computational Fluid and Solid Mechanics in June 2001.

No abstract uploaded!