Search

Convexity is, without a doubt, one of the most desirable features in optimization. Many optimization problems that are nonconvex in their original settings may become convex after performing certain equivalent transformations. This paper studies the conditions for such hidden convexity. More specifically, some transformation-independent sufficient conditions have been derived for identifying hidden convexity. The derived sufficient conditions axe readily verifiable for quadratic optimization problems. The global minimizer of a hidden convex programming problem can be identified using a local search algorithm. [ABSTRACT FROM AUTHOR]

This paper continues earlier work on mathematical techniques for generating optimized algorithms for computing finite element stiffness matrices. These techniques start from representing the stiffness matrix for an affine element as a collection of contractions between reference tensors and an element-dependent geometry tensor. We go beyond the complexity-reducing binary relations explored in [R. C. Kirby, A. Logg, L. R. Scott, and A. R. Terrel, SIAM J. Sci. Comput., 28 (2006), pp. 224-240] to consider geometric relationships between three or more objects. Algorithms based on these relationships often have even fewer operations than those based on complexity-reducing relations. [ABSTRACT FROM AUTHOR]

In this paper, we consider the efficient computation of derivatives of a functional (the quantity of interest) which depends on the solution of a PDE-constrained optimization problem with inequality constraints and which may be different from the cost functional. The optimization problem is subject to perturbations in the data. We derive conditions under with the quantity of interest possesses first and second order derivatives with respect to the perturbation parameters. An algorithm for the efficient evaluation of these derivatives is developed, with considerable savings over a direct approach, especially in the case of high-dimensional parameter spaces. The computational cost is shown to be small compared to that of the overall optimization algorithm. Numerical experiments involving a parameter identification problem for Navier--Stokes flow and an optimal control problem for a reaction-diffusion system are presented which demonstrate the efficiency of the method. [ABSTRACT FROM AUTHOR]

This paper presents the problem of maximizing the determinant of a real K x K- matrix B, subject to the constraint that each row bk of B satisfies bktΓkbk ≤ 1, where Γ1, … , ΓK are K given real symmetric positive definite matrices. This problem comes from a specific blind signal separation approach, but the criterion differs from approximate diagonalization criteria usually encountered in this area. Furthermore our criterion corresponds to the following nice geometrical problem: given K ellipsoids in RK, εk = {x : xtΓkx ≤ 1}, k = 1, … , K, find K vectors, b1 ∈ ε1, … , bK ∈ εK, such that the volume of the parallelepiped defined by these vectors is maximum. Existence and uniqueness of the solution are discussed. An iterative algorithm, based on a relaxation technique, is proposed in order to solve this problem, and its convergence is proved under a simple sufficient condition. Some numerical experiments are performed showing the behavior of the algorithm and its comparison with Newton's methods for nonlinear optimization. [ABSTRACT FROM AUTHOR]

We study the continuous trajectories for solving monotone nonlinear mixed complementarity problems over symmetric cones. While the analysis in [L. Faybusovich, Positivity, 1 (1997), pp. 331-357] depends on the optimization theory of convex log-barrier functions, our approach is based on the paper of Monteiro and Pang [Math. Oper. Res., 23 (1998), pp. 39-60], where a vast set of conclusions concerning continuous trajectories is shown for monotone complementarity problems over the cone of symmetric positive semidefinite matrices. As an application of the results, we propose a homogeneous model for standard monotone nonlinear complementarity problems over symmetric cones and discuss its theoretical aspects. Consequently, we show the existence of a path having the following properties: (a) The path is bounded and has a trivial starting point without any regularity assumption concerning the existence of feasible or strictly feasible solutions. (b) Any accumulation point of the path is a solution of the homogeneous model. (c) If the original problem is solvable, then every accumulation point of the path gives us a finite solution. (d) If the original problem is strongly infeasible, then, under the assumption of Lipschitz continuity, any accumulation point of the path gives us a finite certificate proving infeasibility. [ABSTRACT FROM AUTHOR]

