Practical active-set Euclidian trust-region method with spectral projected gradients for bound-constrained minimization

A practical active-set method for bound-constrained minimization is introduced. Within the current face the classical Euclidian trust-region method is employed. Spectral projected gradient directions are used to abandon faces. Numerical results are presented.     

有界约束半光滑方程组的非单调投影信赖域方法

投影信赖域策略结合非单调线搜索算法解有界约束非线性半光滑方程组.基于简单有界约束的非线性优化问题构建信赖域子问题,半光滑类牛顿步在可行域投影得到投影牛顿的试探步,获得新的搜索方向,结合非单调线搜索技术得到回代步,获得新的步长.在合理的条件下,证明算法不仅具有整体收敛性且保持超线性收敛速率.引入非单调技术能克服高度非线性的病态问题,加速收敛性进程,得到超线性收敛速率.     

An optimal subgradient algorithm for large-scale bound-constrained convex optimization

This paper shows that the optimal subgradient algorithm (OSGA)—which uses first-order information to solve convex optimization problems with optimal complexity—can be used to efficiently solve arbitrary bound-constrained convex optimization problems. This is done by constructing an explicit method as well as an inexact scheme for solving the bound-constrained rational subproblem required by OSGA. This leads to an efficient implementation of OSGA on large-scale problems in applications arising from signal and image processing, machine learning and statistics. Numerical experiments demonstrate the promising performance of OSGA on such problems. A software package implementing OSGA for bound-constrained convex problems is available.     

Evaluating numerical ODE/DAE methods,algorithms and software

Until recently, the testing of ODE/DAE software has been limited to simple comparisons and benchmarking. The process of developing software from a mathematically specified method is complex: it entails constructing control structures and objectives, selecting iterative methods and termination criteria, choosing norms and many more decisions. Most software constructors have taken a heuristic approach to these design choices, and as a consequence two different implementations of the same method may show significant differences in performance. Yet it is common to try to deduce from software comparisons that one method is better than another. Such conclusions are not warranted, however, unless the testing is carried out under true ceteris paribus conditions. Moreover, testing is an empirical science and as such requires a formal test protocol; without it conclusions are questionable, invalid or even false.We argue that ODE/DAE software can be constructed and analyzed by proven, “standard” scientific techniques instead of heuristics. The goals are computational stability, reproducibility, and improved software quality. We also focus on different error criteria and norms, and discuss modifications to DASPK and RADAU5. Finally, some basic principles of a test protocol are outlined and applied to testing these codes on a variety of problems.     

Stopping rules and backward error analysis for bound-constrained optimization

Termination criteria for the iterative solution of bound-constrained optimization problems are examined in the light of backward error analysis. It is shown that the problem of determining a suitable perturbation on the problem’s data corresponding to the definition of the backward error is analytically solvable under mild assumptions. Moreover, a link between existing termination criteria and this solution is clarified, indicating that some standard measures of criticality may be interpreted in the sense of backward error analysis. The backward error problem is finally considered from the multicriteria optimization point of view and some numerical illustration is provided.     

Whitney differentiability of optimal-value functions for bound-constrained convex programming problems

ABSTRACT

In the spirit of the Whitney Extension Theorem, consider a function on a compact subset of Euclidean space to be ‘Whitney-differentiable’ if it is a restriction of a continuously Fréchet-differentiable function with an open domain. Whitney-differentiable functions have been shown to have useful (yet possibly nonunique) derivatives and calculus properties even on the boundaries of their domains. This article shows that optimal-value functions for bound-constrained convex programmes with Whitney-differentiable objective functions are themselves Whitney-differentiable, even when the linear-independence constraint qualification is not satisfied. This result extends classic sensitivity results for convex programmes, and generalizes recent work. As an application, sufficient conditions are presented for generating continuously differentiable convex underestimators of nonconvex functions for use in methods for deterministic global optimization in the multivariate McCormick framework. In particular, the main result is applied to generate Whitney-differentiable convex underestimators for quotients of functions with known Whitney-differentiable relaxations.     

