DualSolve

Purpose

Solve linear programming problems when a dual feasible solution is available.

DualSolve solves problems of the form

${\begin{array}{cccccl}\min \limits _{x}&f(x)&=&c^{T}x&&\\s/t&x_{L}&\leq &x&\leq &x_{U}\\&&&Ax&=&b_{U}\\\end{array}}$

where $x,x_{L},x_{U}\in \mathbb {R} ^{n}$ , $c\in \mathbb {R} ^{n}$ , $A\in \mathbb {R} ^{m\times n}$ and $b_{U}\in \mathbb {R} ^{m}$.

Finite upper bounds on x are added as extra inequality constraints. Finite nonzero lower bounds on x are added as extra inequality constraints. Fixed variables are treated explicitly. Adding slack variables and making necessary sign changes gives the problem in the standard form

${\begin{array}{ccccl}\min \limits _{x}&f_{P}(x)&=&c^{T}x&\\s/t&{\hat {A}}x&=&b&\\&x&\geq &0&\end{array}}$

and the following dual problem is solved,

${\begin{array}{ccccl}\max \limits _{y}&f_{D}(y)&=&b^{T}y\\s/t&{\hat {A}}^{T}y&\leq &c\\&y&urs&\end{array}}$

with $x,c\in \mathbb {R} ^{n}$ , $A\in \mathbb {R} ^{{\hat {m}}\times n}$ and $b,y\in \mathbb {R} ^{m}$.

Calling Syntax

[Result] = DualSolve(Prob)

Description of Inputs

Prob	Problem description structure. The following fields are used:
	QP.c	Constant vector.
	A	Constraint matrix for linear constraints.
	b_L	Lower bounds on the linear constraints.
	b_U	Upper bounds on the linear constraints.
	x_L	Lower bounds on the variables.
	x_U	Upper bounds on the variables.
	x_0	Starting point, must be dual feasible.
	y_0	Dual parameters (Lagrangian multipliers) at x _0.
	QP.B	Active set B_0 at start: B(i) = 1: Include variable x(i) is in basic set. B(i) = 0: Variable x(i) is set on its lower bound. B(i) = -1: Variable x(i) is set on its upper bound.
	Solver.Alg	Variable selection rule to be used: 0: Minimum reduced cost (default). 1: Bland's anti-cycling rule. 2: Minimum reduced cost. Dantzig's rule.
	PriLevOpt	Print Level.
	optParam	Structure with special fields for optimization parameters, see TOMLAB Appendix A. Fields used are: MaxIter, wait, eps_f, eps_Rank and xTol.

Description of Outputs

Result	Structure with result from optimization. The following fields are changed:
	x_k	Optimal primal solution x.
	f_k	Function value at optimum.
	v_k	Optimal dual parameters. Lagrange multipliers for linear constraints.
	x_0	Starting point.
	Iter	Number of iterations.
	QP.B	Optimal active set.
	ExitFlag	Exit flag: 0: Optimal solution found. 1: Maximal number of iterations reached. No primal feasible solution found. 2: Infeasible Dual problem. 4: Illegal step length due to numerical difficulties. Should not occur. 6: No dual feasible starting point found. 7: Illegal step length due to numerical difficulties. 8: Convergence because fk >= QP.DualLimit. 9: xL(i) > xU(i) + xTol for some i. No solution exists.
Solver	Solver used.
SolverAlgorithm	Solver algorithm used.
	c	Constant vector in standard form formulation.
	A	Constraint matrix for linear constraints in standard form.
	b	Right hand side in standard form.

Description

When a dual feasible solution is available, the dual simplex method is possible to use. There are three rules available for variable selection. Bland's cycling prevention rule is the choice if fear of cycling exist. The other two are variants of minimum reduced cost variable selection, the original Dantzig's rule and one which sorts the variables in increasing order in each step (the default choice).

M-files Used

cpTransf.m

See Also

lpSimplex