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     

An approximation algorithm for convex multi-objective programming problems

In multi-objective convex optimization it is necessary to compute an infinite set of nondominated points. We propose a method for approximating the nondominated set of a multi-objective nonlinear programming problem, where the objective functions and the feasible set are convex. This method is an extension of Benson’s outer approximation algorithm for multi-objective linear programming problems. We prove that this method provides a set of weakly ε-nondominated points. For the case that the objectives and constraints are differentiable, we describe an efficient way to carry out the main step of the algorithm, the construction of a hyperplane separating an exterior point from the feasible set in objective space. We provide examples that show that this cannot always be done in the same way in the case of non-differentiable objectives or constraints.     

Utility Function Programs and Optimization over the Efficient Set in Multiple-Objective Decision Making

Natural basic concepts in multiple-objective optimization lead to difficult multiextremal global optimization problems. Examples include detection of efficient points when nonconvexities occur, and optimization of a linear function over the efficient set in the convex (even linear) case. Assuming that a utility function exists allows one to replace in general the multiple-objective program by a single, nonconvex optimization problem, which amounts to a minimization over the efficient set when the utility function is increasing. A new algorithm is discussed for this utility function program which, under natural mild conditions, converges to an -approximate global solution in a finite number of iterations. Applications include linear, convex, indefinite quadratic, Lipschitz, and d.c. objectives and constraints.     

On Extensions of the Frank-Wolfe Theorems

In this paper we consider optimization problems defined by a quadratic objective function and a finite number of quadratic inequality constraints. Given that the objective function is bounded over the feasible set, we present a comprehensive study of the conditions under which the optimal solution set is nonempty, thus extending the so-called Frank-Wolfe theorem. In particular, we first prove a general continuity result for the solution set defined by a system of convex quadratic inequalities. This result implies immediately that the optimal solution set of the aforementioned problem is nonempty when all the quadratic functions involved are convex. In the absence of the convexity of the objective function, we give examples showing that the optimal solution set may be empty either when there are two or more convex quadratic constraints, or when the Hessian of the objective function has two or more negative eigenvalues. In the case when there exists only one convex quadratic inequality constraint (together with other linear constraints), or when the constraint functions are all convex quadratic and the objective function is quasi-convex (thus allowing one negative eigenvalue in its Hessian matrix), we prove that the optimal solution set is nonempty.     

A numerically stable least squares solution to the quadratic programming problem

The strictly convex quadratic programming problem is transformed to the least distance problem — finding the solution of minimum norm to the system of linear inequalities. This problem is equivalent to the linear least squares problem on the positive orthant. It is solved using orthogonal transformations, which are memorized as products. Like in the revised simplex method, an auxiliary matrix is used for computations. Compared to the modified-simplex type methods, the presented dual algorithm QPLS requires less storage and solves ill-conditioned problems more precisely. The algorithm is illustrated by some difficult problems.      

Initialization in semidefinite programming via a self-dual skew-symmetric embedding

The formulation of interior point algorithms for semidefinite programming has become an active research area, following the success of the methods for large-scale linear programming. Many interior point methods for linear programming have now been extended to the more general semidefinite case, but the initialization problem remained unsolved.In this paper we show that the initialization strategy of embedding the problem in a self-dual skew-symmetric problem can also be extended to the semidefinite case. This method also provides a solution for the initialization of quadratic programs and it is applicable to more general convex problems with conic formulation.     

A Computational Study of the Homogeneous Algorithm for Large-scale Convex Optimization

Recently the authors have proposed a homogeneous and self-dual algorithm for solving the monotone complementarity problem (MCP) [5]. The algorithm is a single phase interior-point type method; nevertheless, it yields either an approximate optimal solution or detects a possible infeasibility of the problem. In this paper we specialize the algorithm to the solution of general smooth convex optimization problems, which also possess nonlinear inequality constraints and free variables. We discuss an implementation of the algorithm for large-scale sparse convex optimization. Moreover, we present computational results for solving quadratically constrained quadratic programming and geometric programming problems, where some of the problems contain more than 100,000 constraints and variables. The results indicate that the proposed algorithm is also practically efficient.     

Branch-and-Bound Outer Approximation Algorithm for Sum-of-Ratios Fractional Programs

In this article, a branch and-bound outer approximation algorithm is presented for globally solving a sum-of-ratios fractional programming problem. To solve this problem, the algorithm instead solves an equivalent problem that involves minimizing an indefinite quadratic function over a nonempty, compact convex set. This problem is globally solved by a branch-and-bound outer approximation approach that can create several closed-form linear inequality cuts per iteration. In contrast to pure outer approximation techniques, the algorithm does not require computing the new vertices that are created as these cuts are added. Computationally, the main work of the algorithm involves solving a sequence of convex programming problems whose feasible regions are identical to one another except for certain linear constraints. As a result, to solve these problems, an optimal solution to one problem can potentially be used to good effect as a starting solution for the next problem.     

