Interior point algorithms

MacDonald, W. B., A. N. Hrymak, and S. Treiber. Interior Point Algorithms for Refinery Scheduhng Problems in Froc. 4th Annual Symp. Frocess Systems Engineering (Aug. 5-9, 1991) HI.13.1-16. 

Sourander, M. L. M. Kolari J. C. Cugini J. B. Poje and D. C. White. Control and Optimization of Olefin-Cracking Heaters. Hydrocarbon Process, pp. 63-68 (June, 1984). Ye, Y. Interior Point Algorithms Theory and Analysis. Wiley, New York (1997). 

Interior Point algorithms (Luenberger and Ye, 2008 Martin, 1999 Vanderbei, 2007) were created to overcome this shortcoming of the Simplex method. 

The appearance of the first of Interior Point algorithms (Karmarkar, 1984) caused a kind of revolution in the field of applied mathematics since the Simplex method s long history had seemed exhaustive when it came to solving linear programming problems. 

Hence, the problem is reduced to the condition that a set of inn vector products will be positive. Standard linear programming tools can solve Eq. (12). We use the BPMPD program of C. S. Meszaros [49], which is based on the interior point algorithm. We seek a point in parameter space that satisfies the constraints, and we do not optimize a function in that space. In this case, the interior point algorithm places the solution at the maximally feasible point, which is at the center of the accessible volume of parameters [50]. 

An interior-point algorithm is one that improves a feasible interior solution point of the linear program by steps through the interior, rather tha one that improves by steps around the boundary of the feasible region, as the Simplex does (see Fig. A.2b). 

If the matrix Q is positive semidefinite (positive definite) when projected into the null space of the active constraints, then (3-98) is (strictly) convex and the QP is a global (and unique) minimum. Otherwise, local solutions exist for (3-98), and more extensive global optimization methods are needed to obtain the global solution. Like LPs, convex QPs can be solved in a finite number of steps. However, as seen in Fig. 3-57, these optimal solutions can lie on a vertex, on a constraint boundary, or in the interior. A number of active set strategies have been created that solve the KKT conditions of the QP and incorporate efficient updates of active constraints. Popular methods include null space algorithms, range space methods, and Schur complement methods. As with LPs, QP problems can also be solved with interior point methods [see Wright (1996)]. 

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... 

Considering such recent relevance of SDP in quantum chemistry, this chapter discusses some practical aspects of this variational calculation of the 2-RDM formulated as an SDP problem. We first present the definition of an SDP problem, and then the primal and dual SDP formulations of the variational calculation of the 2-RDM as SDP problems (Section II), an efficient algorithm to solve the SDP problems the primal-dual interior-point method (Section III), a brief section about alternative and also efficient augmented Lagrangian methods (Section IV), and some computational aspects when solving the SDP problems (Section V). 

Finally, the general algorithm framework of the infeasible primal-dual path-following Mehrotra-type predictor-corrector interior-point method is the following. 

Yu. Nesterov and A. Nemirovskii, Interior-Point Polynomial Algorithms in Convex Programming, SIAM, Philadelphia, 1993. 

For three dimensions, the AR construction algorithm is similar to the one described above—with the added possibility that we can find a (one-dimensional) connector on the AR that is described by a DSR. Glasser et al. (1992) defined conditions under which DSRs appear on the AR along with a direct method for finding the feed addition rate, q. While the conditions for DSRs appear to occur infrequently, examples have been constructed in the space of conversion, temperature, and residence time where the DSR was a prominent part of the AR. Nevertheless, Hildebrandt and co-workers conclude that most ARs will consist only of CSTR and PFR surfaces. In dealing with n-dimensional problems, Hildebrandt and Feinberg noted that the AR boundary is defined by line segments and PFR trajectories, with at most n structures needed to define a point on the AR boundary and n + 1 structures needed to define an interior point of the AR. Thus, for three-dimensional problems, at most three parallel structures (PFRs, CSTRs, DSRs) are needed to define any AR boundary point. 

The outer-approximation algorithm (Section II.A) took six iterations to identify this solution, with a projection factor, e, of. 05 on the disturbance amplitude. Both vertex and nonvertex constraint maximizers were identified, confirming the need to consider nonvertex maximizers. The variables that contributed nonvertex maximizers were the step switching times (several times) and the measurement lags (once). Robustness was verified with respect to all vertex combinations of uncertain values and a random selection of interior points (ivert = 1, nrand y = 1000). 

Wachter, A. Biegler, L.T. On the Implementation of a Primal-Dual Interior Point Filter Line Search Algorithm for Large-Scale Nonlinear Programming, Research Report IBM T, J. Watson Research Center Yorktown, 2004. 

Wachter, A. and Biegler, L. (2006). On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Mathematical Programming 106, pp. 25-57. 

When equality constraints are also present, some recent algorithms derived from interior point methods for linear programming use a barrier method that generates steps by solving the following minimization problem ... 

---