Violator spaces: Structure and algorithms

Sharir and Welzl introduced an abstract framework for optimization problems, called LP-type problems or also generalized linear programming problems, which proved useful in algorithm design. We define a new, and as we believe, simpler and more natural framework: violator spaces, which constitute a proper generalization of LP-type problems. We show that Clarkson's randomized algorithms for low-dimensional linear programming work in the context of violator spaces. For example, in this way we obtain the fastest known algorithm for the P-matrix generalized linear complementarity problem with a constant number of blocks. We also give two new characterizations of LP-type problems: they are equivalent to acyclic violator spaces, as well as to concrete LP-type problems (informally, the constraints in a concrete LP-type problem are subsets of a linearly ordered ground set, and the value of a set of constraints is the minimum of its intersection).     

Complexity of linear programming

The complexity of linear programming is discussed in the “integer” and “real number” models of computation. Even though the integer model is widely used in theoretical computer science, the real number model is more useful for estimating an algorithm's running time in actual computation.Although the ellipsoid algorithm is a polynomial-time algorithm in the integer model, we prove that it has unbounded complexity in the real number model. We conjecture that there exists no polynomial-time algorithm for the linear inequalities problem in the real number model. We also conjecture that linear inequalities are strictly harder than linear equalities in all “reasonable” models of computation.     

Some Randomized Algorithms for Convex Quadratic Programming

We adapt some randomized algorithms of Clarkson [3] for linear programming to the framework of so-called LP-type problems, which was introduced by Sharir and Welzl [10]. This framework is quite general and allows a unified and elegant presentation and analysis. We also show that LP-type problems include minimization of a convex quadratic function subject to convex quadratic constraints as a special case, for which the algorithms can be implemented efficiently, if only linear constraints are present. We show that the expected running times depend only linearly on the number of constraints, and illustrate this by some numerical results. Even though the framework of LP-type problems may appear rather abstract at first, application of the methods considered in this paper to a given problem of that type is easy and efficient. Moreover, our proofs are in fact rather simple, since many technical details of more explicit problem representations are handled in a uniform manner by our approach. In particular, we do not assume boundedness of the feasible set as required in related methods. Accepted 7 May 1997     

Global Optimization Versus Integer Programming in Portfolio Optimization under Nonconvex Transaction Costs

This paper is concerned with a portfolio optimization problem under concave and piecewise constant transaction cost. We formulate the problem as nonconcave maximization problem under linear constraints using absolute deviation as a measure of risk and solve it by a branch and bound algorithm developed in the field of global optimization. Also, we compare it with a more standard 0–1 integer programming approach. We will show that a branch and bound method elaborating the special structure of the problem can solve the problem much faster than the state-of-the integer programming code.     

Computing small solutions of Burgers' equation backwards in time

We construct and analyze an algorithm for the numerical computation of Burgers' equation for preceding times, given an a priori bound for the solution and an approximation to the terminal data. The method is based on the “backward beam equation” coupled with an iterative procedure for the solution of the nonlinear problem via a sequence of linear problems. We also present the results of several numerical experiments. It turns out that the procedure converges “asymptotically,” i.e., in the same manner in which an asymptotic expansion converges. This phenomenon seems related to the “destruction of information,” at t = 0, which is typical in backwards dissipative equations. We derive a priori stability estimates for the analytic backwards problem, and we observe that in many numerical experiments, the distance backwards in time where significant accuracy can be attained is much larger than would be expected on the basis of such estimates. The method is useful for small solutions. Problems where steep gradients occur require considerably more precision in measurement. The algorithm is applicable to other semilinear problems.     

Numerical analysis of generalised max-plus eigenvalue problems

This paper is concerned with the deterministic discrete-time infinite horizon optimisation problem on a compact metric space with an average cost criterion involving two functions K (the “cost”) and T (the “time”). Firstly, we collect the different characterisations of the value λ in terms of generalised max-plus eigenvalue problem and in terms of linear programming. Secondly, we prove an error bound on λ when the space is discretised.     

线性比式和规划问题的输出空间分支定界算法

本文旨在针对线性比式和规划这一NP-Hard非线性规划问题提出新的全局优化算法.首先,通过引入p个辅助变量把原问题等价的转化为一个非线性规划问题,这个非线性规划问题的目标函数是乘积和的形式并给原问题增加了p个新的非线性约束,再通过构造凸凹包络的技巧对等价问题的目标函数和约束条件进行相应的线性放缩,构成等价问题的一个下界线性松弛规划问题,从而提出了一个求解原问题的分支定界算法,并证明了算法的收敛性.最后,通过数值结果比较表明所提出的算法是可行有效的.     

Global optimization algorithm for sum of generalized polynomial ratios problem

