Stochastic ultimate load analysis:models and solution methods 1

The stochastic ultimate load analysis model used in the safety analysis of engineering structures can be treated as a special case of chance-constrained problems (CCP) which minimize a stochastic cost function subject to some probabilistic constraints. Some special cases (such as a deterministic cost function with probabilistic constraints or deterministic constraints with a random cost function) for ultimate load analysis have airady been investigated by various researchers. In this paper, a generai probabilistic approach to stochastic ultimate load analysis is given. In doing so, some approximation techniques are needed due to the fact that the problems at hand are too complicated to evaluate precisely. We propose two extensions of the SQP method in which the variables appear in the algorithms inexactly. These algorithms are shown to be globally convergent for all models and locally superlinearly convergent for some special cases     

A <Emphasis Type="Italic">d</Emphasis>-person Differential Game with State Space Constraints

We consider a network of d companies (insurance companies, for example) operating under a treaty to diversify risk. Internal and external borrowing are allowed to avert ruin of any member of the network. The amount borrowed to prevent ruin is viewed upon as control. Repayment of these loans entails a control cost in addition to the usual costs. Each company tries to minimize its repayment liability. This leads to a d -person differential game with state space constraints. If the companies are also in possible competition a Nash equilibrium is sought. Otherwise a utopian equilibrium is more appropriate. The corresponding systems of HJB equations and boundary conditions are derived. In the case of Nash equilibrium, the Hamiltonian can be discontinuous; there are d interlinked control problems with state constraints; each value function is a constrained viscosity solution to the appropriate discontinuous HJB equation. Uniqueness does not hold in general in this case. In the case of utopian equilibrium, each value function turns out to be the unique constrained viscosity solution to the appropriate HJB equation. Connection with Skorokhod problem is briefly discussed.     

<Emphasis Type="Italic">ε</Emphasis>-Optimality and <Emphasis Type="Italic">ε</Emphasis>-Lagrangian Duality for a Nonconvex Programming Problem with an Infinite Number of Constraints

In this paper, ε-optimality conditions are given for a nonconvex programming problem which has an infinite number of constraints. The objective function and the constraint functions are supposed to be locally Lipschitz on a Banach space. In a first part, we introduce the concept of regular ε-solution and propose a generalization of the Karush-Kuhn-Tucker conditions. These conditions are up to ε and are obtained by weakening the classical complementarity conditions. Furthermore, they are satisfied without assuming any constraint qualification. Then, we prove that these conditions are also sufficient for ε-optimality when the constraints are convex and the objective function is ε-semiconvex. In a second part, we define quasisaddlepoints associated with an ε-Lagrangian functional and we investigate their relationships with the generalized KKT conditions. In particular, we formulate a Wolfe-type dual problem which allows us to present ε-duality theorems and relationships between the KKT conditions and regular ε-solutions for the dual. Finally, we apply these results to two important infinite programming problems: the cone-constrained convex problem and the semidefinite programming problem.     

On the first homology of automorphism groups of manifolds with geometric structures

Hermann and Thurston proved that the group of diffeomorphisms with compact support of a smooth manifold M which are isotopic to the identity is a perfect group. We consider the case where M has a geometric structure. In this paper we shall survey on the recent results of the first homology of the diffeomorphism groups which preserve a smooth G-action or a foliated structure on M. We also work in Lipschitz category. This research was partially supported by Grant-in-Aid for Scientific Research (No. 16540058), Japan Society for the Promotion of Science. This research was partially supported by Grant-in-Aid for Scientific Research (No. 14540093), Japan Society for the Promotion of Science.     

A simplified test for optimality

A simplification of recent characterizations of optimality in convex programming involving the cones of decrease and constancy of the objective and constraint functions is presented. In the original characterization due to Ben-Israelet al., optimality was verified or a feasible direction of decrease was determined by considering a number of sets equal to the number of subsets of the set of binding constraints. By first finding the set of constraints which is binding at every feasible point, it is possible to verify optimality or determine a feasible direction of decrease by considering a single set. In the case of faithfully convex functions, this set can be found by solving at mostp systems of linear equations and inequalities, wherep is the number of constraints.This work was partly supported by NSF Grant No. Eng 76-10260.     

