On the Use of Augmented Lagrangians in the Solution of Generalized Semi-Infinite Min-Max Problems

We present an approach for the solution of a class of generalized semi-infinite optimization problems. Our approach uses augmented Lagrangians to transform generalized semi-infinite min-max problems into ordinary semi-infinite min-max problems, with the same set of local and global solutions as well as the same stationary points. Once the transformation is effected, the generalized semi-infinite min-max problems can be solved using any available semi-infinite optimization algorithm. We illustrate our approach with two numerical examples, one of which deals with structural design subject to reliability constraints.     

An Inexact Modified Subgradient Algorithm for Primal-Dual Problems via Augmented Lagrangians

We consider a primal optimization problem in a reflexive Banach space and a duality scheme via generalized augmented Lagrangians. For solving the dual problem (in a Hilbert space), we introduce and analyze a new parameterized Inexact Modified Subgradient (IMSg) algorithm. The IMSg generates a primal-dual sequence, and we focus on two simple new choices of the stepsize. We prove that every weak accumulation point of the primal sequence is a primal solution and the dual sequence converges weakly to a dual solution, as long as the dual optimal set is nonempty. Moreover, we establish primal convergence even when the dual optimal set is empty. Our second choice of the stepsize gives rise to a variant of IMSg which has finite termination.     

Numerical Solution of Non-Steady State Porous Flow Free Boundary Problems

The aim of this paper is the study of the convergence of a finite element approximation for a variational inequality related to free boundary problems in non-steady fluid flow through porous media. There have been many results in the stationary case, for example, the steady dam problems, the steady flow well problems, etc. In this paper we shall deal with the axisymmetric non-steady porous flow well problem. It is well know that by means of Torelli's transform this problem, similar to the non-steady rectangular dam problem, can be reduced a variational, inequality, and the existence, uniqueness and regularity of the solution can be obtained ([12, 7]). Now we study the numerical solution of this variational inequality. The main results are as follows: 1. We establish new regularity properties for the solution $W$ of the variation inequality. We prove that $W \in L^\infty(0, T; H^2(D))$, $γ_0W\in L^\infty(0, T; H^2(T_n))$ and $D_1γ_0W\in L^2(0, T; H^1(T_n))$ (see Theorem 2.5). Friedman and Torelli [7] obtained $W\in L^2(0, T; H^2(D))$. Our new regularity properties will be used for error estimation. 2. We prove that the error estimate for the finite element solution of the variational inequality is $$ ( \sum^N_{i=1}\| W^1 - W^1_h \|^2_{H^1(D)}\Delta t)^{1/2} = O(h+\Delta t^{1/2})$$ (see Theorem 3.4). In the stationary case the error estimate is $\|W-W_h\|_{H^1(D)} = O(k)$ ([3,6]). 3. We give a numerical example and compare the result with the corresponding result in the stationary case. The result of this paper are valid for the non-ready rectangular dam problem with stationary or quasi-stationary initial data (see [7], p.534).     

Augmented Lagrangians which are quadratic in the multiplier

We present a class of new augmented Lagrangian functions with the essential property that each member is concave quadratic when viewed as a function of the multiplier. This leads to an improved duality theory and to a related class of exact penalty functions. In addition, a relationship between Newton steps for the classical Lagrangian and the new Lagrangians is established.This work was supported in part by ARO Grant No. DAAG29-77-G-0125.     

Duality and Exact Penalization for General Augmented Lagrangians

We consider a problem of minimizing an extended real-valued function defined in a Hausdorff topological space. We study the dual problem induced by a general augmented Lagrangian function. Under a simple set of assumptions on this general augmented Lagrangian function, we obtain strong duality and existence of exact penalty parameter via an abstract convexity approach. We show that every cluster point of a sub-optimal path related to the dual problem is a primal solution. Our assumptions are more general than those recently considered in the related literature.     

Numerical Comparison of Augmented Lagrangian Algorithms for Nonconvex Problems

