Documentation

# solve

Solve optimization problem

## Syntax

``sol = solve(prob)``
``sol = solve(prob,x0)``
``sol = solve(___,Name,Value)``
``[sol,fval] = solve(___)``
``[sol,fval,exitflag,output,lambda] = solve(___)``

## Description

example

````sol = solve(prob)` solves the optimization problem `prob`.```

example

````sol = solve(prob,x0)` solves `prob` starting from the point `x0`.```

example

````sol = solve(___,Name,Value)` modifies the solution process using one or more name-value pair arguments in addition to the input arguments in previous syntaxes.```
````[sol,fval] = solve(___)` also returns the objective function value at the solution using any of the input arguments in previous syntaxes.```

example

````[sol,fval,exitflag,output,lambda] = solve(___)` also returns an exit flag describing the exit condition, an `output` structure containing additional information about the solution process, and, for non-integer problems, a Lagrange multiplier structure.```

## Examples

collapse all

Solve a linear programming problem defined by an optimization problem.

```x = optimvar('x'); y = optimvar('y'); prob = optimproblem; prob.Objective = -x - y/3; prob.Constraints.cons1 = x + y <= 2; prob.Constraints.cons2 = x + y/4 <= 1; prob.Constraints.cons3 = x - y <= 2; prob.Constraints.cons4 = x/4 + y >= -1; prob.Constraints.cons5 = x + y >= 1; prob.Constraints.cons6 = -x + y <= 2; sol = solve(prob)```
```Optimal solution found. ```
```sol = struct with fields: x: 0.6667 y: 1.3333 ```

Find a minimum of the `peaks` function, which is included in MATLAB®, in the region ${x}^{2}+{y}^{2}\le 4$. To do so, convert the `peaks` function to an optimization expression.

```prob = optimproblem; x = optimvar('x'); y = optimvar('y'); fun = fcn2optimexpr(@peaks,x,y); prob.Objective = fun;```

Include the constraint as an inequality in the optimization variables.

`prob.Constraints = x^2 + y^2 <= 4;`

Set the initial point for `x` to 1 and `y` to –1, and solve the problem.

```x0.x = 1; x0.y = -1; sol = solve(prob,x0)```
```Local minimum found that satisfies the constraints. Optimization completed because the objective function is non-decreasing in feasible directions, to within the value of the optimality tolerance, and constraints are satisfied to within the value of the constraint tolerance. ```
```sol = struct with fields: x: 0.2283 y: -1.6255 ```

Compare the number of steps to solve an integer programming problem both with and without an initial feasible point. The problem has eight integer variables and four linear equality constraints, and all variables are restricted to be positive.

```prob = optimproblem; x = optimvar('x',8,1,'LowerBound',0,'Type','integer');```

Create four linear equality constraints and include them in the problem.

```Aeq = [22 13 26 33 21 3 14 26 39 16 22 28 26 30 23 24 18 14 29 27 30 38 26 26 41 26 28 36 18 38 16 26]; beq = [ 7872 10466 11322 12058]; cons = Aeq*x == beq; prob.Constraints.cons = cons;```

Create an objective function and include it in the problem.

```f = [2 10 13 17 7 5 7 3]; prob.Objective = f*x;```

Solve the problem without using an initial point, and examine the display to see the number of branch-and-bound nodes.

`[x1,fval1,exitflag1,output1] = solve(prob);`
```LP: Optimal objective value is 1554.047531. Cut Generation: Applied 8 strong CG cuts. Lower bound is 1591.000000. Branch and Bound: nodes total num int integer relative explored time (s) solution fval gap (%) 10000 1.13 0 - - 18188 1.85 1 2.906000e+03 4.509804e+01 22039 2.30 2 2.073000e+03 2.270974e+01 24105 2.51 3 1.854000e+03 9.973046e+00 24531 2.56 3 1.854000e+03 1.347709e+00 24701 2.58 3 1.854000e+03 0.000000e+00 Optimal solution found. Intlinprog stopped because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer within tolerance, options.IntegerTolerance = 1e-05 (the default value). ```

For comparison, find the solution using an initial feasible point.