Towards Strong Duality in Integer Programming

We consider in this paper the Lagrangian dual method for solving general integer programming. New properties of Lagrangian duality are derived by a means of perturbation analysis. In particular, a necessary and sufficient condition for a primal optimal solution to be generated by the Lagrangian relaxation is obtained. The solution properties of Lagrangian relaxation problem are studied systematically. To overcome the difficulties caused by duality gap between the primal problem and the dual problem, we introduce an equivalent reformulation for the primal problem via applying a pth power to the constraints. We prove that this reformulation possesses an asymptotic strong duality property. Primal feasibility and primal optimality of the Lagrangian relaxation problems can be achieved in this reformulation when the parameter p is larger than a threshold value, thus ensuring the existence of an optimal primal-dual pair. We further show that duality gap for this partial pth power reformulation is a strictly decreasing function of p in the case of a single constraint. Dedicated to Professor Alex Rubinov on the occasion of his 65th birthday. Research supported by the Research Grants Council of Hong Kong under Grant CUHK 4214/01E, and the National Natural Science Foundation of China under Grants 79970107 and 10571116.     

Optimal impulsive control of compartment models,I: Qualitative aspects

Optimal impulsive control of systems arising from linear compartment models for drug distribution in the human body is considered. A system of linear, time-invariant, homogeneous differential equations is given along with a set of continuous constraints on state and control. The object is to develop a constructive algorithm for the computation of the optimal control relative to a convex cost functional. It is first shown that under suitable hypotheses, satisfying the continuous constraints is equivalent to satisfying the constraints at a finite set of abstractly definedcritical points. Once these critical points have been determined, the solution of the optimal control problem is found as the solution of a finite-dimensional convex programming problem. The set of critical points can often be determineda priori solely from the qualitative behavior of the solutions of the system. A class of such problems, generalizing the so-calledplateau effect, is considered in detail. It is shown that the solution achieving the plateau effect is indeed optimal in certain cases. In a subsequent paper, an iterative algorithm will be given for the solution of these problems when the critical points cannot all be determineda priori.This work was supported in part by the National Science Foundation under Grant No. GP-20130.     

Partial Augmented Lagrangian Method and Mathematical Programs with Complementarity Constraints

In this paper, we apply a partial augmented Lagrangian method to mathematical programs with complementarity constraints (MPCC). Specifically, only the complementarity constraints are incorporated into the objective function of the augmented Lagrangian problem while the other constraints of the original MPCC are retained as constraints in the augmented Lagrangian problem. We show that the limit point of a sequence of points that satisfy second-order necessary conditions of the partial augmented Lagrangian problems is a strongly stationary point (hence a B-stationary point) of the original MPCC if the limit point is feasible to MPCC, the linear independence constraint qualification for MPCC and the upper level strict complementarity condition hold at the limit point. Furthermore, this limit point also satisfies a second-order necessary optimality condition of MPCC. Numerical experiments are done to test the computational performances of several methods for MPCC proposed in the literature. This research was partially supported by the Research Grants Council (BQ654) of Hong Kong and the Postdoctoral Fellowship of The Hong Kong Polytechnic University. Dedicated to Alex Rubinov on the occassion of his 65th birthday.     

Estimation of elastic parameters in beams and certain plates:H 1 regularization

The estimation of elastic parameters in beams and certain types of plates is discussed using anH ¹-regularization technique that easily accommodates pointwise constraints. The optimal coefficient is shown to enjoy more regularity than that assumed in the formulation of the problem. This additional smoothness is useful for analyzing the limit behavior of finite-dimensional problems. Numerical results are presented.This work was supported in part by the Air Force Office of Scientific Research, Grant AFOSR-84-0271.     