The objectives of this paper are twofold. We devise a general framework for identifying locally optimal algorithmic parameters. Algorithmic parameters are treated as decision variables in a problem for which no derivative knowledge or existence is assumed. A derivative-free method for optimization seeks to minimize some measure of performance of the algorithm being fine-tuned. This measure is treated as a black-box and may be chosen by the user. Examples are given in the text. The second objective is to illustrate this framework by specializing it to the identification of locally optimal trust-region parameters in unconstrained optimization. The derivative-free method chosen to guide the process is the mesh adaptive direct search, a generalization of pattern search methods. We illustrate the flexibility of the latter and in particular make provision for surrogate objectives. Locally, optimal parameters with respect to overall computational time on a set of test problems are identified. Each function call may take several hours and may not always return a predictable result. A tailored surrogate function is used to guide the search towards a local solution. The parameters thus identified differ from traditionally used values, and allow one to solve a problem that remained otherwise unsolved in a reasonable time using traditional values. [ABSTRACT FROM AUTHOR]

This paper studies theoretical and practical properties of interior-penalty methods for mathematical programs with complementarity constraints. A framework for implementing these methods is presented, and the need for adaptive penalty update strategies is motivated with examples. The algorithm is shown to be globally convergent to strongly stationary points, under standard assumptions. These results are then extended to an interior-relaxation approach. Superlinear convergence to strongly stationary points is also established. Two strategies for updating the penalty parameter are proposed, and their efficiency and robustness are studied on an extensive collection of test problems. [ABSTRACT FROM AUTHOR]

The generalized mean function has been widely used in convex analysis and mathematical programming. This paper studies a further generalization of such a function. A necessary and sufficient condition is obtained for the convexity of a generalized function. Additional sufficient conditions that can be easily checked are derived for the purpose of identifying some classes of functions which guarantee the convexity of the generalized functions. We show that some new classes of convex functions with certain regularity (such as S*-regularity) can be used as building blocks to construct such generalized functions. [ABSTRACT FROM AUTHOR]

In this paper we propose a new derivative-free algorithm for linearly constrained finite minimax problems. Due to the nonsmoothness of this class of problems, standard derivative-free algorithms can locate only points which satisfy weak necessary optimality conditions. In this work we define a new derivative-free algorithm which is globally convergent toward standard stationary points of the finite minimax problem. To this end, we convert the original problem into a smooth one by using a smoothing technique based on the exponential penalty function of Kort and Bertsekas. This technique depends on a smoothing parameter which controls the approximation to the finite minimax problem. The proposed method is based on a sampling of the smooth function along a suitable search direction and on a particular updating rule for the smoothing parameter that depends on the sampling stepsize. Numerical results on a set of standard minimax test problems are reported. [ABSTRACT FROM AUTHOR]

The notion of weighted centers is essential in V-space interior-point algorithms for linear programming. Although there were some successes in generalizing this notion to semidefinite programming via weighted center equations, we still do not have a generalization that preserves two important properties--(1) each choice of weights uniquely determines a pair of primal-dual weighted centers, and (2) the set of all primal-dual weighted centers completely fills up the relative interior of the primal-dual feasible region. This paper presents a new notion of weighted centers for semidefinite programming that possesses both uniqueness and completeness. Furthermore, it is shown that under strict complementarity, these weighted centers converge to weighted centers of optimal faces. Finally, this convergence result is applied to homogeneous cone programming, where the central paths defined by a certain class of optimal barriers for homogeneous cones are shown to converge to analytic centers of optimal faces in the presence of strictly complementary solutions. [ABSTRACT FROM AUTHOR]

In the paper, the global optimization problem of a multidimensional "black-box" function satisfying the Lipschitz condition over a hyperinterval with an unknown Lipschitz constant is considered. A new efficient algorithm for solving this problem is presented. At each iteration of the method a number of possible Lipschitz constants are chosen from a set of values varying from zero to infinity. This idea is unified with an efficient diagonal partition strategy. A novel technique balancing usage of local and global information during partitioning is proposed. A new procedure for finding lower bounds of the objective function over hyperintervals is also considered. It is demonstrated by extensive numerical experiments performed on more than 1600 multidimensional test functions that the new algorithm shows a very promising performance. [ABSTRACT FROM AUTHOR]

