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 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]

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]

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]

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]

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]

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]

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]

Considering iterative sequences that arise when approximate solutions xk to a numerical problem are updated by xk+1 = xk +v(xk), where v is a differentiable vector field, we derive necessary and sufficient conditions for such discrete processes to converge to a stationary point of v at different Q-rates in terms of a similar notion of fast convergence for the corresponding continuous processes. [ABSTRACT FROM AUTHOR]

We introduce two-stage stochastic semidefinite programs with recourse and present an interior point algorithm for solving these problems using Bender's decomposition. This decomposition algorithm and its analysis extend Zhao's results [Math. Program., 90 (2001), pp. 507-536] for stochastic linear programs. The convergence results are proved by showing that the logarithmic barrier associated with the recourse function of two-stage stochastic semidefinite programs with recourse is a strongly self-concordant barrier on the first stage solutions. The short-step variant of the algorithm requires O(√p + Kr ln μ0/∈) Newton iterations to follow the first stage central path from a starting value of the barrier parameter μ0 to a terminating value ∈. The long-step variant requires O((p + Kr) lnμ0/∈) damped Newton iterations. The calculation of the gradient and Hessian of the recourse function and the first stage Newton direction decomposes across the second stage scenarios. [ABSTRACT FROM AUTHOR]

We introduce and prove convergence of a damped Newton algorithm to approximate solutions of the semidiscrete optimal transport problem with storage fees, corresponding to a problem with hard capacity constraints. This is a variant of the optimal transport problem arising in queue penalization problems and has applications to data clustering. Our result is novel, as it is the first numerical method with proven convergence for this variant problem; additionally, the algorithm applies to the classical semidiscrete optimal transport problem but does not require any connectedness assumptions on the support of the source measure, in contrast with existing results. Furthermore we find some stability results of the associated Laguerre cells. All of our results come with quantitative rates. We also present some numerical examples. [ABSTRACT FROM AUTHOR]

We present a novel accelerated primal-dual (APD) method for solving a class of deterministic and stochastic saddle point problems (SPPs). The basic idea of this algorithm is to incorporate a multistep acceleration scheme into the primal-dual method without smoothing the objective function. For deterministic SPP, the APD method achieves the same optimal rate of convergence as Nesterov's smoothing technique. Our stochastic APD method exhibits an optimal rate of convergence for stochastic SPP not only in terms of its dependence on the number of the iteration, but also on a variety of problem parameters. To the best of our knowledge, this is the first time that such an optimal algorithm has been developed for stochastic SPP in the literature. Furthermore, for both deterministic and stochastic SPP, the developed APD algorithms can deal with the situation when the feasible region is unbounded, as long as a saddle point exists. In the unbounded case, we incorporate the modified termination criterion introduced by Monteiro and Svaiter in solving an SPP posed as a monotone inclusion, and demonstrate that the rate of convergence of the APD method depends on the distance from the initial point to the set of optimal solutions. Some preliminary numerical results of the APD method for solving both deterministic and stochastic SPPs are also included. [ABSTRACT FROM AUTHOR]

We present algorithms for solving a number of new models of facility location which generalize the classical Fermat-Torricelli problem. Our first approach involves using Nesterov's smoothing technique and the minimization majorization principle to build smooth approximations that are convenient for applying smooth optimization schemes. Another approach uses subgradient-type algorithms to cope directly with the nondifferentiability of the cost functions. Convergence results of the algorithms are proved and numerical tests are presented to show the effectiveness of the proposed algorithms. [ABSTRACT FROM AUTHOR]

The problem of the singular value decomposition of a matrix can be brought into an optimization problem on the product of two Stiefel manifolds of different sizes. The steepest descent, the conjugate gradient, and Newton's methods for the problem are developed and applied with several numerical experiments. These algorithms do not need the preconditioning that is inevitable in the usual singular value decomposition algorithm. The present Newton's method can serve to make more accurate the singular value decomposition obtained by other existing algorithms. In addition, degenerate optimal solutions are studied, together with numerical experiments, to show that those solutions form a disconnected submanifold. [ABSTRACT FROM AUTHOR]

Stochastic programming problems arise in many practical situations, hi general, the deterministic equivalents of these problems can be very large and may not be solvable directly by general-purpose optimization approaches. For the particular case of two-stage stochastic programs, we consider decomposition approaches akin to a regularized L-shaped method that can handle inexactness ill the subproblem solution. From a nonsmooth optimization perspective, these variants amount to applying a proximal bundle method to an oracle that gives inaccurate values for the objective function and a subgradient. Rather than forcing early termination of the subproblem optimization to define inexact oracles, we select a small subset of scenarios for which the subproblem solution is exact, and we replace the information for the remaining scenarios by a fast procedure that does not involve solving an optimization problem. The inaccurate oracle information creates inexact cuts in the master program, which are well handled by the recently introduced inexact bundle methods. The proposed approaches are validated by encouraging numerical results on several two-stage stochastic linear programs found in the literature. [ABSTRACT FROM AUTHOR]

