The bestL 2-approximation by finite sums of functions with separable variables

Summary We consider the problem of the best approximation of a given functionh L ² (X × Y) by sums _k=1 ⁿ f _k f _k, with a prescribed numbern of products of arbitrary functionsf _k L ² (X) andg _k L ² (Y). As a co-product we develop a new proof of the Hilbert—Schmidt decomposition theorem for functions lying inL ² (X × Y).     

On estimating workload in interval branch-and-bound global optimization algorithms

In general, solving Global Optimization (GO) problems by Branch-and-Bound (B&B) requires a huge computational capacity. Parallel execution is used to speed up the computing time. As in this type of algorithms, the foreseen computational workload (number of nodes in the B&B tree) changes dynamically during the execution, the load balancing and the decision on additional processors is complicated. We use the term left-over to represent the number of nodes that still have to be evaluated at a certain moment during execution. In this work, we study new methods to estimate the left-over value based on the observed amount of pruning. This provides information about the remaining running time of the algorithm and the required computational resources. We focus on their use for interval B&B GO algorithms.     

On the selection of subdivision directions in interval branch-and-bound methods for global optimization

This paper investigates the influence of the interval subdivision selection rule on the convergence of interval branch-and-bound algorithms for global optimization. For the class of rules that allows convergence, we study the effects of the rules on a model algorithm with special list ordering. Four different rules are investigated in theory and in practice. A wide spectrum of test problems is used for numerical tests indicating that there are substantial differences between the rules with respect to the required CPU time, the number of function and derivative evaluations, and the necessary storage space. Two rules can provide considerable improvements in efficiency for our model algorithm.The work has been supported by the Grants OTKA 2879/1991, and MKM 414/1994.     

Valid inequalities for separable concave constraints with indicator variables

We study valid inequalities for optimization models that contain both binary indicator variables and separable concave constraints. These models reduce to a mixed-integer linear program (MILP) when the concave constraints are ignored, or to a nonconvex global optimization problem when the binary restrictions are ignored. In algorithms designed to solve these problems to global optimality, cutting planes to strengthen the relaxation are traditionally obtained using valid inequalities for the MILP only. We propose a technique to obtain valid inequalities that are based on both the MILP constraints and the concave constraints. We begin by characterizing the convex hull of a four-dimensional set consisting of a single binary indicator variable, a single concave constraint, and two linear inequalities. Using this analysis, we demonstrate how valid inequalities for the single node flow set and for the lot-sizing polyhedron can be “tilted” to give valid inequalities that also account for separable concave functions of the arc flows. We present computational results demonstrating the utility of the new inequalities for nonlinear transportation problems and for lot-sizing problems with concave costs. To our knowledge, this is one of the first works that simultaneously convexifies both nonconvex functions and binary variables to strengthen the relaxations of practical mixed-integer nonlinear programs.     

Association measures for interval variables

Advances in Data Analysis and Classification - Symbolic Data Analysis (SDA) is a relatively new field of statistics that extends conventional data analysis by taking into account intrinsic data...     

On comonotonic functions of uncertain variables

Uncertain variable is used to model quantities in uncertainty. This paper considers comonotonic functions of an uncertain variable, and gives their uncertainty distributions. Besides, it proves the linearity of expected value operator on comonotonic functions of an uncertain variable.     

Convex programming with single separable constraint and bounded variables

In this paper a minimization problem with convex objective function subject to a separable convex inequality constraint “≤” and bounded variables (box constraints) is considered. We propose an iterative algorithm for solving this problem based on line search and convergence of this algorithm is proved. At each iteration, a separable convex programming problem with the same constraint set is solved using Karush-Kuhn-Tucker conditions. Convex minimization problems subject to linear equality/ linear inequality “≥” constraint and bounds on the variables are also considered. Numerical illustration is included in support of theory.     

A new nonlinear interval programming method for uncertain problems with dependent interval variables

This paper proposes a new nonlinear interval programming method that can be used to handle uncertain optimization problems when there are dependencies among the interval variables. The uncertain domain is modeled using a multidimensional parallelepiped interval model. The model depicts single-variable uncertainty using a marginal interval and depicts the degree of dependencies among the interval variables using correlation angles and correlation coefficients. Based on the order relation of interval and the possibility degree of interval, the uncertain optimization problem is converted to a deterministic two-layer nesting optimization problem. The affine coordinate is then introduced to convert the uncertain domain of a multidimensional parallelepiped interval model to a standard interval uncertain domain. A highly efficient iterative algorithm is formulated to generate an efficient solution for the multi-layer nesting optimization problem after the conversion. Three computational examples are given to verify the effectiveness of the proposed method.     

An algorithm for a separable integer programming problem with cumulatively bounded variables

An algorithm is presented for obtaining the optimal solution of an integer programming problem in which the nested constraints represent the cumulative bounding of the variables and the objective function is a sum of concave functions of one variables. The algorithm requires O(m log(m)log²(b_m/m)) time, where m is the number of variables and b_m is an upper bound on the sum of the m variables, b_m ⩾m⩾1. It is also demonstrated that a special case of identical concave functions is solvable in O(m). Both results significantly improve the previous bounds for these problems.     

On the existence of convex decompositions of partially separable functions

The concept of a partially separable functionf developed in [4] is generalized to include all functionsf that can be expressed as a finite sum of element functionsf _i whose Hessians have nontrivial nullspacesN _i , Such functions can be efficiently minimized by the partitioned variable metric methods described in [5], provided that each element functionf _i is convex. If this condition is not satisfied, we attempt toconvexify the given decomposition by shifting quadratic terms among the originalf _i such that the resulting modified element functions are at least locally convex. To avoid tests on the numerical value of the Hessian, we study the totally convex case where all locally convexf with the separability structureN _i ¹ have a convex decomposition. It is shown that total convexity only depends on the associated linear conditions on the Hessian matrix. In the sparse case, when eachN _i is spanned by Cartesian basis vectors, it is shown that a sparsity pattern corresponds to a totally convex structure if and only if it allows a (permuted) LDL^T factorization without fill-in.     

Bounding separable recourse functions with limited distribution information

The recourse function in a stochastic program with recourse can be approximated by separable functions of the original random variables or linear transformations of them. The resulting bound then involves summing simple integrals. These integrals may themselves be difficult to compute or may require more information about the random variables than is available. In this paper, we show that a special class of functions has an easily computable bound that achieves the best upper bound when only first and second moment constraints are available.This research has been partially supported by the National Science Foundation under Grants ECS-8304065 and ECS-8815101, by the Office of Naval Research Grant N00014-86-K-0628 and by the National Research Council under a Research Associateship at the Naval Postgraduate School, Monterey, California.     

Epsilon-inflation with contractive interval functions

For contractive interval functions [g] we show that results from the iterative process after finitely many iterations if one uses the epsilon-inflated vector as input for [g] instead of the original output vector [x] ^k . Applying Brouwer's fixed point theorem, zeros of various mathematical problems can be verified in this way.