This paper proposes some nonlinear Uzawa methods for solving linear and nonlinear saddle-point problems. A nonlinear inexact Uzawa algorithm is first introduced for linear saddle-point problems. Two different PCG techniques are allowed in the inner and outer iterations of the algorithm. This algorithm is then extended for a class of nonlinear saddle-point problems arising from some convex optimization problems with linear constraints. For this extension, some PCG method used in the inner iteration needs to be carefully constructed so that it converges in a certain energy norm instead of the usual $l^2$-norm. It is shown that the new algorithm converges under some practical conditions and there is no need for any a priori estimates on the minimal and maximal eigenvalues of the two local preconditioned systems involved. The two new methods perform more efficiently than the existing methods in the cases where no good preconditioners are available for the Schur complements. [ABSTRACT FROM AUTHOR]

Interior gradient (subgradient) and proximal methods for convex constrained minimization have been much studied, in particular for optimization problems over the nonnegative octant. These methods are using non-Euclidean projections and proximal distance functions to exploit the geometry of the constraints. In this paper, we identify a simple mechanism that allows us to derive global convergence results of the produced iterates as well as improved global rates of convergence estimates for a wide class of such methods, and with more general convex constraints. Our results are illustrated with many applications and examples, including some new explicit and simple algorithms for conic optimization problems. In particular, we derive a class of interior gradient algorithms which exhibits an $O(k^{-2})$ global convergence rate estimate. [ABSTRACT FROM AUTHOR]

This paper discusses dynamical systems for disk-covering and sphere-packing problems. We present facility location functions from geometric optimization and characterize their differentiable properties. We design and analyze a collection of distributed control laws that are related to nonsmooth gradient systems. The resulting dynamical systems promise to be of use in coordination problems for networked robots; in this setting the distributed control laws correspond to local interactions between the robots. The technical approach relies on concepts from computational geometry, nonsmooth analysis, and the dynamical system approach to algorithms. [ABSTRACT FROM AUTHOR]

We discuss two approximation paradigms that were used to construct many approximation algorithms during the last two decades, the primal-dual schema and the local ratio technique. Recently, primal-dual algorithms were devised by first constructing a local ratio algorithm and then transforming it into a primal-dual algorithm. This was done in the case of the $2$-approximation algorithms for the feedback vertex set problem and in the case of the first primal-dual algorithms for maximization problems. Subsequently, the nature of the connection between the two paradigms was posed as an open question by Williamson [Math. Program., 91 (2002), pp. 447--478]. In this paper we answer this question by showing that the two paradigms are equivalent. [ABSTRACT FROM AUTHOR]

In the early eighties Lojasiewicz [in Seminari di Geometria 1982-1983, Università di Bologna, Istituto di Geometria, Dipartimento di Matematica, 1984, pp. 115--117] proved that a bounded solution of a gradient flow for an analytic cost function converges to a well-defined limit point. In this paper, we show that the iterates of numerical descent algorithms, for an analytic cost function, share this convergence property if they satisfy certain natural descent conditions. The results obtained are applicable to a broad class of optimization schemes and strengthen classical "weak convergence" results for descent methods to "strong limit-point convergence" for a large class of cost functions of practical interest. The result does not require that the cost has isolated critical points and requires no assumptions on the convexity of the cost nor any nondegeneracy conditions on the Hessian of the cost at critical points. [ABSTRACT FROM AUTHOR]

This paper presents a new strongly polynomial cut canceling algorithm for minimum cost submodular flow. The algorithm is a generalization of our similar cut canceling algorithm for ordinary min-cost flow. The algorithm scales a relaxed optimality parameter and creates a second, inner relaxation that is a kind of submodular max flow problem. The outer relaxation uses a novel technique for relaxing the submodular constraints that allows our previous proof techniques to work. The algorithm uses the min cuts from the max flow subproblem as the relaxed most positive cuts it chooses to cancel. We show that this algorithm needs to cancel only ${\mathrm O}(n^3)$ cuts per scaling phase, where $n$ is the number of nodes. Furthermore, we show how to slightly modify this algorithm to get a strongly polynomial running time. Finally, we briefly show how to extend this algorithm to the separable convex cost case and that the same technique can be used to construct a polynomial time maximum mean cut canceling algorithm for submodular flow. [ABSTRACT FROM AUTHOR]

