As of Ubuntu 18.04 gksu is depreciated, pkexec requires an install and doesn't always work. Here's another way:
Per edm's answer, edit the .desktop EXEC line, but prepend only with "sudo ", e.g. /usr/bin/nvidia-settings becomes sudo /usr/bin/nvidia-settings. MenuLibre users (and maybe other GUI menu editors): the Command line in MenuLibre sends to the EXEC line in in the .desktop file, so you don't need to bother digging the .desktop file out.
If you try this out from the menu now, nothing will happen. Sudo is called with no GUI so nothing happens and it fails silently. This is expected.
In terminal: sudo visudo then add at bottom (right click paste):
YOURUSERNAME ALL=(ALL) NOPASSWD: /usr/bin/nvidia-settings
ctrl+o to save, enter, ctrl+X to close file. Should work now.