Mathematical modeling - nonlinear programming

Catalog

Basic concepts

convex programming

Discriminant theorem

Quadratic programming model

The solution of nonlinear programming

Unconstrained extreme value problem

Constrained extremum problem

Solver based solution

Problem based solution

other

---

Nonlinear programming ： A mathematical expression describing the objective function or constraints , At least one is a nonlinear function .

Basic concepts

remember yes n Dimensional space A point in （n Dimension vector ）,,, Is defined in Real valued functions on . if f,g,h At least one of the functions is x The nonlinear function of , It is called the general form of nonlinear programming model ：

  Global optimal solution ： if , also There are , said Is the global optimal solution .

  Locally optimal solution ：x In the neighborhood of （ Also included in the feasible region ）,x The corresponding function value is the smallest , be x Is the local optimal solution .

Unconstrained nonlinear programming problem It can be expressed as ：

convex programming

Convex programming is a special nonlinear programming problem , The global optimal solution can be obtained .

convex set ：

  Convex function ：

The nonnegative linear combination of finite convex functions defined on a convex set is still convex

Discriminant theorem

The determinant of a positive semidefinite matrix is nonnegative .

Hesse matrix ：

  For the general form of nonlinear programming model , if f(x) Is a convex function ,g(x) Is a convex function ,h(x) by Linear function , Then the nonlinear programming problem is called convex programming . The local optimal solution of convex programming is the global optimal solution , The set of optimal solutions forms a convex set . When the objective function is strictly convex , The optimal solution must be unique .

Example

f(x) and g2(x) Determinant of the Hesse matrix ：

  Other constraints are linear functions , So it's a convex programming problem

clc,clear
prob = optimproblem;
x = optimvar('x',2,'LowerBound',0);
prob.Objective = sum(x.^2)-4*x(1)+4;
con = [-x(1)+x(2)-2 <= 0
    x(1)^2-x(2)+1 <= 0];
prob.Constraints.con = con;
x0.x = rand(2,1)% Nonlinear programming must be given an initial value ,x0 Name at will 
[s,f,flag,o] = solve(prob,x0);
s.x

ans =

    0.5536
    1.3064

Quadratic programming model

The objective function is a quadratic function of the decision vector , The constraints are linear , Then this model is called quadratic programming model , General form ：

  among ：

  When H Positive definite when , The objective function is minimized when , The model is convex quadratic programming , The local optimal solution of convex quadratic programming is the global optimal solution . If not convex programming , It is recommended to use fmincon function .

Example

The objective function is to minimize , however H Is a negative definite matrix , So it's not convex programming .

clc,clear
x = optimvar('x',2,'LowerBound',0);
h = [-1,-0.15;-0.15,-2];
f = [98;277];
a = [1,1;1,-2];
b = [100;0];
prob = optimproblem('Objective',x'*h*x+f'*x);
prob.Constraints = a*x <= b;
[s,f,flag,o] = solve(prob);
s.x

ans =

     1
     1

[1,1] Is the local optimal solution , Use fmincon function ：

fx = @(x)x'*h*x+f'*x;
[x,y] = fmincon(fx,rand(2,1),a,b,[],[],[0;0],[])

x =

   1.0e-07 *

    0.2533
    0.3400
y =

   1.1901e-05

The solution of nonlinear programming

Unconstrained extreme value problem

MATLAB The functions used to solve unconstrained minima in the toolbox are ：

  Example

clc,clear
f = @(x) x(1)^3-x(2)^3+3*x(1)^2+3*x(2)^2-9*x(1);
g = @(x) -f(x);
[m1,n1] = fminunc(f,[0,0])% Find the minimum 
[m2,n2] = fminsearch(g,[0,0]);% Find the maximum 
m2,-n2

m1 =

    1.0000   -0.0000
n1 =

    -5
m2 =

   -3.0000    2.0000
ans =

   31.0000

Constrained extremum problem

There are also solver based solutions and problem-based solutions

Solver based solution

The standard form of the mathematical model is ：

  example ：

clc,clear
fun1 = @(x) sum(x.^2)+8;
[x,y] = fmincon(fun1,rand(3,1),[],[],[],[],zeros(3,1),[],@fun2)

function [c,ceq] = fun2(x)
c = [-x(1)^2+x(2)-x(3)^2
    x(1)+x(2)^2+x(3)^3-20];
ceq = [-x(1)-x(2)^2+2
    x(2)+2*x(3)^2-3];
end

Problem based solution

clc,clear
x = optimvar('x',3,'LowerBound',0);
prob = optimproblem('Objective',sum(x.^2)+8);
con1 = [-x(1)^2+x(2)-x(3)^2 <= 0
    x(1)+x(2)^2+x(3)^3 <= 20];
con2 = [-x(1)-x(2)^2+2 == 0
    x(2)+2*x(3)^2 == 3];
prob.Constraints.con1 = con1;
prob.Constraints.con2 = con2;
x0.x = rand(3,1);
[s,f,flag,out] = solve(prob,x0);
s.x,f

 

other

The return value of an anonymous function can only have one , It could be a vector .