Hello,
What is the algorithm that is used in quadprog function solver in Matlab.
Thanks in advance,
MATLAB: Quadratic programming (QP) solver in matlab
qpquadprog function
Related Solutions
MATLAB: Using Branch and Bound Algorithm to solve Discrete Binary Quadratic Programming (QP) problem
Can I use the branch and bound algorithm to solve my problem ((Discrete Binary Quadratic Programming (QP) problem)) in Matlab
No, except in the special case where your QP is also an LP. In that case, use intlinprog.
if no, Does GA is an effective algorithm that can I use to solve my problem?
The only way to find out is to try.
It might be a bit safer to formulate ceq differentiably
ceq=norm(x)^2-1You could also consider providing gradient calculations for the objective function and constraints, since the formulae for those are fairly simple.
Lastly, I would point out that the problem has a closed form solution, which you might consider if your problem dimension is not too large. Below is my implementation, though I warn you that it is fairly new and untried.
function [x,fval] = trustregprob(Q,b,w,doEquality)%Solve trust region minimization problems using eigendecomposition
%
% [x,J] = trustregprob(Q,b,w)
% [x,J] = trustregprob(Q,b,w,doInequality)
%%When doEquality=true (the default), solves
%% Minimize J(x) = x.'*Q*x/2-dot(b,x) such that |x| = w
%%When doEquality=false, solves instead subject to |x|<=w
%%Q is assumed symmetric, but not necessarily p.s.d. Since the solution is based on
%eigendecomposition, it is appropriate mainly for Q not too large. If multiple
%solutions exist, only one solution is returned.
if ~exist('doEquality','var') doEquality=true; endif w<0, error 'Arguemnt ''w'' must be non-negative.'; endif ~w x=zeros(size(b));x=x(:); fval=0; returnendN=size(Q,1);[V,H]=eig((Q+Q)/2);h=diag(H);posdefIneq=all(h>=0) & ~doEquality;if ~isreal(h) || ~isreal(V), disp 'Q not symmetric?' keyboard; endif ~any(b) if posdefIneq x=b; %all zeros
else [lambda,imin] = min(h); x=w*V(:,imin); end if nargout>1, fval=(x.'*(h.*x))/2; endelseif posdefIneq Vt=V.'; g=Vt*b; x=g./h; if norm(x)<w if nargout>1, fval=(x.'*(h.*x))/2 - dot(g,x); end x=V*x; else [x,fval]= trustregprob(spdiags(h,0),g,w); endelse %diagonalize
Vt=V.'; g=Vt*b; hmin=min(h); idx=logical(g); gnz=g(idx); hnz=h(idx); [him,im]=min(hnz); gim=gnz(im); fun=@(lambda) norm( gnz./(hnz-lambda) ) - w; ub=him-abs(gim)/w; i=0; lb=ub-10^i; while fun(lb)>=0 i=i+1; lb=ub-10^i; end lambda=fzero(fun,[lb,ub]); if lambda>hmin x=g; x(idx)=g(idx)./(h(idx)-hmin); cc=w-norm(x)^2; nidx=~idx; nn=sum(nidx); x(nidx)=sqrt(cc/nn); else x=g; x(idx)=g(idx)./(h(idx)-lambda); end if nargout>1, fval=(x.'*(h.*x))/2 - dot(g,x); end x=V*x;end
Best Answer