Parser for signomial and geometric programs

Abstract

A method and apparatus for parsing signomial and geometric programs, referred to herein as “the Parser”. Signomial and Geometric programming is a unique class of mathematical problems that is useful in the study of optimization problems. The Parser is a program designed to recognize and parse both signomial and geometric programs such that they may be accepted and solved by signomial and geometric program solvers. The Parser accepts an optimization problem from a user in the form of algebraic expressions. The Parser can then identify the problem as a signomial program and can further determine if it reduces to a geometric program. If either a signomial or geometric program exists, the Parser converts the algebraic expressions to a compact numeric format that can be accepted by a computer-aided solver. In the case of a geometric program, the solver may find a global solution to the optimization problem. However, in the case of signomial program, the solver may only find a local solution. The solution found by the solver is routed back to the Parser which reports it in a user-readable format.

1 . A computer implemented method, comprising: 
 performing the following method by reading program code and processing the program code with a processing unit: 
 accepting a machine readable description of an optimization problem, said machine readable description of said optimization including a machine readable description of an algebraic expression, said algebraic expression being one of: 
 a signomial inequality;  
 a posynomial inequality;  
 a monomial equality;  
 
 parsing said optimization problem with a computer to create a second machine readable description of said optimization problem, said second machine readable description of said optimization problem having a format that is acceptable to a computer implemented optimization problem solver, said format representing said algebraic expression as a set of numeric values, said set of numeric values including a first value that is a coefficient of said algebraic expression, said set of numeric values including a second-value that is an exponent of said algebraic expression.  
   
     
     
         2 . The method of  claim 1  where said parsing further comprises identifying said algebraic expression within said optimization problem.  
     
     
         3 . The method of  claim 2  further comprising identifying a second algebraic expression within said optimization problem after said algebraic expression is said identified.  
     
     
         3 . The method of  claim 1  where said parsing further comprises storing into memory a variable declaration of said optimization problem.  
     
     
         4 . The method of  claim 1  wherein said parsing further comprises substituting a second identified algebraic expression of said optimization problem into said algebraic expression, said algebraic expression having a variable that said second algebraic expression defines.  
     
     
         5 . The method of  claim 1  wherein said optimization problem has a minimized objective.  
     
     
         6 . The method of  claim 1  wherein said optimization problem has a maximized objective.  
     
     
         7 . The method of  claim 1  wherein said optimization problem is a geometric program.  
     
     
         8 . The method of  claim 1  wherein said optimization problem is a signomial program.  
     
     
         9 . A computer implemented method, comprising: 
 performing the following method by reading program code and processing the program code with a processing unit: 
 accepting a machine readable description of an optimization problem, said machine readable description of said optimization including a machine readable description of an algebraic expression, said algebraic expression having multiple terms, a term of said algebraic expression having the following form:  
   cx 1   a1 x 2   a2  . . . x n   an    
 parsing said optimization problem with a computer to create a second machine readable description of said optimization problem, said second machine readable description of said optimization problem having a format that is acceptable to a computer implemented optimization problem solver, said format including a first value that is a coefficient of said algebraic expression and a second value that is an exponent of said algebraic expression.  
   
     
     
         10 . The method of  claim 7  where said parsing further comprises identifying said algebraic expression within said optimization problem.  
     
     
         11 . The method of  claim 8  further comprising identifying a second algebraic expression within said optimization problem after said algebraic expression is said identified.  
     
     
         12 . The method of  claim 7  where said parsing further comprises storing into memory a variable declaration of said optimization problem.  
     
     
         13 . The method of  claim 7  wherein said parsing further comprises substituting a second identified algebraic expression of said optimization problem into said algebraic expression, said algebraic expression having a variable that said second algebraic expression defines.  
     
     
         14 . The method of  claim 7  wherein said optimization problem has a minimized objective.  
     
     
         15 . The method of  claim 7  wherein said optimization problem has a maximized objective.  
     
     
         16 . The method of  claim 9  wherein said optimization problem is a geometric program.  
     
     
         17 . The method of  claim 9  wherein said optimization problem is a signomial program.