Complexity and algorithms for convex network optimization and other nonlinear problems

Nonlinear optimization algorithms are rarely discussed from a complexity point of view. Even the concept of solving nonlinear problems on digital computers is not well defined. The focus here is on a complexity approach for designing and analyzing algorithms for nonlinear optimization problems providing optimal solutions with prespecified accuracy in the solution space. We delineate the complexity status of convex problems over network constraints, dual of flow constraints, dual of multi-commodity, constraints defined by a submodular rank function (a generalized allocation problem), tree networks, diagonal dominant matrices, and nonlinear Knapsack problem's constraint. All these problems, except for the latter in integers, have polynomial time algorithms which may be viewed within a unifying framework of a proximity-scaling technique or a threshold technique. The complexity of many of these algorithms is furthermore best possible in that it matches lower bounds on the complexity of the respective problems. In general nonseparable optimization problems are shown to be considerably more difficult than separable problems. We compare the complexity of continuous versus discrete nonlinear problems and list some major open problems in the area of nonlinear optimization. MSC classification: 90C30, 68Q25     

Sequential convexification in reverse convex and disjunctive programming

This paper is about a property of certain combinatorial structures, called sequential convexifiability, shown by Balas (1974, 1979) to hold for facial disjunctive programs. Sequential convexifiability means that the convex hull of a nonconvex set defined by a collection of constraints can be generated by imposing the constraints one by one, sequentially, and generating each time the convex hull of the resulting set. Here we extend the class of problems considered to disjunctive programs with infinitely many terms, also known as reverse convex programs, and give necessary and sufficient conditions for the solution sets of such problems to be sequentially convexifiable. We point out important classes of problems in addition to facial disjunctive programs (for instance, reverse convex programs with equations only) for which the conditions are always satisfied. Finally, we give examples of disjunctive programs for which the conditions are violated, and so the procedure breaks down.The research underlying this report was supported by Grant ECS-8601660 of The National Science Foundation and Contract N00014-85-K-0198 with the Office of Naval Research. Reproduction in whole or in part is permitted for any purpose of the U.S. Government.On leave from the University of Aarhus, Denmark.     

Fast value iteration: an application of Legendre-Fenchel duality to a class of deterministic dynamic programming problems in discrete time*

ABSTRACT

We propose an algorithm, which we call ‘Fast Value Iteration’ (FVI), to compute the value function of a deterministic infinite-horizon dynamic programming problem in discrete time. FVI is an efficient algorithm applicable to a class of multidimensional dynamic programming problems with concave return (or convex cost) functions and linear constraints. In this algorithm, a sequence of functions is generated starting from the zero function by repeatedly applying a simple algebraic rule involving the Legendre-Fenchel transform of the return function. The resulting sequence is guaranteed to converge, and the Legendre-Fenchel transform of the limiting function coincides with the value function.     

Linear bilevel multi-follower programming with independent followers

This paper considers a particular case of linear bilevel programming problems with one leader and multiple followers. In this model, the followers are independent, meaning that the objective function and the set of constraints of each follower only include the leader’s variables and his own variables. We prove that this problem can be reformulated into a linear bilevel problem with one leader and one follower by defining an adequate second level objective function and constraint region. In the second part of the paper we show that the results on the optimality of the linear bilevel problem with multiple independent followers presented in Shi et al. [The kth-best approach for linear bilevel multi-follower programming, J. Global Optim. 33, 563–578 (2005)] are based on a misconstruction of the inducible region.     

Lagrangian Relaxations on Networks by <Emphasis Type="Italic">ε</Emphasis>-Subgradient Methods