```x0.x = [8 62 23 103 53 84 46 34]'; [x2,fval2,exitflag2,output2] = solve(prob,x0);```
```LP: Optimal objective value is 1554.047531. Cut Generation: Applied 8 strong CG cuts. Lower bound is 1591.000000. Relative gap is 59.20%. Branch and Bound: nodes total num int integer relative explored time (s) solution fval gap (%) 3627 0.64 2 2.154000e+03 2.593968e+01 5844 0.86 3 1.854000e+03 1.180593e+01 6204 0.91 3 1.854000e+03 1.455526e+00 6400 0.92 3 1.854000e+03 0.000000e+00 Optimal solution found. Intlinprog stopped because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer within tolerance, options.IntegerTolerance = 1e-05 (the default value). ```
`fprintf('Without an initial point, solve took %d steps.\nWith an initial point, solve took %d steps.',output1.numnodes,output2.numnodes)`
```Without an initial point, solve took 24701 steps. With an initial point, solve took 6400 steps. ```

Giving an initial point does not always improve the problem. For this problem, using an initial point saves time and computational steps. However, for some problems, an initial point can cause `solve` to take more steps.

Solve the problem

`$\underset{x}{\mathrm{min}}\left(-3{x}_{1}-2{x}_{2}-{x}_{3}\right)\phantom{\rule{0.2777777777777778em}{0ex}}subject\phantom{\rule{0.2777777777777778em}{0ex}}to\left\{\begin{array}{l}{x}_{3}\phantom{\rule{0.2777777777777778em}{0ex}}binary\\ {x}_{1},{x}_{2}\ge 0\\ {x}_{1}+{x}_{2}+{x}_{3}\le 7\\ 4{x}_{1}+2{x}_{2}+{x}_{3}=12\end{array}$`

without showing iterative display.

```x = optimvar('x',2,1,'LowerBound',0); x3 = optimvar('x3','Type','integer','LowerBound',0,'UpperBound',1); prob = optimproblem; prob.Objective = -3*x(1) - 2*x(2) - x3; prob.Constraints.cons1 = x(1) + x(2) + x3 <= 7; prob.Constraints.cons2 = 4*x(1) + 2*x(2) + x3 == 12; options = optimoptions('intlinprog','Display','off'); sol = solve(prob,'Options',options)```
```sol = struct with fields: x: [2x1 double] x3: 1 ```

Examine the solution.

`sol.x`
```ans = 2×1 0 5.5000 ```
`sol.x3`
```ans = 1 ```

Force `solve` to use `intlinprog` as the solver for a linear programming problem.

```x = optimvar('x'); y = optimvar('y'); prob = optimproblem; prob.Objective = -x - y/3; prob.Constraints.cons1 = x + y <= 2; prob.Constraints.cons2 = x + y/4 <= 1; prob.Constraints.cons3 = x - y <= 2; prob.Constraints.cons4 = x/4 + y >= -1; prob.Constraints.cons5 = x + y >= 1; prob.Constraints.cons6 = -x + y <= 2; sol = solve(prob,'Solver', 'intlinprog')```
```LP: Optimal objective value is -1.111111. Optimal solution found. No integer variables specified. Intlinprog solved the linear problem. ```
```sol = struct with fields: x: 0.6667 y: 1.3333 ```

Solve the mixed-integer linear programming problem described in Solve Integer Programming Problem with Nondefault Options and examine all of the output data.

```x = optimvar('x',2,1,'LowerBound',0); x3 = optimvar('x3','Type','integer','LowerBound',0,'UpperBound',1); prob = optimproblem; prob.Objective = -3*x(1) - 2*x(2) - x3; prob.Constraints.cons1 = x(1) + x(2) + x3 <= 7; prob.Constraints.cons2 = 4*x(1) + 2*x(2) + x3 == 12; [sol,fval,exitflag,output] = solve(prob)```
```LP: Optimal objective value is -12.000000. Optimal solution found. Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer within tolerance, options.IntegerTolerance = 1e-05 (the default value). ```
```sol = struct with fields: x: [2x1 double] x3: 1 ```
```fval = -12 ```
```exitflag = OptimalSolution ```
```output = struct with fields: relativegap: 0 absolutegap: 0 numfeaspoints: 1 numnodes: 0 constrviolation: 0 message: 'Optimal solution found....' solver: 'intlinprog' ```

