The omnipresence of Lagrange

Lagrangian relaxation is usually considered in the combinatorial optimization community as a mere technique, sometimes useful to compute bounds. It is actually a very general method, inevitable as soon as one bounds optimal values, relaxes constraints, convexifies sets, generates columns etc. In this paper we review this method, from both points of view of theory (to dualize a given problem) and algorithms (to solve the dual by nonsmooth optimization).     

Convexification of a Noninferior Frontier

In a recent paper by Li (Ref. 1), a scheme was proposed to convexify an efficient frontier for a vector optimization problem by rescaling each component of the vector objective functions by its p-power. For sufficiently large p, it was shown that the transformed efficient frontier is cone-convex; hence, the usual linear scalarization (or supporting hyperplane) method can be used to find the efficient solutions. An outstanding question remains: What is the minimum value of p such that the efficient frontier can be convexified? In this note, we answer the above question by deriving some theoretical lower bounds for p.

     

New error bounds and their applications to convergence analysis of iterative algorithms

We present two new error bounds for optimization problems over a convex set whose objective function f is either semianalytic or γ-strictly convex, with γ≥1. We then apply these error bounds to analyze the rate of convergence of a wide class of iterative descent algorithms for the aforementioned optimization problem. Our analysis shows that the function sequence {f(x ^k )} converges at least at the sublinear rate of k ^-ε for some positive constant ε, where k is the iteration index. Moreover, the distances from the iterate sequence {x ^k } to the set of stationary points of the optimization problem converge to zero at least sublinearly. Received: October 5, 1999 / Accepted: January 1, 2000?Published online July 20, 2000     

Improving Hadamard's inequality *

We study several bounds for the determinant of an n × n positive definite Hermitian matrix A. These bounds are the best possible given certain data about A. We find the best bounds in the cases that we are given: (i) the diagonal elements of A: (ii) the traces trA,tr A ² and n and (iii)n, tr A tr A ² and the diagonal elements of A. In case (i) we get the well known Hadamard inequality. The other bounds are Hadamard type bounds. The bounds are found using optimization techniques.     

Upper bounds for revenue maximization in a satellite scheduling problem

This paper presents upper bounds for the Satellite Revenue Selection and Schedulingproblem (SRSS). A compact model of this generalized Prize Collecting Traveling Salesman Problem with Time Windows is defined and enriched with valid inequalities based on task interval reasoning. The non-concavity of the objective function to be maximized is also studied. Finally a Russian Dolls approach combines bounds on nested sub-problems. These first upper bounds for the SRSS problem are compared to best known solutions of the benchmark of the optimization challenge organized by the French OR society.Received: June 2003, Revised: January 2004, MSC classification: 90C90     

Some bounds for coefficients of schlicht pseudo-conformal mappings

Summary The author considers a schlicht pseudo-conformal mapping of a domainB in the (z ₁ , z ₂ )-space onto the Reinhardt circular domainC in the (ξ ₁ , ξ ₂ )-space by a pair of functions (see (1)§ 1). The domainB is assumed to include the bicylinder ((2)§ 2) and to omit four planes z_k=a_k, z_k=b_k, k=1, 2. Upper bounds for a sequence of the coefficients _μv ^(k) of the developments (1) are given, see p. 304. The upper bounds depend only on a_k, b_k, k=1, 2, and on the radii r_k of the bicylinder ((2)§ 2). The bounds are obtained by using the method of the kernel function. The result can be considered as an analogue to the inequalities of Grunsky in the theory of functions of one complex variable. To Enrico Bompiani on his scientific Jubiles This paper was prepared under the sponsorship of the N. S. F.     

Convex Envelopes of Monomials of Odd Degree

Convex envelopes of nonconvex functions are widely used to calculate lower bounds to solutions of nonlinear programming problems (NLP), particularly within the context of spatial Branch-and-Bound methods for global optimization. This paper proposes a nonlinear continuous and differentiable convex envelope for monomial terms of odd degree, x ^2k+1, where k N and the range of x includes zero. We prove that this envelope is the tightest possible. We also derive a linear relaxation from the proposed envelope, and compare both the nonlinear and linear formulations with relaxations obtained using other approaches.     

Fast deterministic approximation for the multicommodity flow problem

In this paper we consider an optimization version of the multicommodity flow problem which is known as the maximum concurrent flow problem. We show that an approximate solution to this problem can be computed deterministically using O(k(ε ⁻² + logk) logn) 1-commodity minimum-cost flow computations, wherek is the number of commodities,n is the number of nodes, andε is the desired precision. We obtain this bound by proving that in the randomized algorithm developed by Leighton et al. (1995) the random selection of commodities can be replaced by the deterministic round-robin without increasing the total running time. Our bound significantly improves the previously known deterministic upper bounds and matches the best known randomized upper bound for the approximation concurrent flow problem. A preliminary version of this paper appeared inProceedings of the 6th ACM-SIAM Symposium on Discrete Algorithms, San Francisco CA, 1995, pp. 486–492.     

