A Geometric Build-Up Algorithm for Solving the Molecular Distance Geometry Problem with Sparse Distance Data

Nuclear magnetic resonance (NMR) structure modeling usually produces a sparse set of inter-atomic distances in protein. In order to calculate the three-dimensional structure of protein, current approaches need to estimate all other missing distances to build a full set of distances. However, the estimation step is costly and prone to introducing errors. In this report, we describe a geometric build-up algorithm for solving protein structure by using only a sparse set of inter-atomic distances. Such a sparse set of distances can be obtained by combining NMR data with our knowledge on certain bond lengths and bond angles. It can also include confident estimations on some missing distances. Our algorithm utilizes a simple geometric relationship between coordinates and distances. The coordinates for each atom are calculated by using the coordinates of previously determined atoms and their distances. We have implemented the algorithm and tested it on several proteins. Our results showed that our algorithm successfully determined the protein structures with sparse sets of distances. Therefore, our algorithm reduces the need of estimating the missing distances and promises a more efficient approach to NMR structure modeling.     

Solving Posynomial Geometric Programming Problems via Generalized Linear Programming

This paper revisits an efficient procedure for solving posynomial geometric programming (GP) problems, which was initially developed by Avriel et al. The procedure, which used the concept of condensation, was embedded within an algorithm for the more general (signomial) GP problem. It is shown here that a computationally equivalent dual-based algorithm may be independently derived based on some more recent work where the GP primal-dual pair was reformulated as a set of inexact linear programs. The constraint structure of the reformulation provides insight into why the algorithm is successful in avoiding all of the computational problems traditionally associated with dual-based algorithms. Test results indicate that the algorithm can be used to successfully solve large-scale geometric programming problems on a desktop computer.     

Decomposition Algorithm Model for Singly Linearly-Constrained Problems Subject to Lower and Upper Bounds

Many real applications can be formulated as nonlinear minimization problems with a single linear equality constraint and box constraints. We are interested in solving problems where the number of variables is so huge that basic operations, such as the evaluation of the objective function or the updating of its gradient, are very time consuming. Thus, for the considered class of problems (including dense quadratic programs), traditional optimization methods cannot be applied directly. In this paper, we define a decomposition algorithm model which employs, at each iteration, a descent search direction selected among a suitable set of sparse feasible directions. The algorithm is characterized by an acceptance rule of the updated point which on the one hand permits to choose the variables to be modified with a certain degree of freedom and on the other hand does not require the exact solution of any subproblem. The global convergence of the algorithm model is proved by assuming that the objective function is continuously differentiable and that the points of the level set have at least one component strictly between the lower and upper bounds. Numerical results on large-scale quadratic problems arising in the training of support vector machines show the effectiveness of an implemented decomposition scheme derived from the general algorithm model.     

A Computational Study of the Homogeneous Algorithm for Large-scale Convex Optimization

Recently the authors have proposed a homogeneous and self-dual algorithm for solving the monotone complementarity problem (MCP) [5]. The algorithm is a single phase interior-point type method; nevertheless, it yields either an approximate optimal solution or detects a possible infeasibility of the problem. In this paper we specialize the algorithm to the solution of general smooth convex optimization problems, which also possess nonlinear inequality constraints and free variables. We discuss an implementation of the algorithm for large-scale sparse convex optimization. Moreover, we present computational results for solving quadratically constrained quadratic programming and geometric programming problems, where some of the problems contain more than 100,000 constraints and variables. The results indicate that the proposed algorithm is also practically efficient.     

On the computation of protein backbones by using artificial backbones of hydrogens

NMR experiments provide information from which some of the distances between pairs of hydrogen atoms of a protein molecule can be estimated. Such distances can be exploited in order to identify the three-dimensional conformation of the molecule: this problem is known in the literature as the Molecular Distance Geometry Problem (MDGP). In this paper, we show how an artificial backbone of hydrogens can be defined which allows the reformulation of the MDGP as a combinatorial problem. This is done with the aim of solving the problem by the Branch and Prune (BP) algorithm, which is able to solve it efficiently. Moreover, we show how the real backbone of a protein conformation can be computed by using the coordinates of the hydrogens found by the BP algorithm. Formal proofs of the presented results are provided, as well as computational experiences on a set of instances whose size ranges from 60 to 6000 atoms.     

