Search

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]

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]

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]

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]

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]

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]

We consider the expected residual minimization formulation of the stochastic R0 matrix linear complementarity problem. We show that the involved matrix being a stochastic R0 matrix is a necessary and sufficient condition for the solution set of the expected residual minimization problem to be nonempty and bounded. Moreover, local and global error bounds are given for the stochastic R0 matrix linear complementarity problem. A stochastic approximation method with acceleration by averaging is applied to solve the expected residual minimization problem. Numerical examples and applications of traffic equilibrium and system control are given. [ABSTRACT FROM AUTHOR]

An active set algorithm (ASA) for box constrained optimization is developed. The algorithm consists of a nonmonotone gradient projection step, an unconstrained optimization step, and a set of rules for branching between the two steps. Global convergence to a stationary point is established. For a nondegenerate stationary point, the algorithm eventually reduces to unconstrained optimization without restarts. Similarly, for a degenerate stationary point, where the strong second order sufficient optimality condition holds, the algorithm eventually reduces to unconstrained optimization without restarts. A specific implementation of the ASA is given which exploits the recently developed cyclic Barzilai-Borwein (CBB) algorithm for the gradient projection step and the recently developed conjugate gradient algorithm CG_DESCENT for unconstrained optimization. Numerical experiments are presented using box constrained problems in the CUTEr and MINPACK-2 test problem libraries. [ABSTRACT FROM AUTHOR]

In a numerical study, Contreras and Tapia demonstrated the value of selectively sizing the BFGS secant update. A conclusion of the current study is that there is value in following a sizing of the BFGS update with a shifting of the BFGS update. Our motivation for such a strategy comes from the known fact that the BFGS update is prone to producing updates with large eigenvalues. Hence, sizing may contribute to near singularity, and shifting can help compensate for this deficiency. We follow Contreras and Tapia in our form of selective sizing. Our form of shifting can be viewed as switching from the BFGS update to an alternative member of the Broyden family of updates. Our shift is obtained by minimizing a weighted form of the Byrd-Nocedal measure over a sized Broyden family of secant updates. Numerically, our most effective shift is the one that gives the member of the class which is closest to steepest descent in the Byrd-Nocedal measure. [ABSTRACT FROM AUTHOR]