CODEWITHSUNDEEP
matlaboptimization
Yuval Atzmon
Yuval Atzmon

Reputation: 5945

How to solve a quadratically constrained optimization in MATLAB

I would like to solve efficiently the following minimization problem

min(w^TBw + w*g), s.t. ||w||_2 <= Delta., B is Positive Definite

This is equivalent to a "trust region step" [More' & Sorenson], which MATLAB doc say that it is used for the fsolve function.

However, the fsolve function, evaluates the function F(x) = 0, and not the minimization problem i am seeking to solve.

Any idea how to use matlab's implemeted "trust region step" for my problem?

I thougt about trying to solve the first derivative of the Lagrangian of my minimization problem. but I am not sure it will be equivalent. i.e. using fsolve with F(x) = [(B+lambda*I)w +g; w^Tw - Delta] where x = [w; lambda]

Thank you in advance Yuval

Upvotes: 1

Views: 247

Answers (2)

Nitish
Nitish

Reputation: 7196

You should use CG Steilhaug. Anything else is an overkill.

You can refer to any standard optimization textbook for details but the algorithm is specifically designed to solve this problem.

The code is also available here.

Upvotes: 0

tmyklebu
tmyklebu

Reputation: 14215

fsolve solves systems of nonlinear equations. It can use a trust region method to do so. However, this is not what you're asking about; you're asking how to solve a specific trust-region subproblem with high accuracy. (Your TRS is special because the objective function is convex. TRSes can still be solved quickly if B is indefinite.)

You can find the unconstrained minimiser of your objective as -B^{-1} g/2. If this has norm at most Delta, you're done. Otherwise, you want to find the smallest lambda >= 0 such that -(B + lambda I)^{-1} g/2 has norm at most Delta. There's a very fast iteration that finds an appropriate lambda using a few Cholesky factorisations, but I can't recall what it is.

Upvotes: 1

Related Questions