0
$\begingroup$

I am looking for the name of a sequential optimization, if that technique makes indeed any sense and exists.

Given the solution $x^*$ to a non-linear non-convex problem \begin{equation*} \begin{aligned} & \underset{x}{\text{minimize}} & \mathbf{f(x)}\\ & \text{subject to} & A_1\mathbf {x} \leq \mathbf {b}_1 \end{aligned} \end{equation*} with $f(x)$ non-linear and non-convex, is it reasonable to look at the quadratic problem \begin{equation*} \begin{aligned} & \underset{x}{\text{minimize}} & \frac{1}{2}\mathbf {x} ^{\mathrm{T} }Q\mathbf{x} +\mathbf{c}^{\mathrm {T} }\mathbf {x} \\ & \text{subject to} & A_2\mathbf {x} \leq \mathbf {b}_2 \\ & &\lVert \mathbf{x-x^*} \rVert_2 \leq \epsilon \end{aligned} \end{equation*} and if so, is there a name for looking for the solution of one optimization problem that is in some sense (not necessarily in the sense of the Euclidean norm) close to the solution of another. The practical background is that I would like to use different solvers for each problem. I understand that the solution $\overline{x}$ of the quadratic problem is not a global solution. Is there a name under which this has been studied?

$\endgroup$
1
  • $\begingroup$ Are you just referencing Sequential Quadratic Programming, cite: Griva, Nash and Sofer: Linear and Non-Linear Optimization p573. Note this algorithm implemented in SciPy as method "SLSQP", sequential least squares quadratic programming. $\endgroup$ – Attack68 Aug 2 '18 at 23:53
2
$\begingroup$

I'm not sure what you're exactly looking for? Perhaps of use:

  • Gradient descent ($Q = \frac{1}{\alpha} I$) or Newton's method ($Q = \nabla^2 f$) can both be interpreted as minimizing successive quadratic approximations of a function.
  • A method where you repeatedly update your answer is called an iterative method.
  • Constraining the feasible set to some ball around a point (not necessarily the solution) is related to trust region methods.
  • A comprehensive reference on numerical optimization is Nocedal and Wright.
$\endgroup$
2
  • 2
    $\begingroup$ Could also mention Sequential Quadratic Optimization $\endgroup$ – noob2 Aug 2 '18 at 22:48
  • $\begingroup$ Sequential Quadratic Optimization is what I was looking for, all the other answers were also very instructive. $\endgroup$ – hps Aug 4 '18 at 16:32

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.