TALK ABSTRACTS for WCOM–AUTUMN 1996

Tseng, “Merit functions for semi-definite complementarity problems”

Many merit functions (also called exact penalty functions) have been proposed for the complementarity problem defined over ℜ^{n}, the space of n-dimensional real vectors. (Formally, the problem is to find, for a given F : ℜ^{n} ↦ ℜ^{n}, an x ∈ ℜ^{n} satisfying x ≥ 0, F (x) ≥ 0, ⟨x, F (x)⟩ = 0, where ⟨ , ⟩ denotes the Euclidean inner product.) We study the extension of these merit functions to the complementarity problem defined over the space of n × n real symmetric matrices, where the Euclidean inner product is replaced by the matrix trace inner product and entrywise nonnegativity of vectors is replaced by positive semi-definiteness of matrices. The extension suggests new methods for solving semi-definite programming problems.

Salinger, “Dynamic splitting: an operator splitting algorithm for the multistage stochastic programming problem”

A method of decomposition will be described that is based on a saddle point characterization of optimality for such large-scale problems of convex type. Classical linear-quadratic dynamic programming (unconstrained) alternates with solving small subproblems that concern only what happens at a particular time under a particular scenario.

Vityaev, “On the certainty equivalence principle in nonlinear control and the Hamilton-Jacobi-Bellman-Isaac equation”

This talk will begin with introducing worst-case design problems in nonlinear control. A game theory approach will be used to derive Hamilton-Jacobi equation. The certainty equivalence principle will be introduced. New results will be briefly announced at the end.

Xu, “Interior and non-interior path-following methods for complemearity problems”

All of the currently available interior point path-following methods for the linear complementarity problem (LCP) are based on Newton’s method applied to a fixed set of nonlinear equations characterizing the central path. We consider an alternative system of equations studied by Chen, Harker, and Kanzow that also characterizes the central path. In the Chen-Harker and Kanzow papers, Newton’s method is applied to this alternative system without the requirement that the iterates remain in the interior of the positive orthant. The numerical performance of these methods is as good or better than the performance of the standard interior point strategies applied to LCP. In light of these experiments, one is led to speculate that a polynomial complexity result should exist for some variation of the Chen-Harker and Kanzow algorithms. In this talk we propose just such a variation having polynomial complexity. The primary drawback of the proposed algorithm is that it requires the iterates to remain in the interior of the positive orthant. A non-interior point variation that is globally linearly convergent is also presented. However, we have not resolved the complexity of this non-interior method. We illustrate the practical performance of these algorithms by applying them to a few simple test problems.

Ruszczynski, “A stochastic branch-and-bound method”

Stochastic integer programming problems are very difficult. One source of difficulties is the combinatorial complexity, the other one is the stochastic nature which makes the objective function hard to evaluate.

We present a new methodology to address such complex problems. It combines ideas from optimization theory and statistics and has a form of a stochastic branch-and-bound method. At each step of the method a certain partition of the feasible set is considered, and for each subset stochastic estimates of lower and upper bounds for the objective function are calculated. These are used to construct a new partition for which new estimates are generated, etc.

Contrary to many heuristic random search or learning methods, the new approach is convergent with probability one to the optimal solution and provides confidence intervals for intermediate solutions. We show that stochastic lower and upper bounds in many cases can be calculated much easier than deterministic bounds and we present a number of techniques for improving their accuracy.

We also discuss generalizations of the approach to stochastic global optimization. Finally, we present some numerical results, and in particular application of the new methodology to the problem of water quality management.

Loewen, “Necessary conditions for nonLipschitzian optimal control problems”

I will discuss a simple proof of the Maximum Principle for the optimal control of nonsmooth ordinary differential equations under Lipschitz continuity assumptions weaker than those in standard treatments. This proof, devised jointly with R. B. Vinter and H. Zheng, combines problem reformulation with Ekeland’s variational principle, followed by an application of Clarke’s nonsmooth maximum principle.

Wolenski, “Proximal analysis and the minimal time function”

For x ∈ R^{n}, let T (x) denote the least time that a trajectory of a given control system originating from x can reach a given closed set S (the ”target” set). The (possibly extended-real-valued) function T (·) is called the minimal time function. Using notions of flow invariance, we illustrate that T (·) is the proximal solution to an appropiate Hamilton-Jacobi equation that satisfies certain boundary conditions. Further related results include the following. (1) A formula that relates the proximal subgradients of T (·) to certain proximal normal vectors of its level sets. (2) Necessary and sufficient conditions for local Lipschitz behavior of T (·) near the target set. (3) Sufficient conditions for attainability.

Jeyakumar, “Approximate Jacobians and nonsmooth analysis”

A frequent problem in modeling is the proper treatment of nonsmooth functions and the development of efficient numerical methods for nonsmooth optimization problems. In this talk I will introduce a new concept of approximate Jacobian for a continuous vectorvalued map and discuss applications to optimization problems. The approach is based on the successful recent construction of a convexificator of real-valued valued functions. Mean value conditions for continuous vector-valued maps and Taylor’s expansions for continuously Gâteaux differentiable functions (i.e. C^{1} functions) will be discussed in terms of approximate Jacobians and approximate Hessians respectively. Monotonicity characterizations and second-order necessary and sufficient conditions for optimality and convexity of C^{1} functions will also be discussed.