4

I am trying to find the saddle point of a quadratic form: $$f(\mathbf{x})=\mathbf{x}^\mathrm{T} \mathbf{A}\mathbf{x}+\mathbf{x}^T\mathbf{b}+\mathbf{c}$$ using a minimization/maximization-like algorithm. Is there such solution method available somewhere? I want to avoid the $\nabla\cdot f(\mathbf{x})=\mathbf{0}$ approach because I later want to add inequality constraints. The point that I am seeking is a maximum in one direction and a minimum in all other directions.

edit The above problem comes from the following formulation: imagine an externally forced one degree-of-freedom oscillator whose displacement $u(t)$ satisfies the equation of motion: $$m\ddot{u}+ku=f \cos \omega t$$ where $m$ and $k$ are respectively the mass and stiffness of the oscillator; $f$ and $\omega$ defines the forcing term. I would like to use a modified version of Hamilton's principle to find the forced steady state solution (the transient part is ignored). Since I am interested in periodic orbits only, the sought (periodic) solution satisfies: $$\delta\bigl(\int_0^T \frac{1}{2} m \dot{u}^2- \frac{1}{2} k u^2+fu\cos \omega t \,\mathrm{d}t\bigr)=0\quad;\quad u(0)=u(T)\quad;\quad \dot{u}(0)=\dot{u}(T)\qquad(1)$$ where $T=2\pi/\omega$. As the Hamilton's principle says, the solution is an extremum of the underlying functional, not a minimum necessarily.

I now want to find an approximation of $u(t)$, as for instance: $$u(t)=a_1+a_2\cos\omega t + a_3\sin \omega t\qquad (2)$$ where $a_1$, $a_2$, and $a_3$ have to be found. I just have to plug (2) in (1) and find the point $(a_1,a_2,a_3)$ that makes the functional stationary. For reasons that are not given here, I would like to reformulate this in a $\max\min$ problem since I know for this specific case that the solution is a saddle point, ie a maximum along $a_1$ and a minimum along $(a_2,a_3)$. The quadratic form given at the top of the message comes from plugging (2) in (1) with $\mathbf{x}=(a_1,a_2,a_3)$.

pluton
  • 1,209
  • 2
  • 11
  • 30
  • How would you define the saddle point of an inequality-constrained problem? –  Aug 19 '12 at 18:18
  • Let us note $\mathbf{x}={x_0,x_1,\dots,x_n}$ then the problem would be: find $\max_{x_0}\min_{x_1,\dots,x_n}; f(\mathbf{x})$ under linear inequality constraints $\mathbf{G}\mathbf{x}-\mathbf{q}\leq 0$. Not sure if it makes sense but it would be something like that. – pluton Aug 19 '12 at 19:04
  • Could you look for local extrema where $\nabla f = 0$ and then also consider the boundary of the constraint region? Compare and choose the point you desire? At a local extreme you can determine the nature of the critical point $p$ ( $\nabla f (p)=0$) by shifting variables at the point to write $f(y) = f(p)+y^TMy$. The eigenvalues of $M$ indicate if the point is min/max or saddle or trough. – James S. Cook Aug 19 '12 at 19:23
  • It may be doable when $n$ is small but I'd say that it would quickly becomes intractable as $n$ increases. Knowing that the solution of the unconstrained problem is a saddle is no the difficulty. The difficulty is about how to formulate the problem with linear inequalities within a $\max\min$ strategy. The first question is: is the formulation correct? – pluton Aug 19 '12 at 19:32

1 Answers1

1

The problem you specify, $$\min f(x)=x^TAx+x^Tb$$ subject to $$Gx-q\leq 0$$ is a quadraric programming problem. See the wiki page for solution procedures.

For the saddle point, rather than the minimum, the conjugate residual method is developed to find this point.

Daryl
  • 5,598
  • Thanks for the hint on the "conjugate residual method": it looks interesting. The problem I was specifying was not a $\min f$, in the sense of finding a minimum of $f$, but rather a $\min\max f$ (not sure about the relevance of the notation) in the sense of finding saddle points. – pluton Aug 21 '12 at 13:46
  • By the way, do you know if this conjugate residual method generalizes to cases with inequality constraints? – pluton Aug 21 '12 at 14:01
  • @pluton I've not studied the algorithm in detail, but I suspect that it may be able to be generalised to use with constraints. Look up null space method, which can be used to effectively remove the constraints. – Daryl Aug 21 '12 at 21:32
  • I think that the null space method is also called the "active-set" method. Anyway, I'll have a look. I'm surprised that there is nothing available in usual soft packages. I'm suspecting something wrong in the formulation. Thanks – pluton Aug 22 '12 at 03:26
  • $min max f$, minimization with respect to which variable and maximization with respect to what? – user85361 Mar 07 '17 at 14:01