4
$\begingroup$

Can someone explain me at a high level the difference between an SCP and an SQP to solve a nonlinear (nonconvex) program?

Assume my problem is something like

$$\min\limits_x. \quad f(x)$$ $$s.t. \quad g(x) \leq 0 $$

where both $f$ and $g$ are (in general) nonconvex.

My understanding is that (regardless or trust-region or line-search variants) SCP tackles the problem by forming a convex approximation of the objective $\tilde f$ around the current iterate $x^k$ and similarly linearise the constraints $g(x) \approx \tilde g(x) = g(x^k) + \nabla g(x^k)(x-x^k)$ and solve the the convex subproblem

$$\min\limits_x. \quad \tilde f(x)$$ $$s.t. \quad \tilde g(x) \leq 0 $$

to obtain the next iterate $x^{k+1}$ or at least the direction $d$ such that $x^{k+1} = x^k + \alpha d$.

In the same vein as far as my understanding goes SQP find the next iterate by solving the quadratic problem

$$\min\limits_x. \quad \hat f(x)$$ $$s.t. \quad \hat g(x) \leq 0 $$

where $\hat g = g(x^k) + \nabla g(x^k)(x-x^k)$ and $\hat f(x) = f(x^k) + \nabla f(x^k)d + d B_k d$ where $B_k$ is the Hessian or an approximation of it.

So is the difference between the two methods just the assumed shape of the convex approximation of the objective $f$ ?

Or am I missing some details?

$\endgroup$
4
$\begingroup$

In SCP (a.k.a. SCA), at each outer iteration:

Objective function is replaced by a convex approximation, not necessarily quadratic.

Nonlinear inequality constraints are replaced by convex approximations, not necessarily linear. Nonlinear equality constraints are replaced by linear approximations.

Therefore, at each outer iteration of SCP, a convex optimization problem is solved.

In SQP (a.k.a. SCA), at each outer iteration:

Objective function is replaced by a quadratic approximation (of the Lagrangian), not necessarily convex.

Nonlinear constraints are replaced by linear approximations.

Therefore, at each outer iteration of SQP, a Quadratic Programming (QP) problem is solved, but it is not necessarily convex.

Indeed, there are other possibilities, which correspond to neither SCP nor SQP, such as at each outer iteration, replacing the objective function with a possibly non-convex quadratic approximation, while retaining convex conic constraints.

Whether using SCP, SQP, or some other variant, a key to achieving convergence to something (global convergence to a local optimum or at least stationary point) is use of trust regions or line search. Unfortunately, many people, whose name does not happen to be Stephen Boyd, and without his ability and judgment, implement "crude" SCP with no trust region or line search. This often results in dismal failure, as evidenced by http://ask.cvxr.com/ being littered with such terrible implementations. Most people would be better served using an existing high quality local or global non-convex nonlinear solver. There is a reason such solvers are more than 10 lines long.

$\endgroup$
3
  • 2
    $\begingroup$ "Most people would be better served using an existing high quality local or global non-convex nonlinear solver." Pretty much the truth in all areas where mathematical software is used. People should just be using the high-quality implementations that are out there, rather than re-inventing the wheel... $\endgroup$ Feb 6 at 20:38
  • $\begingroup$ Can you suggest an "high-quality open-source local non-convex nonlinear solver" ? $\endgroup$
    – FooBant
    Feb 9 at 8:36
  • 2
    $\begingroup$ IPOPT is a high quality open source local non-convex nonlinear solver. $\endgroup$ Feb 9 at 14:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.