# Presentation: 532894

## Numerica

- A Modeling Language for Global Optimization
- Laurent Michel
- University of Connecticut

## Overview

- Global Optimization
- Local Methods
- Global Methods
- Numerica
- The Language
- The Semantics
- The Implementation

## Credits

- Algorithms
- Van Hentenryck, D. McAllester, D. kapur, J-F. Puget
- Language Design
- Van Hentenryck, Y. Deville
- Semantics
- Van Hentenryck, F. Benhamou, Y. Deville
- Implementation
- Van Hentenryck

## Global Optimization

- Equation Solving: finding all solutions to
- Optimization: finding all global optima to

## Complexity

- Computational Complexity
- in PSPACE
- NP-Hard
- Experimental Fact
- Many challenging problems with less than 10 variables

## Floating Point...

- Checking a solution may be hard

## Floating Point...

- Checking a solution may be hard

## Numerical Errors

- A small numerical errors may have dramatic effects

## What Can Computers Do?

## Beliefs...

*	**It would be wonderful if we had a general purpose computer routine that would tell use: “The roots of f**1**(x) are 0,3,4 and 5; the real roots of  f**2**(x) are 1 and 0.888; f**3**(x) has no real roots.”*
*	**It is unlikely that there will ever be such a routine. In general, the questions of existence and uniqueness -- does a problem have a solution and is it unique ?-- are beyond the capabilities one can expect of algorithms that solve non-linear problems. In fact, we must readily admit that for any computer algorithm there exist nonlinear functions (infinitely continuously differentiable, if you wish) perverse enough to defeat the algorithm. Therefore, all a user can be guaranteed from any algorithm applied to a nonlinear problem is the answer: “An approximate solution to the problem is...” or “No approximate solution to the problem was found in the allocated time.”*

## Beliefs...

- Computers cannot find all solutions
- Computers cannot prove the absence of solutions
- Computers cannot prove existence of solutions
- Computers cannot prove unicity of a solution
- Computers cannot find a global optimum

## Focus of the Talk

- Intuition
- equation solving
- one-dimensional illustrations
- basic ideas

## Overview

- Global Optimization
- Local Methods
- Global Methods
- Numerica
- The Language
- The Semantics
- The Implementation

## Local Methods

- Start with a guess
- Use local information to improve it
-  typical example: Newton method
- Fast when close to a root
- quadratic convergence
- Pitfalls
- convergence

## Pitfalls

- Looping
- Absence of Progress

## Globally Convergent Local Methods

- Converge to a stationary point from almost everywhere
- Enhance local methods with a “global” component

## Globally Convergent Local Methods

- Typical examples
- Quasi-Newton Methods
- Secant Methods
- Advantages
- fast
- Most appropriate when
- one solution
- numerically stable

## Globally Convergent Local Methods

- Limitations
- No guarantee of convergence
- No guarantee of convergence to a solution
- No guarantee of convergence to a *desired* solution
- What they cannot do
- Prove the absence of solutions
- Find all solutions
- Prove existence and unicity

## Overview

- Global Optimization
- Local Methods
- Global Methods
- Numerica
- The Language
- The Semantics
- The Implementation

## Continuation Methods

*A* is an easy system: C(0)
*B* is the original system: C(1)
- Increase *t* from 0 to 1

## Continuation Methods

- Basic Ideas
- A must have at least as many solutions as B
- Do not lose solutions (path crossing)
- Avoid solutions at infinities
- Techniques
- Approximate the number of solutions (BKK bound)
- Use randomization

## Continuation Methods

- Most appropriate for
- polynomials
- less than 20 variables
- Limitations
- the approximation of the number of solutions is exponential in the degree of the system
- cannot prove the absence of solutions

## Interval Methods

- Collect Global Information
- over infinitely many points
- in finite time
- Guarantee Correctness
- account for numerical errors
- Moore 1966

## Trivial Operator: Box(0)

- Check if the interval evaluation contains 0