Class of tight bounds on the Q‐function with closed‐form upper bound on relative error

In this paper, we propose a novel class of parametric bounds on the Q‐function, which are lower bounds for 1 ≤ a < 3 and x > x_t = (a (a‐1) / (3‐a))^1/2, and upper bound for a = 3. We prove that the lower and upper bounds on the Q‐function can have the same analytical form that is asymptotically equal, which is a unique feature of our class of tight bounds. For the novel class of bounds and for each particular bound from this class, we derive the beneficial closed‐form expression for the upper bound on the relative error. By comparing the bound tightness for moderate and large argument values not only numerically, but also analytically, we demonstrate that our bounds are tighter compared with the previously reported bounds of similar analytical form complexity.     

Some new bounds for the maximum number of vertex colorings of a (v,e)-graph

Let f(v, e, λ) denote the maximum number of proper vertex colorings of a graph with v vertices and e edges in λ colors. In this paper we present some new upper bounds for f(v, e, λ). In particular, a new notion of pseudo-proper colorings of a graph is given, which allows us to significantly improve the upper bounds for f(v, e, 3) given by Lazebnik and Liu in the case where e > v²/4. © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 115–128, 1998     

Fair upper bounds for the curvature in univariate convex interpolation

In convex interpolation the curvature of the interpolants should be as small as possible. We attack this problem by treating interpolation subject to bounds on the curvature. In view of the concexity the lower bound is equal to zero while the upper bound is assumed to be piecewise constant. The upper bounds are called fair with respect to a function class if the interpolation problem becomes solvable for all data sets in strictly convex position. We derive fair a priori bounds for classes of quadraticC ¹, cubicC ², and quarticC ³ splines on refined grids.     

Deciding finiteness for matrix groups over function fields

LetF be a field andt an indeterminate. In this paper we consider aspects of the problem of deciding if a finitely generated subgroup of GL(n,F(t)) is finite. WhenF is a number field, the analysis may be easily reduced to deciding finiteness for subgroups of GL(n,F), for which the results of [1] can be applied. WhenF is a finite field, the situation is more subtle. In this case our main results are a structure theorem generalizing a theorem of Weil and upper bounds on the size of a finite subgroup generated by a fixed number of generators with examples of constructions almost achieving the bounds. We use these results to then give exponential deterministic algorithms for deciding finiteness as well as some preliminary results towards more efficient randomized algorithms. Supported in part by NSF DMS Awards 9404275 and Presidential Faculty Fellowship.     

Optimization in engineering design

This paper presents a method for solving a class of constrained optimization problems in finite-dimensional spaces. This type of problem usually arises in connection with parameter optimization in engineering design. Most often, these problems consist of incorporating upper and/or lower bounds on the variables in otherwise unconstrained optimization problems. The proposed method replaces the original optimization problem withm constraints (m>1) by a sequence of optimization problems with one constraint only. The theory behind this method is discussed in the subsequent sections.This research was supported by NSF Grant No. GK-4984.     

The lower bounds of life span of classical solutions to one‐dimensional initial‐Neumann boundary value problems for general quasilinear wave equations

In this paper, we will study the lower bounds of the life span (the maximal existence time) of solutions to the initial‐boundary value problems with small initial data and zero Neumann boundary data on exterior domain for one‐dimensional general quasilinear wave equations u_tt?u_xx=b(u,Du)u_xx+F(u,Du). Our lower bounds of the life span of solutions in the general case and special case are shorter than that of the initial‐Dirichlet boundary value problem for one‐dimensional general quasilinear wave equations. We clarify that although the lower bounds in this paper are same as that in the case of Robin boundary conditions obtained in the earlier paper, however, the results in this paper are not the trivial generalization of that in the case of Robin boundary conditions because the fundamental Lemmas 2.4, 2.5, 2.6, and 2.7, that is, the priori estimates of solutions to initial‐boundary value problems with Neumann boundary conditions, are established differently, and then the specific estimates in this paper are different from that in the case of Robin boundary conditions. Another motivation for the author to write this paper is to show that the well‐posedness of problem 1.1 is the essential precondition of studying the lower bounds of life span of classical solutions to initial‐boundary value problems for general quasilinear wave equations. The lower bound estimates of life span of classical solutions to initial‐boundary value problems is consistent with the actual physical meaning. Finally, we obtain the sharpness on the lower bound of the life span 1.8 in the general case and 1.10 in the special case. Copyright © 2015 John Wiley & Sons, Ltd.     