A new technique for solving polynomial nonlinear constrained optimal control problems is presented. The problem is reformulated into a parametric optimization problem, which in turn is solved in a two-step procedure. First, in a precomputation step, the equation part of the corresponding first order optimality conditions is solved for a generic value of the parameter. Relying on the underlying algebraic geometry, this first solution makes it, possible to solve efficiently and in real time the corresponding optimal control problem at the measured parameter value for each subsequent time step. This approach has a probability one guarantee of finding the global optimal solution at each step. Controller synthesis for two applications from the area of power electronics featuring a dc-ac converter and a dc-dc converter are discussed to motivate the proposed approach. [ABSTRACT FROM AUTHOR]

Computational convex analysis algorithms have been rediscovered several times in the past by researchers from different fields. To further communications between practitioners, we review the field of computational convex analysis, which focuses on the numerical computation of fundamental transforms arising from convex analysis. Current models use symbolic, numeric, and hybrid symbolic-numeric algorithms. Our objective is to disseminate widely the most efficient numerical algorithms useful for applications in image processing (computing the distance transform, the generalized distance transform, and mathematical morphology operators), partial differential equations (solving Hamilton--Jacobi equations and using differential equations numerical schemes to compute the convex envelope), max-plus algebra (computing the equivalent of the fast Fourier transform), multifractal analysis, etc. The fields of applications include, among others, computer vision, robot navigation, thermodynamics, electrical networks, medical imaging, and network communication. [ABSTRACT FROM AUTHOR]

We study some methods of subgradient projections for solving a convex feasibility problem with general (not necessarily hyperplanes or half-spaces) convex sets in the inconsistent case and propose a strategy that controls the relaxation parameters in a specific self-adapting manner. This strategy leaves enough user flexibility but gives a mathematical guarantee for the algorithm's behavior in the inconsistent case. We present the numerical results of computational experiments that illustrate the computational advantage of the new method. [ABSTRACT FROM AUTHOR]

We propose a new iterative approach for solving linear programs over convex cones. Assuming that Slater's condition is satisfied, the conic problem is transformed to the minimization of a convex differentiable function in the primal-dual space. This function shows similarities with the augmented Lagrangian function and is called "augmented primal-dual function" or "apd-function". The evaluation of the function and its derivative is cheap if the projection of a given point onto the cone can be computed cheaply, and if the projection of a given point onto the affine subspace defining the primal problem can be computed cheaply. For the special case of a semidefinite program, a certain regularization of the apd-function is analyzed. Numerical examples minimizing the apd-function with a conjugate gradient method illustrate the potential of the approach. [ABSTRACT FROM AUTHOR]

We study the convergence of an iterative projection/reflection algorithm originally proposed for solving what are known as phase retrieval problems in optics. There are two features that frustrate any analysis of iterative methods for solving the phase retrieval problem: nonconvexity and infeasibility. The algorithm that we developed, called relaxed averaged alternating reflections (RAAR), was designed primarily to address infeasibility, though our strategy has advantages for nonconvex problems as well. In the present work we investigate the asymptotic behavior of the RAAR algorithm for the general problem of finding points that achieve the minimum distance between two closed convex sets in a Hilbert space with empty intersection, and for the problem of finding points that achieve a local minimum distance between one closed convex set and a closed prox-regular set, also possibly nonintersecting. The nonconvex theory includes and expands prior results limited to convex sets with nonempty intersection. To place the RAAR algorithm in context, we develop parallel statements about the standard alternating projections algorithm and gradient descent. All of the various algorithms are unified as instances of iterated averaged alternating proximal reflectors applied to a sum of regularized maximal monotone mappings. [ABSTRACT FROM AUTHOR]

Second-order sufficient optimality conditions are established for the optimal control of semilinear elliptic and parabolic equations with pointwise constraints on the control and the state. In contrast to former publications on this subject, the cone of critical directions is the smallest possible in the sense that the second-order sufficient conditions are the closest to the associated necessary ones. The theory is developed for elliptic distributed controls in domains up to dimension three. Moreover, problems of elliptic boundary control and parabolic distributed control are discussed in spatial domains of dimension two and one, respectively. [ABSTRACT FROM AUTHOR]

Abstract. We present iterative methods for finding the critical points and/or the minima of extended real valued functions of the form Ø =ψ — ip+g—h, where ψ is a differentiate function and g and h are convex, proper, and lower semicontinuous. The underlying idea relies upon the discretization of a first older dissipative dynamical system which allows us to preserve the local feature and to obtain some convergence results. The main theorems not only recover known convergence results in this field but also provide a theoretical basis for the development of new iterative methods. [ABSTRACT FROM AUTHOR]

A class of trust-region methods is presented for solving unconstrained nonlinear and possibly nonconvex discretized optimization problems, like those arising in systems governed by partial differential equations. The algorithms in this class make use of the discretization level as a means of speeding up the computation of the step. This use is recursive, leading to true multilevel/multiscale optimization methods reminiscent of multigrid methods in linear algebra and the solution of partial differential equations. A simple algorithm of the class is then described and its numerical performance is shown to be numerically promising. This observation then motivates a proof of global convergence to first-order stationary points on the fine grid that is valid for all algorithms in the class. [ABSTRACT FROM AUTHOR]