Pith. sign in

REVIEW 2 major objections 8 minor 22 references

${\varepsilon}$-optimality in reverse convex optimization

T0 review · 2 major / 8 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A point with h(x̄)=0 is an ε-optimal solution of a reverse convex program exactly when every ε′-subgradient of h at x̄ lies in an (αε+ε′)-subgradient of some positive scaling of f.

desk verdict The epsilon-optimality theorem is correct and genuinely new, but the abstract overstates its scope: it only characterizes boundary points with h(x)=0, not all approximate global optima. read the letter →

arxiv 2506.00638 v1 pith:FBKCJGTQ submitted 2025-05-31 math.OC

M. El Maghri , H. Sellak This is my paper
classification math.OC MSC 90C2690C2949J52
keywords Reverseconvexoptimizationε-OptimalityDCvectorε-Efficiencyε-Subdifferentialsapproximateglobaloptimalitynonlinearequalityconstraint
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Reverse convex programs minimize a convex function over a nonconvex feasible region of the form $h(x) \ge 0$, where $h$ is itself convex. The paper establishes the first characterization of approximate ($\varepsilon$-optimal) global solutions for this class of problems. At any boundary point $\bar{x}$ with $h(\bar{x})=0$, the point is an $\varepsilon$-optimum precisely when every $\varepsilon'$-subgradient of $h$ at $\bar{x}$ is also an $(\alpha\varepsilon+\varepsilon')$-subgradient of some scaled objective $\alpha f$, for some $\alpha>0$. The proof converts the reverse program into an unconstrained bicriteria difference-of-convex (DC) problem and applies an $\varepsilon$-efficiency criterion for such problems; at $\varepsilon=0$ the condition reduces to the known exact global-optimality criterion. The same route yields new conditions for reverse programs with additional convex constraints and for nonlinear equality constraints.

What carries the argument

The load-bearing object is the $\varepsilon$-subdifferential of an extended convex function, $\partial_\varepsilon \varphi(\bar{x}) = \{x^* : \varphi(x) \ge \varphi(\bar{x}) + \langle x^*, x-\bar{x}\rangle - \varepsilon \text{ for all } x\}$. The paper embeds the reverse program in the bicriteria DC program $(f,0)-(0,h)=(f,-h)$ and shows, in Lemma 1, that $\varepsilon$-optimality of the scalar problem is equivalent to $\varepsilon$-efficiency of this vector problem, with the boundary condition used for the reverse direction. The decisive transfer theorem states that for difference vector programs, $\varepsilon$-efficiency of $\bar{x}$ is equivalent to the inclusion of every strong $\varepsilon'$-subdifferential of the subtracted map in the appropriate $\varepsilon'$-subdifferential of the first map, for all $\varepsilon'\ge0$; applying this to $F=(f,0)$ and $G=(0,h)$ and using scalarization of convex vector maps produces the scalar inclusion of Theorem 3. The standing hypothesis that all needed $\varepsilon$-subdifferentials be nonempty is automatically satisfied for proper convex lower semicontinuous functions when $\varepsilon>0$, and for $\varepsilon=0$ under a standard closedness qualification.

What would settle it

Compute with $f(x)=x^2+x$, $h(x)=x$, and $\varepsilon=0.2$ on $X=\mathbb{R}$. At the boundary point $\bar{x}=0$ the essential inequality holds ($\inf_X f=-0.25 < f(0)-0.2=-0.2$), yet $x=0.1$ is feasible with $f(0.1)=0.11 \le \inf_{x\ge0}(x^2+x)+0.2=0.2$, so $x=0.1$ is an $\varepsilon$-optimal solution despite $h(0.1)>0$. This shows that no condition confined to the boundary $h(\bar{x})=0$ can characterize all approximate optima of a reverse convex program; any proposed full characterization must account for interior $\varepsilon$-optima, and this example tests whether it does.

Watch

Extended reading notes

Core claim

