Reducing quadratic programming problem to regression problem: Stepwise algorithm

Quadratic programming is concerned with minimizing a convex quadratic function subject to linear inequality constraints. The variables are assumed to be nonnegative. The unique solution of quadratic programming (QP) problem (QPP) exists provided that a feasible region is non-empty (the QP has a feasible space).A method for searching for the solution to a QP is provided on the basis of statistical theory. It is shown that QPP can be reduced to an appropriately formulated least squares (LS) problem (LSP) with equality constraints and nonnegative variables. This approach allows us to obtain a simple algorithm to solve QPP. The applicability of the suggested method is illustrated with numerical examples.     

An Exterior Newton Method for Strictly Convex Quadratic Programming

We propose an exterior Newton method for strictly convex quadratic programming (QP) problems. This method is based on a dual formulation: a sequence of points is generated which monotonically decreases the dual objective function. We show that the generated sequence converges globally and quadratically to the solution (if the QP is feasible and certain nondegeneracy assumptions are satisfied). Measures for detecting infeasibility are provided. The major computation in each iteration is to solve a KKT-like system. Therefore, given an effective symmetric sparse linear solver, the proposed method is suitable for large sparse problems. Preliminary numerical results are reported.     

Warmstarting for interior point methods applied to the long-term power planning problem

The long-term planning of electricity generation in a liberalised market using the Bloom and Gallant model can be posed as a quadratic programming (QP) problem with an exponential number of linear inequality constraints called load-matching constraints (LMCs) and several other linear non-LMCs. Direct solution methods are inefficient at handling such problems and a heuristic procedure has been devised to generate only those LMCs that are likely to be active at the optimiser. The problem is then solved as a finite succession of QP problems with an increasing, though still limited, number of LMCs, which can be solved efficiently using a direct method, as would be the case with a QP interior-point algorithm. Warm starting between successive QP solutions helps then in reducing the number of iterations necessary to reach the optimiser.     

Robust memory state feedback model predictive control for discrete-time uncertain state delayed systems

In this paper, we propose a memory state feedback model predictive control (MPC) law for a discrete-time uncertain state delayed system with input constraints. The model uncertainty is assumed to be polytopic, and the delay is assumed to be unknown, but with a known upper bound. We derive a sufficient condition for cost monotonicity in terms of LMI, which can be easily solved by an efficient convex optimization algorithm. A delayed state dependent quadratic function with an estimated delay index is considered for incorporating MPC problem formulation. The MPC problem is formulated to minimize the upper bound of infinite horizon cost that satisfies the sufficient conditions. Therefore, a less conservative sufficient conditions in terms of linear matrix inequality (LMI) can be derived to design a more robust MPC algorithm. A numerical example is included to illustrate the effectiveness of the proposed method.     

Solving some optimal control problems using the barrier penalty function method

In this paper we present a new approach to solve a two-level optimization problem arising from an approximation by means of the finite element method of optimal control problems governed by unilateral boundary-value problems. The problem considered is to find a minimum of a functional with respect to the control variablesu. The minimized functional depends on control variables and state variablesx. The latter are the optimal solution of an auxiliary quadratic programming problem, whose parameters depend onu.Our main idea is to replace this QP problem by its dual and then apply the barrier penalty method to this dual QP problem or to the primal one if it is in an appropriate form. As a result we obtain a problem approximating the original one. Its good property is the differentiable dependence of state variables with respect to the control variables. Furthermore, we propose a method for finding an approximate solution of a penalized lower-level problem if the optimal solution of the original QP problem is known. We apply the result obtained to some optimal shape design problems governed by the Dirichlet-Signorini boundary-value problem.This research was supported by the Academy of Finland and the Systems Research Institute of the Polish Academy of Sciences.     

Global and Local Quadratic Minimization

We present a method which when applied to certain non-convex QP will locatethe globalminimum, all isolated local minima and some of the non-isolated localminima. The method proceeds by formulating a (multi) parametric convex QP interms ofthe data of the given non-convex QP. Based on the solution of the parametricQP,an unconstrained minimization problem is formulated. This problem ispiece-wisequadratic. A key result is that the isolated local minimizers (including theglobalminimizer) of the original non-convex problem are in one-to-one correspondencewiththose of the derived unconstrained problem.The theory is illustrated with several numerical examples. A numericalprocedure isdeveloped for a special class of non-convex QP's. It is applied to a problemfrom theliterature and verifies a known global optimum and in addition, locates apreviously unknown local minimum.     

The projection method of optimization applied to engineering plasticity problems

In engineering plasticity, the behavior of a structure (e.g., a frame or truss) under a variety of loading conditions is studied. Two primary types of analysis are generally conducted. Limit analysis determines the rigid plastic collapse load for a structure and can be formulated as a linear program (LP). Deformation analysis at plastic collapse can be formulated as a quadratic program (QP). The constraints of the two optimization problems are closely related. This paper presents a specialization of the projection method for linear programming for the limit-load analysis problem. The algorithm takes advantage of the relationship between the LP constraints and QP constraints to provide advantageous starting data for the projection method applied to the QP problem. An important feature of the method is that it avoids problems of apparent infeasibility due to roundoff errors. Experimental results are given for two medium-sized problems.This work was supported by the National Research Council of Canada under Research Grant No. A8189.     

