I. Mathematical Optimization

1.1 Definition

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 functionsIt'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)

1.2 least square (estimate)& linear programming

Least-squares and linear programming

1.2.1 Least squares problem

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.

1.2.2 Linear planning

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.

1.3 Convex optimization

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.

1.4 Nonlinear programming

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。

1.5 Outline

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

Recommended>>
1、C mathematical calculation package MathNET
2、The most popular VR videos on YouTube theres one for you
3、10 Years of GitHub Thanks to You
4、ShareSDK 3rd party sharing and login problems encountered
5、No more charges MapD database open source coming from the past to point out how to get started