Non-Proprietary Optimization - Plan and Status

From ASCEND

Contents 1 Sponsorship 2 Abstract 3 Detailed plan 3.1 By mid-term review: 3.2 After mid-term review: 3.3 Optional/stretch target tasks: 4 Notes 5 Tools Used

Sponsorship

This project was funded through the Google Summer of Code (2009) program.

Abstract

ASCEND is a modeling environment with a number of integrated solvers, used to model complex engineering problems. Among others, it includes a wrapper for CONOPT - a commercial optimization tool. CONOPT a being commercial product cannot be packaged with ASCEND for free distribution and the lack of a free, good optimization tool limits the utility of ASCEND. This can be bettered by including a wrapper for IPOPT and adding support for Hessian Matrices followed by tight integration.

Detailed plan

By mid-term review:

• Identify current segfault cause in asc_ipopt.c and eliminate it
• complete the implementation of IPOPT solver-wrapper for ASCEND (solvers/ipopt/asc_ipopt.c)
  • Completion of ipopt_eval_jac_g
  • Completion of ipopt_eval_g
  • Completion of ipopt_eligible_solver (optional)
  • Inconsistency and Divergence in asc_ipopt.c
  • add missing configuration parameters
  • solved status for variables
• create test .a4c models for use with IPOPT (use verifiable problems of different sizes)
  • Problems picked from Hock-Schittkowsky test suite
• add execution of these models to test.py (for Unit testing/Regression Testing)
• implement reverse-automatic differentiation for first derivative calculations (Check implementation details on Reverse Automatic Differentiation Implementation)
• implement test suite for the reverse first derivative routines, including all the 'usual' algebraic operators etc (eg see ascend/compiler/test, CUnit)
• implement second-derivative routines for 'usual' non-linear algebraic relations
• implement test suite for the second derivative routines, including all the 'usual' algebraic operators etc (eg see ascend/compiler/test, CUnit)

After mid-term review:

• add support for external 'black box' relations in second derivative routines
• add routines to perform exact calculation of hessian matrix for use with IPOPT
• add test cases in test.py to demonstrate use of exact hessian in IPOPT solver

Optional/stretch target tasks:

• Detailed performance evaluation of exact/numerical hessian matrix calculation
• Benchmark performance of IPOPT versis CONOPT.
• Port exact hessian calculation back to the CONOPT solver and provide configuration setting to allow its use
• Completion of ipopt_resolve (optional)
• Scaling in IPOPT
• Ability to interrupt the solver
• Feedback for user on solver status

Notes

• Identified the related headers that are to be analyzed and generated callgraphs and reverse callgraphs to help locate the fault easier. And sometimes these help understand new code and how it functions allowing you to focus only on the essentials. Cflow was used to generate callgraphs.
• Files that have been identified for analysis are the following
  • • solvers/ipopt/asc_ipopt.c
    • ascend/solver/solver.h
    • ascend/system/slv_client.h
    • ascend/system/slv_common.h
    • ascend/system/slv_stdcalls.h
• Also, as a quick tip, use Cscope to search for headers, symbols, etc within a bunch of files under a directory.
• Information on implementing an external solver is given in External Solvers.
• One can browse the libascend documentation here Note: Module pages may be long but files may look manageable. Also, header dependencies are shown in a neat way. For example, have a look at this
• Relations are maintained in separate lists and objective functions are maintained in separate lists. Refer to ascend/system/analyze.c. Have a look at analyze_make_master_lists. Also both are mutually exclusive.
• IPOPT uses triplet format to maintain SPARSE MATRICES.
• rel_incidence_list (ascend/system/rel.h) gives an incidence list of a particular relation. (Look for sindex at ascend/system/var.h)
• use rel_make_name (ascend/system/rel.h) to get the label of the relation for debugging purposes.
• Hessian is not implemented yet. Quasi-Newton approximation to Hessian calculations provided by IPOPT is used
• Notes on using filters for relations and variables is given here
• Good book on Autodiff : Evaluating Derivatives by Andreas Griewank

Tools Used

Callgraph Generation:

cflow -ix -I <include directory> <filename>

For Reverse Callgraph:

cflow -ix -r -I <include directory> <filename>

CScope: cd to the directory in which you want to search for the symbol. (Look at the the manpage for more options)

cscope -qR