Key Concepts of Optimization
Key concepts of optimization (as used in standard optimization modeling) ==Optimization as “minimize an objective over a feasible set.”== Many seemingly different problems can be put into a common framework: minimizin...
Key concepts of optimization (as used in standard optimization modeling) ==Optimization as “minimize an objective over a feasible set.”== Many seemingly different problems can be put into a common framework: minimizing an objective function over a feasible set.[:cite[1]{ln=2}], [:cite[1]{ln=3}] ==Decision / optimization variables== (the quantities you get to choose). In the standard framework, the optimization variable is denoted $\tilde{x}\in\mathbb{R}^n$.[:cite[2]{ln=5}] ==Objective function== (what you are trying to minimize or maximize). In standard form, the objective is $f 0(\tilde{x})$, called the objective function.[:cite[2]{ln=10}] ==Constraints== (requirements the decision variables must satisfy), including: ==Inequality constraints== of the form $f i(\tilde{x}) \le 0$.[:cite[2]{ln=11}] ==Equality constraints== of the form $h j(\tilde{x}) = 0$.[:cite[2]{ln=12}] Constraints can be either equalities or inequalities (e.g., in the variables $x i$).[:cite[3]{ln=4}] ==Feasible set $\Omega$== (all choices that satisfy every constraint). The feasible set is explicitly defined as the set of all $\tilde{x}$ that satisfy all constraints.[:cite[2]{ln=13}], and described as “the set of all $(x 1,x 2)$ pairs which obey the constraints” in an example.[:cite[3]{ln=3}] ==Solutions / minimizers (optimal solutions)== A solution is any $\tilde{x}^\star\in\Omega$ that attains the minimum value of the objective across all feasible $\tilde{x}\in\Omega$; $\tilde{x}^\star$ is also called a minimizer of $f 0$ over $\Omega$.[:cite[4]{ln=7}], [:cite[4]{ln=10}] ==Problem value $p^\star$== (the optimal objective value), written as $p^\star = \min {\tilde{x}\in\Omega} f 0(\tilde{x}).$ This is emphasized to be a real number (a scalar), not a vector.[:cite[5]{ln=2}], [:cite[5]{ln=10}] ==Argmin notation== (the set of minimizers). The argmin is a set of vectors, and any element of this set is an optimal solution/minimizer.[:cite[6]{ln=1}] It may contain zero vectors (no global optima realized), one, multiple, or infinitely many vectors depending on the problem.[:cite[6]{ln=2}], [:cite[6]{ln=6}], [:cite[6]{ln=7}], [:cite[6]{ln=8}] ==Unconstrained vs. constrained optimization== If there are no constraints, then $\Omega=\mathbb{R}^n$ and the problem is unconstrained; otherwise it is constrained.[:cite[4]{ln=11}], [:cite[4]{ln=12}] ==Minimum vs. infimum (existence subtleties)== When the minimum does not exist but a greatest lower bound does, the concept of an infimum generalizes the minimum; when the minimum exists, it equals the infimum.[:cite[7]{ln=2}], [:cite[7]{ln=3}], [:cite[7]{ln=4}] ==Convexity (why some problems are easier)== Least squares is described as “easy” because it is convex; convex problems are easier because any local optimum is a global optimum.[:cite[8]{ln=2}], [:cite[8]{ln=3}]