For a problem without any integer constraints, you can also obtain a nonempty Lagrange multiplier structure as the fifth output.

Create and solve an optimization problem using named index variables. The problem is to maximize the profit-weighted flow of fruit to various airports, subject to constraints on the weighted flows.

```rng(0) % For reproducibility p = optimproblem('ObjectiveSense', 'maximize'); flow = optimvar('flow', ... {'apples', 'oranges', 'bananas', 'berries'}, {'NYC', 'BOS', 'LAX'}, ... 'LowerBound',0,'Type','integer'); p.Objective = sum(sum(rand(4,3).*flow)); p.Constraints.NYC = rand(1,4)*flow(:,'NYC') <= 10; p.Constraints.BOS = rand(1,4)*flow(:,'BOS') <= 12; p.Constraints.LAX = rand(1,4)*flow(:,'LAX') <= 35; sol = solve(p);```
```LP: Optimal objective value is -1027.472366. Heuristics: Found 1 solution using rounding. Upper bound is -1027.233133. Relative gap is 0.00%. Cut Generation: Applied 1 mir cut, and 2 strong CG cuts. Lower bound is -1027.233133. Relative gap is 0.00%. Optimal solution found. Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer within tolerance, options.IntegerTolerance = 1e-05 (the default value). ```

Find the optimal flow of oranges and berries to New York and Los Angeles.

`[idxFruit,idxAirports] = findindex(flow, {'oranges','berries'}, {'NYC', 'LAX'})`
```idxFruit = 1×2 2 4 ```
```idxAirports = 1×2 1 3 ```
`orangeBerries = sol.flow(idxFruit, idxAirports)`
```orangeBerries = 2×2 0 980.0000 70.0000 0 ```

This display means that no oranges are going to `NYC`, 70 berries are going to `NYC`, 980 oranges are going to `LAX`, and no berries are going to `LAX`.

List the optimal flow of the following:

`Fruit Airports`

` ----- --------`

` Berries NYC`

` Apples BOS`

` Oranges LAX`

`idx = findindex(flow, {'berries', 'apples', 'oranges'}, {'NYC', 'BOS', 'LAX'})`
```idx = 1×3 4 5 10 ```
`optimalFlow = sol.flow(idx)`
```optimalFlow = 1×3 70.0000 28.0000 980.0000 ```

This display means that 70 berries are going to `NYC`, 28 apples are going to `BOS`, and 980 oranges are going to `LAX`.

## Input Arguments

collapse all

Optimization problem, specified as an `OptimizationProblem` object. Create a problem by using `optimproblem`.

Example: ```prob = optimproblem; prob.Objective = obj; prob.Constraints.cons1 = cons1;```

Initial point, specified as a structure with field names equal to the variable names in `prob`.

For an example using `x0` with named index variables, see Create Initial Point for Optimization with Named Index Variables.

Example: If `prob` has variables named `x` and `y`: `x0.x = [3,2,17]; x0.y = [pi/3,2*pi/3]`.

Data Types: `struct`

### Name-Value Pair Arguments

Specify optional comma-separated pairs of `Name,Value` arguments. `Name` is the argument name and `Value` is the corresponding value. `Name` must appear inside quotes. You can specify several name and value pair arguments in any order as `Name1,Value1,...,NameN,ValueN`.

Example: `solve(prob,'options',opts)`

Optimization options, specified as the comma-separated pair consisting of `'options'` and an object created by `optimoptions` or an options structure such as created by `optimset`.

Internally, the `solve` function calls `linprog`, `intlinprog`, `quadprog`, `lsqlin`, `lsqnonneg`, `fminunc`, or `fmincon`. For the default solver, see `'solver'`.

Ensure that `options` are compatible with the solver. For example, `intlinprog` does not allow options to be a structure, and `lsqnonneg` does not allow options to be an object.