LMI Approach to Robust Model Predictive Control

This paper introduces a new approach to robust model predictive control (MPC) based on conservative approximations to semi-infinite optimization using linear matrix inequalities (LMIs). The method applies to problems with convex quadratic costs, linear and convex quadratic constraints, and linear predictive models with bounded uncertainty. If the MPC optimization problem is feasible at the initial control step (the first application of the MPC optimization), it is shown that the MPC optimization problems will be feasible at all future time steps and that the controlled system will be closed-loop stable. The method is illustrated with a solenoid control example. The authors thank the anonymous reviewers for suggestions that improved the presentation of this work. The work was supported in part by the EPRI/DoD Complex Interactive Networks/Systems Initiative under Contract EPRI-W08333-05 and by the US Army Research Office Contract DAAD19-01-1-0485.     

Globally solving nonconvex quadratic programming problems via completely positive programming

Nonconvex quadratic programming (QP) is an NP-hard problem that optimizes a general quadratic function over linear constraints. This paper introduces a new global optimization algorithm for this problem, which combines two ideas from the literature—finite branching based on the first-order KKT conditions and polyhedral-semidefinite relaxations of completely positive (or copositive) programs. Through a series of computational experiments comparing the new algorithm with existing codes on a diverse set of test instances, we demonstrate that the new algorithm is an attractive method for globally solving nonconvex QP.     

Model predictive control for switched systems with a novel mixed time/event-triggering mechanism

This paper investigates observer-based model predictive control (MPC) for switched systems with a mixed time/event-triggering mechanism. The problem of predictive control that can achieve receding horizon optimization is considered and solved by minimizing an upper bound of the quadratic cost function. Since the system state may not be fully measured in practice, state observers are employed to estimate. A mixed mechanism including adaptive event-triggering and time-triggering is proposed, which can be switched determined by a threshold describing system performance to better balance system resource utilization and performance requirements. Then, a closed-loop switched system subject to networked-time-delay is modeled. Piecewise Lyapunov function technique and average dwell time approach are utilized to ensure asymptotical stability. Afterwards, MPC controller construction problem is turned into a LMIs feasibility problem. A new solving method of sufficient conditions for co-design of the state observers, feedback controllers and mixed triggering mechanism is derived. Lastly, simulation examples illustrate the correctness and advantages of research content.     

解带有二次约束二次规划的一个整体优化方法

在本文中，我们提出了一种解带有二次约束二次规划问题（QP）的新算法，这种方法是基于单纯形分枝定界技术，其中包括极小极大问题和线性规划问题作为子问题，利用拉格朗日松弛和投影次梯度方法来确定问题（QP）最优值的下界，在问题（QP）的可行域是n维的条件下，如果这个算法有限步后终止，得到的点必是问题（QP）的整体最优解；否则，该算法产生的点的序列{v^k}的每一个聚点也必是问题（QP）的整体最优解。     

A splitting method for quadratic programming problem

1. IntroductionThe quadratic programming (QP) problem is the most simple one in nonlinear pro-gramming and plays a very important role in optimization theory and applications.It is well known that matriX splitting teChniques are widely used for solving large-scalelinear system of equations very successfully. These algorithms generate an infinite sequence,in contrast to the direct algorithms which terminate in a finite number of steps. However,iterative algorithms are considerable simpler tha…     

An SR1/BFGS SQP algorithm for nonconvex nonlinear programs with block-diagonal Hessian matrix

We present a quasi-Newton sequential quadratic programming (SQP) algorithm for nonlinear programs in which the Hessian of the Lagrangian function is block-diagonal. Problems with this characteristic frequently arise in the context of optimal control; for example, when a direct multiple shooting parametrization is used. In this article, we describe an implementation of a filter line-search SQP method that computes search directions using an active-set quadratic programming (QP) solver. To take advantage of the block-diagonal structure of the Hessian matrix, each block is approximated separately by quasi-Newton updates. For nonconvex instances, that arise, for example, in optimum experimental design control problems, these blocks are often found to be indefinite. In that case, the block-BFGS quasi-Newton update can lead to poor convergence. The novel aspect in this work is the use of SR1 updates in place of BFGS approximations whenever possible. The resulting indefinite QPs necessitate an inertia control mechanism within the sparse Schur-complement factorization that is carried out by the active-set QP solver. This permits an adaptive selection of the Hessian approximation that guarantees sufficient progress towards a stationary point of the problem. Numerical results demonstrate that the proposed approach reduces the number of SQP iterations and CPU time required for the solution of a set of optimal control problems.     

Duality and solutions for quadratic programming over single non-homogeneous quadratic constraint