The efficiency of the network flow techniques can be exploited in the solution of nonlinearly constrained network flow problems by means of approximate subgradient methods. The idea is to solve the dual problem by using ε-subgradient methods, where the dual function is estimated by minimizing approximately a Lagrangian function, which relaxes the side constraints and is subject only to network constraints. In this paper, convergence results for some kind of ε-subgradient methods are put forward. Moreover, in order to evaluate the quality of the solution and the efficiency of these methods some of them have been implemented and their performances computationally compared with codes that are able to solve the proposed test problems.     

A convergence result for a sequence of distributed-parameter optimal control problems

In this paper, we consider a sequence of abstract optimal control problems by allowing the cost integrand, the partial differential operator, and the control constraint set all to vary simultaneously. Using the notions of -convergence of functions,G-convergence of operators, and Kuratowski-Mosco convergence of sets, we show that the values of the approximating problems converge to that of the limit problem. Also we show that a convergent sequence of optimal pairs for the approximating problems has a limit which is optimal for the limit problem. A concrete example of parabolic optimal control problems is worked out in detail.This research was supported by NSF Grant No. DMS-88-02688.     

New Constrained Optimization Reformulation of Complementarity Problems

We suggest a reformulation of the complementarity problem CP(F) as a minimization problem with nonnegativity constraints. This reformulation is based on a particular unconstrained minimization reformulation of CP(F) introduced by Geiger and Kanzow as well as Facchinei and Soares. This allows us to use nonnegativity constraints for all the variables or only a subset of the variables on which the function F depends. Appropriate regularity conditions ensure that a stationary point of the new reformulation is a solution of the complementarity problem. In particular, stationary points with negative components can be avoided in contrast to the reformulation as unconstrained minimization problem. This advantage will be demonstrated for a class of complementarity problems which arise when the Karush–Kuhn–Tucker conditions of a convex inequality constrained optimization problem are considered.     

Analysis of Fractional Covering of Some Supply Management Problems

We study a supply management problem with a linear cost function and its mixed integer program. A parametric family of such problems, possessing exponential L _k -coverings, is constructed. Besides, the NP-hard expansion of the family, which has the same property, is formulated.     

Approximate Subgradient Methods for Nonlinearly Constrained Network Flow Problems

The minimization of nonlinearly constrained network flow problems can be performed by using approximate subgradient methods. The idea is to solve this kind of problem by means of primal-dual methods, given that the minimization of nonlinear network flow problems can be done efficiently exploiting the network structure. In this work, it is proposed to solve the dual problem by using ε-subgradient methods, as the dual function is estimated by minimizing approximately a Lagrangian function, which includes the side constraints (nonnetwork constraints) and is subject only to the network constraints. Some well-known subgradient methods are modified in order to be used as ε-subgradient methods and the convergence properties of these new methods are analyzed. Numerical results appear very promising and effective for this kind of problems This research was partially supported by Grant MCYT DPI 2002-03330.     

-Optimality conditions for composed convex optimization problems

The aim of the present paper is to provide a formula for the -subdifferential of f+gh different from the ones which can be found in the existent literature. Further we equivalently characterize this formula by using a so-called closedness type regularity condition expressed by means of the epigraphs of the conjugates of the functions involved. Even more, using the -subdifferential formula we are able to derive necessary and sufficient conditions for the -optimal solutions of composed convex optimization problems.     

An extension of the Kaskosz maximum principle

We strengthen the conventional maximum principle for the optimal control of nonsmooth differential equations with nonsmooth unilateral constraints. This strengthened principle applies, in particular, to any admissible relaxed trajectory whose endpoint lies on the boundary of the attainable set generated by unrelaxed admissible trajectories. In this new principle the generalized Jacobian of the right-hand side can be replaced by the generalized Jacobian of any compatible selectionh(t, x) of the convexified right-hand side that is Lipschitzian inx. This extends a recent result of Barbara Kaskosz that applies to problems without unilateral constraints and with the functionh restricted to a certain form. We also show how our arguments extend to unilateral problems defined by functional-integral equations (and, in particular, delay-differential equations).This work was partially supported by the National Science Foundation under Grant DMS 8619002.