For suggestions on options settings to improve an `intlinprog` solution or the speed of a solution, see Tuning Integer Linear Programming. For `linprog`, the default `'dual-simplex'` algorithm is generally memory-efficient and speedy. Occasionally, `linprog` solves a large problem faster when the `Algorithm` option is `'interior-point'`. For suggestions on options settings to improve a nonlinear problem's solution, see Options in Common Use: Tuning and Troubleshooting and Improve Results.

Example: ```options = optimoptions('intlinprog','Display','none')```

Optimization solver, specified as the comma-separated pair consisting of `'solver'` and the name of a listed solver.

Problem TypeDefault SolverOther Allowed Solvers
Linear objective, linear constraints`linprog``intlinprog`, `quadprog`
Linear objective, linear and integer constraints`intlinprog``linprog`, `quadprog` (integer constraints ignored)
Quadratic objective, linear constraints`quadprog``lsqlin`, `lsqnonneg` (if objective cannot be converted to minimize ||C*x - d||^2 then `solve` throws an error for these solvers)
Minimize ||C*x - d||^2 subject to linear constraints`lsqlin` when the objective is a constant plus a sum of squares of linear expressions`quadprog`, `lsqnonneg` (Constraints other than x >= 0 are ignored for `lsqnonneg`)
Minimize ||C*x - d||^2 subject to x >= 0`lsqlin``quadprog`, `lsqnonneg`
Minimize general nonlinear function f(x)`fminunc``fmincon`
Minimize general nonlinear function f(x) subject to some constraints, or minimize any function subject to nonlinear constraints`fmincon`(none)

### Caution

For maximization problems, do not specify the `lsqlin` and `lsqnonneg` solvers. If you do, `solve` throws an error, because these solvers cannot maximize.

Example: `'intlinprog'`

Data Types: `char` | `string`

## Output Arguments

collapse all

Solution, returned as a structure. The fields of the structure are the names of the optimization variables. See `optimvar`.

Objective function value at the solution, returned as a real number.

### Tip

If you neglect to ask for `fval`, you can calculate it using:

`fval = evaluate(prob.Objective,sol)`

Reason the solver stopped, returned as a categorical variable. This table describes the exit flags for the `intlinprog` solver.

Exit Flag for `intlinprog`Numeric EquivalentMeaning
`OptimalWithPoorFeasibility``3`

The solution is feasible with respect to the relative `ConstraintTolerance` tolerance, but is not feasible with respect to the absolute tolerance.

`IntegerFeasible`2`intlinprog` stopped prematurely, and found an integer feasible point.
`OptimalSolution`

`1`

The solver converged to a solution `x`.

`SolverLimitExceeded`

`0`

`intlinprog` exceeds one of the following tolerances:

• `LPMaxIterations`

• `MaxNodes`

• `MaxTime`

• `RootLPMaxIterations`

See Tolerances and Stopping Criteria. `solve` also returns this exit flag when it runs out of memory at the root node.

`OutputFcnStop``-1``intlinprog` stopped by an output function or plot function.
`NoFeasiblePointFound`

`-2`

No feasible point found.

`Unbounded`

`-3`

The problem is unbounded.

`FeasibilityLost`

`-9`

Solver lost feasibility.

Exitflags `3` and `-9` relate to solutions that have large infeasibilities. These usually arise from linear constraint matrices that have large condition number, or problems that have large solution components. To correct these issues, try to scale the coefficient matrices, eliminate redundant linear constraints, or give tighter bounds on the variables.

This table describes the exit flags for the `linprog` solver.

Exit Flag for `linprog`Numeric EquivalentMeaning
`OptimalWithPoorFeasibility``3`

The solution is feasible with respect to the relative `ConstraintTolerance` tolerance, but is not feasible with respect to the absolute tolerance.

`OptimalSolution``1`

The solver converged to a solution `x`.

`SolverLimitExceeded``0`

The number of iterations exceeds `options.MaxIterations`.

`NoFeasiblePointFound``-2`

No feasible point found.

`Unbounded``-3`

The problem is unbounded.

