Local Feasible QP-Free Algorithms for the Constrained Minimization of SC1 Functions

We consider the problem of minimizing an SC¹ function subject to inequality constraints. We propose a local algorithm whose distinguishing features are that: (a) a fast convergence rate is achieved under reasonable assumptions that do not include strict complementarity at the solution; (b) the solution of only linear systems is required at each iteration; (c) all the points generated are feasible. After analyzing a basic Newton algorithm, we propose some variants aimed at reducing the computational costs and, in particular, we consider a quasi-Newton version of the algorithm.     

A Quasi-Newton Penalty Barrier Method for Convex Minimization Problems

We describe an infeasible interior point algorithm for convex minimization problems. The method uses quasi-Newton techniques for approximating the second derivatives and providing superlinear convergence. We propose a new feasibility control of the iterates by introducing shift variables and by penalizing them in the barrier problem. We prove global convergence under standard conditions on the problem data, without any assumption on the behavior of the algorithm.     

An Adaptive Algorithm for Vector Partitioning

The vector partition problem concerns the partitioning of a set A of n vectors in d-space into p parts so as to maximize an objective function c which is convex on the sum of vectors in each part. Here all parameters d, p, n are considered variables. In this paper, we study the adjacency of vertices in the associated partition polytopes. Using our adjacency characterization for these polytopes, we are able to develop an adaptive algorithm for the vector partition problem that runs in time O(q(L)v) and in space O(L), where q is a polynomial function, L is the input size and v is the number of vertices of the associated partition polytope. It is based on an output-sensitive algorithm for enumerating all vertices of the partition polytope. Our adjacency characterization also implies a polynomial upper bound on the combinatorial diameter of partition polytopes. We also establish a partition polytope analogue of the lower bound theorem, indicating that the output-sensitive enumeration algorithm can be far superior to previously known algorithms that run in time polynomial in the size of the worst-case output.     

Heuristic Rejection in Interval Global Optimization

Based on the investigation carried out in Ref. 1, this paper incorporates new studies about the properties of inclusion functions on subintervals while a branch-and-bound algorithm is solving global optimization problems. It is found that the relative place of the global minimum value within the inclusion function value of the objective function at the current interval indicates mostly whether the given interval is close to a minimizer point. This information is used in a heuristic interval rejection rule that can save a considerable amount of computation. Illustrative examples are discussed and an extended numerical study shows the advantages of the new approach.     

Studying the Complexity of Global Verification for NP-Hard Discrete Optimization Problems

This paper examines the complexity of global verification for MAX-SAT, MAX-k-SAT (for k3), Vertex Cover, and Traveling Salesman Problem. These results are obtained by adaptations of the transformations that prove such problems to be NP-complete. The class of problems PGS is defined to be those discrete optimization problems for which there exists a polynomial time algorithm such that given any solution , either a solution can be found with a better objective function value or it can be concluded that no such solution exists and is a global optimum. This paper demonstrates that if any one of MAX-SAT, MAX-k-SAT (for k3), Vertex Cover, or Traveling Salesman Problem are in PGS, then P=NP.     

Ab initio Tertiary Structure Prediction of Proteins

A daunting challenge in the area of computational biology has been to develop a method to theoretically predict the correct three-dimensional structure of a protein given its linear amino acid sequence. The ability to surmount this challenge, which is known as the protein folding problem, has tremendous implications. We introduce a novel ab initio approach for the protein folding problem. The accurate prediction of the three-dimensional structure of a protein relies on both the mathematical model used to mimic the protein system and the technique used to identify the correct structure. The models employed are based solely on first principles, as opposed to the myriad of techniques relying on information from statistical databases. The framework integrates our recently proposed methods for the prediction of secondary structural features including helices and strands, as well as -sheet and disulfide bridge formation. The final stage of the approach, which culminates in the tertiary structure prediction of a protein, utilizes search techniques grounded on the foundations of deterministic global optimization, powerful methods which can potentially guarantee the correct identification of a protein's structure. The performance of the approach is illustrated with bovine pancreatic trypsin inhibitor protein and the immunoglobulin binding domain of protein G.     

A parallel method for time discretization of parabolic equations based on Laplace transformation and quadrature

We consider the discretization in time of an inhomogeneous parabolicequation in a Banach space setting, using a representation ofthe solution as an integral along a smooth curve in the complexleft half-plane which, after transformation to a finite interval,is then evaluated to high accuracy by a quadrature rule. Thisreduces the problem to a finite set of elliptic equations withcomplex coefficients, which may be solved in parallel. The paperis a further development of earlier work by the authors, wherewe treated the homogeneous equation in a Hilbert space framework.Special attention is given here to the treatment of the forcingterm. The method is combined with finite-element discretizationin spatial variables.     

Computing Zeta Functions of Kummer Curves via Multiplicative Characters

We present a practical polynomial-time algorithm for computing the zeta function of a Kummer curve over a finite field of small characteristic. Such algorithms have recently been obtained using a method of Kedlaya based upon Monsky–Washnitzer cohomology, and are of interest in cryptography. We take a different approach. The problem is reduced to that of computing the L-function of a multiplicative character sum. This latter task is achieved via a cohomological formula based upon the work of Dwork and Reich. We show, however, that our method and that of Kedlaya are very closely related.Dedicated to the memory of Gian-Carlo Rota     

On Global Optimality Conditions and Cutting Plane Algorithms

We discuss global optimality conditions and cutting plane algorithms for DC optimization. The discussion is motivated by certain incorrect results that have appeared recently in the literature on these topics. Incidentally, we investigate the relation of the Tikhonov reciprocity theorem to the optimality conditions for general nonconvex global optimization problems and show how the outer-approximation scheme developed earlier for DC programming can be used to solve a wider class of problems.