In this paper, a global optimization algorithm is proposed for solving sum of generalized polynomial ratios problem (P) which arises in various practical problems. Due to its intrinsic difficulty, less work has been devoted to globally solve the problem (P). For such problems, we present a branch and bound algorithm. In this method, by utilizing exponent transformation and new three-level linear relaxation method, a sequence of linear relaxation programming of the initial nonconvex programming problem (P) are derived which are embedded in a branch and bound algorithm. The proposed method need not introduce new variables and constraints and it is convergent to the global minimum of prime problem by means of the subsequent solutions of a series of linear programming problems. Several numerical examples in the literatures are tested to demonstrate that the proposed algorithm can systematically solve these examples to find the approximate ?-global optimum.     

Global optimization method for maximizing the sum of difference of convex functions ratios over nonconvex region

A global optimization algorithm is presented for maximizing the sum of difference of convex functions ratios problem over nonconvex feasible region. This algorithm is based on branch and bound framework. To obtain a difference of convex programming, the considered problem is first reformulated by introducing new variables as few as possible. By using subgradient and convex envelope, the fundamental problem of estimating lower bound in the branch and bound algorithm is transformed into a relaxed linear programming problem which can be solved efficiently. Furthermore, the size of the relaxed linear programming problem does not change during the algorithm search. Lastly, the convergence of the algorithm is analyzed and the numerical results are reported.     

Bus driver duty optimization using an integer programming and evolutionary hybrid algorithm

This paper describes the details of a successful application where an integer programming and evolutionary hybrid algorithm was used to solve a bus driver duty optimization problem. The task is NP-hard, therefore theoretically optimal solutions can only be calculated for very small problem instances. Our aim is to obtain solutions of good quality within reasonable time limits. We first applied an integer programming approach to a set partitioning problem. The model was solved with a column generation algorithm in a branch and bound scheme. In order to solve larger real-life problems, we have combined the integer programming method with a greedy 1+1 steady state evolutionary algorithm. The resulting hybrid algorithm was capable of providing near-optimal solutions within reasonable timescales to larger instances of the bus driver scheduling problem. We present the results and running times of our algorithm in detail, as well as possible directions of future improvements.     

Global optimization for the sum of generalized polynomial fractional functions

In this paper, a branch and bound approach is proposed for global optimization problem (P) of the sum of generalized polynomial fractional functions under generalized polynomial constraints, which arises in various practical problems. Due to its intrinsic difficulty, less work has been devoted to globally solving this problem. By utilizing an equivalent problem and some linear underestimating approximations, a linear relaxation programming problem of the equivalent form is obtained. Consequently, the initial non-convex nonlinear problem (P) is reduced to a sequence of linear programming problems through successively refining the feasible region of linear relaxation problem. The proposed algorithm is convergent to the global minimum of the primal problem by means of the solutions to a series of linear programming problems. Numerical results show that the proposed algorithm is feasible and can successfully be used to solve the present problem (P).     

Heuristic algorithms for the inverse mixed integer linear programming problem

The recent development in inverse optimization, in particular the extension from the inverse linear programming problem to the inverse mixed integer linear programming problem (InvMILP), provides more powerful modeling tools but also presents more challenges to the design of efficient solution techniques. The only reported InvMILP algorithm, referred to as Alg^InvMILP, although finitely converging to global optimality, suffers two limitations that greatly restrict its applicability: it is time consuming and does not generate a feasible solution except for the optimal one. This paper presents heuristic algorithms that are designed to be implemented and executed in parallel with Alg^InvMILP in order to alleviate and overcome its two limitations. Computational experiments show that implementing the heuristic algorithm on one auxiliary processor in parallel with Alg^InvMILP on the main processor significantly improves its computational efficiency, in addition to providing a series of improving feasible upper bound solutions. The additional speedup of parallel implementation on two or more auxiliary processors appears to be incremental, but the upper bound can be improved much faster.     

分支定界算法求解带有释放时间的单机双代理调度问题

本文研究了带有释放时间的单机双代理调度问题,目标函数为极小化最大完工时间和。为了便于利用优化软件求解,建立了混合整数规划模型。考虑到该问题具有NP困难性,因此采用近似与精确算法分别求解不同规模问题。针对大规模问题,提出了优势代理优先启发式算法,并证明了其渐近最优性。针对小规模问题,设计了分支定界法进行最优求解,其中基于释放时间的分支规则和基于加工中断的下界有效地减少了运算时间。最后,通过数值测试验证了分支定界算法的有效性以及启发式算法的收敛性。     

Information Geometry and Interior-Point Algorithms in Semidefinite Programs and Symmetric Cone Programs

We develop an information geometric approach to conic programming. Information geometry is a differential geometric framework specifically tailored to deal with convexity, naturally arising in information science including statistics, machine learning and signal processing etc. First we introduce an information geometric framework of conic programming. Then we focus on semidefinite and symmetric cone programs. Recently, we demonstrated that the number of iterations of Mizuno–Todd–Ye predictor–corrector primal–dual interior-point methods is (asymptotically) expressed with an integral over the central trajectory called “the curvature integral”. The number of iterations of the algorithm is approximated surprisingly well with the integral even for fairly large linear/semidefinite programs with thousands of variables. Here we prove that “the curvature integral” admits a rigorous differential geometric expression based on information geometry. We also obtain an interesting information geometric global theorem on the central trajectory for linear programs. Together with the numerical evidence in the aforementioned work, we claim that “the number of iterations of the interior-point algorithm is expressed as a differential geometric quantity.”     