A feasible direction algorithm for convex optimization: Global convergence rates

At each iteration, the algorithm determines a feasible descent direction by minimizing a linear or quadratic approximation to the cost on the feasible set. The algorithm is easy to implement if the approximation is easy to minimize on the feasible set, which happens in some important cases. Convergence rate information is obtained, which is sufficient to enable deduction of the number of iterations needed to achieve a specified reduction in the distance from the optimum (measured in terms of the cost). Existing convergence rates for algorithms for solving such convex problems are either asymptotic (and so do not enable the required number of iterations to be deduced) or decrease as the number of constraints increases. The convergence rate information obtained here, however, is independent of the number of constraints. For the case where the quadratic approximation to the cost is not strictly convex (which includes the linear approximation case), the diameter is the only property of the feasible set which affects the convergence rate information. If the quadratic approximation is strictly convex, the convergence rate is independent of the size and geometry of the feasible set. An application to a control-constrained optimal control problem is outlined.     

Preconditioning by Projectors in the Solution of Contact Problems: A Parallel Implementation

A non-overlapping domain decomposition algorithm of the Neumann–Neumann type for solving contact problems of elasticity is presented. Using the duality theory of convex programming, the discretized problem turns into a quadratic one with equality and bound constraints. The dual problem is modified by orthogonal projectors to the natural coarse space. The resulting problem is solved by an augmented Lagrangian algorithm. The projectors ensure an optimal convergence rate for the solution of the auxiliary linear problems by the preconditioned conjugate gradient method. Relevant aspects on the numerical linear algebra of these problems are presented, together with an efficient parallel implementation of the method.     

A parametric successive underestimation method for convex multiplicative programming problems

This paper addresses itself to the algorithm for minimizing the product of two nonnegative convex functions over a convex set. It is shown that the global minimum of this nonconvex problem can be obtained by solving a sequence of convex programming problems. The basic idea of this algorithm is to embed the original problem into a problem in a higher dimensional space and to apply a branch-and-bound algorithm using an underestimating function. Computational results indicate that our algorithm is efficient when the objective function is the product of a linear and a quadratic functions and the constraints are linear. An extension of our algorithm for minimizing the sum of a convex function and a product of two convex functions is also discussed.     

Coradiant sets and $$\varepsilon $$-efficiency in multiobjective optimization

In multi-parametric programming an optimization problem is solved as a function of certain parameters, where the parameters are commonly considered to be bounded and continuous. In this paper, we use the case of strictly convex multi-parametric quadratic programming (mp-QP) problems with affine constraints to investigate problems where these conditions are not met. Based on the combinatorial solution approach for mp-QP problems featuring bounded and continuous parameters, we show that (i) for unbounded parameters, it is possible to obtain the multi-parametric solution if there exists one realization of the parameters for which the optimization problem can be solved and (ii) for binary parameters, we present the equivalent mixed-integer formulations for the application of the combinatorial algorithm. These advances are combined into a new, generalized version of the combinatorial algorithm for mp-QP problems, which enables the solution of problems featuring both unbounded and binary parameters. This novel approach is applied to mixed-integer bilevel optimization problems and the parametric solution of the dual of a convex problem.     

Quadratic factorization heuristics for copositive programming

Copositive optimization problems are particular conic programs: optimize linear forms over the copositive cone subject to linear constraints. Every quadratic program with linear constraints can be formulated as a copositive program, even if some of the variables are binary. So this is an NP-hard problem class. While most methods try to approximate the copositive cone from within, we propose a method which approximates this cone from outside. This is achieved by passing to the dual problem, where the feasible set is an affine subspace intersected with the cone of completely positive matrices, and this cone is approximated from within. We consider feasible descent directions in the completely positive cone, and regularized strictly convex subproblems. In essence, we replace the intractable completely positive cone with a nonnegative cone, at the cost of a series of nonconvex quadratic subproblems. Proper adjustment of the regularization parameter results in short steps for the nonconvex quadratic programs. This suggests to approximate their solution by standard linearization techniques. Preliminary numerical results on three different classes of test problems are quite promising.     

An outcome space approach for generalized convex multiplicative programs

