XVI.2. Software requirements

XVI.2.1 Introduction

Real time optimization has higher requirements for optimization formulation and implementation. Since multi-objective optimization plays an important role in the posture and motion prediction of virtual soldiers, research is needed for good formulation and implementation of optimization algorithms. In this chapter, some requirements for real time optimization and optimization codes are discussed. This provides a guideline for the choice and testing of NLP codes in the next chapter.

XVI.2.2 Requirements for Real Time Optimization

Following are some major characteristics of the real-time optimization in the VSR project: 

1.   It must be efficient and fast. In order to meet the requirements for real-time on-line applications, the optimization algorithms must be efficient, especially for large problems. When alternate formulations are considered, sparse capacity and treatment of large number of equality constraints become important.

2.   It must be robust. In a software environment, an optimization package needs to be able to solve most, if not all of the problems. Therefore, in stead of solving special problems, the algorithm used in the optimization codes should be robust to solve very general problems.

3.   It needs good formulations. Alternate formulations, which are explicit in terms of optimization variables, may in general reduce the computational efforts and enhance the accuracy of the results. Finite difference approximations are not affordable for large-scale applications, in terms of computational efforts and efficiency.

4.   It should have features to solve large-scale problems. When the full human model is considered and dynamics is included in the formulation, the optimization problem itself will become very large. Sparsity is also very important, because the problem is in fact sparse.

Other concerns are also needed when a particular optimization package is considered. For example, in the VSR optimization problems, it is hard to obtain second order derivative information. Therefore, optimization packages that require second order derivative information are not preferred in the project.

XVI.2.3 Discussion

The general requirements for real time optimization discussed in Section (2.2) will be used as a general guideline for the choice and numerical test of NLP codes in later chapters.

XVI.3. AVAILABLE GRADIENT BASED optimization ENgines

XVI.3.1  Introduction

In this chapter, some available large-scale NLP codes are reviewed and compared. Some of these codes will be tested for the VSR project in the next chapter.

XVI.3.2  List of Software and Comparison

Real-time full-size virtual soldier optimization features large-scale optimization with a large number of variables and constraints. Besides this sparse matrices capacity and efficient treatment of large number of equality constraints become important criteria to choose optimization codes. The following is a list of currently available codes for large-scale optimization: BIGDOT (Vanderplaats 2000), IPOPT, LOQO (Vanderbei 2000), KNITRO (Byrd et al. 1997), MINOS (Murtagh and Saunders 1983), SNOPT (Gill et al. 2002), LANCELOT (Conn et al. 1992), CONOPT (Drud 1992), NLPSPR, SPRNLP in SOCS (Betts and Frank 1994), BARNLP in SOCS (Betts and Frank 1994), PENNON (Kocvara and Stingl 2003).

Table 3.1 A list of available large-scale NLP codes 

XVI.3.3.  Summary

Certainly these codes use different optimization algorithms. MINOS uses a reduced-gradient method or a projected Lagrangian method and is most efficient for linear programming (LP) or linear-constrained NLP problems. Numerical tests have shown that MINOS is not very efficient for large nonlinear problem. From the requirements of the project and experience of past research, sequential quadratic programming (SQP) and interior point method (IP) are finally determined to chosen as test methods. SNOPT (SQP), KNITRO (IP) are focused on to test large-scale numerical examples.

XVI.4. benchmark WITh Large-scale AnD sparse problem

XVI.4.1. Introduction

In this chapter, some optimization codes are tested with the VSR examples or large-scale sparse structural design problems. Results are compared and the performance of the codes is discussed. Recommendations are given.

XVI.4.2. VSR Examples

