solve

Purpose

The main routine for solving optimization problems

Syntax

result = problem.solve
result = problem.solve(th)
result = solve(problem)

Description

The main routine for solving non-parametric (LP, QP, MILP, MIQP) and parametric problems (MPLP, MPQP, PLCP). The result is returned in the appropriate format depending on the problem. The Opt class serves as general wrapper for preprocessing the data involved in optimization, including necessary error checks. Once the data are valid, then are passed to mpt_solve or mpt_solvemp function that calls the appropriate solver without any errorchecks.

For parametric problems it is possible to solve the problem for a particular value of the parameters ../../../../../fig/mpt/modules/solvers/@Opt/solve1.png if provided as an argument th.

Input Arguments

problem

Object of the Opt class that defines the optimization problem to be solved.

Class: Opt

Output Arguments

result

Structure with the date that represents the solution to given problem. For non-parametric problems the solution is returned with the following fields.

Class: struct

result.xopt

Optimal solution for primal variables.

Class: double

result.obj

Objective value.

Class: double

result.lambda

Lagrangian multipliers

Class: double

result.exitflag

An integer value that informs if the result was feasible (1), or otherwise (different from 1)

Class: double

result.how

A string that informs if the result was feasible ('ok'), or if any problem appeared through optimization

Class: char

result

Structure with the date that represents the solution to given problem. For parametric problems the solution is returned with the following fields.

Class: struct

result.xopt

Optimal solution for variables ../../../../../fig/mpt/modules/solvers/@Opt/solve2.png, ../../../../../fig/mpt/modules/solvers/@Opt/solve3.png from PLCP reformulation if the problem was solved using PLCP solver. If the original problem was given as MPLP/MPQP, then this field returns also primal, dual variables, and the objective value for given problem. The solution is given as a collection of polyhedra in the same dimension with certain properties and is given as PolyUnion class. The function data associated to each variable is stored under Function, in particular in res.Set(i).Func{j} where the index ../../../../../fig/mpt/modules/solvers/@Opt/solve4.png corresponds to i-th region and index ../../../../../fig/mpt/modules/solvers/@Opt/solve5.png to j-th function.

Class: PolyUnion

result.exitflag

An integer value that informs if the result was feasible (1), or otherwise (different from 1)

Class: double

result.how

A string that informs if the result was feasible ('ok'), or if any problem appeared through optimization

Class: char

result.stats

Other details from the computation that might be of interest, such as the number of pivots, elapsed time, etc.

Class: struct

Example(s)

Example 1

Solve an LP stored in file sc50b. Load the data
 load sc50b 
 Create the optimization problem using Opt class
 problem = Opt('A',A,'b',b,'Ae',Aeq,'be',beq,'lb',lb,'f',f) 
-------------------------------------------------
Linear program
	Num variables:               48
	Num inequality constraints:  30
	Num equality constraints:    20
	Num lower bounds             48
	Solver:                     LCP
-------------------------------------------------
Solve the problem
 result = problem.solve 
result = 

        xopt: [48x1 double]
      lambda: [1x1 struct]
         obj: -69.9999999999999
         how: 'ok'
    exitflag: 1

Example 2

Create random PLCP problem and solve it Generate data
 H = randn(5); M = sqrt(2)*H'*H; q=randn(5,1); Q = randn(5,2); 
 Provide bounds on the parameters 
 Ath = randn(8,2); bth = 5*ones(8,1); 
 Construct the problem 
 problem = Opt('M',M,'q',q,'Q',Q,'Ath',Ath,'bth',bth); 
 Solve the problem 
 result = problem.solve 
mpt_plcp: 10 regions

result = 

        xopt: [1x1 PolyUnion]
    exitflag: 1
         how: 'ok'
       stats: [1x1 struct]

We can plot the solution
 result.xopt.plot 

../../../../../fig/mpt/modules/solvers/@Opt/solve_img_1.png

Example 3

Formulate linear parametric problem ../../../../../fig/mpt/modules/solvers/@Opt/solve6.png with the help of YALMIP.
 sdpvar x1 x2 th 
 Objective function: 
  obj = x1-2*x2*th+th; 
 Constraints: 
  F = [ x1-x2 >= th; x1>=0; x2>=0; -1<= th <= 1]; 
 Construct an instance of Opt class that represents parametric linear program 
 problem=Opt(F,obj,th,[x1;x2]) 
-------------------------------------------------
Parametric linear program
	Num variables:                2
	Num inequality constraints:   5
	Num equality constraints:     0
	Num lower bounds              2
	Num upper bounds              2
	Num parameters:               1
	Solver:                     PLCP
-------------------------------------------------
Solve the above problem quickly for the point th=0.5 without generating explicit solution
 problem.solve(0.5) 
ans = 

        xopt: [2x1 double]
      lambda: [1x1 struct]
         obj: 1
         how: 'ok'
    exitflag: 1

Verify this result by solving the problem parametrically
 res=problem.solve; 
mpt_plcp: 2 regions
Plot the optimal cost function
 res.xopt.fplot('obj','linewidth',3); 

../../../../../fig/mpt/modules/solvers/@Opt/solve_img_2.png

Evaluate the explicit solution for the point th=0.5
 res.xopt.feval(0.5,'obj') 
ans =

     1

See Also

opt, mpt_solve, mpt_solvemp


© 2010-2013 Martin Herceg: ETH Zurich, herceg@control.ee.ethz.ch