In this paper we propose a long-step logarithmic barrier function method for convex quadratic programming with linear equality constraints. After a reduction of the barrier parameter, a series of long steps along proj...
详细信息
In this paper we propose a long-step logarithmic barrier function method for convex quadratic programming with linear equality constraints. After a reduction of the barrier parameter, a series of long steps along projected Newton directions are taken until the iterate is in the vicinity of the center associated with the current value of the barrier parameter. We prove that the total number of iterations is O(square-root nL) or O(nL), depending on how the barrier parameter is updated.
In this paper, we study a gradient-based neural network method for solving strictly convex quadratic programming (SCQP) problems. By converting the SCQP problem into a system of ordinary differential equation (ODE), w...
详细信息
In this paper, we study a gradient-based neural network method for solving strictly convex quadratic programming (SCQP) problems. By converting the SCQP problem into a system of ordinary differential equation (ODE), we are able to show that the solution trajectory of this ODE tends to the set of stationary points of the original optimization problem. It is shown that the proposed neural network is stable in the sense of Lyapunov and can converge to an exact optimal solution of the original problem. It is also found that a larger scaling factor leads to a better convergence rate of the trajectory. The simulation results also show that the proposed neural network is feasible and efficient. The simulation results are very attractive.
This article presents a polynomial predictor-corrector interior-point algorithm for convex quadratic programming based on a modified predictor-corrector interior-point algorithm. In this algorithm, there is only one c...
详细信息
This article presents a polynomial predictor-corrector interior-point algorithm for convex quadratic programming based on a modified predictor-corrector interior-point algorithm. In this algorithm, there is only one corrector step after each predictor step, where Step 2 is a predictor step and Step 4 is a corrector step in the algorithm. In the algorithm, the predictor step decreases the dual gap as much as possible in a wider neighborhood of the central path and the corrector step draws iteration points back to a narrower neighborhood and make a reduction for the dual gap. It is shown that the algorithm has O（√nL） iteration complexity which is the best result for convex quadratic programming so far.
Computational methods are proposed for solving a convexquadratic program (QP). Active-set methods are defined for a particular primal and dual formulation of a QP with general equality constraints and simple lower bo...
详细信息
Computational methods are proposed for solving a convexquadratic program (QP). Active-set methods are defined for a particular primal and dual formulation of a QP with general equality constraints and simple lower bounds on the variables. In the first part of the paper, two methods are proposed, one primal and one dual. These methods generate a sequence of iterates that are feasible with respect to the equality constraints associated with the optimality conditions of the primal-dual form. The primal method maintains feasibility of the primal inequalities while driving the infeasibilities of the dual inequalities to zero. The dual method maintains feasibility of the dual inequalities while moving to satisfy the primal inequalities. In each of these methods, the search directions satisfy a KKT system of equations formed from Hessian and constraint components associated with an appropriate column basis. The composition of the basis is specified by an active-set strategy that guarantees the nonsingularity of each set of KKT equations. Each of the proposed methods is a conventional active-set method in the sense that an initial primal- or dual-feasible point is required. In the second part of the paper, it is shown how the quadratic program may be solved as a coupled pair of primal and dual quadratic programs created from the original by simultaneously shifting the simple-bound constraints and adding a penalty term to the objective function. Any conventional column basis may be made optimal for such a primal-dual pair of shifted-penalized problems. The shifts are then updated using the solution of either the primal or the dual shifted problem. An obvious application of this approach is to solve a shifted dual QP to define an initial feasible point for the primal (or vice versa). The computational performance of each of the proposed methods is evaluated on a set of convex problems from the CUTEst test collection.
In this paper we develop a long-step primal-dual infeasible path-following algorithm for convex quadratic programming (CQP) whose search directions are computed by means of a preconditioned iterative linear solver. We...
详细信息
In this paper we develop a long-step primal-dual infeasible path-following algorithm for convex quadratic programming (CQP) whose search directions are computed by means of a preconditioned iterative linear solver. We propose a new linear system, which we refer to as the augmented normal equation (ANE), to determine the primal-dual search directions. Since the condition number of the ANE coefficient matrix may become large for degenerate CQP problems, we use a maximum weight basis preconditioner introduced in [ A. R. L. Oliveira and D. C. Sorensen, Linear Algebra Appl., 394 ( 2005), pp. 1 - 24;M. G. C. Resende and G. Veiga, SIAM J. Optim., 3 ( 1993), pp. 516 - 537;P. Vaida, Solving Linear Equations with Symmetric Diagonally Dominant Matrices by Constructing Good Preconditioners, Tech. report, Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL, 1990] to precondition this matrix. Using a result obtained in [ R. D. C. Monteiro, J. W. O'Neal, and T. Tsuchiya, SIAM J. Optim., 15 ( 2004), pp. 96 - 100], we establish a uniform bound, depending only on the CQP data, for the number of iterations needed by the iterative linear solver to obtain a sufficiently accurate solution to the ANE. Since the iterative linear solver can generate only an approximate solution to the ANE, this solution does not yield a primal-dual search direction satisfying all equations of the primal-dual Newton system. We propose a way to compute an inexact primal-dual search direction so that the equation corresponding to the primal residual is satisfied exactly, while the one corresponding to the dual residual contains a manageable error which allows us to establish a polynomial bound on the number of iterations of our method.
Recently, with the advent of powerful optimisation algorithms for Markov random fields (MRFs), priors of high arity (more than two) have been put into practice more widely. The statistical relationship between object ...
详细信息
Recently, with the advent of powerful optimisation algorithms for Markov random fields (MRFs), priors of high arity (more than two) have been put into practice more widely. The statistical relationship between object parts encoding shape in a covariant space, also known as the point distribution model (PDM), is a widely employed technique in computer vision which has been largely overlooked in the context of higher-order MRF models. This paper focuses on such higher-order statistical shape priors and illustrates that in a spatial transformation invariant space, these models can be formulated as convexquadratic programmes. As such, the associated energy of a PDM may be optimised efficiently using a variety of different dedicated algorithms. Moreover, it is shown that such an approach in the context of graph matching can be utilised to incorporate both a global rigid and a non-rigid deformation prior into the problem in a parametric form, a problem which has been rarely addressed in the literature. The paper then illustrates an application of PDM priors for different tasks using graphical models incorporating factors of different cardinalities.
This paper addresses the problem of computing the minimal and the maximal optimal value of a convex quadratic programming (CQP) problem when the coefficients are subject to perturbations in given intervals. Contrary t...
详细信息
This paper addresses the problem of computing the minimal and the maximal optimal value of a convex quadratic programming (CQP) problem when the coefficients are subject to perturbations in given intervals. Contrary to the previous results concerning on some special forms of CQP only, we present a unified method to deal with interval CQP problems. The problem can be formulated by using equation, inequalities or both, and by using sign-restricted variables or sign-unrestricted variables or both. We propose simple formulas for calculating the minimal and maximal optimal values. Due to NP-hardness of the problem, the formulas are exponential with respect to some characteristics. On the other hand, there are large sub-classes of problems that are polynomially solvable. For the general intractable case we propose an approximation algorithm. We illustrate our approach by a geometric problem of determining the distance of uncertain polytopes. Eventually, we extend our results to quadratically constrained CQP, and state some open problems.
A constraint-reduced Mehrotra-predictor-corrector algorithm for convex quadratic programming is proposed. (At each iteration, such algorithms use only a subset of the inequality constraints in constructing the search ...
详细信息
A constraint-reduced Mehrotra-predictor-corrector algorithm for convex quadratic programming is proposed. (At each iteration, such algorithms use only a subset of the inequality constraints in constructing the search direction, resulting in CPU savings.) The proposed algorithm makes use of a regularization scheme to cater to cases where the reduced constraint matrix is rank deficient. Global and local convergence properties are established under arbitrary working-set selection rules subject to satisfaction of a general condition. A modified active-set identification scheme that fulfills this condition is introduced. Numerical tests show great promise for the proposed algorithm, in particular for its active-set identification scheme. While the focus of the present paper is on dense systems, application of the main ideas to large sparse systems is briefly discussed.
This paper proposes a neural network model for solving convex quadratic programming (CQP) problems, whose equilibrium points coincide with Karush-Kuhn-Tucker (KKT) points of the CQP problem. Using the equality transfo...
详细信息
This paper proposes a neural network model for solving convex quadratic programming (CQP) problems, whose equilibrium points coincide with Karush-Kuhn-Tucker (KKT) points of the CQP problem. Using the equality transformation and Fischer-Burmeister (FB) function, we construct the neural network model and present the KKT condition for the CQP problem. In contrast to two existing neural networks for solving such problems, the proposed neural network has fewer variables and neurons, which makes circuit realization easier. Moreover, the proposed neural network is asymptotically stable in the sense of Lyapunov such that it converges to an exact optimal solution of the CQP problem. Simulation results are provided to show the feasibility and efficiency of the proposed network. (C) 2016 Elsevier B.V. All rights reserved.
Recently an infeasible interior-point algorithm for linear programming (LP) was presented by Liu and Sun. By using similar predictor steps, we give a (feasible) predictor-corrector algorithm for convexquadratic progr...
详细信息
Recently an infeasible interior-point algorithm for linear programming (LP) was presented by Liu and Sun. By using similar predictor steps, we give a (feasible) predictor-corrector algorithm for convex quadratic programming (QP). We introduce a (scaled) proximity measure and a dynamical forcing factor (centering parameter). The latter is used to force the duality gap to decrease. The algorithm can decrease the duality gap monotonically. Polynomial complexity can be proved and the result coincides with the best one for LP, namely, .
暂无评论