Search

This paper presents a finite-difference quasi-Newton method for the minimization of noisy functions. The method takes advantage of the scalability and power of BFGS updating, and employs an adaptive procedure for choosing the differencing interval h based on the noise estimation techniques of Hamming [Introduction to Applied Numerical Analysis, Courier Corporation, North Chelmsford, MA, 2012] and Mor\'e and Wild [SIAM J. Sci. Comput., 33 (2011), pp. 1292--1314]. This noise estimation procedure and the selection of h are inexpensive but not always accurate, and to prevent failures the algorithm incorporates a recovery mechanism that takes appropriate action in the case when the line-search procedure is unable to produce an acceptable point. A novel convergence analysis is presented that considers the effect of a noisy line-search procedure. Numerical experiments comparing the method to a function interpolating trust-region method are presented. [ABSTRACT FROM AUTHOR]

In this paper we introduce three new classes of nonnegative forms (or equivalently, symmetric tensors) and their extensions. The newly identified nonnegative symmetric tensors constitute distinctive convex cones in the space of general symmetric tensors (order six or above). For the special case of quartic forms, they collapse into the set of convex quartic homogeneous polynomial functions. We discuss the properties and applications of the new classes of nonnegative symmetric tensors in the context of polynomial and tensor optimization. Numerical experiments for solving certain polynomial optimization models based on the new class es of nonnegative symmetric tensors are presented. [ABSTRACT FROM AUTHOR]

Solving feasibility problems is a central task in mathematics and the applied sciences. One particularly successful method is the Douglas--Rachford algorithm. In this paper, we provide many new conditions sufficient for finite convergence. Numerou s examples illustrate our results. [ABSTRACT FROM AUTHOR]

This paper presents a new verified optimization method for the problem of finding the densest packings of nonoverlapping equal circles in a square. In order to provide reliable numerical results, the developed algorithm is based on interval analysis. As one of the most efficient parts of the algorithm, an interval-based version of a previous elimination procedure is introduced. This method represents the remaining areas still of interest as polygons fully calculated in a reliable way. Currently the most promising strategy of finding optimal circle packing configurations is to partition the original problem into subproblems. Still, as a result of the highly increasing number of subproblems, earlier computer-aided methods were not able to solve problem instances where the number of circles was greater than 27. The present paper provides a carefully developed technique resolving this difficulty by eliminating large groups of subproblems together. As a demonstration of the capabilities of the new algorithm the problems of packing 28, 29, and 30 circles were solved within very tight tolerance values. Our verified procedure decreased the uncertainty in the location of the optimal packings by more than 700 orders of magnitude in all cases. [ABSTRACT FROM AUTHOR]

In this paper, we seek the conjugate gradient direction closest to the direction of the scaled memoryless BFGS method and propose a family of conjugate gradient methods for unconstrained optimization. An improved Wolfe line search is also proposed, which can avoid a numerical drawback of the original Wolfe line search and guarantee the global convergence of the conjugate gradient method under mild conditions. To accelerate the algorithm, we introduce adaptive restarts along negative gradients based on the extent to which the function approximates some quadratic function during previous iterations. Numerical experiments with the CUTEr collection show that the proposed algorithm is promising. [ABSTRACT FROM AUTHOR]

Traditionally, a multiuser problem is a constrained optimization problem characterized by a set of users, an objective given by a sum of user-specific utility functions, and a collection of linear constraints that couple the user decisions. The users do not share the information about their utilities, but do communicate values of their decision variables. The multiuser problem is to maximize the sum of the user-specific utility functions subject to the coupling constraints, while abiding by the informational requirements of each user. In this paper, we focus on generalizations of convex multiuser optimization problems where the objective and constraints are not separable by user and instead consider instances where user decisions are coupled, both in the objective and through nonlinear coupling constraints. To solve this problem, we consider the application of gradient-based distributed algorithms on an approximation of the multiuser problem. Such an approximation is obtained through a Tikhonov regularization and is equipped with estimates of the difference between the optimal function values of the original problem and its regularized counterpart. In the algorithmic development, we consider constant step-length primal-dual and dual schemes in which the iterate computations are distributed naturally across the users; i.e., each user updates its own decision only. Convergence in the primal-dual space is provided in limited coordination settings, which allows for differing step lengths across users as well as across the primal and dual space. We observe that a generalization of this result is also available when users choose their regularization parameters independently from a prescribed range. An alternative to primal-dual schemes can be found in dual schemes that are analyzed in regimes where approximate primal solutions are obtained through a fixed number of gradient steps. Per-iteration error bounds are provided in such regimes, and extensions are provided to regimes where users independently choose their regularization parameters. Our results are supported by a case study in which the proposed algorithms are applied to a multiuser problem arising in a congested traffic network. [ABSTRACT FROM AUTHOR]

