Search

We present in this paper two different classes of general multiple-splitting algorithms for solving finite-dimensional convex optimization problems. Under the assumption that the function being minimized can be written as the sum of K convex functions, each of which has a Lipschitz continuous gradient, we prove that the number of iterations needed by the first class of algorithms to obtain an ε-optimal solution is O((K - 1)L/ε), where L is an upper bound on all of the Lipschitz constants. The algorithms in the second class are accelerated versions of those in the first class, where the complexity result is improved to O(√(K - 1)L/ε) while the computational effort required at each iteration is almost unchanged. To the best of our knowledge, the complexity results presented in this paper are the first ones of this type that have been given for splitting and alternating direction-type methods. Moreover, all algorithms proposed in this paper are parallelizable, which makes them particularly attractive for solving certain large-scale problems. [ABSTRACT FROM AUTHOR]

Continuous linear programs have attracted considerable interest due to their potential for modeling manufacturing, scheduling, and routing problems. While efficient simplex-type algorithms have been developed for separated continuous linear programs, crude time discretization remains the method of choice for solving general (nonseparated) problenl instances. In this paper we propose a more generic approximation scheme for nonseparated continuous linear programs, where we approximate the functional decision variables (policies) by polynomial and piecewise polynomial decision rules. This restriction results in an upper bound on the original problem, which can be computed efficiently by solving a tractable semidefinite program. To estimate the approximation error, we also compute a lower bound by solving a dual continuous lineal program in (piecewise) polynomial decision rules. We establish the convergence of the primal and dual approximations under Stater-type constraint qualifications. We also highlight the potential of our method for optimizing large-scale multiclass queueing systems and dynamic Leontief models. [ABSTRACT FROM AUTHOR]

In this paper, we propose an efficient approach for solving a class of large-scale convex optimization problems. The problem we consider is the minimization of a convex function over a simple (possibly infinite-dimensional) convex set, under the additional constraint Au ∈ T, where A is a linear operator and T is a convex set whose dimension is small compared to the dimension of the feasible region. In our approach, we dualize the linear constraints, solve the resulting dual problem with a purely dual gradient-type method and show how to reconstruct an approximate primal solution. Because the linear constraints have been dualized, the dual objective function typically becomes separable, mid therefore easy to compute. In order to accelerate our scheme, we introduce a novel double smoothing technique that involves regularization of the dual problem to allow the use of a fast gradient method. As a result, we obtain a method with complexity O(1/ε ln 1/ε) gradient iterations, where ε is the desired accuracy for the primal-dual solution. Our approach covers, in particular, optimal control problems with a trajectory governed by a system of linear differential equations, where the additional constraints can, for example, force the trajectory to visit some convex sets at certain moments in time. [ABSTRACT FROM AUTHOR]

The stochastic variational inequality (VI) has been used widely in engineering and economics as an effective mathematical model for a number of equilibrium problems involving uncertain data. This paper presents a new expected residual minimization (ERM) formulation for a class of stochastic VI. The objective of the ERM-formulation is Lipschitz continuous and semismooth which helps us guarantee the existence of a solution and convergence of approximation methods. We propose a globally convergent (a.s.) smoothing sample average approximation (SSAA) method to minimize the residual function; this minimization problem is convex for the linear stochastic VI if the expected matrix is positive semidefinite. We show that the ERM problem and its SSAA problems have minimizers in a compact set and any cluster point of minimizers and stationary points of the SSAA problems is a minimizer and a stationary point of the ERM problem (a.s.). Our examples come from applications involving traffic flow problems. We show that the conditions we impose are satisfied and that the solutions, efficiently generated by the SSAA procedure, have desirable properties. [ABSTRACT FROM AUTHOR]