Test driving three 1995 genetic algorithms: New test functions and geometric matching

Genetic algorithms have attracted a good deal of interest in the heuristic search community. Yet there are several different types of genetic algorithms with varying performance and search characteristics. In this article we look at three genetic algorithms: an elitist simple genetic algorithm, the CHC algorithm and Genitor. One problem in comparing algorithms is that most test problems in the genetic algorithm literature can be solved using simple local search methods. In this article, the three algorithms are compared using new test problems that are not readily solved using simple local search methods. We then compare a local search method to genetic algorithms for geometric matching and examine a hybrid algorithm that combines local and genetic search. The geometric matching problem matches a model (e.g., a line drawing) to a subset of lines contained in a field of line fragments. Local search is currently the best known method for solving general geometric matching problems.     

求解鲁棒主成分分析的新交替下降方向法

鲁棒主成分分析作为统计与数据科学领域的基本工具已被广泛研究,其核心原理是把观测数据分解成低秩部分和稀疏部分.本文基于鲁棒主成分分析的非凸模型,提出了一种新的基于梯度方法和非单调搜索技术的高斯型交替下降方向法.在新算法中,交替更新低秩部分和稀疏部分相关的变量,其中低秩部分的变量是利用一步带有精确步长的梯度下降法进行更新,稀疏部分的变量是采用非单调搜索技术进行更新.本文在一定的条件下建立了新算法的全局收敛理论.最后的数值试验结果表明了新算法的有效性.     

求解混合流水线调度问题的离散人工蜂群算法

本文给出了一种离散的人工蜂群算法(HDABC)用于求解混合流水车间调度(HFS)问题。采用工件排序的编码方式,并设计了四种邻域结构。雇佣蜂依次分派到解集中每个解,采用结合问题特征的局部搜索策略完成挖掘搜索工作。跟随蜂随机选择两个解并挑选较优者作为当前解,完成进一步的探优过程。侦察蜂采用三种策略跳出局部极小。通过34个同构并行机HFS问题和2个异构并行机HFS实际调度问题的实验,并与当前文献中的典型算法对比,验证了本文提出的算法无论在算法时间还是在求解质量上,都具备良好的性能。     

Combining a hybrid preconditioner and a optimal adjustment algorithm to accelerate the convergence of interior point methods

In this work, the optimal adjustment algorithm for p coordinates, which arose from a generalization of the optimal pair adjustment algorithm is used to accelerate the convergence of interior point methods using a hybrid iterative approach for solving the linear systems of the interior point method. Its main advantages are simplicity and fast initial convergence. At each interior point iteration, the preconditioned conjugate gradient method is used in order to solve the normal equation system. The controlled Cholesky factorization is adopted as the preconditioner in the first outer iterations and the splitting preconditioner is adopted in the final outer iterations. The optimal adjustment algorithm is applied in the preconditioner transition in order to improve both speed and robustness. Numerical experiments on a set of linear programming problems showed that this approach reduces the total number of interior point iterations and running time for some classes of problems. Furthermore, some problems were solved only when the optimal adjustment algorithm for p coordinates was used in the change of preconditioners.     

A comparison of two methods for solving 0–1 integer programs using a general purpose simulated annealing algorithm

0–1 problems are often difficult to solve. Although special purpose algorithms (exact as well as heuristic) exist for solving particular problem classes or problem instances, there are few general purpose algorithms for solving practical-sized instances of 0–1 problems. This paper deals with a general purpose heuristic algorithm for 0–1 problems. In this paper, we compare two methods based on simulated annealing for solving general 0–1 integer programming problems. The two methods differe in the scheme used for neighbourhood transitions in the simulated annealing framework. We compare the performance of the two methods on the set partitioning problem.     

Global optimization for generalized geometric programming problems with discrete variables

