Quadratic program

Keywords, protein folding, tertiary structure, potential energy surface, global optimization, empirical potential, residue potential, surface potential, parameter estimation, density estimation, cluster analysis, quadratic programming... 

Given the pair and surface potentials, the weights are then constructed by solving the convex bound constrained quadratic program... 

Successive Quadratic Programming (SQP) The above approach to finding the optimum is called a feasible path method, as it attempts at all times to remain feasible with respect to the equahty and inequahty constraints as it moves to the optimum. A quite different method exists called the Successive Quadratic Programming (SQP) method, which only requires one be feasible at the final solution. Tests that compare the GRG and SQP methods generaUy favor the SQP method so it has the reputation of being one of the best methods known for nonlinear optimization for the type of problems considered here. 

Reformulating the necessaiy conditions as a linear quadratic program has an interesting side effect. We can simply add linearizations of the inactive inequalities to the problem ana let the ac tive set be selected by the algorithm used to solve the linear quadratic program. 

This linear quadratic program will have a unique solution if B i) is kept positive definite. Efncient solution methods exist for solving it (Refs. 119 and 123). 

One important class of nonlinear programming techniques is called quadratic programming (QP), where the objective function is quadratic and the constraints are hnear. While the solution is iterative, it can be obtained qmckly as in linear programming. This is the basis for the newest type of constrained multivariable control algorithms called model predic tive control. The dominant method used in the refining industiy utilizes the solution of a QP and is called dynamic matrix con-... 

Another method for solving nonlinear programming problems is based on quadratic programming (QP)1. Quadratic programming is an optimization procedure that minimizes a quadratic objective function subject to linear inequality or equality (or both types) of constraints. For example, a quadratic function of two variables x and X2 would be of the general form ... 

As shown in Fig. 3-53, optimization problems that arise in chemical engineering can be classified in terms of continuous and discrete variables. For the former, nonlinear programming (NLP) problems form the most general case, and widely applied specializations include linear programming (LP) and quadratic programming (QP). An important distinction for NLP is whether the optimization problem is convex or nonconvex. The latter NLP problem may have multiple local optima, and an important question is whether a global solution is required for the NLP. Another important distinction is whether the problem is assumed to be differentiable or not. 

Convex Cases of NLP Problems Linear programs and quadratic programs are special cases of (3-85) that allow for more efficient solution, based on application of KKT conditions (3-88) through (3-91). Because these are convex problems, any locally optimal solution is a global solution. In particular, if the objective and constraint functions in (3-85) are linear, then the following linear program (LP)... 

Quadratic programs (QPs) represent a slight modification of (3-97) and can be stated as... 

Problem 4.1 is nonlinear if one or more of the functions/, gv...,gm are nonlinear. It is unconstrained if there are no constraint functions g, and no bounds on the jc,., and it is bound-constrained if only the xt are bounded. In linearly constrained problems all constraint functions g, are linear, and the objective/is nonlinear. There are special NLP algorithms and software for unconstrained and bound-constrained problems, and we describe these in Chapters 6 and 8. Methods and software for solving constrained NLPs use many ideas from the unconstrained case. Most modem software can handle nonlinear constraints, and is especially efficient on linearly constrained problems. A linearly constrained problem with a quadratic objective is called a quadratic program (QP). Special methods exist for solving QPs, and these iare often faster than general purpose optimization procedures. 

LP software includes two related but fundamentally different kinds of programs. The first is solver software, which takes data specifying an LP or MILP as input, solves it, and returns the results. Solver software may contain one or more algorithms (simplex and interior point LP solvers and branch-and-bound methods for MILPs, which call an LP solver many times). Some LP solvers also include facilities for solving some types of nonlinear problems, usually quadratic programming problems (quadratic objective function, linear constraints see Section 8.3), or separable nonlinear problems, in which the objective or some constraint functions are a sum of nonlinear functions, each of a single variable, such as... 

Note that there are n + m equations in the n + m unknowns x and A. In Section 8.6 we describe an important class of NLP algorithms called successive quadratic programming (SQP), which solve (8.17)—(8.18) by a variant of Newton s method. 

The vector x can contain slack variables, so the equality constraints (8.33) may contain some constraints that were originally inequalities but have been converted to equalities by inserting slacks. Codes for quadratic programming allow arbitrary upper and lower bounds on x we assume x>0 only for simplicity. 

Successive quadratic programming (SQP) methods solve a sequence of quadratic programming approximations to a nonlinear programming problem. Quadratic programs (QPs) have a quadratic objective function and linear constraints, and there exist efficient procedures for solving them see Section 8.3. As in SLP, the linear constraints are linearizations of the actual constraints about the selected point. The objective is a quadratic approximation to the Lagrangian function, and the algorithm is simply Newton s method applied to the KTC of the problem. 

For problems with only equality constraints, we could simply solve the linear equations (8.66)-(8.67) for (Ax, AX) and iterate. To accommodate both equalities and inequalities, an alternative viewpoint is useful. Consider the quadratic programming problem... 

Fan, Y. S. Sarkar and L. Lasdon. Experiments with Successive Quadratic Programming Algorithms. J Optim Theory Appli 56 (3), 359-383 (March 1988). 

Temet, D. J. and L. T. Biegler. Recent Improvements to a Multiplier-free Reduced Hessian Successive Quadratic Programming Algorithm. Comp Chem Engin 22 963 (1998). 

Vassiliadis, V. S. and S. A. Brooks. Application of the Modified Barrier Method in Large-Scale Quadratic Programming Problems. Comp Chem Engin 22 1197-1205 (1998). 

---