## Newton Interval Operator

- Interval generalization of Newton’s method (Moore, 66)

## Newton Interval Operation

## Newton Interval Operator

## Interval Methods

- Advantages
- numerically reliable
- guaranteed convergence
- existence & uniqueness proofs
- can isolate all solutions
- can prove the absence of solutions

## Interval Methods

- Limitations
- considered very slow
- dependency problem
- Many occurrences of the same variables
- intervals may grow exponentially
- not adapted to certain classes of problems
- Least Square Problems

## Overview

- Global Optimization
- Local Methods
- Global Methods
- Numerica
- The Language
- The Semantics
- The Implementation

## Numerica

- A Modeling Language
- statements are very close to descriptions in textbooks
- clear semantics
- A Novel Constraint-Solving Algorithm
- numerical analysis
- close to a solution
- artificial intelligence
- far from a solution

## Numerica

- Functionalities
- based on a novel interval method
- locate all geometrically isolated solutions
- Most Appropriate for
- highly nonlinear problems
- problems with multiple solutions
- problems with no solution
- problems where no external knowledge is available

## Circle & Parabola

- Statement

**Variable: **
**  ****x,y;**
**body:**
**	****solve system all**
**	****	****x^2+y^2=1;**
**	****	****x^2=y;**

**Solution: 1 [SAFE]**
**------------**
**x = -0.78615137775742  + [-0.38305e-14 , -0.26091e-14]**
**y = 0.61803398874989   + [0.37923e-14 , 0.59018e-14]**
**Solution: 2 [SAFE]**
**------------**
**x = 0.78615137775742   + [0.26091e-14 , 0.38305e-14]**
**y = 0.61803398874989   + [0.37923e-14 , 0.59018e-14]**

## Kinematics

- Challenging because
- many solutions
- local methods diverge easily
- Statement
- generic constraints
- trigonometric features

- B

- 0

- B

- 1

- x,y

- 

- 

- 

- 

## Kinematics

**Input:**
**	****int x : “X coordinate”;**
**	****int y : “Y coordinate”;**
**Range:**
**	****seg = [1..2];**
**Constant:**
**	****int l : array[seg] = [1,2];**
**Variable:**
**	****t : array[seg] in [0..2*****pi****];**
**Body:**
**	****solve system all**
**	****	****l[2]*cos(t[2])+l[1]*cos(t[1]) = x;**
**	****	****l[2]*sin(t[2])+l[1]*sin(t[1]) = y; **

## Broyden Banded Function

- Typical benchmarks from numerical analysis

## Model

**Input:**
**	****int n : “Number of variables”;**
**Range: **
**	****idx = [1..n];**
**Set:**
**	****J[i in idx] = {j in [max(1,i-5)..min(n,i+1)] | i <> j};**
**Variable:**
**	****x : array[idx] in [-10e8..10e8];**
**Body: solve system all**
**	****[i in idx] : **
**      ****0 = x[i] * (2 + 5* x[i]^2)+1 - **
**          ****Sum****(k in J[i]) x[k] * (1+x[k]);**

## Behavior

- Numerica
- is linear (experimentally) in the number of variables
- proves the existence of the unique solution
- does not make any choice (no branching)
- solves the problem for 320 variables in 150 seconds
- Comparison
- out of scope for continuation methods

## Overview

- Global Optimization
- Local Methods
- Global Methods
- Numerica
- The Language
- The Semantics
- The Implementation

## Semantics

- Intervals
- [a,b] = {r **| **ar b}
- Canonical intervals
- [a,a]  or [a,a+]

## Interval Extension

- Is this correct?

## Interval Extensions

- Outward Rounding
- specify the direction of rounding
- IEEE standards (but very-system dependent)
- Other Operations
- e.g., trigonometric functions
- tedious and complex
- Many Possible Interval Extensions
- e.g. centered forms
- huge research topic

## Semantics of Numerica