Generalized geometric programming (GGP) problems occur frequently in engineering design and management, but most existing methods for solving GGP actually only consider continuous variables. This article presents a new branch-and-bound algorithm for globally solving GGP problems with discrete variables. For minimizing the problem, an equivalent monotonic optimization problem (P) with discrete variables is presented by exploiting the special structure of GGP. In the algorithm, the lower bounds are computed by solving ordinary linear programming problems that are derived via a linearization technique. In contrast to pure branch-and-bound methods, the algorithm can perform a domain reduction cut per iteration by using the monotonicity of problem (P), which can suppress the rapid growth of branching tree in the branch-and-bound search so that the performance of the algorithm is further improved. Computational results for several sample examples and small randomly generated problems are reported to vindicate our conclusions.     

Descent Direction Stochastic Approximation Algorithm with Adaptive Step Sizes

A stochastic approximation (SA) algorithm with new adaptive step sizes for solving unconstrained minimization problems in noisy environment is proposed. New adaptive step size scheme uses ordered statistics of fixed number of previous noisy function values as a criterion for accepting good and rejecting bad steps. The scheme allows the algorithm to move in bigger steps and avoid steps proportional to $1/k$ when it is expected that larger steps will improve the performance. An algorithm with the new adaptive scheme is defined for a general descent direction. The almost sure convergence is established. The performance of new algorithm is tested on a set of standard test problems and compared with relevant algorithms. Numerical results support theoretical expectations and verify efficiency of the algorithm regardless of chosen search direction and noise level. Numerical results on problems arising in machine learning are also presented. Linear regression problem is considered using real data set. The results suggest that the proposed algorithm shows promise.     

A new class of hybrid extragradient algorithms for solving quasi-equilibrium problems

Generalized Nash equilibrium problems are important examples of quasi-equilibrium problems. The aim of this paper is to study a general class of algorithms for solving such problems. The method is a hybrid extragradient method whose second step consists in finding a descent direction for the distance function to the solution set. This is done thanks to a linesearch. Two descent directions are studied and for each one several steplengths are proposed to obtain the next iterate. A general convergence theorem applicable to each algorithm of the class is presented. It is obtained under weak assumptions: the pseudomonotonicity of the equilibrium function and the continuity of the multivalued mapping defining the constraint set of the quasi-equilibrium problem. Finally some preliminary numerical results are displayed to show the behavior of each algorithm of the class on generalized Nash equilibrium problems.     

Global and Local Search Algorithms for Concave Cost Transshipment Problems

Traditionally, the minimum cost transshipment problems have been simplified as linear cost problems, which are not practical in real applications. Recently, some advanced local search algorithms have been developed that can directly solve concave cost bipartite network problems. However, they are not applicable to general transshipment problems. Moreover, the effectiveness of these modified local search algorithms for solving general concave cost transshipment problems is doubtful. In this research, we propose a global search algorithm for solving concave cost transshipment problems. Effecient methods for encoding, generating initial populations, selection, crossover and mutation are proposed, according to the problem characteristics. To evaluate the effectiveness of the proposed global search algorithm, four advanced local search algorithms based on the threshold accepting algorithm, the great deluge algorithm, and the tabu search algorithm, are also developed and are used for comparison purpose. To assist with the comparison of the proposed algorithms, a randomized network generator is designed to produce test problems. All the tests are performed on a personal computer. The results indicate that the proposed global search algorithm is more effective than the four advanced local algorithms, for solving concave cost transshipment problems.     

Reverse Convex Programming Approach in the Space of Extreme Criteria for Optimization over Efficient Sets

The problem of minimizing a convex function over the difference of two convex sets is called ‘reverse convex program’. This is a typical problem in global optimization, in which local optima are in general different from global optima. Another typical example in global optimization is the optimization problem over the efficient set of a multiple criteria programming problem. In this article, we investigate some special cases of optimization problems over the efficient set, which can be transformed equivalently into reverse convex programs in the space of so-called extreme criteria of multiple criteria programming problems under consideration. A suitable algorithm of branch and bound type is then established for globally solving resulting problems. Preliminary computational results with the proposed algorithm are reported.     