Augmented Lagrangian algorithms are very popular tools for solving nonlinear programming problems. At each outer iteration of these methods a simpler optimization problem is solved, for which efficient algorithms can be used, especially when the problems are large. The most famous Augmented Lagrangian algorithm for minimization with inequality constraints is known as Powell-Hestenes-Rockafellar (PHR) method. The main drawback of PHR is that the objective function of the subproblems is not twice continuously differentiable. This is the main motivation for the introduction of many alternative Augmented Lagrangian methods. Most of them have interesting interpretations as proximal point methods for solving the dual problem, when the original nonlinear programming problem is convex. In this paper a numerical comparison between many of these methods is performed using all the suitable problems of the CUTE collection.This author was supported by ProNEx MCT/CNPq/FAPERJ 171.164/2003, FAPESP (Grants 2001/04597-4 and 2002/00094-0 and 2003/09169-6) and CNPq (Grant 302266/2002-0).This author was partially supported by CNPq-Brasil and CDCHT-Venezuela.This author was supported by ProNEx MCT/CNPq/FAPERJ 171.164/2003, FAPESP (Grant 2001/04597-4) and CNPq.     

Addressing the greediness phenomenon in Nonlinear Programming by means of Proximal Augmented Lagrangians

When one solves Nonlinear Programming problems by means of algorithms that use merit criteria combining the objective function and penalty feasibility terms, a phenomenon called greediness may occur. Unconstrained minimizers attract the iterates at early stages of the calculations and, so, the penalty parameter needs to grow excessively, in such a way that ill-conditioning harms the overall convergence. In this paper a regularization approach is suggested to overcome this difficulty. An Augmented Lagrangian method is defined with the addition of a regularization term that inhibits the possibility that the iterates go far from a reference point. Convergence proofs and numerical examples are given.     

On Numerical Solution of Shape Inverse Problems

The new method is proposed for the numerical solution of a class of shape inverse problems. The size and the location of a small opening in the domain of integration of an elliptic equation is identified on the basis of an observation. The observation includes the finite number of shape functionals. The approximation of the shape functionals by using the so-called topological derivatives is used to perform the learning process of an artificial neural network. The results of computations for 2D examples show, that the method allows to determine an approximation of the global solution to the inverse problem, sufficiently closed to the exact solution. The proposed method can be extended to the problems with an opening of general shape and to the identification problems of small inclusions. However, the mathematical theory of the proposed approach still requires futher research. In particular, the proof of global convergence of the method is an open problem.     

Numerical Solution of Exterior Problems by the Peripheral Block Over-relaxation Method

The numerical solution of exterior problems involving ellipticpartial differential equations presents a formidable problem,even with present day computers and the recent improvementsin convergence rates of iterative methods. In this paper, the successive peripheral block over-relaxationmethod (SPOR) previously successively applied to a variety ofboundary value problems in annular and circular regions (Benson& Evans, 1972) is shown to be a suitable method for exteriorproblems.     

On Duality in Nonconvex Vector Optimization in Banach Spaces Using Augmented Lagrangians

This paper shows how the use of penalty functions in terms of projections on the constraint cones, which are orthogonal in the sense of Birkhoff, permits to establish augmented Lagrangians and to define a dual problem of a given nonconvex vector optimization problem. Then the weak duality always holds. Using the quadratic growth condition together with the inf-stability or a kind of Rockafellar's stability called stability of degree two, we derive strong duality results between the properly efficient solutions of the two problems. A strict converse duality result is proved under an additional convexity assumption, which is shown to be essential.     

Augmented Lagrangians with possible infeasibility and finite termination for global nonlinear programming

In a recent paper, Birgin, Floudas and Martínez introduced an augmented Lagrangian method for global optimization. In their approach, augmented Lagrangian subproblems are solved using the $\alpha $ BB method and convergence to global minimizers was obtained assuming feasibility of the original problem. In the present research, the algorithm mentioned above will be improved in several crucial aspects. On the one hand, feasibility of the problem will not be required. Possible infeasibility will be detected in finite time by the new algorithms and optimal infeasibility results will be proved. On the other hand, finite termination results that guarantee optimality and/or feasibility up to any required precision will be provided. An adaptive modification in which subproblem tolerances depend on current feasibility and complementarity will also be given. The adaptive algorithm allows the augmented Lagrangian subproblems to be solved without requiring unnecessary potentially high precisions in the intermediate steps of the method, which improves the overall efficiency. Experiments showing how the new algorithms and results are related to practical computations will be given.     