Motivated by an obstacle problem for a membrane subject to cohesion forces, constrained minimization problems involving a nonconvex and nondifferentiable objective functional representing the total potential energy are considered. The associated first-order optimality system leads to a hemivaxiational inequality, which can also be interpreted as a special complementarity problem in function space. Besides an analytical investigation of first-order optimality, a primal-dual active set solver is introduced. It is associated to a limit case of a semismooth Newton method for a regularized version of the underlying problem class. For the numerical algorithms studied in this paper, global as well as local convergence properties are derived and verified numerically. [ABSTRACT FROM AUTHOR]

Gould and Robinson [SIAM J. Optim., 20 (2010), pp. 2023-2048] proved global convergence of a second derivative SQP method for minimizing the exact ℓ1-merit function for a fixed value of the penalty parameter. This result required the properties of a so-called Cauchy step, which was itself computed from a so-called predictor step. In addition, they allowed for the additional computation of a variety of (optional) accelerator steps that were intended to improve the efficiency of the algorithm. The main purpose of this paper is to prove that a nonmonotone variant of the algorithm is quadratically convergent for two specific realizations of the accelerator step; this is verified with preliminary numerical results on the Hock and Schittkowski test set. Once fast local convergence is established, we consider two specific aspects of the algorithm that are important for an efficient implementation. First, we discuss a strategy for defining the positive-definite matrix Bk used in computing the predictor step that is based on a limited-memory BFGS update. Second, we provide a simple strategy for updating the penalty parameter based on approximately minimizing the ℓ1-penalty function over a sequence of increasing values of the penalty parameter. [ABSTRACT FROM AUTHOR]

We consider a class of complementarity problems involving functions which are not Lipschitz continuous. In this paper we reformulate this class of non-Lipschitzian complementarity problems into a Lipschitzian complementarity problem. Then we propose an inexact smoothing Newton method to solve this Lipschitzian complementarity problem. We prove that our proposed method converges quadratically and globally under a mild condition. Numerical results show that this method is promising. This method can solve these kinds of complementarity problems with one million variables in reasonable time on a PC with 1 GB of RAM. [ABSTRACT FROM AUTHOR]

This paper presents a new method for the numerical solution of nonlinear multiobjective optimization problems with an arbitrary partial ordering in the objective space induced by a closed pointed convex cone. This algorithm is based on the well-known scalarization approach by Pascoletti and Serafini and adaptively controls the scalarization parameters using new sensitivity results. The computed image points give a nearly equidistant approximation of the whole Pareto surface. The effectiveness of this new method is demonstrated with various test problems and an applied problem from medicine. [ABSTRACT FROM AUTHOR]

The recently introduced proximal average of two convex functions is a convex function with many useful properties. In this paper, we introduce and systematically study the proximal average for finitely many convex functions. The basic properties of the proximal average with respect to the standard convex-analytical notions (domain, Fenchel conjugate, subdifferential, proximal mapping, epi-continuity, and others) are provided and illustrated by several examples. [ABSTRACT FROM AUTHOR]

Recently, a semidefinite programming (SDP) relaxation approach has been proposed to solve the sensor network localization problem. Although it achieves high accuracy in estimating the sensor locations, the speed of the SDP approach is not satisfactory for practical applications. In this paper we propose methods to further relax the SDP relaxation, more precisely, to relax the single semidefinite matrix cone into a set of small-size semidefinite submatrix cones, which we call a sub-SDP (SSDP) approach. We present two such relaxations. Although they are weaker than the original SDP relaxation, they retain the key theoretical property, and numerical experiments show that they are both efficient and accurate. The speed of the SSDP is even faster than that of other approaches based on weaker relaxations. The SSDP approach may also pave a way to efficiently solving general SDP problems without sacrificing the solution quality. [ABSTRACT FROM AUTHOR]