Gradient learning in a classification setting by gradient descent

Learning gradients is one approach for variable selection and feature covariation estimation when dealing with large data of many variables or coordinates. In a classification setting involving a convex loss function, a possible algorithm for gradient learning is implemented by solving convex quadratic programming optimization problems induced by regularization schemes in reproducing kernel Hilbert spaces. The complexity for such an algorithm might be very high when the number of variables or samples is huge. We introduce a gradient descent algorithm for gradient learning in classification. The implementation of this algorithm is simple and its convergence is elegantly studied. Explicit learning rates are presented in terms of the regularization parameter and the step size. Deep analysis for approximation by reproducing kernel Hilbert spaces under some mild conditions on the probability measure for sampling allows us to deal with a general class of convex loss functions.     

An infeasible interior-point algorithm for solving primal and dual geometric programs

In this paper an algorithm is presented for solving the classical posynomial geometric programming dual pair of problems simultaneously. The approach is by means of a primal-dual infeasible algorithm developed simultaneously for (i) the dual geometric program after logarithmic transformation of its objective function, and (ii) its Lagrangian dual program. Under rather general assumptions, the mechanism defines a primal-dual infeasible path from a specially constructed, perturbed Karush-Kuhn-Tucker system.Subfeasible solutions, as described by Duffin in 1956, are generated for each program whose primal and dual objective function values converge to the respective primal and dual program values. The basic technique is one of a predictor-corrector type involving Newton’s method applied to the perturbed KKT system, coupled with effective techniques for choosing iterate directions and step lengths. We also discuss implementation issues and some sparse matrix factorizations that take advantage of the very special structure of the Hessian matrix of the logarithmically transformed dual objective function. Our computational results on 19 of the most challenging GP problems found in the literature are encouraging. The performance indicates that the algorithm is effective regardless of thedegree of difficulty, which is a generally accepted measure in geometric programming. Research supported in part by the University of Iowa Obermann Fellowship and by NSF Grant DDM-9207347.     

Solving Large Scale Molecular Distance Geometry Problems by a Smoothing Technique via the Gaussian Transform and D.C. Programming

We study a continuation approach via the Gaussian transform and D.C. programming for solving both exact and general distance geometry problems. This approach relies on a new formulation of the problems and their Gaussian transforms which are both smooth D.C. (difference of convex functions) programs. A D.C. optimization algorithm is investigated for solving the transformed problems. Numerical experiments on the data derived from PDB data bank up to 4189 atoms show the usefulness of the reformulation, the globality of sought solutions, the robustness and the efficiency of the proposed approach.     

Construction of the Solvability Set in Differential Games with Simple Motion and Nonconvex Terminal Set

We consider planar zero-sum differential games with simple motion, fixed terminal time, and polygonal terminal set. The geometric constraint on the control of each player is a convex polygonal set or a line segment. In the case of a convex terminal set, an explicit formula is known for the solvability set (a level set of the value function, maximal u-stable bridge, viability set). The algorithm corresponding to this formula is based on the set operations of algebraic sum and geometric difference (the Minkowski difference). We propose an algorithm for the exact construction of the solvability set in the case of a nonconvex polygonal terminal set. The algorithm does not involve the additional partition of the time interval and the recovery of intermediate solvability sets at additional instants. A list of half-spaces in the three-dimensional space of time and state coordinates is formed and processed by a finite recursion. The list is based on the polygonal terminal set with the use of normals to the polygonal constraints on the controls of the players.     

A relaxed cutting plane method for semi-infinite semi-definite programming

In this paper, we develop two discretization algorithms with a cutting plane scheme for solving combined semi-infinite and semi-definite programming problems, i.e., a general algorithm when the parameter set is a compact set and a typical algorithm when the parameter set is a box set in the m-dimensional space. We prove that the accumulation point of the sequence points generated by the two algorithms is an optimal solution of the combined semi-infinite and semi-definite programming problem under suitable assumption conditions. Two examples are given to illustrate the effectiveness of the typical algorithm.