Global convergence in constrained optimization algorithms has traditionally been enforced by the use of parametrized penalty functions. Recently, the filter strategy has been introduced as an alternative. At least part of the motivation for using filter methods consists of avoiding the need for estimating a suitable penalty parameter, which is often a delicate task. In this paper, we demonstrate that the use of a parametrized penalty function in nonsmooth convex optimization can be avoided without using the relatively complex filter methods. We propose an approach which appears to be more direct and easier to implement, in the sense that it is closer in spirit and structure to the well-developed unconstrained bundle methods. Preliminary computational results are also reported. [ABSTRACT FROM AUTHOR]

A line search method is proposed for nonlinear programming using Fletcher and Leyffer's filter method, which replaces the traditional merit function. A simple modification of the method proposed in a companion paper [SIAM J. Optim., 16 (2005), pp. 1--31] introducing second order correction steps is presented. It is shown that the proposed method does not suffer from the Maratos effect, so that fast local convergence to second order sufficient local solutions is achieved. [ABSTRACT FROM AUTHOR]

This paper is concerned with the solution of a linear system with multiple right-hand sides. Such problems arise from nonlinear, time-dependent, inverse, or optimization problems. In order to solve these problems efficiently we use block variants of the conjugate gradient method and combine them with cache aware algorithms. Further, we describe the acceleration of algebraic multigrid (AMG) methods by using such cache aware algorithms. Finally, numerical studies are presented that show the high efficiency of the proposed methods. [ABSTRACT FROM AUTHOR]

It is well known that the so-called first-order predictor-corrector methods working in a large neighborhood of the central path are among the most efficient interior-point methods (IPMs) for linear optimization (LO) problems. However, the best known iteration complexity of this type of method is $O(n \log\frac{(x^0)^Ts^0}{\varepsilon})$. It is of interest to investigate whether the complexity of first-order predictor-corrector type methods can be further improved. In this paper, based on a specific self-regular proximity function, we define a new large neighborhood of the central path. In particular, we show that the new neighborhood matches the standard large neighborhood that is defined by the infinity norm and widely used in the IPM literature. A new first-order predictor-corrector method for LO that uses a search direction induced by self-regularity in corrector steps is proposed. We prove that our predictor-corrector algorithm, working in a large neighborhood, has an $O(\sqrt{n}\log n \log\frac{(x^0)^Ts^0}{\varepsilon})$ iteration bound. Local superlinear convergence of the algorithm is also established. [ABSTRACT FROM AUTHOR]

In this paper we consider a particular class of nonlinear optimization problems involving both continuous and discrete variables. The distinguishing feature of this class of nonlinear mixed variable optimization problems is that the structure and the number of variables of the problem depend on the values of some discrete variables. In particular, we define a general algorithm model for the solution of this class of problems, that draws inspiration from the approach recently proposed by Audet and Dennis [SIAM J. Optim., 11 (2001), pp. 573--594], and is based on the strategy of combining in a suitable way a local search with respect to the continuous variables and a local search with respect to the discrete variables. We prove global convergence of the algorithm model without specifying the local continuous search, but only identifying some reasonable requirements. Moreover, we define a particular derivative-free algorithm for solving mixed variable programming problems where the continuous variables are linearly constrained and derivative information is not available. Finally, we report numerical results obtained by the proposed algorithm in solving a real optimal design problem. These results show the effectiveness of the approach. [ABSTRACT FROM AUTHOR]

