| |
pdco
Purpose
Primal-Dual Barrier Method for Convex Objectives
Syntax
[x,y,z,inform,PDitns,CGitns,time] = ...
pdco( Fname,Aname,b,bl,bu,d1,d2,options,x0,y0,z0,xsize,zsize, Prob );
Description
pdco solves optimization problems of the form
minimize phi(x) + 1/2 norm(D1*x)^2 + 1/2 norm(r)^2
x,r
subject to A*x + D2*r = b, bl <= x <= bu, r unconstrained,
where
phi(x) is a smooth convex function defined by function pdObj;
A is an m x n matrix defined by matrix or function pdMat;
b is a given m-vector;
D1, D2 are positive-definite diagonal matrices defined from d1, d2.
In particular, d2 indicates the accuracy required for
satisfying each row of Ax = b.
D1 and D2 (via d1 and d2)
provide primal and dual regularization
respectively. They ensure that the primal and dual solutions
(x,r) and (y,z) are unique and bounded.
A scalar d1 is equivalent to
d1 = ones(n,1), D1 = diag(d1).
A scalar d2 is equivalent to
d2 = ones(m,1), D2 = diag(d2).
Typically, d1 = d2 = 1e-4.
These values perturb phi(x) only slightly (by about
1e-8) and request
that A*x = b be satisfied quite accurately (to about
1e-8).
Set d1 = 1e-4, d2 = 1 for least-squares problems with bound
constraints.
The problem is then
minimize phi(x) + 1/2 norm(d1*x)^2 + 1/2 norm(A*x - b)^2
subject to bl <= x <= bu.
More generally, d1 and d2 may be n and
m vectors containing any positive
values (preferably not too small, and typically no larger than 1).
Bigger elements of d1 and d2 improve the stability of
the solver.
At an optimal solution, if x(j) is on its lower or upper bound,
the corresponding z(j) is positive or negative respectively.
If x(j) is between its bounds, z(j) = 0.
If bl(j) = bu(j), x(j) is fixed at that value and
z(j) may have
either sign.
Also, r and y satisfy r = D2 y, so that
Ax + D2^2 y = b.
Thus if d2(i) = 1e-4, the i-th row of
Ax = b will be satisfied to
approximately 1e-8. This determines how large d2(i)
can safely be.
External functions
options = pdcoSet; provided with pdco.m
[obj,grad,hess] = pdObj( x, Prob ); provided by user
y = pdMat( name,mode,m,n,x ); provided by user if pdMat
Input Parameters
pdObj is a string containing the name of a function pdObj.m
or a function_handle for such a function
such that [obj,grad,hess] = pdObj(x, Prob) defines
obj = phi(x) : a scalar,
grad = gradient of phi(x) : an n-vector,
hess = diag(Hessian of phi): an n-vector.
Examples:
If phi(x) is the linear function c'x, pdObj should return
[obj,grad,hess] = [c'*x, c, zeros(n,1)].
If phi(x) is the entropy function E(x) = sum x(j) log x(j),
[obj,grad,hess] = [E(x), log(x)+1, 1./x].
pdMat may be an explicit m x n matrix A (preferably sparse!),
or a string containing the name of a function pdMat.m
or a function_handle for such a function
such that y = pdMat( name,mode,m,n,x )
returns y = A*x (mode=1) or y = A'*x (mode=2).
The input parameter "name" will be the string pdMat.
b is an m-vector.
bl is an n-vector of lower bounds. Non-existent bounds
may be represented by bl(j) = -Inf or bl(j) <= -1e+20.
bu is an n-vector of upper bounds. Non-existent bounds
may be represented by bu(j) = Inf or bu(j) >= 1e+20.
d1, d2 may be positive scalars or positive vectors (see above).
options is a structure that may be set and altered by pdcoSet
(type help pdcoSet).
x0, y0, z0 provide an initial solution.
xsize, zsize are estimates of the biggest x and z at the solution.
They are used to scale (x,y,z). Good estimates
should improve the performance of the barrier method.
Prob Tomlab Prob structure. Used as second argument in the
call to pdObj
Printing in pdsco if Prob.PriLevOpt > 0 (default = 1)
Output Parameters
x is the primal solution.
y is the dual solution associated with Ax + D2 r = b.
z is the dual solution associated with bl <= x <= bu.
inform = 0 if a solution is found;
= 1 if too many iterations were required;
= 2 if the linesearch failed too often.
PDitns is the number of Primal-Dual Barrier iterations required.
CGitns is the number of Conjugate-Gradient iterations required
if an iterative solver is used (LSQR).
time is the cpu time used.
See Also
pdcoTL
|
pdcoTL |