Optimization - shivamvats/notes GitHub Wiki

Most well-developed theory and tools.

• Subgradient Methods: Used to solve convex minimization problems. They are slower than Newton's method but converge even when applied to a non-differentiable objective function, whereas Newton's method does not converge on non-differentiable problems.

Submodular Functions: Plays a similar role in discrete optimization as convexity plays in continuous optimization. Let V be a set of points, then the domain is the power-set of V. A function F defined on this power-set is modular if F(S U a) >= F(T U a) for all S < T and a in V \ T. i.e. if you have less to begin with (S), then you gain more from something new. Example, sensor-coverage: if a region is already well covered with sensors, then adding another sensor has lower return than adding one to a region with fewer sensors. details1

Values for a set of n design variables (x1, x2,..., xn) are to be found that minimize a scalar-valued objective function, such that a set of m inequality constraints are satisfied.

If the objective is quadratic in the design variables and the constraints are linearly independent, then the optimization problem has a unique solution.

One way to solve such problems is by using the method of Lagrange multipliers, in which the objective is modified through the addition of terms that describe the constraints.

More details: http://people.duke.edu/~hpgavin/cee201/LagrangeMultipliers.pdf

1. McCormick Envelopes: These are a type of convex relaxations used in bilinear non-linear programming problems, often used to solve a mixed integer programming problem by relaxing the problem so that it becomes a convex non-linear program. Solving this convex NLP will provide a lower bound on the original mixed-integer MLP. See mccormick-envelopes.

1. Lemke's algorithm: It is a simplex-like algorithm for solving linear complementarity and mixed linear complementarity problems.

1. SNOPT : General purpose program for solving constrained optimization problems- linear, quadratic and non-linear. Can be used via C and MATLAB.
2. IPOPT
3. NLOPT
4. JuMP : Modeling language and supporting packages for optimization in Julia.
5. TrajectoryOptimization : Library of solvers for trajectory optimization written in Julia. Provides interface to SNOPT.