Solving a Nonlinear Programming Problem with Excel VBA

A nonlinear programming (NLP) problem is formulated similarly to a linear programming (LP) problem, except that the objective function and/or at least one constraint is nonlinear. Consequently, NLP problems are harder than LP problems, and there is no general method analogous to the Simplex method for LP. NLP also includes nonlinear integer and discrete optimization problems.

By solution approach, nonlinear optimization problems are divided into:

• Constrained optimization (finding extrema subject to constraints and bounds), and
• Unconstrained optimization (finding extrema without additional conditions).

There exist many numerical methods; the appropriate choice depends on the type of nonlinearity. The Excel Solver add-in helps with the numerical solution of NLP problems.

Solving a System of Nonlinear Equations with Solver

Consider the system

(1)

where f_i(x,y), i=1,2 are nonlinear functions of x,y and C_i are constants.

A pair (x,y) solves if it solves the single nonlinear equation

(2)

Geometrically, solutions (1) are the intersection points of the curves f₁(x,y)=C_{1 ,} f₂(x,y)=C_2.

Root-finding procedure:

• Determine (at least approximately) an interval where solutions may exist for (1) or (2). Consider domains, behavior of the functions, etc. Sometimes a reasonable initial guess is used.
• Tabulate the function in (2) over a grid of x,yx,y on the chosen interval, or plot the curves f₁(x,y)=C₁  and f₂(x,y)=C_2..
• Localize candidate roots—pick grid points where (2) is minimal, or identify curve intersections for (1).
• Use Solver to refine each candidate into an accurate root.

Worked Example.

Let’s solve the following system of nonlinear equations:

(x-1)^2 + (y+1)^2 = 4
5x + 4y = 2.

It is easy to see that the solutions are the intersection points of a circle (radius = 2, center (1, –1)) and a line.

We can replace this system by the equivalent single equation:

(x - 1)^2 + (y + 1)^2 - 4 + (5x + 4y - 2)^2 = 0

for which we will find the solutions using the Solver add-in.

1.Interval for exploration and plotting

From the graphs, a reasonable search box is [−3,3][-3,3] for both x and y.

• Cells B3:B43: values of x.
• Plotting formulas (Excel) for the two branches of the circle and the line:
  • C3: =-1+SQRT(4-(B3-1)^2)
  • D3: =-1-SQRT(4-(B3-1)^2)
  • E3: =(2-5*B3)/4

2. Tabulation on [−3,3][-3,3] with step 0.5

Create a grid and compute the objective

Φ(x,y)=((x−1)2+(y+1)2−4)2+(5x+4y−2)2

to identify small values (potential roots).

3. Root localization on a grid

• A47:A59: x-values on [−3,3][-3,3] with step 0.5.
• B46:N46: y-values on [−3,3][-3,3] with step 0.5.
• B47 (copy to B47:N59):
• =((($A47-1)^2+(B$46+1)^2-4)^2+(5*$A47+4*B$46-2)^2)
• B62 (copy across to get row minima as needed):
• =MIN(B47:B60)

From this coarse scan, example candidate pairs include (−2.5,−2.5)(-2.5,-2.5), (2,−2)(2,-2), (0,0.5)(0,0.5), (0,1)(0,1).

4. Refinement with Solver

• Place initial guesses in D69:E72 (each row one candidate (x,y)(x,y)).
• Objective cell G69 (copy to G69:G72):
• =((D69-1)^2+(E69+1)^2-4)^2+(5*D69+4*E69-2)^2

• Open Solver:
  • Set Objective: G69 (then G70, … for each row).
  • To: Min.
  • By Changing Variable Cells: D69:E69.
  • Subject to the Constraints: (none needed here; unconstrained).
  • Options: For nonlinear problems, you may use GRG Nonlinear; provide reasonable starting values.

Run Solver for each initial guess.

Results (as reported):
The system has two solutions:

• (x,y)≈(2.3675745729901,  −2.45934248863711)
• (x,y)≈(−0.123564081639673,  0.654434224216163)