This paper deals with the class of generalized semi-infinite programming problems (GSIPs) in which the index set of the inequality constraints depends on the decision vector and all emerging functions are assumed to be continuously differentiable. We introduce two extensions of the Kuhn-Tucker constraint qualification (which is based on the existence of a tangential continuously differentiable arc) to the class of GSIPs, prove a corresponding Karush-Kuh n-Tucker theorem, and discuss its assumptions. Finally, we present several examples which illustrate for the class of GSIPs some interrelations between the considered extensions of the Mangasarian-Fromovitz constraint qualification, the Abadie constraint qualification, and the Kuhn-Tucker constraint qualification. [ABSTRACT FROM AUTHOR]

In this paper, we study the projection onto the intersection of an affine subspace and a convex set and provide a particular treatment for the cone of positive semidefinite matrices. Among applications of this problem is the calibration of covariance matrices. We propose a Lagrangian dualization of this least-squares problem, which leads us to a convex differentiable dual problem. We propose to solve the latter problem with a quasi-Newton algorithm. We assess this approach with numerical experiments which show that fairly large problems can be solved efficiently. [ABSTRACT FROM AUTHOR]

Consider the ultrasonic imaging of a fetal head, a standard procedure for assessing the growth and development of the fetus in utero. The size and shape of certain cross sections of the skull are particularly important in such assessments. The technician/radiologist spatially moves an ultrasonic transducer over the pregnant woman's abdomen and acquires three-dimensional information from the real-time two-dimensional video images. The ability to draw conclusions from such images is built upon an acquired practical knowledge as to what is bone, what is tissue, and what is sensor noise. Can one mechanize this intuitive understanding which allows the technician/radiologist to delineate between inherent biological variation and variation chic to sensor noise, and in so doing, reconstruct the fetal head? The approach of the present paper is that of a probabilistic recovery of the fetal head. The "space of realizable fetal heads" is viewed as the result of similarity (translation × scale × rotation) transformations being applied to a given fetal head prototype. A model of the ultrasonic imaging of a fetal head is formulated and prior knowledge is incorporated, resulting in an a posteriori probability measure on the "space of realizable fetal heads." Sampling from this probability measure is achieved and justified via a time-homogeneous diffusion on a Riemannian, compact, simply connected, oriented manifold with boundary. The discretization of the diffusion is implemented into code, and the algorithm is applied to actual ultrasound prenatal images. [ABSTRACT FROM AUTHOR]

Two graphs G and H with the same vertex set V are P4-isomorphic if every four vertices {a, b, c, d} V induce a chordless path (denoted by P4) in G if and only if they induce a P4 in H. We call a graph split-perfect if it is P4-isomorphic to a split graph (i.e., a graph being partitionable into a clique and a stable set). This paper characterizes the new class of split-perfect graphs using the concepts of homogeneous sets and p-connected graphs and leads to a linear time recognition algorithm for split-perfect graphs, as well as efficient algorithms for classical optimization problems on split-perfect graphs based on the primeval decomposition of graphs. The optimization results considerably extend previous ones on smaller classes such as P4-sparse graphs, P4-1ite graphs, P4-laden graphs, and (7,3)-graphs. Moreover, split-perfect graphs form a new subclass of brittle graphs containing the superbrittle graphs for which a new characterization is obtained leading to linear time recognition. [ABSTRACT FROM AUTHOR]

We study some continuous dynamical systems associated with constrained optimization problems. For that purpose, we introduce the concept of elliptic barrier operators and develop a unified framework to derive and analyze the associated class of gradient-like dynamical systems, called A-driven descent method (A-DM). Prominent methods belonging to this class include several continuous descent methods studied earlier in the literature such as steepest descent method, continuous gradient projection methods and Newton-type methods as well as continuous interior descent methods such as Lotka-Volterra-type differential equations and Riemannian gradient methods. Related discrete iterative methods such as proximal interior point algorithms based on Bregman functions and second order homogeneous kernels can also be recovered within our framework and allow for deriving some new and interesting dynamics. We prove global existence and strong viability results of the corresponding trajectories of (A-DM) for a smooth objective function. When the objective function is convex, we analyze the asymptotic behavior at infinity of the trajectory produced by the proposed class of dynamical systems (A -DM). In particular, we derive a general criterion ensuring the global convergence of the trajectory of (A-DM) to a minimizer of a convex function over a closed convex set. This result is then applied to several dynamics built upon specific elliptic barrier operators. Throughout the paper, our results are illustrated with many examples. [ABSTRACT FROM AUTHOR]