`FoundNaN``-4`

`NaN` value encountered during execution of the algorithm.

`PrimalDualInfeasible``-5`

Both primal and dual problems are infeasible.

`DirectionTooSmall``-7`

The search direction is too small. No further progress can be made.

`FeasibilityLost``-9`

Solver lost feasibility.

Exitflags `3` and `-9` relate to solutions that have large infeasibilities. These usually arise from linear constraint matrices that have large condition number, or problems that have large solution components. To correct these issues, try to scale the coefficient matrices, eliminate redundant linear constraints, or give tighter bounds on the variables.

This table describes the exit flags for the `lsqlin` solver.

Exit Flag for `lsqlin`Numeric EquivalentMeaning
`FunctionChangeBelowTolerance``3`

Change in the residual is smaller than the specified tolerance `options.FunctionTolerance`. (`trust-region-reflective` algorithm)

`StepSizeBelowTolerance`

`2`

Step size smaller than `options.StepTolerance`, constraints satisfied. (`interior-point` algorithm)

`OptimalSolution``1`

The solver converged to a solution `x`.

`SolverLimitExceeded``0`

The number of iterations exceeds `options.MaxIterations`.

`NoFeasiblePointFound``-2`

The problem is infeasible. Or, for the `interior-point` algorithm, step size smaller than `options.StepTolerance`, but constraints are not satisfied.

`IllConditioned``-4`

Ill-conditioning prevents further optimization.

`NoDescentDirectionFound``-8`

The search direction is too small. No further progress can be made. (`interior-point` algorithm)

This table describes the exit flags for the `quadprog` solver.

Exit Flag for `quadprog`Numeric EquivalentMeaning
`LocalMinimumFound``4`

Local minimum found; minimum is not unique.

`FunctionChangeBelowTolerance``3`

Change in the objective function value is smaller than the specified tolerance `options.FunctionTolerance`. (`trust-region-reflective` algorithm)

`StepSizeBelowTolerance`

`2`

Step size smaller than `options.StepTolerance`, constraints satisfied. (`interior-point-convex` algorithm)

`OptimalSolution``1`

The solver converged to a solution `x`.

`SolverLimitExceeded``0`

The number of iterations exceeds `options.MaxIterations`.

`NoFeasiblePointFound``-2`

The problem is infeasible. Or, for the `interior-point` algorithm, step size smaller than `options.StepTolerance`, but constraints are not satisfied.

`IllConditioned``-4`

Ill-conditioning prevents further optimization.

`Nonconvex`

`-6`

Nonconvex problem detected. (`interior-point-convex` algorithm)

`NoDescentDirectionFound``-8`

Unable to compute a step direction. (`interior-point-convex` algorithm)

This table describes the exit flags for the `fminunc` solver.

Exit Flag for `fminunc`Numeric EquivalentMeaning
`NoDecreaseAlongSearchDirection``5`

Predicted decrease in the objective function is less than the `options.FunctionTolerance` tolerance.

`FunctionChangeBelowTolerance``3`

Change in the objective function value is less than the `options.FunctionTolerance` tolerance.

`StepSizeBelowTolerance`

`2`

Change in `x` is smaller than the `options.StepTolerance` tolerance.

`OptimalSolution``1`

Magnitude of gradient is smaller than the `options.OptimalityTolerance` tolerance.

`SolverLimitExceeded``0`

Number of iterations exceeds `options.MaxIterations` or number of function evaluations exceeds `options.MaxFunctionEvaluations`.

`OutputFcnStop``-1`

Stopped by an output function or plot function.

`Unbounded``-3`

Objective function at current iteration is below `options.ObjectiveLimit`.

This table describes the exit flags for the `fmincon` solver.

Exit Flag for `fmincon`Numeric EquivalentMeaning
`NoDecreaseAlongSearchDirection``5`

Magnitude of directional derivative in search direction is less than 2*`options.OptimalityTolerance` and maximum constraint violation is less than `options.ConstraintTolerance`.

`SearchDirectionTooSmall``4`

Magnitude of the search direction is less than 2*`options.StepTolerance` and maximum constraint violation is less than `options.ConstraintTolerance`.

