3
$\begingroup$

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)$.

  • 0
    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?2012-08-19

1 Answers 1

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.

  • 0
    $min max f$, minimization with respect to which variable and maximization with respect to what?2017-03-07