Properties of an interior embedding for solving nonlinear optimization problems

The paper presents an interior embedding of nonlinear optimization problems. This embedding satisfies a sufficient condition for the success of pathfollowing algorithms with jumps being applied to one-parametric optimization problems.?The one-parametric problem obtained by the embedding is supposed to be regular in the sense of Jongen, Jonker and Twilt. This asumption is analyzed, and its genericity is proved in the space of the original optimization problems. Received May 20, 1997 / Revised version received October 6, 1998?Published online May 12, 1999     

A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities

In this paper we take a new look at smoothing Newton methods for solving the nonlinear complementarity problem (NCP) and the box constrained variational inequalities (BVI). Instead of using an infinite sequence of smoothing approximation functions, we use a single smoothing approximation function and Robinson’s normal equation to reformulate NCP and BVI as an equivalent nonsmooth equation H(u,x)=0, where H:ℜ ²ⁿ →ℜ ²ⁿ , u∈ℜ ⁿ is a parameter variable and x∈ℜ ⁿ is the original variable. The central idea of our smoothing Newton methods is that we construct a sequence {z ^k =(u ^k ,x ^k )} such that the mapping H(·) is continuously differentiable at each z ^k and may be non-differentiable at the limiting point of {z ^k }. We prove that three most often used Gabriel-Moré smoothing functions can generate strongly semismooth functions, which play a fundamental role in establishing superlinear and quadratic convergence of our new smoothing Newton methods. We do not require any function value of F or its derivative value outside the feasible region while at each step we only solve a linear system of equations and if we choose a certain smoothing function only a reduced form needs to be solved. Preliminary numerical results show that the proposed methods for particularly chosen smoothing functions are very promising. Received June 23, 1997 / Revised version received July 29, 1999?Published online December 15, 1999     

SOR- and Jacobi-type iterative methods for solving <Emphasis Type="Italic">ℓ</Emphasis><Subscript>1</Subscript> − <Emphasis Type="Italic">ℓ</Emphasis><Subscript>2</Subscript> problems by way of Fenchel duality

We present an SOR-type algorithm and a Jacobi-type algorithm that can effectively be applied to the ℓ ₁ − ℓ ₂ problem by exploiting its special structure. The algorithms are globally convergent and can be implemented in a particularly simple manner. Relations with coordinate minimization methods are discussed.     

A randomized Delaunay triangulation heuristic for the Euclidean Steiner tree problem in <Emphasis Type="Italic">ℜ</Emphasis><Superscript><Emphasis Type="Italic">d</Emphasis></Superscript>

We present a heuristic for the Euclidean Steiner tree problem in ℜ ^d for d≥2. The algorithm utilizes the Delaunay triangulation to generate candidate Steiner points for insertion, the minimum spanning tree to identify the Steiner points to remove, and second-order cone programming to optimize the location of the remaining Steiner points. Unlike other ESTP heuristics relying upon Delaunay triangulation, we insert Steiner points probabilistically into Delaunay triangles to achieve different subtrees on subsets of terminal points. We govern this neighbor generation procedure with a local search framework that extends effectively into higher dimensions. We present computational results on benchmark test problems in ℜ ^d for 2≤d≤5.     

Penalization techniques in L ∞ optimization problems with unbounded horizon

In this work we present a numerical procedure for the ergodic optimal minimax control problem. Restricting the development to the case with relaxed controls and using a perturbation of the instantaneous cost function, we obtain discrete solutions U _ε ^k that converge to the optimal relaxed cost U when the relation ship between the parameters of discretization k and penalization ε is an appropriate one. This paper aims to be a tribute to Prof. Roberto L.V. González who died after we finished this work. This paper was supported by grant PIP 5379 CONICET.     

Induction over Strategic Agents: a genetic algorithm solution

We study the problem called Induction over Strategic Agents. This problem has proven hard to solve, even for small problems. We start by reducing the problem to an unconstrained search over w∈ℜ ⁿ . Once we accomplish this, we develop a Genetic Algorithm to perform this search. We compare our results to those obtained on a Mixed Integer formulation.     

A smooth method for the finite minimax problem

We consider unconstrained minimax problems where the objective function is the maximum of a finite number of smooth functions. We prove that, under usual assumptions, it is possible to construct a continuously differentiable function, whose minimizers yield the minimizers of the max function and the corresponding minimum values. On this basis, we can define implementable algorithms for the solution of the minimax problem, which are globally convergent at a superlinear convergence rate. Preliminary numerical results are reported.This research was partially supported by the National Research Program on Metodi di ottimizzazione per le decisioni, Ministero dell'Università e della Ricerca Scientifica e Tecnologica, Italy.     