The paper's central result is Theorem 3: for convex $f$, for $h$ satisfying the hypothesis that every $\varepsilon$-subdifferential of $h$ is nonempty, and for a boundary point $\bar{x}$ with $h(\bar{x})=0$ and $\inf_X f < f(\bar{x})-\varepsilon$, the membership $\bar{x} \in \varepsilon\text{-argmin}_{h(x)\ge 0} f(x)$ is equivalent to the inclusion $\partial_{\varepsilon'}h(\bar{x}) \subseteq \bigcup_{\alpha>0} \partial_{\alpha\varepsilon+\varepsilon'}(\alpha f)(\bar{x})$ holding for every $\varepsilon' \ge 0$. Here $\partial_\delta \varphi$ is the set of linear functionals whose affine minorants stay within tolerance $\delta$ of $\varphi$. The equivalence is proved by rewriting the reverse program as the unconstrained bicriteria DC problem $(f,0)-(0,h)=(f,-h)$, applying a general $\varepsilon$-efficiency criterion for difference vector optimization, and then scalarizing the convex vector map. The boundary condition $h(\bar{x})=0$ is needed for the sufficiency direction, and the strict inequality is used in the necessity direction; together they isolate the nontrivial case the paper calls essential.

Load-bearing premise

The characterization applies only to points on the constraint boundary $h(\bar{x})=0$ with the strict inequality $\inf_X f < f(\bar{x})-\varepsilon$; for $\varepsilon>0$, approximate optima of reverse convex programs can occur strictly inside the feasible region, and the theorem has nothing to say about those points.

Editorial extensions

If this is right

  • At $\varepsilon=0$ with finite convex $f$ and $h$, Theorem 3 reduces to the previously known exact global-optimality criterion, so the new condition is a direct extension of the exact theory.
  • With additional convex inequality constraints $G(x)\le 0$, the same proof gives an $\varepsilon$-optimality criterion in terms of subdifferentials of $\alpha f + \mu\cdot G$, provided a Slater-type or closedness qualification holds.
  • For the nonlinear equality constraint $h(x)=0$, the derived criterion uses subdifferentials of $\alpha f + \beta h$ with $\alpha>0$, $\beta\ge0$; the paper notes this is new even for exact solutions.
  • Because the route runs through the bicriteria representation, future refinements of $\varepsilon$-efficiency conditions for difference vector optimization will automatically supply refinements for reverse convex programs.
  • Under the paper's boundary-reduction lemma, when $f$ and $h$ are finite convex and the objective is strictly better at the unconstrained infimum than on the feasible set, equality-constrained and reverse-constrained $\varepsilon$-optima coincide on the boundary $h=0$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • For $\varepsilon>0$, the boundary hypothesis is a real restriction: approximate optima of reverse convex programs can lie strictly inside the feasible region. A complete characterization of all $\varepsilon$-optimal points would need an extra tolerance on $h$ or a projection step that sends interior candidates to the boundary.
  • The union over $\alpha>0$ can be read as a tolerance-transfer rule: the slack $\varepsilon'$ allowed in the constraint is absorbed as an extra $\varepsilon'$ of tolerance in the objective, rescaled by the same $\alpha$ that weights objective versus constraint in the bicriteria formulation. This suggests a numerical test that scans $\alpha$ and checks subgradient membership rather than solving the
  • The equality-constraint criterion resembles an approximate multiplier rule in which $\beta$ plays the role of a multiplier for the equality; comparing it with standard multiplier-rule conditions could show whether the scale parameter $\alpha$ carries independent information.
  • The construction treats $h$ as a single reverse constraint; extending the same bicriteria idea to several simultaneous reverse constraints $h_i(x)\ge 0$ would require a higher-dimensional ordering cone and would likely yield a vectorized version of the condition.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 8 minor

Summary. This paper develops ε-optimality conditions for reverse convex programs, i.e., problems of the form min f(x) subject to h(x) ≥ 0, where f and h are proper convex extended-valued functions on a real topological vector space. The method converts (ROP) into the unconstrained bicriteria difference program (f, 0) − (0, h) and applies the first author's earlier theory of ε-efficiency in difference vector optimization, together with the paper's Theorem 2, which extends the weak-efficiency criterion of [5] to the Pareto (efficient) ε-efficiency case. Theorem 3, the central result, states that for a feasible point \bar{x} with h(\bar{x}) = 0 and a strict essential inequality inf_X f < f(\bar{x}) − ε, the point is an ε-minimizer of (ROP) if and only if every ε′-subgradient of h at \bar{x} lies in the union over α > 0 of the (αε + ε′)-subdifferentials of αf. Setting ε = 0 recovers Hiriart-Urruty's exact characterization. Theorem 4 extends the criterion to additional convex constraints under Moreau–Rockafellar or Attouch–Brésis qualification conditions, and Corollaries 1–3 treat the nonlinear equality-constrained case. I examined the proof of Theorem 3 in detail and found it internally consistent.

Significance. If the results stand, this is a genuine contribution: to my knowledge it is the first approximate-optimality characterization for reverse convex programs, recovering and extending the exact-characterization literature [10, 14, 15]. The extended-value framework and the explicit use of Moreau–Rockafellar and Attouch–Brésis conditions are real improvements in scope, and the ε = 0 case is correctly reduced to Hiriart-Urruty's condition (Remark 1(d)). The proof of Theorem 3 is checkable: the scalarization steps, the case analysis excluding the degenerate multipliers λ₁ = 0 and λ₂ = 0, and the role of the strict essential inequality are all sound. The paper is also explicit about several limitations (Remarks 1(a)–(d) and 3(b)). The main weakness is that the abstract and Section 4 claim a characterization of all approximate global optimal solutions, whereas Theorem 3 only characterizes the boundary slice h(\bar{x}) = 0 of the ε-argmin; for ε > 0, interior ε-optima exist and are left uncharacterized. This is a fixable framing issue rather than an error in the theorems.

major comments (2)
  1. [Abstract; Section 4 (Theorem 3, Lemma 1)] The advertised scope exceeds what is proved. The abstract promises a characterization of approximate global optimal solutions of reverse programs, and Section 4 states that Theorem 3 completely characterizes the (nontrivial) ε-optimal solutions, but Theorem 3 requires h(\bar{x}) = 0, which is essential in the sufficiency direction through the converse of Lemma 1; that converse is false for h(\bar{x}) > 0 (example: f(x) = x², h(x) = x, ε = 1, \bar{x} = 2 lies in E^e_{(1,0)}(f, −h) but is not in the ε-argmin of f over h ≥ 0). For ε > 0 the ε-argmin of a reverse program can contain interior points: with f(x) = x², h(x) = x − 1, ε = 0.5, the ε-argmin over h ≥ 0 is [1, √1.5], and \bar{x} = 1.1 satisfies inf_X f = 0 < f(1.1) − 0.5 = 0.71 and is not an unconstrained ε-minimizer, yet neither Theorem 3 nor Corollary 2 gives any condition for it (Corollary 2 explicitly covers only the boundary slice ε-argmin_{h=0} f = ε-argmin_{h≥0} f ∩ {h = 0}). Remark 1(a) notes that h(\bar{x}) = 0 is used only for sufficiency, but the paper does not draw the consequence: for ε > 0 the characterization covers only part of the ε-argmin (for ε = 0 the boundary restriction is harmless by Lemma 3). Please narrow the abstract and the Section 4 claim to the boundary part of the ε-argmin and add a remark presenting an interior ε-optimum not covered by the theorem.
  2. [Section 4, proof of Theorem 3] The proofs of both directions of Theorem 3 invoke Theorem 1, quoted from [7], to pass from vector ε-subdifferential membership such as (0, x*) ∈ ∂^w_{(ε, ε′)}(f, 0)(\bar{x}) or z* ∈ ∂^p_{ε+ε′}(f, 0)(\bar{x}) to scalar ε-subdifferential conditions with a multiplier λ ∈ R²₊ \ {0}. Theorem 3 is stated for an arbitrary real topological vector space X, with no local-convexity or lower-semicontinuity assumptions, but scalarization theorems of this type are usually proved via separation of convex sets, and the hypotheses under which [7, Theorem 1] holds are not reproduced in the paper. Please state the exact hypotheses of [7, Theorem 1], and if local convexity of X or additional regularity of f is required there, add the corresponding assumption to Theorem 3 and to Corollaries 1 and 3, whose proofs inherit the same step. This is a verification request rather than a claim of a definite error: I found no counterexample to Theorem 3, but the generality of its statement currently exceeds what can be checked from the manuscript and its cited sources.
minor comments (8)
  1. [Section 2] The symbol ⊓ is used for set intersections ('S ⊓ dom F', 'Y₊ ⊓ −Y₊') without being defined; please define it or use ∩ throughout for readability.
  2. [Sections 1 and 4] The paper calls h 'nonconcave' in the introduction, while the hypotheses and applications require h to be convex (with (H′) typically holding for convex l.s.c. functions, as noted in Remark 1(c)); please use 'convex' consistently to avoid ambiguity.
  3. [Section 4, proof of Theorem 3] In the λ₁ = 0 case the clause '∂_{ε′}h(\bar{x}) ⊇ ∂h(\bar{x}) ≠ ∅ (by (H′))' combines two facts: (H′) applied with ε′ = 0 gives ∂h(\bar{x}) ≠ ∅, and the inclusion ∂h(\bar{x}) ⊆ ∂_{ε′}h(\bar{x}) holds because ε′ ≥ 0; please spell these out separately.
  4. [Section 3, Theorem 2] The weak-efficiency half of Theorem 2 is taken from [5, Theorem 2] and carries the necessity direction of Theorem 3; please state the exact hypotheses of [5, Theorem 2] (space assumptions, pointedness of the ordering cone, convexity of F) so the reader can verify that G = (0, h) under (H′) satisfies them.
  5. [Section 5.2, proof of Corollary 1] The reverse implication of Corollary 1 is handled with 'by the same arguments as for Theorem 4'; since it relies on the qualification-free inclusion in (11) (Remark 2), a few explicit lines would make the proof easier to verify.
  6. [Whole paper] Several displays are garbled in the submitted version (e.g., 'X − →R ∪ {+∞}', 'Min f (x)( h(x) ≥ 0', '∀ϵ′ ≥R2+ 0'); clean typesetting is needed before publication.
  7. [Remark 1(a)] Consider adding to Remark 1(a) the sharpness example f(x) = x², h(x) = x, ε = 1, \bar{x} = 2, which shows that the converse of Lemma 1 genuinely requires h(\bar{x}) = 0.
  8. [Section 2] The proper-efficiency sets E^p_ε are defined but never used in the sequel; a sentence indicating they are included for completeness would help the reader.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Theorem 3 is proved from independent convex-analysis tools, not reduced to its own conclusion.

full rationale

The central characterization is a genuine theorem proved from stated assumptions. Lemma 1 is an explicit implication between boundary epsilon-optimality of (ROP) and vector efficiency of (f,-h); Theorem 2 for difference vector programs is either proved in the paper (efficient case) or cited to El Maghri [5] (weak case); Theorem 1 scalarizes vector subdifferentials. None of these auxiliary results presupposes Theorem 3, and the final condition is not defined in terms of the epsilon-argmin it characterizes. No data are fitted, no parameter is calibrated, and no normalization is imposed that would force the equivalence. The self-citations are load-bearing but independent mathematical tools, not the target claim, so under the hard rules they are evidence rather than circularity. The paper's own Remark 1(a)-(c) and Corollary 2 clearly delimit the boundary assumption h(bar x)=0 and the strict essential inequality inf_X f < f(bar x)-epsilon; the abstract's phrase 'characterize approximate global optimal solutions' is broader than the theorem, since interior epsilon-optima (e.g., f(x)=x^2, h(x)=x-1, epsilon=0.5, bar x=1.1) are not covered. That is a scope overstatement, not a derivation that reduces to its own inputs.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

No free parameters or invented entities. The central theorem rests on three cited convex-analysis results, one of which (Theorem 2 for weak efficiency) is the authors' own prior work; the paper proves the efficient case itself.

assumptions (5)
  • standard math The scalarization Theorem 1 with equality for Y_+-convex vector mappings
    Invoked in the proof of Theorem 3 (Section 4) to pass from vector subdifferential inclusions to scalar ones; cited from El Maghri [7].
  • standard math Theorem 2 for sigma=w, the weak-efficiency characterization of difference vector optimization
    Invoked in the necessity part of Theorem 3; cited from El Maghri [5], not proved in this paper.
  • standard math The Moreau-Rockafellar / Attouch-Brezis epsilon-subdifferential sum and composition rules
    Used in Theorem 4 (Section 5.1) to decompose the epsilon-subdifferential of alpha f + delta_{-R^m_+} composed with G; cited from Zalinescu [20, Theorem 2.8.10].
  • domain assumption Tuy's Lemma 3 asserting argmin_{h=0} f = argmin_{h>=0} f under the essential condition
    Used in Corollaries 2 and 3 to transfer equality-constraint results to reverse results; requires f,h finite convex and -infinity <= inf_X f < inf_{h>=0} f.
  • ad hoc to paper Hypothesis (H') that partial_epsilon h(x) is nonempty for all epsilon >= 0 and all x in dom h
    Stated in Theorem 3; needed to apply Theorem 2. It is not automatic in general Banach spaces for epsilon=0, though the Attouch-Brezis condition implies it.

how reviews work

0 comments
Cite this review

Pith. "Pith review of ${\varepsilon}$-optimality in reverse convex optimization." pith.science (2026). https://pith.science/paper/FBKCJGTQ

@misc{pith2026250600638,
  author       = {Pith},
  title        = {Pith review of: $\varepsilon$-optimality in reverse convex optimization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FBKCJGTQ}},
  note         = {Machine review of arXiv:2506.00638}
}
abstract

We characterize approximate global optimal solutions (${\varepsilon}$-optima) to reverse optimization problems, namely, problems whose non-convex constraint is of the form $h(x) \geq 0$. This issue has not been addressed previously in the literature. Our idea consists of converting the reverse program into an unconstrained bicriteria DC program. The main condition presented is obtained in terms of Fenchel's ${\varepsilon}$-subdifferentials thanks to an earlier result in difference vector optimization by El Maghri. This extends and improves similar results from the literature dealing with exact (${\varepsilon} = 0$) solutions. Moreover, as we consider functions with extended values, our approach also applies to reverse problems subject to additional convex constraints, provided that Moreau-Rockafellar or Attouch-Br\'ezis constraint qualification conditions are satisfied. Similarly, new results for the special case of a nonlinear equality constraint $h(x) = 0$ are also obtained.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages

  1. [5]

    El Maghri, M.: ( ϵ-)Efficiency in difference vector optimization. J. Glob. Optim. 61, 803–812 (2015)

    work page 2015

  2. [7]

    El Maghri, M.: Pareto–Fenchel ϵ-subdifferential sum rule and ϵ-efficiency. Optim. Lett. 6, 763–781 (2012)

    work page 2012

  3. [1]

    In: Barroso, J

    Attouch, H., Br´ ezis, H.: Duality for the sum of convex functions in general Banach spaces. In: Barroso, J. (ed.) Aspects of Mathematics and its Applications, pp. 125–

    work page

  4. [2]

    C.: Complementary geometric programming

    Avriel, M., Williams, A. C.: Complementary geometric programming. SIAM J. Appl. Math. 19, 125–141 (1970)

    work page 1970

  5. [3]

    Bansal, P.P., Jacobsen, S.E.: An algorithm for optimizing network flow capacity under economies-of-scale. J. Optim. Theory Appl. 15, 565–586 (1975)

    work page 1975

  6. [4]

    Ben Saad, S., Jacobsen, S.E.: A level set algorithm for a class of reverse convex programs. Ann. Oper. Res. 25, 19–42 (1990) reverse optimization 13

    work page 1990

  7. [6]

    El Maghri, M.: Pareto-Fenchel ϵ-subdifferential composition rule and ϵ-efficiency. Numer. Funct. Anal. Optim. 35, 1–19 (2013)

    work page 2013

  8. [8]

    El Maghri, M., Laghdir, M.: Pareto subdifferential calculus for convex vector map- pings and applications to vector optimization. SIAM J. Optim. 19, 1970–1994 (2009)

    work page 2009

Show all 22 references
  1. [9]

    Hillestad, R.J.: Optimization problems subject to a budget constraint with economies of scale. Oper. Res. 23, 1091-1098 (1975)

    1975

  2. [10]

    Hiriart-Urruty, J.-B.: Conditions for global optimality 2. J. Glob. Optim. 13, 349–367 (1998)

    1998

  3. [11]

    Springer, Berlin (1990)

    Horst, R., Tuy, H.: Global Optimization. Springer, Berlin (1990)

    1990

  4. [12]

    Kybernetika 21, 428–435 (1985)

    Muu, L.D.: A convergent algorithm for solving linear programs with an additional reverse convex constraint. Kybernetika 21, 428–435 (1985)

    1985

  5. [13]

    Rosen, J.B.: Iterative solution of nonlinear optimal control problems. SIAM J. Control 4, 223–244 (1966)

    1966

  6. [14]

    Strekalovsky, A.S.: Global optimality conditions for nonconvex optimization. J. Glob. Optim. 12, 415–434 (1998)

    1998

  7. [15]

    Tseveendorj, I.: Reverse convex problems: an approach based on optimality condi- tions. J. Appli. Math. Decision Sci. 2006, 1–16 (2006)

    2006

  8. [16]

    Tuy, H.: Convex programs with an additional reverse convex constraint. J. Optim. Theory Appl. 52, 463–486 (1987)

    1987

  9. [17]

    IEEE Trans

    Vidigal, L.M., Director, S.W.: A design centering algorithm for nonconvex regions of acceptability. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 1, 13–24 (1982)

    1982

  10. [18]

    Yamada, S., Tanino, T., Inuiguchi, M.: Inner approximation method for a reverse convex programming problem. J. Optim. Theory Appl. 107, 355–389 (2000)

    2000

  11. [19]

    Ekonomika i Matematitcheskie Metody 16, 1069–1081 (1980)

    Zaleesky, A.B.: Nonconvexity of feasible domains and optimization of management decisions (in Russian). Ekonomika i Matematitcheskie Metody 16, 1069–1081 (1980)

    1980

  12. [20]

    World Scientific, Singapore (2002)

    Z˘ alinescu, C.: Convex Analysis in General Vector Spaces. World Scientific, Singapore (2002)

    2002

  13. [21]

    Zhang, Q.: A new necessary and sufficient global optimality condition for canonical DC problems. J. Glob. Optim. 55, 559–577 (2013)

    2013

  14. [133]

    Elsevier, Amsterdam (1986)

    1986

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.