Search

In this paper, we consider approximation algorithms for optimizing a generic multi-variate homogeneous polynomial function, subject to homogeneous quadratic constraints. Such optimization models have wide applications, e.g., in signal processing, magnetic resonance imaging (MRI), data training, approximation theory, and portfolio selection. Since polynomial functions are non-convex, the problems under consideration are all NP-hard in general. In this paper we shall focus on polynomial-time approximation algorithms. In particular, we first study optimization of a multi-linear tensor function over the Cartesian product of spheres. We shall propose approximation algorithms for such problem and derive worst-case performance ratios, which are shown to be dependent only on the dimensions of the model. The methods are then extended to optimize a generic multi-variate homogeneous polynomial function with spherical constraint. Likewise, approximation algorithms are proposed with provable approximation performance ratios. Furthermore, the constraint set is relaxed to be an intersection of co-centered ellipsoids; namely, we consider maximization of a homogeneous polynomial over the intersection of ellipsoids centered at the origin, and propose polynomial-time approximation algorithms with provable worst-case performance ratios. Numerical results are reported, illustrating the effectiveness of the approximation algorithms studied. [ABSTRACT FROM AUTHOR]

This paper presents an active-set algorithm for large-scale optimization that occupies the middle ground between sequential quadratic programming and sequential linear-quadratic programming methods. It consists of two phases. The algorithm first minimizes a piecewise linear approximation of the Lagrangian, subject to a linearization of the constraints, to determine a working set. Then, an equality constrained subproblem based on this working set and using second derivative information is solved in order to promote fast convergence. A study of the local and global convergence properties of the algorithm highlights the importance of the placement of the interpolation points that determine the piecewise linear model of the Lagrangian. [ABSTRACT FROM AUTHOR]

Coordinate descent algorithms solve optimization problems by successively performing approximate minimization along coordinate directions or coordinate hyperplanes. They have been used in applications for many years, and their popularity continues to grow because of their usefulness in data analysis, machine learning, and other areas of current interest. This paper describes the fundamentals of the coordinate descent approach, together with variants and extensions and their convergence properties, mostly with reference to convex objectives. We pay particular attention to a certain problem structure that arises frequently in machine learning applications, showing that efficient implementations of accelerated coordinate descent algorithms are possible for problems of this type. We also present some parallel variants and discuss their convergence properties under several models of parallel execution. [ABSTRACT FROM AUTHOR]

In a two-stage robust covering problem, one of several possible scenarios will appear tomorrow and require to be covered, but costs are higher tomorrow than today. What should you anticipatorily buy today, so that the worst-case cost (summed over both days) is minimized? We consider the $$k$$ -robust model where the possible scenarios tomorrow are given by all demand-subsets of size $$k$$ . In this paper, we give the following simple and intuitive template for $$k$$ -robust covering problems: having built some anticipatory solution, if there exists a single demand whose augmentation cost is larger than some threshold, augment the anticipatory solution to cover this demand as well, and repeat. We show that this template gives good approximation algorithms for $$k$$ -robust versions of many standard covering problems: set cover, Steiner tree, Steiner forest, minimum-cut and multicut. Our $$k$$ -robust approximation ratios nearly match the best bounds known for their deterministic counterparts. The main technical contribution lies in proving certain net-type properties for these covering problems, which are based on dual-rounding and primal-dual ideas; these properties might be of some independent interest. As a by-product of our techniques, we also get algorithms for max-min problems of the form: ' given a covering problem instance, which $$k$$ of the elements are costliest to cover?' For the problems mentioned above, we show that their $$k$$ -max-min versions have performance guarantees similar to those for the $$k$$ -robust problems. [ABSTRACT FROM AUTHOR]

Optimality functions define stationarity in nonlinear programming, semi-infinite optimization, and optimal control in some sense. In this paper, we consider optimality functions for stochastic programs with nonlinear, possibly nonconvex, expected value objective and constraint functions. We show that an optimality function directly relates to the difference in function values at a candidate point and a local minimizer. We construct confidence intervals for the value of the optimality function at a candidate point and, hence, provide a quantitative measure of solution quality. Based on sample average approximations, we develop an algorithm for classes of stochastic programs that include CVaR-problems and utilize optimality functions to select sample sizes. [ABSTRACT FROM AUTHOR]

We perform a smoothed analysis of the GCC-condition number $${\fancyscript{C}(A)}$$ of the linear programming feasibility problem $${\exists x\in\mathbb{R}^{m+1}\,Ax < 0}$$. Suppose that $${\bar{A}}$$ is any matrix with rows $${\overline{a}_i}$$ of euclidean norm 1 and, independently for all i, let a be a random perturbation of $${\overline{a}_i}$$ following the uniform distribution in the spherical disk in S of angular radius arcsin σ and centered at $${\overline{a}_i}$$. We prove that $${\mathbb{E}({\rm ln}\,\fancyscript{C}(A)) =\mathcal{O} (mn/\sigma)}$$. A similar result was shown for Renegar's condition number and Gaussian perturbations by Dunagan et al. (Math Program Ser A, 2009). Our result is robust in the sense that it easily extends to radially symmetric probability distributions supported on a spherical disk of radius arcsin σ, whose density may even have a singularity at the center of the perturbation. Our proofs combine ideas from a recent paper of Bürgisser et al. (Math Comp 77(263), 2008) with techniques of Dunagan et al. [ABSTRACT FROM AUTHOR]