Categoricity of an abstract elementary class in two successive cardinals

We investigate categoricity of abstract elementary classes without any remnants of compactness (like non-definability of well ordering, existence of E.M. models, or existence of large cardinals). We prove (assuming a weak version of GCH around λ) that if ℜ is categorical in λ, λ⁺,LS(ℜ) ≤ λ and has intermediate number of models in λ⁺⁺,then ℜ has a model in λ⁺⁺⁺. Partially supported by the United States-Israel Binational Science Foundation. I thank Alice Leonhardt for the excellent typing. Publication No. 576.     

Minimax detection of a signal in the heteroscedastic Gaussian white noise

We consider the problem of signal detection in the heteroscedastic Gaussian white noise when the set of alternatives is essentially nonparametric. In this setting, we find a family of asymptotically minimax tests. The results are extended to the case of testing a parametric hypothesis against nonparametric sets of alternatives. Bibliography: 8 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 320, 2004, pp. 54–68.     

Generalized convexity and concavity of the optimal value function in nonlinear programming

In this paper we consider generalized convexity and concavity properties of the optimal value functionf ^* for the general parametric optimization problemP(_ε) of the form min _x f(x, ε) s.t.x∈R(ε). Many results on convexity and concavity characterizations off ^* were presented by the authors in a previous paper. Such properties off ^* and the solution set mapS ^* form an important part of the theoretical basis for sensitivity, stability and parametric analysis in mathematical optimization. We give sufficient conditions for several types of generalized convexity and concavity off ^*, in terms of respective generalized convexity and concavity assumptions onf and convexity and concavity assumptions on the feasible region point-to-set mapR. Specializations of these results to the parametric inequality-equality constrained nonlinear programming problem are provided. Research supported by Grant ECS-8619859, National Science Foundation and Contract N00014-86-K-0052, Office of Naval Research.     

Global existence and time decay of small solutions to the landau-ginzburg type equations

We study the Cauchy problem for the nonlinear dissipative equations (0.1) uo∂u-αδu + Β|u|^2/n u = 0,x ∃ Rⁿ,t } 0,u(0,x) = u0(x),x ∃ Rⁿ, where α,Β ∃ C, ℜα 0. We are interested in the dissipative case ℜα 0, and ℜδ(α,Β)≥ 0, θ = |∫ u0(x)dx| ⊋ 0, where δ(α, Β) = ##|α|^n-1n^n/2 / ((n + 1)|α|² + α^{2 n/2}. Furthermore, we assume that the initial data u₀ ∃ L^p are such that (1 + |x|)^αu0 ∃ L¹, with sufficiently small norm ∃ = (1 + |x|)^α u₀ 1 + u₀ p, wherep 1, α ∃ (0,1). Then there exists a unique solution of the Cauchy problem (0.1)u(t, x) ∃ C ((0, ∞); L^∞) ∩ C ([0, ∞); L¹ ∩ L^p) satisfying the time decay estimates for allt0 u(t)||_∞ Cɛt^-n/2(1 + η log 〈t〉)^-n/2, if hg = θ^2/n 2_π ℜδ(α, Β) 0; u(t)||_∞ Cɛt^-n/2(1 + Μ log 〈t〉)^-n/4, if η = 0 and Μ = θ^4/n 4π)² (ℑδ(α, Β))² ℜ((1 + 1/n) υ1-1 υ2) 0; and u(t)||_∞ Cɛt^-n/2(1 + κ log 〈t〉)^-n/6, if η = 0, Μ = 0, κ 0, where υl,l = 1,2 are defined in (1.2), κ is a positive constant defined in (2.31).     

A particle approximation of the solution of the Kushner–Stratonovitch equation

We construct a sequence of branching particle systems α _n convergent in measure to the solution of the Kushner–Stratonovitch equation. The algorithm based on this result can be used to solve numerically the filtering problem. We prove that the rate of convergence of the algorithm is of order n ^?. This paper is the third in a sequence, and represents the most efficient algorithm we have identified so far. Received: 4 February 1997 / Revised version: 26 October 1998     

Minimax risk over quadratically convex sets

We consider the problem of estimating a vector θ = (θ₁, θ₂,…) ∈ Θ ⊂ l ₂ from observations y _i = θ _i + σ _i x _i , i = 1, 2,…, where the random values x _i are N(0, 1), independent, and identically distributed, the parametric set Θ is compact, orthosymmetric, convex, and quadratically convex. We show that in that case, the minimax risk is not very different from sup?_L( P) \sup {\Re_L}\left( \Pi \right) , where ?_L( P) {\Re_L}\left( \Pi \right) is the minimax linear risk in the same problem with parametric set Π, and sup is taken over all the hyperrectangles Π ⊂ Θ. Donoho, Liu, and McGibbon (1990) have obtained this result for the case of equal σ _i , i = 1, 2,…. Bibliography: 4 titles.     