We investigate hierarchies of semidefinite approximations for the chromatic number X(G) of a graph G. We introduce an operator Ϋ mapping any graph parameter ß(G), nested between the stability number α(G) and X(Ḡ), to a new graph parameter Ϋß(G), nested between α(Ḡ) and X(G); Ϋß(G) is polynomial time computable if ß(G) is. As an application, there is no polynomial time computable graph parameter nested between the fractional chromatic number X*(·) and X(·) unless P = NP. Moreover, based on the Motzkin-Straus formulation for α(G), we give (quadratically constrained) quadratic and copositive programming formulations for X(G). Under some mild assumptions, n/ß(G) ≤ Ϋß(G), but, while n/ß(G) remains below X*(G), Ϋß(G) can reach X(G) (e.g., for ß(·) = α(·)). We also define new polynomial time computable lower bounds for X(G), improving the classic Lovász theta number (and its strengthenings obtained by adding nonnegativity and triangle inequalities); experimental results on Hamming graphs, Kneser graphs, and DIMACS benchmark graphs will be given in the follow-up paper [N. Gvozdenović and M. Laurent, SIAM J. Optim., 19 (2008), pp. 592-615]. [ABSTRACT FROM AUTHOR]

In this paper, we prove the continuity of maximum-entropy basis functions using variational analysis techniques. The use of information-theoretic variational principles to derive basis functions is a recent development. In this setting, data approximation is viewed as an inductive inference problem, with the basis functions being synonymous with a discrete probability distribution, and the polynomial reproducing conditions acting as the linear constraints. For a set of distinct nodes {xi}in=1 in ℝd, the convex approximation of a function u(x) is uh(x) = ∑ in=1 pi(x)ui, where {pi}in=1 are nonnegative basis functions, and uh(x) must reproduce affine functions ∑ in=1 pi(x)= 1, ∑ in=1 pi(x)xi = x. Given these constraints, we compute pi(x) by minimizing the relative entropy functional (Kullback-Leibler distance), D(p||m) = ∑in=1 pi(x) ln(pi(x)/mi(x)), where mi(x) is a known prior weight function distribution. To prove the continuity of the basis functions, we appeal to the theory of epiconvergence. [ABSTRACT FROM AUTHOR]

In this paper, we introduce ways of making a pattern search more efficient by reusing previous evaluations of the objective function, based on the computation of simplex derivatives (e.g., simplex gradients). At each iteration, one can attempt to compute an accurate simplex gradient by identifying a sampling set of previously evaluated points with good geometrical properties. This can be done using only past successful iterates or by considering all past function evaluations. The simplex gradient can then be used to reorder the evaluations of the objective function associated with the directions used in the poll step or to update the mesh size parameter according to a sufficient decrease criterion, neither of which requires new function evaluations. We present these procedures in detail and apply them to a set of problems from the CUTEr collection. Numerical results show that these procedures can enhance significantly the practical performance of pattern search methods. [ABSTRACT FROM AUTHOR]

The second-order cone complementarity problem (SOCCP) is a wide class of problems containing the nonlinear complementarity problem (NCP) and the second-order cone programming problem (SOCP). Recently, Fukushima, Luo, and Tseng [SIAM J. Optim., 12 (2001), pp. 436-460] extended some merit functions and their smoothing functions for NCP to SOCCP. Moreover, they derived computable formulas for the Jacobians of the smoothing functions and gave conditions for the Jacobians to be invertible. In this paper, we propose a globally and quadratically convergent algorithm, which is based on smoothing and regularization methods, for solving monotone SOCCP. In particular, we study strong semismoothness and Jacobian consistency, which play an important role in establishing quadratic convergence of the algorithm. Furthermore, we examine the effectiveness of the algorithm by means of numerical experiments. [ABSTRACT FROM AUTHOR]

This paper deals with the application of pattern search methods to the numerical solution of a class of molecular geometry problems with important applications in molecular physics and chemistry. The goal is to find a configuration of a cluster or a molecule with minimum total energy. The minimization problems in this class of molecular geometry problems have no constraints, and the objective function is smooth. The difficulties arise from the existence of several local minima and, especially, from the expensive function evaluation (total energy) and the possible nonavailability of first-order derivatives. We introduce a pattern search approach that attempts to exploit the physical nature of the problem by using energy lowering geometrical transformations and to take advantage of parallelism without the use of derivatives. Numerical results for a particular instance of this new class of pattern search methods are presented, showing the promise of our approach. The new pattern search methods can be used in any other context where there is a user-provided scheme to generate points leading to a potential objective function decrease. [ABSTRACT FROM AUTHOR]