Our paper deals with the interrelation of optimization methods and Lipschitz stability of multifunctions in arbitrary Banach spaces. Roughly speaking, we show that linear convergence of several first order methods and Lipschitz stability mean the same. Particularly, we characterize calmness and the Aubin property by uniformly (with respect to certain starting points) linear convergence of descent methods and approximate projection methods. So we obtain, e.g., solution methods (for solving equations or variational problems) which require calmness only. The relations of these methods to several known basic algorithms are discussed, and errors in the subroutines as well as deformations of the given mappings are permitted. We also recall how such deformations are related to standard algorithms like barrier, penalty or regularization methods in optimization. [ABSTRACT FROM AUTHOR]

We consider a robust formulation, introduced by Krause et al. (J Artif Intell Res 42:427-486, 2011), of the classical cardinality constrained monotone submodular function maximization problem, and give the first constant factor approximation results. The robustness considered is w.r.t. adversarial removal of up to τ elements from the chosen set. For the fundamental case of τ=1, we give a deterministic (1-1/e)-1/Θ(m) approximation algorithm, where m is an input parameter and number of queries scale as O(nm+1). In the process, we develop a deterministic (1-1/e)-1/Θ(m) approximate greedy algorithm for bi-objective maximization of (two) monotone submodular functions. Generalizing the ideas and using a result from Chekuri et al. (in: FOCS 10, IEEE, pp 575-584, 2010), we show a randomized (1-1/e)-ϵ approximation for constant τ and ϵ≤1Ω~(τ), making O(n1/ϵ3) queries. Further, for τ≪k, we give a fast and practical 0.387 algorithm. Finally, we also give a black box result result for the much more general setting of robust maximization subject to an Independence System. [ABSTRACT FROM AUTHOR]

We derive a new approximate version of the alternating direction method of multipliers (ADMM) which uses a relative error criterion. The new version is somewhat restrictive and allows only one of the two subproblems to be minimized approximately, but nevertheless covers commonly encountered special cases. The derivation exploits the long-established relationship between the ADMM and both the proximal point algorithm (PPA) and Douglas-Rachford (DR) splitting for maximal monotone operators, along with a relative-error of the PPA due to Solodov and Svaiter. In the course of analysis, we also derive a version of DR splitting in which one operator may be evaluated approximately using a relative error criterion. We computationally evaluate our method on several classes of test problems and find that it significantly outperforms several alternatives on one problem class. [ABSTRACT FROM AUTHOR]

One of the foremost difficulties in solving Mixed-Integer Nonlinear Programs, either with exact or heuristic methods, is to find a feasible point. We address this issue with a new feasibility pump algorithm tailored for nonconvex Mixed-Integer Nonlinear Programs. Feasibility pumps are algorithms that iterate between solving a continuous relaxation and a mixed-integer relaxation of the original problems. Such approaches currently exist in the literature for Mixed-Integer Linear Programs and convex Mixed-Integer Nonlinear Programs: both cases exhibit the distinctive property that the continuous relaxation can be solved in polynomial time. In nonconvex Mixed-Integer Nonlinear Programming such a property does not hold, and therefore special care has to be exercised in order to allow feasibility pump algorithms to rely only on local optima of the continuous relaxation. Based on a new, high level view of feasibility pump algorithms as a special case of the well-known successive projection method, we show that many possible different variants of the approach can be developed, depending on how several different (orthogonal) implementation choices are taken. A remarkable twist of feasibility pump algorithms is that, unlike most previous successive projection methods from the literature, projection is 'naturally' taken in two different norms in the two different subproblems. To cope with this issue while retaining the local convergence properties of standard successive projection methods we propose the introduction of appropriate norm constraints in the subproblems; these actually seem to significantly improve the practical performance of the approach. We present extensive computational results on the MINLPLib, showing the effectiveness and efficiency of our algorithm. [ABSTRACT FROM AUTHOR]

A numerical solution method for semi-infinite optimization problems with arbitrary, not necessarily box-shaped, index sets is presented. Following the ideas of Floudas and Stein (SIAM J Optim 18:1187-1208, ), convex relaxations of the lower level problem are adaptively constructed and then reformulated as mathematical programs with complementarity constraints and solved. Although the index set is arbitrary, this approximation produces feasible iterates for the original problem. The convex relaxations and needed parameters are constructed with ideas of the αBB method of global optimization and interval methods. It is shown that after finitely many steps an $${\epsilon}$$-stationary point of the original semi-infinite problem is reached. A numerical example illustrates the performance of the proposed method. [ABSTRACT FROM AUTHOR]