This paper describes a class of frame-based direct search methods for unconstrained and linearly constrained optimization. A template is described and analyzed using Clarke's nonsmooth calculus. This provides a unified and simple approach to earlier results for grid-and frame-based methods, and also provides partial convergence results when the objective function is not smooth, undefined in some places, or both. The template also covers many new methods which combine elements of previous ideas using frames and grids. These new methods include grid-based simple descent algorithms which allow moving to points of the grid at every iteration and can automatically control the grid size, provided function values are available. The concept of a grid is also generalized to that of an admissible set, which allows sets, for example, with circular symmetries. The method is applied to linearly constrained problems using a simple barrier approach. [ABSTRACT FROM AUTHOR]

In this paper, by means of the concept of the working set, which is an estimate of the active set, we propose a feasible sequential linear equation algorithm for solving inequality constrained optimization problems. At each iteration of the proposed algorithm, we first solve one system of linear equations with a coefficient matrix of size m x m (where m is the number of constraints) to compute the working set; we then solve a subproblem which consists of four reduced systems of linear equations with a common coefficient matrix. Unlike existing QP-free algorithms, the subproblem is concerned with only the constraints corresponding to the working set. The constraints not in the working set are neglected. Consequently, the dimension of each subproblem is not of full dimension. Without assuming the isolatedness of the stationary points, we prove that every accumulation point of the sequence generated by the proposed algorithm is a KKT point, of the problem. Moreover, after finitely many iterations, the working set becomes independent of the iterates and is essentially the same as the active set of the KKT point. In other words, after finitely many steps, only those constraints which are active at the solution will be involved in the subproblem. Under some additional conditions, we show that the convergence rate is two-step superlinear or even Q-superlinear. We also report some preliminary numerical experiments to show that the proposed algorithm is practicable and effective for the test problems. [ABSTRACT FROM AUTHOR]

The BFGS method is one of the most, famous quasi-Newton algorithms for unconstrained optimization. In 1984, Powell presented an example of a function of two variables that shows that the Polak Ribi[egrave;]re Polyak (PRP) conjugate gradient method and the BFGS quasi-Newt, on method may cycle around eight nonstationary points if each line search picks a local minimum that provides a reduction in the objective function. In this paper, a new technique of choosing parameters is introduced, and an example with only six cyclic points is provided. It is also noted through the examples that the BFGS method with Wolfe line searches need not converge for nonconvex objective functions. [ABSTRACT FROM AUTHOR]

In this paper, we sketch common properties of a class of so-called subgraph optimization problems that can be systematically solved on distance-hereditary graphs. Based on the found properties, we then develop a general problem-solving paradigm that solves these problems efficiently in parallel. As a by-product, we also obtain new linear-time algorithms by a sequential simulation of our parallel algorithms. Let Td(V, E) and P[sub d](V, E) denote the time and processor complexities, respectively, required to construct a decomposition tree of a distance-hereditary graph G = (V, E) on a PRAM model M[sub d]. Based on the proposed paradigm, we show that the maximum independent set problem, the maximum clique problem, the vertex connectivity problem, the domination problem, and the independent domination problem can be sequentially solved in O(V + E) time, and solved in parallel in O(T[sub d](V, E) + log V) time using O(P[sub d](V, E) + V/log V) processors on M[sub d]. By constructing a decomposition tree under a CREW PRAM, we also show that T[sub d](V, E) = O(log² V) and P[sub d](V, E) = O(V + E). [ABSTRACT FROM AUTHOR]

In this paper an algorithm for extracting a stable differential-algebraic subsystem from a path-constrained dynamical system is proposed. The subsystem may be integrated directly by a differential-algebraic system integrator to evaluate constraints in shooting- or multiple shooting- type direct methods for solving path-constrained dynamic optimization problems. The algorithm appends algebraic constraints to the unconstrained ordinary differential equation subsystem based on a stability estimate for the resulting differential-algebraic system. The logarithmic norm is used to compute a stability estimate for index 1 and index 2 subsystems. The working of the algorithm is illustrated with examples. [ABSTRACT FROM AUTHOR]