This paper extends and completes the discussion by Xing et?al. (Canonical dual solutions to the quadratic programming over a quadratic constraint, submitted) about the quadratic programming over one quadratic constraint (QP1QC). In particular, we relax the assumption to cover more general cases when the two matrices from the objective and the constraint functions can be simultaneously diagonalizable via congruence. Under such an assumption, the nonconvex (QP1QC) problem can be solved through a dual approach with no duality gap. This is unusual for general nonconvex programming but we can explain by showing that (QP1QC) is indeed equivalent to a linearly constrained convex problem, which happens to be dual of the dual of itself. Another type of hidden convexity can be also found in the boundarification technique developed in Xing et?al. (Canonical dual solutions to the quadratic programming over a quadratic constraint, submitted).     

A New Semidefinite Programming Bound for Indefinite Quadratic Forms Over a Simplex

The paper describes a method for computing a lower bound of the global minimum of an indefinite quadratic form over a simplex. The bound is derived by computing an underestimator of the convex envelope by solving a semidefinite program (SDP). This results in a convex quadratic program (QP). It is shown that the optimal value of the QP is a lower bound of the optimal value of the original problem. Since there exist fast (polynomial time) algorithms for solving SDP's and QP's the bound can be computed in reasonable time. Numerical experiments indicate that the relative error of the bound is about 10 percent for problems up to 20 variables, which is much better than a known SDP bound.     

Optimal Prioritized Infeasibility Handling in Model Predictive Control: Parametric Preemptive Multiobjective Linear Programming Approach

All practical implementations of model-based predictive control (MPC) require a means to recover from infeasibility. We propose a strategy designed for linear state-space MPC with prioritized constraints. It relaxes optimally an infeasible MPC optimization problem into a feasible one by solving a single-objective linear program (LP) online in addition to the standard online MPC optimization problem at each sample. By optimal, it is meant that the violation of a lower prioritized constraint cannot be made less without increasing the violation of a higher prioritized constraint. The problem of computing optimal constraint violations is naturally formulated as a parametric preemptive multiobjective LP. By extending well-known results from parametric LP, the preemptive multiobjective LP is reformulated into an equivalent standard single-objective LP. An efficient algorithm for offline design of this LP is given, and the algorithm is illustrated on an example.     

A coordinate gradient descent method for linearly constrained smooth optimization and support vector machines training

Support vector machines (SVMs) training may be posed as a large quadratic program (QP) with bound constraints and a single linear equality constraint. We propose a (block) coordinate gradient descent method for solving this problem and, more generally, linearly constrained smooth optimization. Our method is closely related to decomposition methods currently popular for SVM training. We establish global convergence and, under a local error bound assumption (which is satisfied by the SVM QP), linear rate of convergence for our method when the coordinate block is chosen by a Gauss-Southwell-type rule to ensure sufficient descent. We show that, for the SVM QP with n variables, this rule can be implemented in O(n) operations using Rockafellar’s notion of conformal realization. Thus, for SVM training, our method requires only O(n) operations per iteration and, in contrast to existing decomposition methods, achieves linear convergence without additional assumptions. We report our numerical experience with the method on some large SVM QP arising from two-class data classification. Our experience suggests that the method can be efficient for SVM training with nonlinear kernel.     

Identifying the optimal partition in convex quadratic programming

Given an optimal solution for a convex quadratic programming (QP) problem, the optimal partition of the QP can be computed by solving a pair of linear or QP problems for which nearly optimal solutions are known.     

A kind of nonmonotone filter method for nonlinear complementarity problem

The nonlinear complementarity problem can be reformulated as a nonlinear programming. For solving nonlinear programming, sequential quadratic programming (SQP) type method is very effective. But the QP subproblem may be inconsistent. In this paper, we propose a kind nonmonotone filter method in which the QP subproblem is consistent. By means of nonmonotone filter, this method has no demand on the penalty parameter which is difficult to obtain. Moreover, the restoration phase is not needed any more. Under reasonable conditions, we obtain the global convergence of the algorithm. Some numerical results are presented.     

A Perturbation approach for an inverse quadratic programming problem

We consider an inverse quadratic programming (QP) problem in which the parameters in both the objective function and the constraint set of a given QP problem need to be adjusted as little as possible so that a known feasible solution becomes the optimal one. We formulate this problem as a linear complementarity constrained minimization problem with a positive semidefinite cone constraint. With the help of duality theory, we reformulate this problem as a linear complementarity constrained semismoothly differentiable (SC¹) optimization problem with fewer variables than the original one. We propose a perturbation approach to solve the reformulated problem and demonstrate its global convergence. An inexact Newton method is constructed to solve the perturbed problem and its global convergence and local quadratic convergence rate are shown. As the objective function of the problem is a SC¹ function involving the projection operator onto the cone of positively semi-definite symmetric matrices, the analysis requires an implicit function theorem for semismooth functions as well as properties of the projection operator in the symmetric-matrix space. Since an approximate proximal point is required in the inexact Newton method, we also give a Newton method to obtain it. Finally we report our numerical results showing that the proposed approach is quite effective.