We consider two min-max problems (1) minimizing the supremum of finitely many rational functions over a compact basic semi-algebraic set and (2) solving a 2-player zero-sum polynomial game in randomized strategies with compact basic semi-algebraic sets of pure strategies. In both problems the optimal value can be approximated by solving a hierarchy of semidefinite relaxations, in the spirit of the moment approach developed in Lasserre (SIAM J Optim 11:796-817, 2001; Math Program B 112:65-92, 2008). This provides a unified approach and a class of algorithms to compute Nash equilibria and min-max strategies of several static and dynamic games. Each semidefinite relaxation can be solved in time which is polynomial in its input size and practice on a sample of experiments reveals that few relaxations are needed for a good approximation (and sometimes even for finite convergence), a behavior similar to what was observed in polynomial optimization. [ABSTRACT FROM AUTHOR]

Adding cuts based on copositive matrices, we propose to improve Lovász’ bound θ on the clique number and its tightening θ′ introduced by McEliece, Rodemich, Rumsey, and Schrijver. Candidates for cheap and efficient copositivity cuts of this type are obtained from graphs with known clique number. The cost of previously established semidefinite programming bound hierarchies starting with θ′ rapidly increases with the order (and quality requirements). By contrast, the bounds proposed here are relatively cheap in the sense that computational effort is comparable to that required for θ′. [ABSTRACT FROM AUTHOR]

The exponential weight algorithm has been introduced in the framework of discrete time on-line problems. Given an observed process $$\{X_m\}_{m=1,2,\ldots}$$ the input at stage m + 1 is an exponential function of the sum $$S_m = \sum_{\ell = 1}^m X_{\ell}$$ . We define the analog algorithm for a continuous time process X t and prove similar properties in terms of external or internal consistency. We then deduce results for discrete time from their counterpart in continuous time. Finally we compare this approach to another continuous time approximation of a discrete time exponential algorithm based on the average sum S m / m. [ABSTRACT FROM AUTHOR]

Given a graph with costs on the edges, the power of a node is the maximum cost of an edge leaving it, and the power of the graph is the sum of the powers of the nodes of this graph. Motivated by applications in wireless multi-hop networks, we consider four fundamental problems under the power minimization criteria: the Min-Power b-Edge-Cover problem (MP b-EC) where the goal is to find a min-power subgraph so that the degree of every node v is at least some given integer b( v), the Min-Power k-node Connected Spanning Subgraph problem (MP k-CSS), Min-Power k-edge Connected Spanning Subgraph problem (MP k-CSS), and finally the Min-Power k-Edge-Disjoint Paths problem in directed graphs (MP k-EDP). We give an O(log4 n)-approximation algorithm for MP b-EC. This gives an O(log4 n)-approximation algorithm for MP k-CSS for most values of k, improving the best previously known O( k)-approximation guarantee. In contrast, we obtain an $$O(\sqrt{n})$$ approximation algorithm for ECSS, and for its variant in directed graphs (i.e., MP k-EDP), we establish the following inapproximability threshold: MP k-EDP cannot be approximated within O(2log1-ε n) for any fixed ε > 0, unless NP-hard problems can be solved in quasi-polynomial time. [ABSTRACT FROM AUTHOR]

Given an undirected graph G=( V, E) and three specified terminal nodes t 1, t 2, t 3, a 3-cut is a subset A of E such that no two terminals are in the same component of G\ A. If a non-negative edge weight c e is specified for each e∈ E, the optimal 3-cut problem is to find a 3-cut of minimum total weight. This problem is [InlineMediaObject not available: see fulltext.]-hard, and in fact, is max-[InlineMediaObject not available: see fulltext.]-hard. An approximation algorithm having performance guarantee [InlineMediaObject not available: see fulltext.] has recently been given by Călinescu, Karloff, and Rabani. It is based on a certain linear-programming relaxation, for which it is shown that the optimal 3-cut has weight at most [InlineMediaObject not available: see fulltext.] times the optimal LP value. It is proved here that [InlineMediaObject not available: see fulltext.] can be improved to [InlineMediaObject not available: see fulltext.], and that this is best possible. As a consequence, we obtain an approximation algorithm for the optimal 3-cut problem having performance guarantee [InlineMediaObject not available: see fulltext.]. In addition, we show that [InlineMediaObject not available: see fulltext.] is best possible for this algorithm. [ABSTRACT FROM AUTHOR]

In this survey, we give an overview of a technique used to design and analyze algorithms that provide approximate solutions to NP-hard problems in combinatorial optimization. Because of parallels with the primal-dual method commonly used in combinatorial optimization, we call it the primal-dual method for approximation algorithms. We show how this technique can be used to derive approximation algorithms for a number of different problems, including network design problems, feedback vertex set problems, and facility location problems. [ABSTRACT FROM AUTHOR]