On the convergence of interior-reflective Newton methods for nonlinear minimization subject to bounds

We consider a new algorithm, an interior-reflective Newton approach, for the problem of minimizing a smooth nonlinear function of many variables, subject to upper and/or lower bounds on some of the variables. This approach generatesstrictly feasible iterates by using a new affine scaling transformation and following piecewise linear paths (reflection paths). The interior-reflective approach does not require identification of an activity set. In this paper we establish that the interior-reflective Newton approach is globally and quadratically convergent. Moreover, we develop a specific example of interior-reflective Newton methods which can be used for large-scale and sparse problems.Research partially supported by the Applied Mathematical Sciences Research Program (KC-04-02) of the Office of Energy Research of the U.S. Department of Energy under grant DE-FG02-86ER25013.A000, and in part by NSF, AFOSR, and ONR through grant DMS-8920550, and by the Advanced Computing Research Institute, a unit of the Cornell Theory Center which receives major funding from the National Science Foundation and IBM Corporation, with additional support from New York State and members of its Corporate Research Institute.Corresponding author.     

Misclassification minimization

The problem of minimizing the number of misclassified points by a plane, attempting to separate two point sets with intersecting convex hulls inn-dimensional real space, is formulated as a linear program with equilibrium constraints (LPEC). This general LPEC can be converted to an exact penalty problem with a quadratic objective and linear constraints. A Frank-Wolfe-type algorithm is proposed for the penalty problem that terminates at a stationary point or a global solution. Novel aspects of the approach include: (i) A linear complementarity formulation of the step function that counts misclassifications, (ii) Exact penalty formulation without boundedness, nondegeneracy or constraint qualification assumptions, (iii) An exact solution extraction from the sequence of minimizers of the penalty function for a finite value of the penalty parameter for the general LPEC and an explicitly exact solution for the LPEC with uncoupled constraints, and (iv) A parametric quadratic programming formulation of the LPEC associated with the misclassification minimization problem.This material is based on research supported by Air Force Office of Scientific Research Grant F49620-94-1-0036 and National Science Foundation Grants CCR-9101801 and CDA-9024618.     

Drinfeld algebra deformations, homotopy comodules and the associahedra

The aim of this work is to construct a cohomology theory controlling the deformations of a general Drinfel'd algebra and thus finish the program which began in [13], [14]. The task is accomplished in three steps. The first step, which was taken in the aforementioned articles, is the construction of a modified cobar complex adapted to a non-coassociative comultiplication. The following two steps each involves a new, highly non-trivial, construction. The first construction, essentially combinatorial, defines a differential graded Lie algebra structure on the simplicial chain complex of the associahedra. The second construction, of a more algebraic nature, is the definition of a map of differential graded Lie algebras from the complex defined above to the algebra of derivations on the bar resolution. Using the existence of this map and the acyclicity of the associahedra we can define a so-called homotopy comodule structure (Definition 3.3 below) on the bar resolution of a general Drinfel'd algebra. This in turn allows us to define the desired cohomology theory in terms of a complex which consists, roughly speaking, of the bimodule and bicomodule maps from the bar resolution to the modified cobar resolution. The complex is bigraded but not a bicomplex as in the Gerstenhaber-Schack theory for bialgebra deformations. The new components of the coboundary operator are defined via the constructions mentioned above. The results of the paper were announced in [12].

     

Optimal life strategies in organisms exposed to recurrent critical events

The optimal partition of energy between survival and reproduction is considered for a population subject to recurrent and potentially lethal critical events. The best strategy is found by maximizing fitness, a functional derived from the Lotka equation. The dynamics is governed by a second-order, age-varying, nonlinear system. The energy storage and the probability of survival are the state variables, while the amounts of energy placed into and withdrawn from the storage are the controls. The optimal life strategy is shown to be as follows: build up the storage at the very beginning of life, and then progressively deplete it to resist the critical events.This work was partially supported by MURST Project Ricerche sui Fondamenti della Conservazione della Natura. The authors would like to thank C. Ricci for suggesting the problem and C. Matessi for helpful discussion.     

Interior-point algorithm for quadratically constrained entropy minimization problems

In this paper, we develop an interior point algorithm for quadratically constrained entropy problems. The algorithm uses a variation of Newton's method to follow a central path trajectory in the interior of the feasible set. The primal-dual gap is made less than a given in at most steps, wheren is the dimension of the problem andm is the number of quadratic inequality constraints.     

Representations of unbounded optimization problems as integer programs

Any optimization problem in a finite structure can be represented as an integer or mixed-integer program in integral quantities.We show that, when an optimization problem on an unbounded structure has such a representation, it is very close to a linear programming problem, in the specific sense described in the following results. We also show that, if an optimization problem has such a representation, no more thann+2 equality constraints need be used, wheren is the number of variables of the problem.We obtain a necessary and sufficient condition for a functionf:SZ, withS Z ⁿ , to have a rational model in Meyer's sense, and show that Ibaraki models are a proper subset of Meyer models.This research was supported by NSF Grant No. GP-37510X1 and ONR Contract No. N00014-75-C0621, NR047-048.     

A deterministic algorithm for constrained enumeration of transmembrane protein folds

A deterministic algorithm for enumeration of transmembrane protein folds is presented. Using a set of sparse pairwise atomic distance constraints (such as those obtained from chemical cross-linking, FRET, or dipolar EPR experiments), the algorithm performs an exhaustive search of secondary structure element packing conformations distributed throughout the entire conformational space. The end result is a set of distinct protein conformations, which can be scored and refined as part of a process designed for computational elucidation of transmembrane protein structures.     

含一般模糊弹性约束的广义模糊变量线性规划

建立并讨论了一类含有一般模糊弹性约束的广义模糊变量线性规划问题.首先,简单介绍了结构元方法并对结构元加权排序中权函数表征决策者风险态度进行了深入分析.然后选取风险中性的决策者来定义序关系,应用Verdegay模糊线性规划方法将含一般模糊弹性约束的广义模糊变量线性规划转化经典的线性规划问题,简化了原问题的求解.最后通过数值算例进一步说明了该方法的有效性.     

Vibration of strings with nonlinear supports

The dynamic string motion, which displacement is unilaterally constrained by the rigid termination condition of an arbitrary geometry has been simulated and analyzed. The treble strings of a grand piano usually terminate at a capo bar, which is situated above the strings. The apex of a V-shaped section of the capo bar defines the end of the speaking length of the strings. A numerical calculation based on the traveling wave solution is proposed for modeling the nonlinearity inducing interactions between the vibrating string and the contact condition at the point of string termination. It was shown that the lossless string vibrates in two distinct vibration regimes. In the beginning the string starts to interact in a nonlinear fashion with the rigid terminator, and the resulting string motion is aperiodic. Consequently, the spectrum of the string motion depends on the amplitude of string vibrations, and its spectral structure changes continuously with the passage of time. The duration of that vibration regime depends on the geometry of the terminator. After some time of aperiodic vibration, the string vibrations settle in a periodic regime where the resulting spectrum remains constant.     

On safe tractable approximations of chance constraints

A natural way to handle optimization problem with data affected by stochastic uncertainty is to pass to a chance constrained version of the problem, where candidate solutions should satisfy the randomly perturbed constraints with probability at least 1 − ?. While being attractive from modeling viewpoint, chance constrained problems “as they are” are, in general, computationally intractable. In this survey paper, we overview several simulation-based and simulation-free computationally tractable approximations of chance constrained convex programs, primarily, those of chance constrained linear, conic quadratic and semidefinite programming.