The key computational kernels of the SOCS library are the sparse nonlinear programming algorithms SPRNLP and BARNLP. For optimal control applications SPRNLP and BARNLP are fully integrated with the SOCS software and are transparent to the control practitioner. However, it is also possible to use SPRNLP and BARNLP independently for applications other than optimal control. The SPRNLP software implements a state-of-the-art sequential quadratic programming (SQP) method, using an augmented Lagrangian merit function and safeguarded line search. SPRNLP can accommodate nonlinear equality and inequality constraints, as well as simple bounds. The BARNLP software implements a sparse primal-dual interior point algorithm, in conjunction with a filter method for globalization. The outstanding performance of the software in benchmark tests has been documented. The package supports four different levels of functionality.

XVI.4.3.  Large-scale Structural Optimization Examples

In order to test the performance of the optimization codes for large-scale problems, several large truss structures have been optimized. This is done with three alternate formulations. A Dell PC with 512 Mb memory and windows 2000 loaded is used for running the programs. SNOPT and KNITRO are used to solve the problems.

SNOPT uses a sequential quadratic programming (SQP) algorithm that calculates the search directions by solving a quadratic programming (QP) subproblem. Each QP subproblem minimizes a quadratic model of the Lagrangian function subject to linearized constraints. An augmented Lagrangian merit function is reduced along the search direction to ensure convergence from any starting point. To treat problems where the number of nonlinear variables is very large, SNOPT uses a limited-memory procedure to update an initial Hessian approximation a limited number of times. The method of SNOPT exploits sparsity in the constraint Jacobian and maintains a limited-memory quasi-Newton approximation for the Hessian of the Lagrangian. The QP subproblems are solved using an reduced-Hessian active-set method that allows for variables appearing linearly in the objective and constraint functions. (The limited-memory Hessian is then semi-definite.)

KNITRO implements an interior point method for nonlinear programming. The nonlinear programming problem is replaced by a series of barrier sub-problems controlled by a barrier parameter. The algorithm uses trust regions and a merit function to promote convergence. Each step is a sum of two components: (i) a normal step whose objective is to improve feasibility; and (ii) a tangential step that aims toward optimality. The tangential step is computed using a projected conjugate gradient iteration. KNITRO does not compute each step by solving a linear algebraic system involving the KKT matrix. Instead, it factors (using MA27 subroutines) a projection matrix, and uses the conjugate gradient method to approximately minimize a quadratic model of the barrier problem. To further promote a fast solution, the linear algebra within KNITRO takes into account the possibly sparse structure of the problems to be solved. KNITRO is recommended for optimal control, parameter identification or economic optimization problems, all with or without constraints.

XVI.4.3.1  Examples

The two large-scale examples tested here are a 200-bar plane truss (Haug and Arora 1979) and a 35-story space truss tower consisting of 1262 elements and 324 nodes (Adeli and Cheng 1994).

XVI.4.3.2  Evaluation

Table 4.1 shows the comparison of sizes for four different formulations for the two design examples. The largest problem solved includes 8864 optimization variables and 18888 constraints. The alternate formulations involve a lot more variables and constraints than the conventional one, as one can expect. Table 4.2 lists the estimated numbers of non-zero elements that need to be stored in SNOPT. It is clear that the Jacobians of the constraint functions in the alternate formulations are quite sparse. The sparsity of matrices needs to be utilized to solve large-scale design problems efficiently. If the sparsity of matrices is not considered, it is quite probable that a normal PC does not have enough memory storage for the algorithm. It is interesting to note that the conventional formulation actually requires more storage as compared to the alternate formulations.

All the formulations worked well and converged to the same optimal solutions for the two design examples, as shown in Table 4.3. These solutions are obtained from SNOPT. Unfortunately, KNITRO is unable to get solutions for most of the problems in 2000 iterations. Table 4.4 lists all the numbers of iterations needed to solve the example problems. It can be seen that reasonable numbers of iterations are used by SNOPT. Therefore, for the design examples and formulations used here, KNITRO is not as efficient as SNOPT. SNOPT is finally recommended to the VSR project.

Table 4.1 Number of variables and behavior constraints for different formulations 

Table 4.2 Numbers of non-zero Jacobian elements for design examples