Optimization Problem Types - Overview

Problem Types - Overview

In an optimization problem, the types of mathematical relationships between the objective and constraints and the decision variables determine how hard it is to solve, the solution methods or algorithms that can be used for optimization, and the confidence you can have that the solution is truly optimal.

A key issue is whether the problem functions are convex or non-convex:  Click Convex Optimization Problems to learn more.  If the objective and all constraints are convex, you can be confident of determining whether there is a feasible solution, finding the globally optimal solution, and solving the problem up to very large size.  If any functions are non-convex, the problem is much harder and you cannot be certain of any of these things.

Below is a list of optimization problem types, arranged in order of increasing difficulty for the solution methods.  To learn more about each type of problem, please click the topics below.

• Linear and Quadratic Programming Problems
• Quadratic Constraints and Conic Optimization Problems
• Integer and Constraint Programming Problems
• Smooth Nonlinear Optimization Problems
• Global Optimization Problems
• Nonsmooth Optimization Problems

All linear functions and some quadratic functions are convex, and the cone constraints in conic optimization problems are also convex functions.  Some but not all smooth nonlinear functions are convex.  Integer and constraint programming problems are inherently non-convex.  Global optimization methods are designed to solve non-convex problems.

When evaluating your objective and constraint formulas, bear in mind that only the parts of formulas that are dependent on the decision variables count.  An Excel formula such as =IF(C1>10,D1,2*D1) is nonsmooth if C1 depends on the decision variables.  But if C1 doesn't depend on the variables, then only D1 or 2*D1 -- not both -- can be selected during the optimization. Hence if D1 is a linear function of the variables, then the IF expression is also a linear function of the variables.

To learn more about Frontline Systems' technology and products for each of these problem types, please click on Solver Technology. 

To choose the method most appropriate for your problem, click Select the Best Product for Your Needs.