It has long been conjectured that the crossing numbers of the complete bipartite graph Km,n and of the complete graph Kn equal Z(m,n) := [n/2] [n-1/2] [m/2][m-1/2] and Z(n):= 1/4 [n/2] [n-1/2] [n-2/2] [n-3/2], respectively. In a 2-page drawing of a graph, the vertices are drawn on a straight line (the spine), and each edge is contained in one of the half-planes of the spine. The 2-page crossing number ν2(G) of a graph G is the minimum number of crossings in a 2-page drawing of G. Somewhat surprisingly, there are 2-page drawings of Km,n (respectively, Kn) with exactly Z(m,n) (respectively, Z(n)) crossings, thus yielding the conjectures (I) ν2(Km,n) ≟ Z(m,n) and (II) ν2(Kn) ≟ Z(n). It is known that (I) holds for min{m,n} ≤ 6, and that (II) holds for n ≤ 14. In this paper we prove that (I) holds asymptotically (that is, limn → ∞ ν2(Km,n)/Z(m, n) = 1) for m = 7 and 8. We also prove (II) for 15 ≤ n ≤ 18 and n ∈ {20, 24}, and establish the asymptotic estimate limn → ∞ ν2(Kn)/Z(n) ≥ 0.9253. The previous best-known lower bound involved the constant 0.8594. [ABSTRACT FROM AUTHOR]

The Nelder-Mead algorithm, a longstanding direct search method for unconstrained optimization published in 1965, is designed to minimize a scalar-valued function f of n real variables using only function values, without any derivative information. Each Nelder-Mead iteration is associated with a nondegenerate simplex defined by n + 1 vertices and their function values; a typical iteration produces a new simplex by replacing the worst vertex by a new point. Despite the method's widespread use, theoretical results have been limited: for strictly convex objective functions of one variable with bounded level sets, the algorithm always converges to the minimizer; for such functions of two variables, the diameter of the simplex converges to zero but examples constructed by McKinnon show that the algorithm may converge to a nonminimizing point. This paper considers the restricted Nelder-Mead algorithm, a variant that does not allow expansion steps. In two dimensions we show that for any nondegenerate starting simplex and any twice-continuously differentiable function with positive definite Hessian and bounded level sets, the algorithm always converges to the minimizer. The proof is based on treating the method as a discrete dynamical system and relies on several techniques that are nonstandard in convergence proofs for unconstrained optimization. [ABSTRACT FROM AUTHOR]

In this paper we study constrained eigenvalue optimization of noncommutative (nc) polynomials, focusing on the polydisc and the ball. Our three main results are as follows: (1) an nc polynomial is nonnegative if and only if it admits a weighted sum of hermitian squares decomposition; (2) (eigenvalue) optima for nc polynomials can be computed using a single semidefinite program (SDP)--this sharply contrasts with the commutative case where sequences of SDPs are needed; (3) the dual solution to this "single" SDP can be exploited to extract eigenvalue optimizers with an algorithm based on two ingredients: solution to a truncated nc moment problem via flat extensions, and Gelfand-Naimark-Segal construction. The implementation of these procedures in our computer algebra system NCSOStools is presented, and several examples pertaining to matrix inequalities are given to illustrate our results. [ABSTRACT FROM AUTHOR]

In this paper we propose new methods for solving huge-scale optimization problems. For problems of this size, even the simplest full-dimensional vector operations are very expensive. Hence, we propose to apply an optimization technique based on random partial update of decision variables. For these methods, we prove the global estimates for the rate of convergence. Surprisingly, for certain classes of objective functions, our results are better than the standard worst-case bounds for deterministic algorithms. We present constrained and unconstrained versions of the method and its accelerated variant. Our numerical test confirms a high efficiency of this technique on problems of very big size. [ABSTRACT FROM AUTHOR]

We consider the linearly constrained separable convex minimization problem whose objective function is separable into m individual convex functions with nonoverlapping variables. A Douglas-Rachford alternating direction method of multipliers (ADM) has been well studied in the literature for the special case of m = 2. But the convergence of extending ADM to the general case of m ≥ 3 is still open. In this paper, we show that the straightforward extension of ADM is valid for the general case of m ≥ 3 if it is combined with a Gaussian back substitution procedure. The resulting ADM with Gaussian back substitution is a novel approach towards the extension of ADM from m = 2 to m ≥ 3, and its algorithmic framework is new in the literature. For the ADM with Gaussian back substitution, we prove its convergence via the analytic framework of contractive-type methods, and we show its numerical efficiency by some application problems. [ABSTRACT FROM AUTHOR]