An efficient interval computing technique for bound-constrained uncertain optimization problems

In this article, a competent interval-oriented approach is proposed to solve bound-constrained uncertain optimization problems. This new class of problems is considered here as an extension of the classical bound-constrained optimization problems in an inexact environment. The proposed technique is nothing but an imitation of the well-known interval analysis-based branch-and-bound optimization approach. Efficiency of this technique is strongly dependent on division, bounding, selection/rejection and termination criteria. The technique involves a multisection division criterion of the accepted/proposed search region. Then, we have employed the interval-ranking definitions with respect to the pessimistic decision makers’ point of view given by Mahato and Bhunia [Interval-arithmetic-oriented interval computing technique for global optimization, Appl. Math. Res. Express 2006 (2006), pp. 1–19] to compare the interval-valued objectives calculated in each subregion and also to select the subregion containing the best interval objective value. The process is continued until the interval width for each variable in the accepted subregion is negligible and ultimately the global or close-to-global interval-valued optimal solution is obtained. The proposed technique has been evaluated numerically using a wide set of newly introduced univariate/multivariate test problems. Finally, to compare the computational results obtained by the proposed method, the graphical representation for some test problems is given.     

A Python/C library for bound-constrained global optimization with continuous GRASP

This paper describes ${\texttt{libcgrpp}}$ , a GNU-style dynamic shared Python/C library of the continuous greedy randomized adaptive search procedure (C-GRASP) for bound constrained global optimization. C-GRASP is an extension of the GRASP metaheuristic (Feo and Resende, 1989) and has been used to solve unstable and nondifferentiable problems, as well as hard global optimization problems, such as chemical equilibrium systems and robot kinematics applications (Hirsch et al. in Optim lett 1:201–212, 2007). After a brief introduction to C-GRASP, we show how to download, install, configure, and use the library through an illustrative example.     

DMulti-MADS: mesh adaptive direct multisearch for bound-constrained blackbox multiobjective optimization

Computational Optimization and Applications - The context of this research is multiobjective optimization where conflicting objectives are present. In this work, these objectives are only available...     

Continuous GRASP with a local active-set method for bound-constrained global optimization

Global optimization seeks a minimum or maximum of a multimodal function over a discrete or continuous domain. In this paper, we propose a hybrid heuristic—based on the CGRASP and GENCAN methods—for finding approximate solutions for continuous global optimization problems subject to box constraints. Experimental results illustrate the relative effectiveness of CGRASP–GENCAN on a set of benchmark multimodal test functions.     

A class of collinear scaling algorithms for bound-constrained optimization: Convergence theorems

