0

I have two optimization problems $min G(x), Ax=b$ and $min F(x), Ax=b$.

Assume continuity, differentiability, convexity of $F(x)$ and $G(x)$.

What is the relationship between optimal solutions of $F(x)$ and $G(x)$ ?

vallev
  • 81
bissi
  • 64
  • 11
  • 1
    This is, unfortunately, an incredibly broad question and I don't think there's an easy way to provide an answer. – ConMan Aug 07 '23 at 00:24
  • @ConMan you are welcome to make any limiting assumptions you would like – bissi Aug 08 '23 at 08:31
  • One equivalent condition is $x$ is an optimal solution to both problems iff both $DF(x)-DG(x) \in \text{Rng}A^T, DF(x)+DG(x) \in \text{Rng}A^T$. Not really sure this is much better than the original problem though, just a different pair of problems to solve. – jet457 Aug 08 '23 at 21:11
  • @jet457 by DF do you mean derivative of F? And why is the second of your conditions true? – bissi Aug 09 '23 at 07:47
  • @bissi By DF I mean the gradient of F. The second condition comes from noting $F$ will be minimized at a point iff that point is a critical point on the constrained surface defined by $Ax=b$. This means $DF$ is in the orthogonal complement of the null space of $A$, which is $\text{Rng}A^T$. The same argument goes through for $G$. The second condition holds iff $DF(x), DG(x) \in \text{Rng}A^T$ by adding and subtracting and adding. – jet457 Aug 09 '23 at 23:09

3 Answers3

3

Because the constraints are equal, your question seems to be equivalent to asking "how are $F$ and $G$ related?" and since they are arbitrary, there is no straightforward answer.

For every point in the constraint set ( $x$ such that $Ax=b$ ) you can assign a value depending on how close they are to minimizing your objective function ( $F(x)$ or $G(x)$). Geometrically you may think of, in the simplest 2d case, bending a flat solution region such that the highest point is your optimum. However the only relationship between two highest points in such bending is precisely dependent on the problem definition.

Your question is sensible to ask, given that in the real world the objective function may not be fixed (think of changing costs or priorities in some business setting).

What you may be referring to may be addressed by "sensitivity analysis in convex optimization".

vallev
  • 81
1

One non-exhaustive example, which is not specific to the structure of your problem, is $G(x) = \alpha F(x) + \beta$, for some $\alpha >0$ and $\beta \in \mathbb{R}$.

rafexiap
  • 658
1

If $G$ is a (positive) monotonic transformation of $F$ — i.e. if there exists some strictly increasing function $h$ such that $G=h\circ F$ — then the set of minimizers will be the same for both problems (this is regardless of the form of the constraint and the other properties of $F$ and $G$).

smcc
  • 5,694
  • Please explain what is a (positive) monotonic transformation. – bissi Aug 15 '23 at 10:29
  • 1
    It is defined above. $G$ is a monotonic transformation of $F$ if there exists a strictly increasing function $h$ such that $G=h\circ F$, i.e. such that $G(x)=(h\circ F)(x)=h(F(x))$ for all $x$ in the domain of $F$. One example of a monotonic transformation is given in rafexiap's answer. In rafexiap's answer, we have $h(y)=\alpha y+\beta$, with the condition $\alpha>0$ ensuring that $h$ is strictly increasing. – smcc Aug 15 '23 at 10:46
  • Understood. Can you give some necessary or sufficient conditions which ensure such a transformation (i.e., the existence of an h)? For example, say $G$ is a log and $F$ is a quadratic. Taylor's series might offer something? – bissi Aug 16 '23 at 08:31