Multilevel algorithms are a successful class of optimization techniques which addresses the mesh partitioning problem. They usually combine a graph contraction algorithm together with a local optimization method which refines the partition at each graph level. In this paper we present an enhancement of the technique which uses imbalance to achieve higher quality partitions. We also present a formulation of the Kernighan­Lin partition optimization algorithm which incorporates load-balancing. The resulting algorithm is tested against a different but related state-of-the-art partitioner and shown to provide improved results. [ABSTRACT FROM AUTHOR]

In this paper, we present a Gauss­Newton-based BFGS method for solving symmetric nonlinear equations which contain, as a special case, an unconstrained optimization problem, a saddle point problem, and an equality constrained optimization problem. A suitable line search is proposed with which the presented BFGS method exhibits an approximate norm descent property. Under appropriate conditions, global convergence and superlinear convergence of the method are established. The numerical results show that the proposed method is successful. [ABSTRACT FROM AUTHOR]

In this paper we examine problems motivated by on-line financial problems and stochastic games. In particular, we consider a sequence of entirely arbitrary distinct values arriving in random order, and must devise strategies for selecting low values followed by high values in such a way as to maximize the expected gain in rank from low values to high values. First, we consider a scenario in which only one low value and one high value may be selected. We give an optimal on-line algorithm for this scenario, and analyze it to show that, surprisingly, the expected gain is n - O(1), and so differs from the best possible off-line gain by only a constant additive term (which is, in fact, fairly small—at most 15). In a second scenario, we allow multiple nonoverlapping low/high selections, where the total gain for our algorithm is the sum of the individual pair gains. We also give an optimal on-line algorithm for this problem, where the expected gain is n²/8 - Θ(n log n). An analysis shows that the optimal expected off-line gain is n²/6 + Θ(1), so the performance of our on-line algorithm is within a factor of 3/4 of the best off-line strategy. [ABSTRACT FROM AUTHOR]

This paper describes a new trust region method for solving large-scale optimization problems with nonlinear equality and inequality constraints. The new algorithm employs interiorpoint techniques from linear programming, adapting them for more general nonlinear problems. A software implementation based entirely on sparse matrix methods is described. The software handles infeasible start points, identifies the active set of constraints at a solution, and can use second derivative information to solve problems. Numerical results are reported for large and small problems, and a comparison is made with other large-scale optimization codes. [ABSTRACT FROM AUTHOR]

In this paper, we consider a large class of vertex partitioning problems and apply to them the theory of algorithm design for problems restricted to partial k-trees. We carefully describe the details of algorithms and analyze their complexity in an attempt to make the algorithms feasible as solutions for practical applications. We give a precise characterization of vertex partitioning problems, which include domination, coloring and packing problems, and their variants. Several new graph parameters are introduced as generalizations of classical parameters. This characterization provides a basis for a taxonomy of a large class of problems, facilitating their common algorithmic treatment and allowing their uniform complexity classification. We present a design methodology of practical solution algorithms for generally NP-hard problems when restricted to partial k-trees (graphs with treewidth bounded by k). This "practicality" accounts for dependency on the parameter k of the computational complexity of the resulting algorithms. By adapting the algorithm design methodology on partial k-trees to vertex partitioning problems, we obtain the first algorithms for these problems with reasonable time complexity as a function of treewidth. As an application of the methodology, we give the first polynomial-time algorithm on partial k-trees for computation of the Grundy number. [ABSTRACT FROM AUTHOR]

In [SIAM J. Optim., 17 (2006), pp. 188-217] Audet and Dennis proposed the class of mesh adaptive direct search (MADS) algorithms for minimization of a nonsmooth function under general nonsmooth constraints. The notation used in the paper evolved since the preliminary versions, and, unfortunately, even though the statement of Proposition 4.2 is correct, it is not compatible with the final notation. The purpose of this note is to show that the proposition is valid. [ABSTRACT FROM AUTHOR]