`FunctionChangeBelowTolerance``3`

Change in the objective function value is less than `options.FunctionTolerance` and maximum constraint violation is less than `options.ConstraintTolerance`.

`StepSizeBelowTolerance`

`2`

Change in `x` is less than `options.StepTolerance` and maximum constraint violation is less than `options.ConstraintTolerance`.

`OptimalSolution``1`

First-order optimality measure is less than `options.OptimalityTolerance`, and maximum constraint violation is less than `options.ConstraintTolerance`.

`SolverLimitExceeded``0`

Number of iterations exceeds `options.MaxIterations` or number of function evaluations exceeds `options.MaxFunctionEvaluations`.

`OutputFcnStop``-1`

Stopped by an output function or plot function.

`NoFeasiblePointFound``-2`

No feasible point found.

`Unbounded``-3`

Objective function at current iteration is below `options.ObjectiveLimit` and maximum constraint violation is less than `options.ConstraintTolerance`.

Information about the optimization process, returned as a structure. The output structure contains the fields in the relevant underlying solver output field, depending on which solver `solve` called:

`solve` includes the additional field `Solver` in the `output` structure to identify the solver used, such as `'intlinprog'`.

Lagrange multipliers at the solution, returned as a structure. For the `intlinprog` solver, `lambda` is empty, `[]`. For the other solvers, `lambda` has these fields:

• `Variables` – Contains fields for each problem variable. Each problem variable name is a structure with two fields:

• `Lower` – Lagrange multipliers associated with the variable `LowerBound` property, returned as an array of the same size as the variable. Nonzero entries mean that the solution is at the lower bound. These multipliers are in the structure `lambda.Variables.variablename.Lower`.

• `Upper` – Lagrange multipliers associated with the variable `UpperBound` property, returned as an array of the same size as the variable. Nonzero entries mean that the solution is at the upper bound. These multipliers are in the structure `lambda.Variables.variablename.Upper`.

• `Constraints` – Contains a field for each problem constraint. Each problem constraint is in a structure whose name is the constraint name, and whose value is a numeric array of the same size as the constraint. Nonzero entries mean that the constraint is active at the solution. These multipliers are in the structure `lambda.Constraints.constraintname`.

### Note

Elements of a constraint array all have the same comparison (`<=`, `==`, or `>=`) and are all of the same type (linear, quadratic, or nonlinear).

## Algorithms

Internally, the `solve` function solves optimization problems by calling a solver:

Before `solve` can call these functions, the problems must be converted to solver form, either by `solve` or some other associated functions or objects. This conversion entails, for example, linear constraints having a matrix representation rather than an optimization variable expression.

The first step in the algorithm occurs as you place optimization expressions into the problem. An `OptimizationProblem` object has an internal list of the variables used in its expressions. Each variable has a linear index in the expression, and a size. Therefore, the problem variables have an implied matrix form. The `prob2struct` function performs the conversion from problem form to solver form. For an example, see Convert Problem to Structure.

For the default and allowed solvers that `solve` calls, depending on the problem objective and constraints, see `'solver'`. You can override the default by using the `'solver'` name-value pair argument when calling `solve`.

For the algorithm that `intlinprog` uses to solve MILP problems, see intlinprog Algorithm. For the algorithms that `linprog` uses to solve linear programming problems, see Linear Programming Algorithms. For the algorithms that `quadprog` uses to solve quadratic programming problems, see Quadratic Programming Algorithms. For the algorithms that `lsqlin` uses to solve linear least-squares problems, see Least-Squares (Model Fitting) Algorithms. For nonlinear solver algorithms, see Unconstrained Nonlinear Optimization Algorithms and Constrained Nonlinear Optimization Algorithms.

### Note

If your objective function is a sum of squares, and you want `solve` to recognize it as such, write it as `sum(expr.^2)`, and not as `expr'*expr`. The internal parser recognizes only explicit sums of squares. For an example, see Nonnegative Least-Squares, Problem-Based.

## Compatibility Considerations

expand all

Errors starting in R2018b

Watch now