A family of algorithms for approximate solution of the bound-constrained minimization problem was introduced in [K.A. Ariyawansa, W.L. Tabor, A class of collinear scaling algorithms for bound-constrained optimization: Derivation and computational results, Technical Report 2003-1, Department of Mathematics, Washington State University, Pullman, WA, 2003, submitted for publication. Available at http://www.math.wsu.edu/math/TRS/2003-1.pdf]. These algorithms employ the standard barrier method, with the inner iteration based on trust region methods. Local models are conic functions rather than the usual quadratic functions, and are required to match first and second derivatives of the barrier function at the current iterate. The various members of the family are distinguished by the choice of a vector-valued parameter, which is the zero vector in the degenerate case that quadratic local models are used. This paper presents a convergence analysis of the family of algorithms presented in [K.A. Ariyawansa, W.L. Tabor, A class of collinear scaling algorithms for bound-constrained optimization: Derivation and computational results, Technical Report 2003-1, Department of Mathematics, Washington State University, Pullman, WA, 2003, submitted for publication. Available at http://www.math.wsu.edu/math/TRS/2003-1.pdf]. Specifically, convergence properties similar to those of barrier methods using quadratic local models are established.     

Empirical minimization

We investigate the behavior of the empirical minimization algorithm using various methods. We first analyze it by comparing the empirical, random, structure and the original one on the class, either in an additive sense, via the uniform law of large numbers, or in a multiplicative sense, using isomorphic coordinate projections. We then show that a direct analysis of the empirical minimization algorithm yields a significantly better bound, and that the estimates we obtain are essentially sharp. The method of proof we use is based on Talagrand's concentration inequality for empirical processes. Research partially supported by NSF under award DMS-0434393. Research partially supported by the Australian Research Council Discovery Porject DP0343616.     

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.     

Break minimization

A break in a {0, 1}-matrix is defined as a 0 with at least one 1 to its left and at least one 1 to its right in the same row. This paper is concerned with {0, 1}-matrices with given column sums and an upper limit for the row sums. In addition, there are limits on the distance from the first to the last 1 in a row. The problem that is considered is to find a {0, 1}-matrix satisfying the conditions such that the total number of breaks is minimum. An algorithm for solving this problem is presented. Computational results illustrate the effectiveness of the algorithm. The investigation originated in a problem of crew rostering.     

Hybrid misclassification minimization

Given two finite point setsA andB in then-dimensional real spaceR ⁿ , we consider the NP-complete problem of minimizing the number of misclassified points by a plane attempting to divideR ⁿ into two halfspaces such that each open halfspace contains points mostly ofA orB. This problem is equivalent to determining a plane {x | x ^T w=} that maximizes the number of pointsx A satisfying inx ^T w>, plus the number of pointsx B satisfyingx ^T w<. A simple but fast algorithm is proposed that alternates between (i) minimizing the number of misclassified points by translation of the separating plane, and (ii) a rotation of the plane so that it minimizes a weighted average sum of the distances of the misclassified points to the separating plane. Existence of a global solution to an underlying hybrid minimization problem is established. Computational comparison with a parametric approach to solve the NP-complete problem indicates that our approach is considerably faster and appears to generalize better as determined by tenfold cross-validation.This material is based on research supported by Air Force Office of Scientific Research Grant F49620-94-1-0036 and National Science Foundation Grant CCR-9322479.     

Submodular function minimization

Submodular functions often arise in various fields of operations research including discrete optimization, game theory, queueing theory and information theory. In this survey paper, we give overview on the fundamental properties of submodular functions and recent algorithmic devolopments of their minimization.      

A class of collinear scaling algorithms for bound-constrained optimization: Derivation and computational results

A family of algorithms for the approximate solution of the bound-constrained minimization problem is described. These algorithms employ the standard barrier method, with the inner iteration based on trust region methods. Local models are conic functions rather than the usual quadratic functions, and are required to match first and second derivatives of the barrier function at the current iterate. The various members of the family are distinguished by the choice of a vector-valued parameter, which is the zero vector in the degenerate case that quadratic local models are used. Computational results are used to compare the efficiency of various members of the family on a selection of test functions.     

An affine scaling trust-region algorithm with interior backtracking technique for solving bound-constrained nonlinear systems

In this paper, we propose a new affine scaling trust-region algorithm in association with nonmonotonic interior backtracking line search technique for solving nonlinear equality systems subject to bounds on variables. The trust-region subproblem is defined by minimizing a squared Euclidean norm of linear model adding the augmented quadratic affine scaling term subject only to an ellipsoidal constraint. By using both trust-region strategy and interior backtracking line search technique, each iterate switches to backtracking step generated by the general trust-region subproblem and satisfies strict interior point feasibility by line search backtracking technique. The global convergence and fast local convergence rate of the proposed algorithm are established under some reasonable conditions. A nonmonotonic criterion should bring about speeding up the convergence progress in some ill-conditioned cases. The results of numerical experiments are reported to show the effectiveness of the proposed algorithm.     

On submodular function minimization

Earlier work of Bixby, Cunningham, and Topkis is extended to give a combinatorial algorithm for the problem of minimizing a submodular function, for which the amount of work is bounded by a polynomial in the size of the underlying set and the largest function value (not its length). Research partially supported by a grant from the Natural Sciences and Engineering Research Council of Canada.