- Interval Solution
- canonical interval enclosing a solution
- Possible Interval Solution
- canonical interval believed to contain a solution
- Numerica Returns
- all interval solutions
- some possible interval solutions

## Overview

- Global Optimization
- Local Methods
- Global Methods
- Numerica
- The Language
- The Semantics
- The Implementation

## Implementation

- Global Search Algorithm
- associate an interval with each variable
- use constraints to prune the intervals
- split an interval into two parts and explore recursively
- Key Issue
- how to prune the search space?
- Key Insight
- view continuous problems as discrete problems

## Pruning

- Numerical analysis
- Interval Newton Operator
- Best when close to a solution
- Artificial Intelligence
- Constraint satisfaction techniques
- Approximations of projections
- Best when far from a solution

## Consistency & Intervals

- Three levels
- Box(0)
- Trivial pruning operator
- Box(1)
- One-dimensional projection
- Box(2)
- Two-dimensional projection
- Three Extensions
- Natural
- Distributed
- Taylor

## Box(0)-Consistency

- Trivial Pruning Operator

## Arc-Consistency

- From Discrete Constraint Satisfaction

## Box(1)-Consistency

- Basic Intuition
- Project on one variable
- How?
- Too hard (complexity is open)
- Approximate
- Replace all other variables by their ranges
- Solve

## Pictorially

## Box(1)-Consistency

- How to obtain box(1)-Consistency?
- Find the “zeros” of an interval function
- Apply an interval method on the interval function
- Bisection
- Interval Newton Method
- Newton Operator
- Limitations
- Pruning may be weak when the intervals are large

## Box(1)-Consistency

- Algorithm
- Narrowing: IE
- Splitting

- function LNAR(F,F’:*I **** I*,I: *I*) : *I *{
-    r = right(I);
-    if 0  F(I) then return ;
-    I = N*(F,F’,I);
-    if 0  F([left(I),left(I)+]) return box(I,[r,r+]);
-    else
-        <I1,I2> = SPLIT(I);
-        if LNAR(F,F’,I1)  
-        then return box(LNAR(F,F’,I1),[r,r+]);
-        else  return box(LNAR(F,F’,I2),[r,r+]);
- }

## Pruned Box

## Extensions

- Can we improve ?
- Idea
- Work directly on the
- Top curve
- Bottom curve
- How ?
- Distributed Extension...
- ... And A Constructive Definition

## Distributed Interval Extension

- Does not preserve the *expression*
- Move *f*  to distributed form

## Constructive Definition

- How to obtain the lower curve ?

## Box(1)-Consistency on DF.

## Taylor Extension

- Natural Extension of Taylor Expansion
- Box(1)-Consistency

## Improving Box(1)

- Notice that
- The Taylor Extension is univariate and linear.
- Compute Box(1) directly

## Box(2)-Consistency

- Stronger Consistency Notion
- Approximate projection on two variables
- effective for very tough problems
- transistor modeling
- chemical engineering
- Apply box-consistency on
- several interval extensions
- (e.g., centered forms)

## Box(2)-Consistency

- Definition

## Box(2)

- In 3-D

## Box(2)

- Pruning

## Proof of Solution

## Optimization

- Reduction to equation solving
- necessary conditions: e.g. Fritz-John conditions
- Branch and Bound
- Accelerators
- Probing
- Local methods

## Conclusion I

- Numerica for global optimization
- easy to use
- orthogonal to local methods
- highly nonlinear problems
- multiple solutions
- no solutions
- scaling
- finitely many isolated solutions
- effective interval algorithm for a variety of areas

## Conclusion II

- Limitations
- Dependency problem (e.g., least square problems)
- Many practical problems are outside the scope of all methods
- Some Extensions
- combination of symbolic and numerical techniques
- differential equations

## Directions

- Safe Linear Estimators
- A way to leverage existing tools
- Exploit semantic information
- Parallel with global constraints in FD-solvers.
- Large Scale optimization