Reference variable methods of solving min–max optimization problems

In this paper, reference variable methods are proposed for solving nonlinear Minmax optimization problems with unconstraint or constraints for the first time, it uses reference decision vectors to improve the methods in Vincent and Goh (J Optim Theory Appl 75:501–519, 1992) such that its algorithm is convergent. In addition, a new method based on KKT conditions of min or max constrained optimization problems is also given for solving the constrained minmax optimization problems, it makes the constrained minmax optimization problems a problem of solving nonlinear equations by a complementarily function. For getting all minmax optimization solutions, the cost function f(x, y) can be constrained as M ₁ < f(x, y) < M ₂ by using different real numbers M ₁ and M ₂. To show effectiveness of the proposed methods, some examples are taken to compare with results in the literature, and it is easy to find that the proposed methods can get all minmax optimization solutions of minmax problems with constraints by using different M ₁ and M ₂, this implies that the proposed methods has superiority over the methods in the literature (that is based on different initial values to get other minmax optimization solutions).     

Random lifts of graphs: Independence and chromatic number

For a graph G, a random n‐lift of G has the vertex set V(G)×[n] and for each edge [u, v] ∈ E(G), there is a random matching between {u}×[n] and {v}×[n]. We present bounds on the chromatic number and on the independence number of typical random lifts, with G fixed and n→∞. For the independence number, upper and lower bounds are obtained as solutions to certain optimization problems on the base graph. For a base graph G with chromatic number χ and fractional chromatic number χ_f, we show that the chromatic number of typical lifts is bounded from below by const ? and also by const ? χ_f/log²χ_f (trivially, it is bounded by χ from above). We have examples of graphs where the chromatic number of the lift equals χ almost surely, and others where it is a.s. O(χ/logχ). Many interesting problems remain open. © 2002 John Wiley & Sons, Inc. Random Struct. Alg., 20, 1–22, 2002     

Evolving sets, mixing and heat kernel bounds

We show that a new probabilistic technique, recently introduced by the first author, yields the sharpest bounds obtained to date on mixing times of Markov chains in terms of isoperimetric properties of the state space (also known as conductance bounds or Cheeger inequalities). We prove that the bounds for mixing time in total variation obtained by Lovász and Kannan, can be refined to apply to the maximum relative deviation |pⁿ(x,y)/π(y)−1| of the distribution at time n from the stationary distribution π. We then extend our results to Markov chains on infinite state spaces and to continuous-time chains. Our approach yields a direct link between isoperimetric inequalities and heat kernel bounds; previously, this link rested on analytic estimates known as Nash inequalities.Research supported in part by NSF Grants #DMS-0104073 and #DMS-0244479.     

Best-possible bounds on sets of bivariate distribution functions

The fundamental best-possible bounds inequality for bivariate distribution functions with given margins is the Fréchet–Hoeffding inequality: If H denotes the joint distribution function of random variables X and Y whose margins are F and G, respectively, then max(0,F(x)+G(y)−1)H(x,y)min(F(x),G(y)) for all x,y in [−∞,∞]. In this paper we employ copulas and quasi-copulas to find similar best-possible bounds on arbitrary sets of bivariate distribution functions with given margins. As an application, we discuss bounds for a bivariate distribution function H with given margins F and G when the values of H are known at quartiles of X and Y.     

Improved Bounds for Ternary Linear Codes of Dimension 8 Using Tabu Search

In this paper, new codes of dimension 8 are presented which give improved bounds on the maximum possible minimum distance of ternary linear codes. These codes belong to the class of quasi-twisted (QT) codes, and have been constructed using a stochastic optimization algorithm, tabu search. Twenty three codes are given which improve or establish the bounds for ternary codes. In addition, a table of upper and lower bounds for d ₃(n, 8) is presented for n 200.     

The max-cut problem and quadratic 0–1 optimization; polyhedral aspects,relaxations and bounds

Given a graphG, themaximum cut problem consists of finding the subsetS of vertices such that the number of edges having exactly one endpoint inS is as large as possible. In the weighted version of this problem there are given real weights on the edges ofG, and the objective is to maximize the sum of the weights of the edges having exactly one endpoint in the subsetS. In this paper, we consider the maximum cut problem and some related problems, likemaximum-2-satisfiability, weighted signed graph balancing. We describe the relation of these problems to the unconstrained quadratic 0–1 programming problem, and we survey the known methods for lower and upper bounds to this optimization problem. We also give the relation between the related polyhedra, and we describe some of the known and some new classes of facets for them.