Augmented Lagrangians with Adaptive Precision Control for Quadratic Programming with Equality Constraints

In this paper we introduce an augmented Lagrangian type algorithm for strictly convex quadratic programming problems with equality constraints. The new feature of the proposed algorithm is the adaptive precision control of the solution of auxiliary problems in the inner loop of the basic algorithm. Global convergence and boundedness of the penalty parameter are proved and an error estimate is given that does not have any term that accounts for the inexact solution of the auxiliary problems. Numerical experiments illustrate efficiency of the algorithm presented     

Numerical Solution of Several Models of Internal Transonic Flow

The paper deals with numerical solution of internal flow problems. It mentions a long tradition of mathematical modeling of internal flow, especially transonic flow at our department. Several models of flow based on potential equation, Euler equations, Navier-Stokes and Reynolds averaged Navier-Stokes equations with proper closure are considered. Some mathematical and numerical properties of the model are mentioned and numerical results achieved by in-house developed methods are presented.     

The Numerical Solution of Constrained Linear Least-squares Problems

The paper describes a numerically stable algorithm to solveconstrained linear least-squares problems and allows rank deficientor underdetermined observation matrices. The method starts withthe calculation of the rank of the observation matrix and thetransformation into a least distance problem. The proposed techniquefor solving the least distance problem can be considered asa generalization of the projection method of Stoer (1971). Startingwith a feasible point, a sequence of iterates is calculatedby minimizing the objective function on the linear boundarymanifold determined by the active constraints. Numerical examplesshow the feasibility of the algorithm.     

Some Results on Augmented Lagrangians in Constrained Global Optimization via Image Space Analysis

The aim of this paper is to present some results for the augmented Lagrangian function in the context of constrained global optimization by means of the image space analysis. It is first shown that a saddle point condition for the augmented Lagrangian function is equivalent to the existence of a regular nonlinear separation in the image space. Local and global sufficient optimality conditions for the exact augmented Lagrangian function are then investigated by means of second-order analysis in the image space. Local optimality result for this function is established under second-order sufficiency conditions in the image space. Global optimality result is further obtained under additional assumptions. Finally, it is proved that the exact augmented Lagrangian method converges to a global solution–Lagrange multiplier pair of the original problem under mild conditions.     

Numerical Solution of Transonic Flow in SE1050 Cascade

The SE1050 cascade is an open test case (QNET network) of plane turbine cascade measured at the IT ASCR wind tunnel. The two regimes with subsonic and supersonic outletMach number were selected for numerical simulation. Several numerical methods have been developed and also several turbulence models have been implemented. Comparison of computed results and experimental data gives us opportunity to discuss main features of transonic flow field in well designed turbine cascade, possibilities of its numerical capturing (grid quality, numerical viscosity, turbulence model, boundary layer transition) and its influence on prediction of energy losses. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

The Numerical Solution of Linear One-dimensional Parabolic Problems by the Method of Moments

^* Present address: Department of Mathematics, Carnegie Institute of Technology, Pittsburg, Pa., U.S.A. An account is given of the method of moments and its applicationto the numerical solution of the simple one-dimensional heatconduction equation. The rapid convergence of the method isdemonstrated by numerical examples and an estimate of the erroris given. Features in common with the matrix method of Wadsworth& Wragg are also discussed.     

Numerical Solution of Parabolic Problems with Nonlocal Boundary Conditions

In this article, the one-dimensional parabolic equation with three types of integral nonlocal boundary conditions is approximated by the implicit Euler finite difference scheme. Stability analysis is done in the maximum norm and it is proved that the radius of the stability region and the stiffness of the discrete scheme depends on the signs of coefficients in the nonlocal boundary condition. The known stability results are improved. In the case of a plain integral boundary condition, the conditional convergence rate is proved and the regularization relation between discrete time and space steps is proposed. The accuracy of the obtained estimates is illustrated by results of numerical experiments.