Lagrangean relaxation for a lower bound to a set partitioning problem with side constraints: properties and algorithms

The problem (P) addressed here is a special set partitioning problem with two additional non-trivial constraints. A Lagrangean Relaxation (LR_u) is proposed to provide a lower bound to the optimal solution to this problem. This Lagrangean relaxation is accomplished by a subgradient optimization procedure which solves at each iteration a special 0–1 knapsack problem (KP-k). We give two procedures to solve (KP-k), namely an implicity enumeration algorithm and a column generation method. The approach is promising for it provides feasible integer solutions to the side constraints that will hopefully be optimal to most of the instances of the problem (P). Properties of the feasible solutions to (KP-k) are highlighted and it is shown that the linear programming relaxation to this problem has a worst case time bound of order O(n³).     

Global maximization of UTA functions in multi-objective optimization

The UTAs (UTilité Additives) type methods for constructing nondecreasing additive utility functions were first proposed by Jacquet-Lagrèze and Siskos in 1982 for handling decision problems of multicriteria ranking. In this article, by UTA functions, we mean functions which are constructed by the UTA type methods. Our purpose is to propose an algorithm for globally maximizing UTA functions of a class of linear/convex multiple objective programming problems. The algorithm is established based on a branch and bound scheme, in which the branching procedure is performed by a so-called I-rectangular bisection in the objective (outcome) space, and the bounding procedure by some convex or linear programs. Preliminary computational experiments show that this algorithm can work well for the case where the number of objective functions in the multiple objective optimization problem under consideration is much smaller than the number of variables.     

A new approach to improve ill-conditioned parabolic optimal control problem via time domain decomposition

In this paper we present a new steepest-descent type algorithm for convex optimization problems. Our algorithm pieces the unknown into sub-blocs of unknowns and considers a partial optimization over each sub-bloc. In quadratic optimization, our method involves Newton technique to compute the step-lengths for the sub-blocs resulting descent directions. Our optimization method is fully parallel and easily implementable, we first presents it in a general linear algebra setting, then we highlight its applicability to a parabolic optimal control problem, where we consider the blocs of unknowns with respect to the time dependency of the control variable. The parallel tasks, in the last problem, turn “on” the control during a specific time-window and turn it “off” elsewhere. We show that our algorithm significantly improves the computational time compared with recognized methods. Convergence analysis of the new optimal control algorithm is provided for an arbitrary choice of partition. Numerical experiments are presented to illustrate the efficiency and the rapid convergence of the method.     

广义几何规划的全局优化算法

对许多工程设计中常用的广义几何规划问题(GGP)提出一种确定性全局优化算法,该算法利用目标和约束函数的线性下界估计,建立GGP的松弛线性规划(RLP),从而将原来非凸问题(GGP)的求解过程转化为求解一系列线性规划问题(RLP).通过可行域的连续细分以及一系列线性规划的解,提出的分枝定界算法收敛到GGP的全局最优解,且数值例子表明了算法的可行性.     

A note on the minimum bounded edge-partition of a tree

Minimum bounded edge-partition divides the edge set of a tree into the minimum number of disjoint connected components given a maximum weight for any component. It is an adaptation of the uniform edge-partition of a tree. An optimization algorithm is developed for this NP-hard problem, based on repeated bin packing of inter-related instances. The algorithm has linear running time for the class of ‘balanced trees’ common for the stochastic programming application which motivated investigation of this problem.Fast 2-approximation algorithms are formed for general instances by replacing the optimal bin packing with almost any bin packing heuristic. The asymptotic worst-case ratio of these approximation algorithms is never better than the absolute worst-case ratio of the bin packing heuristic used.     

Tightening a copositive relaxation for standard quadratic optimization problems

We focus in this paper the problem of improving the semidefinite programming (SDP) relaxations for the standard quadratic optimization problem (standard QP in short) that concerns with minimizing a quadratic form over a simplex. We first analyze the duality gap between the standard QP and one of its SDP relaxations known as “strengthened Shor’s relaxation”. To estimate the duality gap, we utilize the duality information of the SDP relaxation to construct a graph G ^?. The estimation can be then reduced to a two-phase problem of enumerating first all the minimal vertex covers of G ^? and solving next a family of second-order cone programming problems. When there is a nonzero duality gap, this duality gap estimation can lead to a strictly tighter lower bound than the strengthened Shor’s SDP bound. With the duality gap estimation improving scheme, we develop further a heuristic algorithm for obtaining a good approximate solution for standard QP.