[ConvexOptimization(byBoyd) Study Notes] Chapter1-MathematicalOptimization

** Mathematical Optimization (MO)** There are the following meaning:

[ egin{align} &minimize , f_0(x) \ &subject , to , f_i(x)≤b_i, , i=1,...,m ag{1.1} end{align} ]

- The vector (x=(x_1,...,x_n)) is the optimization problem in
**Optimization variable**。 - The function (f_0:R^n→R) is
**objective function**。 - The function (f_i:R^n→R, i=1,...,m) is
**Constraint function**。

What is optimal?？ We have the following meaning：

When (f_0(z) ≥ f_0(x^*)) for any variable (z) satisfying the restriction (f_1(z) ≤ b_1,...,f_m(z) ≤ b_m), then (x^*) is said to be optimal (optimal).

**classify**The optimization problem is said to be when the following conditions in definition (1.1) are satisfied**linear program**。 [f_i(αx+βy)=αf_i(x)+βf_i(y) ag{1.2}]

where (x,y∈R^n) and (α,β∈R).

Similarly when the optimization problem that does not satisfy (1.2) then becomes** nonlinear program (nonlinear program)**。

** Convex Optimization problem (Convex Optimization)** The conditions to be satisfied are more extensive than those for linear programming, so the latter can also be understood as a subset of the former, and the conditions to be satisfied for convex optimization are as follows.
[f_i(αx+βy)≤αf_i(x)+βf_i(y) ag{1.3}]

**understandable meaning**It is not very intuitive just to read the definition (1.1), so to understand it visually with a chestnut.

We all know that in machine learning our goal is to find a model to fit to the data based on some prior knowledge. this time** Optimization variables** (x) is the parameter in the model,** Restriction functions**It's that a priori knowledge and the restrictions on hyperparameters and so on that** objective function** even( with classify Question as an example) Accuracy of model fit to data。

The effectiveness varies between different optimization algorithms and generally depends on these factors :

- Special forms of objective and constraint functions
- Optimizing the number of variables and constraints
- Special structure (sparsity sparse structure)

Least-squaresandlinear programming

**meaning****Least-squares problem (least-squares)**unrestricted， That means at this time meaning(1.1) hit the target(m=0), such objective function meaning as follows： [minimize , f_0(x)=||Ax-b||^2_2=sum_{i=1}^k(a_i^Tx-b_i)^2 ag{1.4}]

where (A ∈ R^{k×n},(k ≥ n)),(a_i^T) is the row vector of A and (x ∈ R^n) is the optimization variable.

**require a solution**Solving the optimization problem in (1.4) can be reduced to a set of linear equations, i.e. [(A^TA)x=A^Tb] The solution is (x=(A^TA)^{-1}A^Tb).**application**Today's algorithms and software can solve least-squares optimization problems very efficiently, even with thousands of variables and terms, in less than a minute (sparse patterns are generally required). So if you can turn the optimization problem into a least squares optimization problem, everything is much simpler.

**meaning**Linear programming is defined as follows: [ egin{align} &minimize , c^Tx \ &subject , to , a_i^Tx≤b_i, i=1,...,m ag{1.5} end{align} ]

where (c, a_1, . . . ,a_m ∈ R^n) and scalars (b_1, . . . , b_m ∈ R).

**require a solution**require a solution Linear programming does not have a simplified formula like least squares， But there are still various ways， for exampleDantzig's simplex method andinterior-point methods( The complexity is typically(n^2m,(m≥n)) stairs)。**application**Although transforming the original optimization problem into a linear programming problem is much more complex than transforming it into a least squares optimization problem, it is not that difficult. There are already some software systems that can automatically transform optimization problems into linear programming.

**meaning**In fact, convex optimization has already been described earlier， Here's a reintroduction。 convex optimization problem meaning as follows： [ egin{align} & minimize , f_0(x) otag \ & subject , to , f_i(x)≤b_i, , i=1,...,m otag \ & f_i(αx+βy)≤αf_i(x)+βf_i(y) ag{1.6} end{align} ] where (x,y∈R^n) and (α,β∈R , with , alpha+eta=1, alpha≥0,eta≥0).**require a solution**For convex optimization problems, there is no solution formula like the least-squares optimization problem, but the interior-point methods are not a bad way to go.**application**Transforming the optimization problem into a convex optimization problem is a bit more difficult than the two above, and this transformation process requires quite a bit of skill, but once the transformation is successful, the solution is as easy as the two optimization problems above.

Nonlinear programming (nonlinear programming) is also called nonlinear optimization (nonlinear optimization).

** Note that a nonlinear optimization problem may or may not be a convex optimization problem.**

At this point the optimization problem solution can be divided into** local optimal solution (math.)**，** global optimal solution**。

The outline of the book is as follows.

- Part I： Theory
- Chapter 2: Convex Sets
- Chapter 3: Convex functions
- Chapter 4：Convex optimization problems
- Chapter 5: Lagrangian duality

- Part II: Applications（ The main point is how convex optimization application In the actual）
- Part III: Algorithms
- unconstrained optimization
- equality constrained optimization
- inequality constrained optimization The third part of the algorithm is divided into three main stages. 1.Base level: quadratic optimization (e.g., least squares) 2.Next level: Newton's algorithm(Newton's method)， For solving unconstrained or equationally constrained problems 3.Top level:Interior-point methods, solving inequality constraints