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?

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

One Response to Interview Question: Basic NLP

  1. Brett says:

    ANSWER (partial)
     
    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).

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s