## Interview Question: Basic NLP

Sample Question #63 (mathematics – optimization)

How do you find the local maximum of a function subject to a linear equality constraint? What’s the dual of this maximization problem?

That is:  max f(x)
x

s.t. g(x) = c where c is a constant

(Here, x is a vector.)

Bonus question: what if the constraint g(x)=c is nonlinear?

This entry was posted in Sample Qs. Bookmark the permalink.

### One Response to Interview Question: Basic NLP

1. Brett says:

Graphically, you can just graph f(x) and find the highest point where it intercepts with g(x).  Of course, this only works if x has dimension less than 3.

Mathematically, we need to consider a few cases.  If f(x) is linear, you will get a corner solution if g(x) is also linear.  If the first and second derivatives of f(x) exist, you can use the Lagrange method: use the Lagrange multiplier to find the solution, and use the 2nd derivatives to make sure if it’s really a local maxim.  (But what if one of these derivatives doesn’t exist?)

The dual problem is to minimize g(x) subject to a constraint of f(x).