Second order necessary and sufficient conditions for convex composite NDO

In convex composite NDO one studies the problem of minimizing functions of the formF:=h ○f whereh:ℝ ^m → ℝ is a finite valued convex function andf:ℝ ⁿ → ℝ ^m is continuously differentiable. This problem model has a wide range of application in mathematical programming since many important problem classes can be cast within its framework, e.g. convex inclusions, minimax problems, and penalty methods for constrained optimization. In the present work we extend the second order theory developed by A.D. Ioffe in [11, 12, 13] for the case in whichh is sublinear, to arbitrary finite valued convex functionsh. Moreover, a discussion of the second order regularity conditions is given that illuminates their essentially geometric nature.     

Smoothing Newton Method for Minimizing the Sum of <Emphasis Type="Italic">p</Emphasis>-Norms

Consider the problem of minimizing the sum of p-norms, where p is a fixed real number in the interval [1,2]. This nondifferentiable problem arises in many applications, including the VLSI (very-large-scale-integration) layout problem, the facilities location problem and the Steiner minimum tree problem under a given topology. In this paper, we establish the optimality conditions, duality and uniqueness results for the problem. We then present a smoothing Newton method by the semismooth equations which are derived from the optimality conditions. The method is globally and superlinearly convergent, and moreover, it is quadratically convergent when p∈[1,3/2]∪{2}. Particularly, the quadratic convergence is proved for the case wherep∈(1,3/2]∪{2} without requiring strict complementarity. Preliminary numerical results are reported, which indicate that the method proposed is extremely promising. The work was supported by the Starting-Up Foundation (B13-B6050640) of Guangdong Province.     

Minimax linear programming problem

In this paper, we consider the following minimax linear programming problem: min z = max_{1 ≤ j ≤ n}{C_jX_j}, subject to Ax = g, x ≥ 0. It is well known that this problem can be transformed into a linear program by introducing n additional constraints. We note that these additional constraints can be considered implicitly by treating them as parametric upper bounds. Based on this approach we develop two algorithms: a parametric algorithm and a primal—dual algorithm. The parametric algorithm solves a linear programming problem with parametric upper bounds and the primal—dual algorithm solves a sequence of related dual feasible linear programming problems. Computation results are also presented, which indicate that both the algorithms are substantially faster than the simplex algorithm applied to the enlarged linear programming problem.     

Branch-and-price-and-cut algorithms for solving the reliable <Emphasis Type="Italic">h</Emphasis>-paths problem

We examine a routing problem in which network arcs fail according to independent failure probabilities. The reliable h-path routing problem seeks to find a minimum-cost set of h ≥ 2 arc-independent paths from a common origin to a common destination, such that the probability that at least one path remains operational is sufficiently large. For the formulation in which variables are used to represent the amount of flow on each arc, the reliability constraint induces a nonconvex feasible region, even when the integer variable restrictions are relaxed. Prior arc-based models and algorithms tailored for the case in which h = 2 do not extend well to the general h-path problem. Thus, we propose two alternative integer programming formulations for the h-path problem in which the variables correspond to origin-destination paths. Accordingly, we develop two branch-and-price-and-cut algorithms for solving these new formulations, and provide computational results to demonstrate the efficiency of these algorithms.     

A non–interior predictor–corrector path following algorithm for the monotone linear complementarity problem

We present a predictor–corrector non–interior path following algorithm for the monotone linear complementarity problem based on Chen–Harker–Kanzow–Smale smoothing techniques. Although the method is modeled on the interior point predictor–corrector strategies, it is the first instance of a non–interior point predictor–corrector algorithm. The algorithm is shown to be both globally linearly convergent and locally quadratically convergent under standard hypotheses. The approach to global linear convergence follows the authors’ previous work on this problem for the case of (P ₀+R ₀) LCPs. However, in this paper we use monotonicity to refine our notion of neighborhood of the central path. The refined neighborhood allows us to establish the uniform boundedness of certain slices of the neighborhood of the central path under the standard hypothesis that a strictly positive feasible point exists. Received September 1997 / Revised version received May 1999?Published online December 15, 1999     

Parametric approach to optimal control

We consider the optimal control problem from view point of parametric aspects. We have examined two cases of the parameterized problems. First case describes the situation when the objective functional contains time t as a parameter. We also show how to apply the parametric optimization techniques, such as pathfollowing methods, for finding a nominal optimal control path.