This paper addresses the problem of minimizing an arbitrary finite sum of products of two convex functions over a convex set. Nonconvex problems in this form constitute a class of generalized convex multiplicative problems. Convex analysis results allow to reformulate the problem as an indefinite quadratic problem with infinitely many linear constraints. Special properties of the quadratic problem combined with an adequate outer approximation procedure for handling its semi-infinite constrained set enable an efficient constraint enumeration global optimization algorithm for generalized convex multiplicative programs. Computational experiences illustrate the proposed approach.     

A neural network for solving a convex quadratic bilevel programming problem

A neural network is proposed for solving a convex quadratic bilevel programming problem. Based on Lyapunov and LaSalle theories, we prove strictly an important theoretical result that, for an arbitrary initial point, the trajectory of the proposed network does converge to the equilibrium, which corresponds to the optimal solution of a convex quadratic bilevel programming problem. Numerical simulation results show that the proposed neural network is feasible and efficient for a convex quadratic bilevel programming problem.     

The extended supporting hyperplane algorithm for convex mixed-integer nonlinear programming

A new deterministic algorithm for solving convex mixed-integer nonlinear programming (MINLP) problems is presented in this paper: The extended supporting hyperplane (ESH) algorithm uses supporting hyperplanes to generate a tight overestimated polyhedral set of the feasible set defined by linear and nonlinear constraints. A sequence of linear or quadratic integer-relaxed subproblems are first solved to rapidly generate a tight linear relaxation of the original MINLP problem. After an initial overestimated set has been obtained the algorithm solves a sequence of mixed-integer linear programming or mixed-integer quadratic programming subproblems and refines the overestimated set by generating more supporting hyperplanes in each iteration. Compared to the extended cutting plane algorithm ESH generates a tighter overestimated set and unlike outer approximation the generation point for the supporting hyperplanes is found by a simple line search procedure. In this paper it is proven that the ESH algorithm converges to a global optimum for convex MINLP problems. The ESH algorithm is implemented as the supporting hyperplane optimization toolkit (SHOT) solver, and an extensive numerical comparison of its performance against other state-of-the-art MINLP solvers is presented.     

单输入多时滞离散系统的线性二次调节问题

研究了单输入多时滞的离散时间系统的线性二次调节问题(LQR问题),给出了求解最优控制输入序列的一种简单有效而又新颖的方法.将该动态的离散时滞系统的LQR最优控制问题最终转化成了一个静态的、不带时滞的数学规划模型——带等式线性约束的严格凸二次规划问题,并利用两种方法解这个二次规划问题,均成功地导出了系统的最优控制输入序列.仿真结果验证了我们的方法的正确有效性.     

Integer Programming Duality in Multiple Objective Programming

The weighted sums approach for linear and convex multiple criteria optimization is well studied. The weights determine a linear function of the criteria approximating a decision makers overall utility. Any efficient solution may be found in this way. This is not the case for multiple criteria integer programming. However, in this case one may apply the more general e-constraint approach, resulting in particular single-criteria integer programming problems to generate efficient solutions. We show how this approach implies a more general, composite utility function of the criteria yielding a unified treatment of multiple criteria optimization with and without integrality constraints. Moreover, any efficient solution can be found using appropriate composite functions. The functions may be generated by the classical solution methods such as cutting plane and branch and bound algorithms.     

Primal and dual algorithms for optimization over the efficient set

ABSTRACT

Optimization over the efficient set of a multi-objective optimization problem is a mathematical model for the problem of selecting a most preferred solution that arises in multiple criteria decision-making to account for trade-offs between objectives within the set of efficient solutions. In this paper, we consider a particular case of this problem, namely that of optimizing a linear function over the image of the efficient set in objective space of a convex multi-objective optimization problem. We present both primal and dual algorithms for this task. The algorithms are based on recent algorithms for solving convex multi-objective optimization problems in objective space with suitable modifications to exploit specific properties of the problem of optimization over the efficient set. We first present the algorithms for the case that the underlying problem is a multi-objective linear programme. We then extend them to be able to solve problems with an underlying convex multi-objective optimization problem. We compare the new algorithms with several state of the art algorithms from the literature on a set of randomly generated instances to demonstrate that they are considerably faster than the competitors.     

On the sample monotonization problem

The problem of finding a maximal subsample in a training sample consisting of the pairs “object-answer” that does not violate monotonicity constraints is considered. It is proved that this problem is NP-hard and that it is equivalent to the problem of finding a maximum independent set in special directed graphs. Practically important cases in which a partial order specified on the set of answers is a complete order or has dimension two are considered in detail. It is shown that the second case is reduced to the maximization of a quadratic convex function on a convex set. For this case, an approximate polynomial algorithm based on linear programming theory is proposed.