Efficient Bisection Projection to Ensure Neural-Network Solution Feasibility for Optimization over General Set
Authors: Enming Liang
Minghua Chen
Venue: ICML 2025 poster (2025)
Keywords: Neural Network
Constraint
Feasibility
Projection
Interior Point
Primary area: general_machine_learning->everything_else
TL;DR: An efficient bisection-based projection scheme to ensure NN solution feasibility over general compact sets.

Abstract: Neural networks (NNs) have emerged as promising tools for solving constrained optimization problems in real-time. However, ensuring constraint satisfaction for NN-generated solutions remains challenging due to prediction errors. Existing methods to ensure NN feasibility either suffer from high computational complexity or are limited to specific constraint types.
We present Bisection Projection, an efficient approach to ensure NN solution feasibility for optimization over general compact sets with non-empty interiors.
Our method comprises two key components:
(i) a dedicated NN (called IPNN) that predicts interior points (IPs) with low eccentricity, which naturally accounts for approximation errors;
(ii) a bisection algorithm that leverages these IPs to recover solution feasibility when initial NN solutions violate constraints.
We establish theoretical guarantees by providing sufficient conditions for IPNN feasibility and proving bounded optimality loss of the bisection operation under IP predictions. 
Extensive evaluations on real-world non-convex problems demonstrate that Bisection Projection achieves superior feasibility and computational efficiency compared to existing methods, while maintaining comparable optimality gaps.

Efficient Bisection Projection to Ensure Neural-Network Solution Feasibility for Optimization over General Set
Enming Liang'
Minghua Chen 12
Abstract
Recent advancements in machine learning (ML) have in- troduced innovative strategies for solving CO problems in real-time, including the end-to-end (E2B) solution map- ping (Amo22). the scheme (CCC+21), the generative modeling framework (LC2),, and hybrid approaches (KFVHW2I). One pow- erful idea is to leverage the universal approximation ability LLPS93) to predict high-quality solutions given input parameters, significantly reducing computation time compared to iterative solvers. For instance, NNs have been trained to solve non-convex optimal power flow problems in grid operations, achiev- ing 2-4 orders of magnitude speedup over iterative solvers PZCC19 GWWM19 PZCZ20 FMVH20) ZB20 DRK20).
Neural networks (NNs) have emerged as promis- ing tools for solving constrained optimization problems real-time. However, ensuring con- straint satisfaction for NN-generated solutions re- mains challenging due prediction errors. Exist- ing methods to ensure NN feasibility either suf- fer from high computational complexity or are limited to specific constraint types. We present Bisection Projection, an efficient approach to en- sure NN solution feasibility for optimization over general compact sets with non-empty interiors. Our method comprises two key components: (i) a dedicated NN (called IPNN) that predicts interior points (IPs) with low eccentricity, which naturally accounts for approximation errors; (ii) bisec- tion algorithm that leverages these IPs to recover solution feasibility when initial NN solutions vio- late constraints. We establish theoretical guaran- tees by providing sufficient conditions for IPNN feasibility and proving bounded optimality loss of the bisection operation under IP predictions. Extensive evaluations on real-world non-convex problems demonstrate that Bisection Projection achieves superior feasibility and computational efficiency compared to existing methods, while maintaining comparable optimality gaps.
(L20) iterative
of neural networks (NNs) (HSW89
Despite the minor optimality loss and significant speedup of NN-based methods, guaranteeing the feasibility of NN solutions with respect to problem constraints, which is im- portant to safe-critical scenarios, remains a challenge due to inherent NN prediction errors. Existing methods to ensure NN feasibility either suffer from high computational com- plexity or are limited to specific constraints. See Sec [2 discussions on related works.
In this paper, we develop Bisection Projection (BP) as simple yet efficient scheme to recover NN solutions fea- sibility over a (fairly) general compact set with a non- empty interior, beyond previous works on linear (WZG+23 ZPCL23) convex (THH23), or ball-homeomorphic con- straints (LC223 LCL224 Our contributions are follows:
1. Introduction
D In Sec. introduce the BP framework for ensuring NN solution feasibility. It comprises two steps: (i) a dedi- cated NN (called IPNN) that predicts interior points (IPs) of low eccentricity; (ii) an efficient bisection algorithm that leverages these IPs to recover solution feasibility.
Constrained Optimization (CO) plays an essential role in various engineering fields, such as supply chain, transporta- tion, and power systems. To solve CO problems, iterative algorithms, such interior point methods, have been devel- oped and embedded within commercial solvers like Gurobi. These tools are designed to tackle CO with high precision, providing high-quality solutions. However, they can be slow for real-time applications with tight time constraints.
D In Sec. establish theoretical guarantees by provid- ing sufficient conditions for IPNN feasibility and proving bounded rccentriicty--ellted optimality loss of the bisection operation under IP predictions.
'Department of Data Science. City University of Hong Kong, Hong Kong "School of Data Science, The Chinese University of Hong Kong (Shenzhen), China. Correspondence to: Minghua Chen <minghua.chene @ @iittu.edutttttt minghua @ www...cu.cc.c.c..e.eeeeeee
> In Sec. 6. we carry out extensive experiments over convex and non-convex problems to evaluate the performance of BP. The results show that it outperforms existing methods in feasibility and run-time complexity while achieving similar optimality losses.
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Bisection Projection
Table Existing work for ensuring NN solution feasibility for continuous constrained optimization prohlems.
Constraint Setting
Performance Guarantee
Existing Work
(refer to Sec. 2 for details)
Input dependent
Non-liness equality
Non-convex inequality
Feasibility ensuring
Optimality bound
Low run-time
Penalty training
Orthogonal Proj.
V X (linear)
X
Preventive learning
(linear)
X
Gauge mapping
x (linear) of
x (linear)
X
DC3
X
Gauge Proj.
X
x (linear)
x (convex)
Homeomorphic Proj.
(BH')
Bisection Proj.
1
BH indicates the constraint set is homeomorphic to ball, which includes all compact convex sets and part of non-convex sets.
2. Related Work
can be constructed. The convex combination of vertices and rays can represent feasible points of linear constraints (FC20 ZSRZ2I) For general compact constraint sets, the probabilistic transformer utilizes collected feasible samples to ensure feasibility (KZLD21). However, scalability re- mains a challenge due to the exponential growth in required samples with increasing dimensionality.
Machine Learning (ML)-driven optimization has emerged as an active research field (PZC19) KFVHW21 cCC+21 Amo22). A fundamental challenge is ensuring neural net- work (NN) solution feasibility under input-dependent con- straints. For basic constraints like simplexes or boxes, fea- sibility can be enforced through activation functions (e.g.. Softmax or Sigmoid). For complex constraints, various approaches have been developed, as summarized in Table [
Projection approach. To enforce solution feasibility, or- thogonal/L2 projection often employed. However, solving projection problems either by iterative solvers or equivalent optimization layers (AKI7 19 CDB+2) WZG 23 ZYZ 24) tensive. Alternative strategies include gradient- based meth- ods (c.g., DC3 (DRK20)) and L20 models (HWFGY21
Equality constraints. Linear equations and certain non- linear equations with constant ranks, can be embedded as neural network layers by predicting a subset of variables and solving for the remaining variables to satisfy the equality constraints Aba66 PZC19 DRK20
over complex constraints is computationally in-
LCL23 DWDS23).
HFL + 22). However, those projection-analogouu methods do not guarantee feasibility for general constraints.
Warm-start approach. The NN predictions serve warm-start points for iterative solvers, potentially reduc- ing the number of iterations required to reach the opti- mal/feasible solution (Die19 19k SHAS24 24).
Homcomorphic Projection ensures NN solution feasibility over ball homeomorpho (BH) constraints by constructing homeomorphism between the constraint set and unit ball using invertible NN, allowing efficient projection via bisection (CL22 LCL44).
Penalty training. To reduce constraint violations of pre- dicted solutions, various penalty functions, such as quadratic penalties. have been incorporated into the NN loss function (COMB19 PZC/20 ZB20 FMVH20). Additionally, inte- gration of the Karush- -uuckr (KKT) conditions as equality constraints has been explored to refine NN perfor- mance NC2Ial) ZCZ21). However, these methods do not ensure solution feasibility.
Gauge function. These works utilize gauge/Minkowski functions (BM08) to conduct projection or constrain NN output. For fixed convex sets, given an interior point, gauge projection can be applied find feasible boundary so- lutions (Mha22). Similar approaches have been applied in the following works (LBGH23 THH23 KU23 LM23 TVH24). The gauge function can also be used to construct bijection, known as gauge mapping, to constrain the NN
Provable training/veriiiiaaton. A Preventive Learning framework is proposed for ensuring linear constraint fea- sibility without post-processing in (ZPC+20) (ZCCL23) which adjusts inequality constraints to account for NN pre- diction errors. A NN editing method applies parametric linear relaxation to find NN weights and ensure output feasi- bility over the polytope (T224). Additionally, NN verifica- tion techniques can also be applied to assess the worst-case performance after training (VQLC20) μAYKJ22 LAL*21)
output within a polytope (TZ22a TZ22b LKM23 LLC23).
In summary, existing approaches either have limited appli- cability or incur significant computational overhead. We propose Bisection Projection a simple yet efficient frame- work to ensure NN solution feasibility over (fairly) general compact sets while maintaining bounded optimality loss. While algorithmically related to gauge-based methods, our method offers broader applicability and provides rigorous theoretical analysis.
Set regresentaion/appooinattioo To guarantee feasibil- ity, inner approximation of the original constraint set
2

---

Bisection Projection
3. Setting and Open Issue
Constraints
We consider the following continuous optimization problem
min [(x, 0) s.t. I E Co:
(I)
ZER
where: x E Cp C R" denotes the decision variable and 0 e C Rd represents the input contextual parameter. Without loss of generality, the input domain and constraint set Co are assumed be compact. The objective function f(x,, #) Lipschitz continuous and potentially non-convex, with optimal solution denoted as zi arg min [f(zz 0)}. The constraint set Co is specified by set of inequalities: g(2, 0) [91 (z, .)......................... Irince (z, 0)] < O.
infeasibility
Optimal solution
Interior point
Prediction region
Figure I. NN predicting optimal solution (on boundary) may incur infeasibility; NN predicting interior points accommodates errors.
optimal solution often lies on the constraint boundary with active constraints, making NN feasibility particularly challenging - Any positive prediction enrors can push NN predictions outside of feasible regions.
While equality constraints are not explicitly included in this formulation, certain classes of equality constraints constant rank can be embedded as neural network layers and satisfied exactly (Aba69) 1ee13] P7CT9 DRK20 LCL23 DWDS23). We do carry out simulations for problems with linear/nonlinear equality constraints in Sec. and provide detailed discussion in Appendix
Current approaches, as summarized in Table | are either computationally intensive or fail provide performance guarantees over general input-dependent constraint sets. To date, ensuring NN solutions feasibility for constraint op- timization in under Assumption [ bounded optimality loss and low computational complexity, remains an open and pressing challenge.
while maintaining
We further specify the constraint set as follows, beyond those discussed related works in Sec.
v0 E O, (i) the constraint set Cy has positive measure] 1 (ii) the set-valued mapping A + Cg continuous in the Hausdorff metric
Assumption 1.
4. The Bisection Projection Framework
We propose Bisection Projection (BP) "project" infeasi- ble NN solutions onto the constraint set with low run-time complexity and minor optimality loss. As detailed in Sec. this framework applies bisection to iteratively narrow the gap between infeasible points and one interior point (IP) to find feasible solutions. In Sec. 4.2 to bound the optimal- ity loss induced by bisection, we introduce the concept of eccentricity for IP and establish its connection projection distance. In Sec. 4.3 to reduce the inference time for find- ing IPs under varying inputs, we train another NN, denoted as IPNN, to predict IPs in real time.
We remark that assumption (i) guarantees the existence of interior points, which is fundamental the bisection approach detailed in Sec. 4.1 and assumption (ii) en- sures continuous deformation of the constraint set with respect to the input parameter, enabling the learning of continuous mappings from inputs to interior points as dis- cussed in Sec. 4.3 These assumptions deliberately ex- clude unusual sets (e.g., vertices of hypereube) from consideration in continuous optimization problem, abling rigorous algorithmic development and theoretical analysis. Despite these restrictions, Assumption enncom- passes a broad class of constraint sets, including linear, con- vex, and ball-homeomorphic sets studied in existing works WZG+23 (ZPCL23
4.1. Bisection with Interior Points
LCL.23 THH223 (CL22)..
Given an infeasible NN prediction To & Co and an IP 28 Cg. we can "project" Ta to Co as:
Open issue. As discussed in Sec. 2 various NN-based meth- ods have demonstrated success in solving constrained opti-
ig = DBPP(GGA BP (2)0 a a (io - x&) + xzz
(2)
mization problems, offering low run-time complexity and small optimality gaps (PZC19 DRK20 PVH23 HCL24)..
where a* E [0. 1] leads to Za E OC, and 0C, is the bound- ary of Cg. As illustrated in Fig. [ the "projected" solution ăø is located on the straight line segment connecting the infeasible solution T9 and IP 2g. We note that there could be multiple ax and corresponding Sa. given pair of 7e and zÿ. To determine one such a", we employ the bisection method, as elaborated in Alg. [ We initiate by drawing a straight line connecting 7e with an IP xg. This segment is guaranteed to intersect the boundary of the feasible region
We denote one such trained NN predictor as F(O)
Rd + R" and define its prediction error as épre supaee [I] (()) 1. Due to the error (pres ensuring NN solution feasibility is non-trivial. As illustrated in Fig.
li.e. Vo E int(Ca), 3e > 0 such that B(r, e) S Co, where B(a,e) e) is the open ball centered at z with radius Pi.e., Vo, O, Ye 0, 38 > such that du (Co, Co,) whenever ||0 1000loll foll < 6, where du denotes the Hausdorff distance.
3

---

Bisection Projection
NN for Optimal Solution
NN solution
Projected solution
0
Constrained Optimization
T e
Interior point
min f(I, !) #ERn
bisection
NN for Interior Point
s.t. x E Co
I
Figure 2. The Bisection Projection framework: we apply one NN to predict a solution for the constraint optimization problem (near- optimal but may not be feasible), and another NN to predict interior points (robust and feasible); then apply bisection (Alg. 1 to recover solution feasibility.
at least once. Subsequently, we apply the bisection algo- rithm to iteratively pinpoint one feasible solution along this segment toward the constraint boundary. Such a bisection operation is applicable to general compact sets with non- empty interiors (Assumption J. and also efficient with linear convergence rate and maintains low per-iteration computational cost involving feasibility checks.
Algorithm 1 Bisection for Feasibility.
Input: an NN prediction ie & Cs and an IP x E Co
I: set total iteration K, or 0, and au
2: for n = 1: K do
3: bisection: Om = (a) + a.))
4: if æ + am (Tg - xz) Cp then
increase lower bound: at f am
We note that the concept of projection projection-analoguus operation with IPs is non-sophisticated, and some works also leverage similar ideas to "project" infeasible prediction MMha2 [HH23] KU23 LM23 TVH24 [CL224) see Ap- pendix A. for details of these methods. However, these works primarily focus fixed convex constraint sets where single IP can be computed offline for online deployment. Two critical gaps remain in the literature: (i) theoretical analysis of how IP selection influences the quality of pro- jected solutions; (ii) developing efficient schemes to obtain IPs for general input-dependent constraint sets in real-time.
Remark 1.
else
decrease upper bound: a, < am
8: end if
9: end for
Output: feasible solution àog aq (āo x²) + 2 E Co
When r = Ucg eccentricity quantifies the variation in point-to-buundary distances, effectively measuring the in- terior point's centrality within the feasible region. For in- stance, the center of a unit ball achieves zero eccentricity. This measure directly relates to the optimality loss in bisec- tion projection - lower eccentricity corresponds to smaller bisection-induced optimality gaps.
Our work advances these fundamental issues by: (i) we first introduce the eccentricity of IP and establish its connection to the bisection-indunt We then employ another NN, called IPNN, to efficiently pre- dict IPs under varying inputs for input-dependent constraint in Sec. |.3 We also present a comprehensive performance analysis in Sec.
projection distance in Sec. 4.2 (ii)
When I C ÖCg is a subset of the boundary, eccentricity pro- vides localized characterization focused on specific bound- ary regions of interest. Particularly, when T encompasses the projected solutions of neural network predictions with bounded errors, this local eccentricity measure yields tighter bounds on the optimality loss compared to the global eccen- tricity measure (i.e., E(rü, 1')) s E(rq, 122) if S l22).
4.2. Minimum-Eccenntrienn IP for Bisection
We first define the eccentricity of IP, which is crucial for bounding the dnecction-indcee projection distance.
Next, we establish the connection between eccentricity mea- and the bisection-induced projection distance.
Definition 4.1 (Eccentricity of IP). For compact set Co satisfying Assumption I with non-empty interior, the ec- centricity for one IP xg E C. with respect to a compact subset of boundary r C OCg is defined as:
Proposition 4.1. Let ãs F(O) be an infeasible NN predic- tion with bounded prediction error [[ -=²]
S Cprei ie BP xa)) be the projected solution with IP x E Co: Then, the worst-case projection distance is bounded as:
Ex I') A max Ily - -=8ll min lly - x8l1
yET
PEr
(3)
max EoEB(s7
|100 - -BP(io -z\il S <pre + E(ag To),
4

---

Bisection Projection
where Blugg fpre) represents the NN prediction region, con- taining all possible NN predictions with an error Cprei and To [BP ki), Vīg E Bl Epre) \ Ca} defines sub- set of the constraint boundary, containing all "projected" infeasible NN predictions.
Algorithm 2 IPNN Training.
Input: Input data {0:] E O, unit ball samples {
1: Training epoch E, batch size B, IPNN vb
Initialize robust margins y 10-2
3: for e: 1 E do
4: Sampling batched data: (0,),-m1 )
The complete proof and a geometric illustration are included in Appendix [. We remark that the applicability of this bound extends to general compact sets under Assumption [ Further, informed by Prop. 4.1, we seek to find an IP with minimized eccentricity (MEIP) with respect to constraint boundary ÖCg to reduce the worst-case bisection-induced projection distance for any infeasible NN solutions.
5: Loss: ((,,,) - Σ P P +7.04, 01)-
-- x-lo((7)
6: Model update: (v, 7) - Adam ((),
7: end for
Output: Trained IPNN sb.
However, computing MEIP exactly presents significant challenges even for convex constraints, due to the non- convex boundary constraints in (26). To address this, we can bound the eccentricity by finding a surrogate central poin such as the Chebyshev center (BBV04), defined as the IP maximizing the minimum distance to the boundary: max { min lly - =EIl}, which is also equivalent to mini- agECs yeaC,
We design the following loss function for IPNN training:
(()((),,)) = Eu [x(2 + 7 u., 0)] - À log(7) (5)
where the IP prediction is denoted as 25 = (0). The first loss term, P(z + u, 0) = [1 + u, 0) I|. de- notes the constraint violation under the perturbed prediction with random samples u from a unit ball, and its expecta- tion represents the penalty for the inscribed ball constraint B(z 7) S Co in 4 The regularization term, log(r). represents the radius maximization objective in and is adjusted by a positive coefficient X.
mizing the second term of the eccentricity in Def. 4.1
Thus, this Chebyshev center serves a relaxation for MEIP and provides an upper bound on the eccentricity. Moreover, it admits a tractable reformulation as the center of the largest Euclidean ball that can be inscribed in Cg. which eliminates the non-convex boundary constraints in (
We also note that the loss function is analogous to the ad- versarial learning techniques like randomized smoothing (CRK19) with Gaussian perturbations and fixed y, ensur- ing the predicted IPs maintain a robust margin 7 from the constraint boundary. Finally, to optimize the aver- age performance across different input parameters, we uniformly sample 0 E O and minimize the total loss as C(v, 7) = EE (C()()) r)]. The IPNN training procedure outlined in Alg. innolves sampling input parameters and unit vectors u and follows regular NN training procedures.
max 26 EC
7, s.t. B(xg. S Co
(4)
However, computing the Chebyshev center for constraint set Co under varying input f poses significant computational challenges, particularly when rapid response times are essen- tial for online applications. To overcome this limitation, we develop a learning- based approach in the following section. We train another neural network (denoted as IPNN) offline to learn the mapping from input parameters to the Cheby- shev centers, thereby reducing the computational burden of finding interior points during real-time deployment.
5. Performance Analysis
In this section, we present a comprehensive analysis of the BP framework: (i) the sufficient conditions for IPNN train- ing for producing feasible IP under any input parameter in Sec. (ii) the optimality loss and run run-time complexity for the bisection operation in Sec. [.2) We also discuss the con- nection to existing approaches (TZ22b LCL23 THH23
4.3. Interior Points Neural Network (IPNN) Training
Sec.5.22
We utilize another neural network, denoted as IPNN vt-:): Rd -> R", to predict the IPs. We remark that such a con- tinuous mapping from input to some IPs of interest exists under Hausdorff continuity specified in the Assumption [
and IPNN training guarantees in Sec. 5.3
5.1. Sufficient Conditions for IPNN Feasibility
*We consider minimize eccentricity E {xr. aCs) with respect to the entire constraint boundary, which is prediction-agnostic and provides robust performance across different NN predictors over the same constraint set. In the appendix C we also discuss prediction-aware eccentricity minimization when NN predictions or optimal solution data are given in advance.
Proposition 5.1. Let D be an ro-covering dataset for input domain as Q C U B(O,,ro): the constraint violation function G(z, 0) max {9, {)} with Lipschitz LG.
and La, for x and B. respectively; and IPNN vé is La-- Lipschitz continuity for O. if G(v()))) 0,) + LL.eLore + I.gorro & 0 = 1,.', NN, then V0 O (0) E Co.
*We provide comprehensive review of different center defini- tions in Appendix A.3 to justify the design of MEIP.
5

---

Bisection Projection
The complete proof is included in Appendix B.2
Prop. 5.1
which is mitigated by the Chebyshev center-informed loss function in ( (iii) The error from finite bisection decreases exponentially with each additional iteration.
establishes sufficient conditions for the trained IPNN to gen- erate IPs for unseen input parameters. These conditions require two key components: (i) the IPNN must achieve fea-
The algorithm's 's run-time complexity, i.e., the number of arithmetic operations, is primarily affected by the number of bisection steps (K) and the complexity of checking feasibil- ity at each step (G). Such a feasibility checking procedure is also known as membership oracle, which has been exten- sively analyzed in (Mha22 LBGH23). Further, for common convex sets, the bisection projection has a closed-form com- putation provided in (THH23).
sibility over finite training samples (i.e., ((v(()))) 0:) & 0) a condition readily satisfied in practice, as demonstrated by our empirical results in Sec. 6 The robust penalty loss in effectively minimizes constraint violations for perturbed IP predictions. (ii) to extend feasibility guarantees to the entire input space 0 E O the IPNN must maintain robust margin for IP prediction that accounts for generalization errors, which can be bounded by Lipschitz conditions (i.e., Lo + Lg,ore).
5.3. Discussions
While direct verification of these Lipschitz constants re- mains computationally intractable, they provide valuable insights into the relative difficulty of guaranteeing feasibil- ity across different constraint types. Specifically, a smaller covering radius r. is required for: "thin" constraint sets (i.e., small robust margin) or highly variable constraint geome- tries (i.e., large LG For such challenging constraints, a smaller covering radius necessitates a larger number of training samples (N), scaling as (()dia to ad- equately cover the input space.
Connection to existing works: As discussed in Sec. 2 the BP framework is algorithmically related to the homeomor- phic projection (LCL23) LCL24) and gauge function-based methods (T/22b) Mha22 THH23). The following proposi- tion reveals the connection between the BP framework and some existing schemes.
Proposition 5.2. The homeomorphic projection (LCL23) with gauge mapping (TZ22a) is equivalent to bisection projection over a convex set. The Gauge projection Mha22 (H1112)) is equivalent to bisection projection with a fixed IP.
We also remark that this condition is based on the Lipschitz- based worst-case analysis, while the empirical experiment shows that IPNN trained over less than 10,000 uniform sample inputs already induces feasible IP prediction under unseen input parameters for high- dimensioalii problems.
The complete proof is included in Appendix A.2 Thus, the bisection projection framework provides unified view for some existing projection-analogous approaches over convex sets. Mcanwhile, we highlight the theoretical analysis and application scenario for BP works on general compact sets under Assumption [T] It also achieves better performance in feasibility and speedup as shown in Sec. 6
5.2. Optimality and Run-time Complexity for Bisection
Theorem 1. Given constraint set Co under Assumption | an infeusible NN prediction Te with bounded error to the optimal solution zi as |:0 z1لl S Epro. and valid IP
Availability and guarantees of IPs. Several existing NN feasibility approaches rely on IPs, including gauge mapping TTZ22a TZ22b] LKM23), gauge projections (TH223 KU23 LM23 TVH24), and homeomorphic pro-
prediction xğ E Ca produced by IPNN, after executing K
steps of bisection shown in Alg. 1 We obtain a solution i:k
satisfying the following:
(i) it is guaranteed to be feasible, i.e., 2 E Co:
jections (CL23 LCL24). While our BP framework sim- ilarly utilizes IPs, it advances the state-of-the-an through: general constraints (Sec. 3), eccentricity- based optimal- ity bound (Sec. and IPNN loss design (5). Despite these advances, the guarantees for NN-based IP findings depend on NN training by minimizing penalty-based loss functions. While exact convergence has been established for over- werr-parameterized NNs (SLL88 LZB22), The general con- vergence analysis remains challenging for practical scenar- ios involving finite-size networks and non-convex penalties and warrants future exploration.
(ii) it has a bounded optimality gap as || - x2ll S
pre +
2- + dCom)
(iii) the run-time complexity is O(KG), where G is the complexity of checking the feasibility of a solution.
The complete proof is included in Appendix B.3 First, given an interior point, the bisection in Alg. I consistently returns a feasible solution. The optimality loss of the re- turned feasible solution is mainly bounded by three factors: the initial NN prediction error for the optimal solution, the eccentricity measure of the predicted IP, and the error due to finite-step bisection. (i) The initial prediction error is typically small, thanks to the NN's universal approximation capabilities. (ii) The eccentricity represents the upper bound of the deviation caused by employing bisection with IPs,
Extension to Multiple Interior Points. The BP framework naturally extends to multiple IPs. Specifically, we can per- form bisection from multiple IPs and select the projected point with the minimal projection distance. A detailed dis- cussion of this extension provided in Appendix A.5
6

---

Bisection Projection
6. Numerical Experiments
shown in Fig. 5
We provide comprehensive visualizations
from Fig. 12 in Appendix
We first consider a toy example to visualize the training and testing performance of our framework in Sec. 6.1] We then carry out comprehensive simulations validate the efficiency of BP against existing methods on various con- strained optimization problems in Sec. 6.2 We also demon- strate the efficacy of key design and parameters in the BP framework through sensitivity analysis in Sec. 66.3 The detailed experimental setting and problem formulations are provided in D
6.2. NN feasibility for Constrained Optimization
We apply the BP framework four benchmark convex problems (QP, convex QCQP, SOCP, and SDP) and two non-convex real-world scenarios, including optimal power flow problems in grid operation (AC-OPF) and joint chance-constrained problems in inventory management (JC- CIM). We follow the established parameter configuration and sampling strategy from available codes in previous works (DR220) LCL23). We first train an NN predictor to learn the mapping from input parameters to the optimal solutions in existing works (DRK20), where the training and testing data are generated by randomly sampling the input parameter and solve the corresponding optimal solutions through iterative solvers as ground truth DRK20 LCL233.
Dataset:
6.1. Illustrative Toy Examples
100
1000 of Penurood
IP leeetbiiity mie (76)
0014
0.2
000
Baselines: (i) Optimizer: for convex optimization, we
use MOSEK to solve the optimal solution. For JCC-IM, we adopt its scenario-based approximation and solve it by MOSEK (PAS09); For AC-OPF problems, we adopt PY- POWER as the specialized solver (ZMSII); (ii) NN: it directly maps the input parameter to the solution without post-processing: (iii) WS: The infeasible prediction of NN is regarded as the warm-start initialization for the iterative solver; (iv) Proj: the infeasible predicted solution by NN processed by orthogonal projection and solved with the iter- ative solver; (v) D-Proj: this is proposed in DC3 (DRK20), which applies gradient descent with equality completion to minimize the constraint violation; (vi) H-Proj: the home- omorphic projection are applied to the infeasible predic- tions (LCL23); (vii) B-Proj: we apply bisection in Alg. [] with predicted IPs to recover the feasibility. To ensure the feasibility of equality constraints, we utilize predict-then- reconstruct techniques (PZCZ20) DRK20), as detailed in Appendix A.4 Note that some baselines shown in Table [ are not included due to their limited applicability.
Trainin Baration
Training Boration
Figure 3. Perturbed penalty loss (left) and IPNN prediction feasi-
bility rate (right) during training.
Robest
2000
4200
0000
8000
10003
2000
.000
60:0
5000
10000
Training leeration
Training Eeration
Figure 4. Robust margin log(7) during training (left) and esti- mated occentricity (right), caleulated by the gap between max- imum and minimum IP-to-boundary distances.
Just
Table 2 summarizes our experimental results across six con- straint optimization problems, revealing several key insights. The BP framework consistently achieves 100% feasibility for initially infeasible NN predictions while offering up to four orders of magnitude speedup compared to standard projection approaches, all while maintaining competitive op- timality loss. Direct NN outputs cannot guarantee complete feasibility due to prediction errors that may push solutions outside the constraint set. Iterative solver-based methods such as warm-start and orthogonal projection ensure fea- sibility with minimal optimality loss but incur substantial computational overhead (exceeding 400 seconds for QCQP problems). The gradient-based D-Proj method, though flexi- ble across different constraint sets, fails to guarantee feasibil- ity and exhibits high sensitivity to step size selection. While
Intarir poira
Irinssible ponta
Projeded point
Figure 5. BP with IPNN prediction given test input parameters,
To validate that the proposed training algorithm for IPNN can indeed produce low-eccentricity points or approximated Chebyshev centers, we consider a non-convex quadratic con-
straint set C.- = {x x Qix y, x bb b, I 0, where the input parameter is defined as = {Q, q, 6) 1,, 6).
We train IPNN over such constraint sets and visualize training and testing performance. Our experiments yield the following observations: (i) Minimizing the penalty loss suc- cessfully improves feasibility over test input parameters, as shown in Fig. 3 (ii) Maximizing the robust margin indeed reduces the eccentricity of IPNN predictions, as shown in Fig. 4 (ii)) After training, bisection projection with IPNN- predicted "central" IPs incurs low projection distance, as
7

---

Bisection Projection
Table 2. Performance comparison for constrained optimization problems.
Feasibility rate (%)
Solution opt. (%)
Objective opt. (%)
Pred.
Post. cost (+)
Feasibility rate (%)
Solution
Objective opt. (5)
Pred. cost (+)
Post.
Method
cost (s)
opt. (%)
cost (s)
QP (m=400, 100, Ray 100. 100. Thoey Thmeq=1000 100)
QCQP (n=400, 100, =00=000 100, Tiney 100)
NN
80.8
2.26
0.97
92.0
3.91
3.26
NN+WS
100
1.81
0.79
5.37
100
3.58
3.01
434
NN+Proj
100
2.26
0.97
5.23
100
3.91
3.26
0.0014
0.0017
NN+D-Proj
80,9
2.26
0.97
11.1
92.3
3.91
3.26
7.23
NN+H-Pro Proj
100
16,49
15.42
0.763
100
3,95
3.31
0,413
NN+B-Proj
100
2.31
1.00
0.0160
100
3,94
3.30
0.0162
SOCP (m=400) 100, Raj 1000 1000)=100)
SDP (n=40x400, d=40, Bay na Mana==1)
NN
89.6
1.24
0.55
58.0
2.10
2.74
NN+WS
100
1.10
0.50
136
100
1.20
1.57
105
NN+Proj
100
1.24
0.55
128
100
2.10
2.74
158
0.0015
0.0017
NN+D-Proj
95.5
1.24
0.55
5.03
58.0
2.10
2.74
236
-N-H-Proj
100
1.25
0.56
0.571
100
31.51
33.67
0,958
NN+B-Proj
100
1,25
0.56
0.0272
100
2.26
2.96
0.0163
AC-OPF (v==76,, d=400, fiey 400, - 1002))
JCC-IM (m=400, d=100,
Mey Mincq = 100,
NN
94.0
0.15
0,001
84.5
1.94
1,40
NN+WS
100
0.14
0.001
4.73
100
1.64
1.21
48.3
NN+Proj
0,25
0.002
14.1
100
1.94
1.40
128
0.251
0.0013
NN+D-Proj
96.5
0.15
0.001
14.9
84.5
1.94
1.40
81.1
NN+H-Proj 100
0.63
0.042
1.32
100
10.24
10.39
0.876
NN+B-Proj 100
0.15
0.001
1.13
100
1.98
1,45
0.193
Evaluation metries: (i) Feasibility: Percentage of feasible solutions among 1.024 test instances, where feasibility requires satisfying
equality and inequality constraints within tolerance = 10 10:;;; (ii) Optimality: Mean absolute percentage error (MAPE) between output and optimal solutions for both decision variables and objective values: (iii) Running-time- Total inference time comprising NN predictions and post-proee post-processing for constraint satisfaction. Iterative solvers are parallelized when computing projections or warm-start solutions. 2 d and n represent the dimensions for input parameter 6 and output decision æ, respectively. and Tamoq denote the number of equality and inequality constraints, respectively.
H-Proj also achieves 100% feasibility, it introduces larger optimality gaps and is less efficient than B-Proj, particu- larly for high-dimensional constraint sets (e.g., SDP), due to complex invertible NN (INN) training and computationally intensive INN calculations during inference.
Prop. 5.1 establishes that increasing both training sample size (N) and robust margin (7) enhances IPNN's feasibil- ity guarantees on unseen inputs. We empirically validate this relationship by evaluating three IPNN variants: trained with maximizing % trained with fixed y, and trained with- out Y, under varying training sample sizes. Fig. O demon- strates that maximizing the robust margin 7 improves out- sampee feasibility (over 1024 test inputs) compared to fixed or zero-margin approaches. These improvements are particularly pronounced under limited training data scenar- ios, confirming the effectiveness of proposed Chebyshev center-informed loss function 5)
In summary, across both convex and non-convex constraint sets, BP demonstrates superior performance by achieving perfect fcasibility or significantly reduced computational complexity while maintaining comparable optimality loss.
6.3. Sensitivity Analysis for BP Framework
We investigate the impact of key components in the BP framework validate their effectiveness.
Impacts of y on optimality of projected solution (Fig.
Impacts of 7 on out-of-sample feasibility (Fig. 6):
nobe load: 0.14
nobat lond: 0.48
Piotaabily Danshly Dansilt
Noy Food Tral-y
0.25
Na
Foed
Probebblyy Dersls
600
Foasibiity Fate (%)
0315
0310
/caabblity
60e
No y
Flod
No y
Fxod
Projection Distance (1-narm)
Projection Distance (1-nam)
Figure 7. Distribution of projection distances for IPNN trained with and without y over QP (left) and JCC-IM (right).
Num training samples (N)
Num training samples (N)
Figure 6. Feasibility rates over unseen test instances for QP (left)
We conducted an ablation study to evaluate the effectiveness of incorporating eccentricity minimization (approximated
and JCC-IM (right) under varying training sample sizes N.
8

---

Bisection Projection
by maximizing ?) on the projection loss. We generated 10,000 infeasible test instances by random Gaussian sam- pling with varying variance magnitudes (noise levels shown in (i.. For each infeasible point, we applied bisection projection using three IPNN variants: trained with maximiz- ing y, trained with fixed y, and trained without 7.
bisection stepsize (e.g., 3 0.1 instead of the standard B = 0.5), which modifies the midpoint calculation to am = 3- on + (1 B) Qu. This more conservative ap- proach guides the solution trajectory incrementally from the infeasible prediction toward the feasible boundary, typically resulting in an intersection point closer to the original neural network output.
Fig shows the distributions of projection distances (mea- sured between infeasible points and their respective pro- jections). The results demonstrate that our IPNN (trained with 7) produces smaller projection distances, confirming the theoretical bounds established in Prop. [4.1 This improved projection quality directly translates to bet- ter optimality preservation when correcting infeasible NN predictions.
While this strategy better preserves the quality of initial predictions, it necessitates additional iterations due to the smaller stepsize. This trade-off between solution quality and computational efficiency should be considered based on the specific application requirements and constraint geometry.
Scalability on constraint dim. and decision dim.: We further remark on the BP framework's 's scalability based on large-scale problems in Table 2 For joint chance con- straints, where constraint dimension grows linearly with sampled scenarios, iterative solver-based approaches face memory limitations (NS06). For AC-OPF in large-scale power grids, non-linear power balance and branch flow con- straints incur high computational complexity for existing solvers (ZMSTT). Our bisection methods require only con- straint checking per iteration, with GPU-based batch pro- cessing further accelerating these calculations.
Impacts of number of bisection steps (Fig. 8
JCCIM
Biseston gap (%)
Running time (ms)
Bicecton gap (56)
5 3 8
Num Disectioo step (8)
Num of bisection stop (8)
7. Conclusion and Limitation
Figure& 8. Effect of the number of bisection steps (B) on optimality gap and running time for QP (left) and JCCIM (right).
We introduce Bisection Projection, an efficient scheme to project infeasible NN predictions onto general compact con- straint sets through bisection. We establish the connection between the eccentricity of interior points (IPs) and pro- jection distance, then employ IPNN to efficiently predict IPs. Our theoretical analysis provides sufficient conditions for IPNN feasibility and proves bounded optimality loss under IP predictions. Extensive simulations demonstrate that bisection projection outperforms existing methods in feasibility and efficiency with comparable optimality.
We investigated how the number of bisection steps during inference affects both solution quality and computational efficiency. As shown in Fig. g and in accordance with Theorem [ the optimality gap decreases exponentially as the number of bisection steps increases. Concurrently, the running time exhibits linear growth due the sequential nature of the computation, continuing until reaching the convergence threshold.
Notably, our experiments demonstrate that for real-time ap- plications, only a small number of bisection steps (typically 5-10) are sufficient to achieve well-coneerged feasible solu- tions, offering an excellent trade-off between solution qual- ity and computational efficiency. This confirms the practical utility of our approach in time-sensitive decision-making contexts.
Our framework has several limitations, suggesting future research directions: (i) extending BP to discrete constraints such as mixed-integer problems for broader applicability, (ii) jointly optimizing interior point selection and bisection trajectory to further reduce optimality gaps, (iii) and exploit- ing grblem-speciff structures like symmetry and sparsity to design NN/IPNN to improve training efficiency.
Impacts of bisection stepsize on optimality (Fig. 19
A Acknowledgements
As illustrated in Fig. 2 when multiple intersections exist between the projection ray and the feasible set boundary, the bisection algorithm may converge to any of these inter- section points. While this phenomenon did not occur in our benchmark optimization problems, it remains a theoretical concern for constraint sets with complex geometries.
This work is supported in part by General Re- search Fund from Research Grants Council, Hong Kong (Project No. 1 11200223), a Collaborative Research Fund from Research Grants Council, Hong Kong (Project No. C1049-24G), an InnoHK initiative, The Government of the HKSAR, Laboratory for AI-Powered Financial Technologies, and a -henzhen-Hong Kong-Macan Sci-
To address potential convergence to boundary points dis- tant from the initial prediction, we may employ a reduced
9

---

Bisection Projection
ence & Technology Project (Category C, Project No. SGDX200205:01122000266 The authors would also like to thank the anonymous reviewers for their helpful comments.
[COMB19] Richard Cheng, Gábor Orosz, Richard M Murray, and Joel W Burdick. End-to-end safe reinforce- ment learning through barrier functions for safety- critical continuous control tasks. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pages 3387-3395, 2019.
Code Availability
Code for data generation and model training is available at Github
[CRK19] Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In international conference on machine learning, pages 1310-1320. PMLR, 2019.
Impact Statement
[Die19] Frederik Diehl. Warm-starting ac optimal power flow with graph neural networks. In 33rd Confer- ence on Neural Information Processing Systems (NeurIPS 2019), pages 1-6, 2019.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here.
[DRK20] Priya L Donti, David Rolnick, and J Zico Kolter. De3: A learning method for optimization with hard constraints. In International Conference on Learn- ing Representations, 2020.
References
[AAB* + 19] Akshay Agrawal, Brandon Amos, Shane Barrait, Stephen Boyd, Steven Diamond, and Zico Kolter. Differentiable convex optimization layers. Ad- vances in neural information processing systems, 32, 2019.
[WDS223] Shutong Ding, Jingya Wang, Yali Du, and Ye Shi. Reduced policy optimization for continuous control with hard constraints. Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[FMVH20] Ferdinando Fioretto, Terrence WK Mak. and Pascal Van Hentenryck. Predicting ac optimal power flows: Combining deep learning and lagrangian dual meth- ods. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 630-637, 2020.
[Aba69] Jean Abadie. Generalization of the wolfe reduced gradient method to the case of nonlinear constraints. Optimization, pages 37-47, 1969.
[AK17] Brandon Amos and J Zico Kolter. Optnet: Differ- entiable optimization as layer in neural networks. In International Conference on Machine Learning, pages 136-145. PMLR, 2017.
[FNC20] Thomas Frerix, Matthias NieBner, and Daniel Cre- mers. Homogeneous linear inequality constraints for neural network activations. In Proceedings of the IEFF/CVF Conference on Computer Vision and Pattern Recognition Workshops, pages 748-749, 2020.
[Amo22] Brandon Amos. Tutorial amortized optimization for learning optimize over continuous domains. arXiv preprint 220i::2222200665,, 2022.
[GWWM19] Neel Guha, Zhecheng Wang, Matt Wytock, and Arun Majumdar. Machine learning for ac opti- mal power flow. arXiv preprint arXiv: 2019.
[9ak19] Kyri Baker. Learning warm-start points for ac opti- mal power flow, 2019 IEFE 29th International Workshop on Machine Learning for Signal Process- ing (MLSP). 2019.
IGXW 24] Xi Gao, Jinxin Xiong, Akang Wang. Jiang Xue, Qingjiang Shi, et al. Ipm-Istm: A learning-based in- terior point method for solving nonlinear programs. Advances in Neural Information Processing Sys- tems, 17:122291-1122999 2024.
[BBV04] Stephen Boyd, Stephen P Boyd, and Lieven Vanden- berghe. Convex optimization. Cambridge university press, 2004.
[BM08] Franco Blanchini and Stefano Miani. Ser-theoretic methods in control, volume 78. Springer, 2008
[HCL24] Wanjun Huang, Minghua Chen, and Steven Low. Unsupervised lcarning for solving ac optimal power flows:
Design, analysis, and experiment. IEEE Transactions on Power Systems, 2024.
[C Tianlong Chen, Xiaohan Chen, Wuyang Chen, Howard Heaton, Jialin Liu, Zhangyang Wang, and Wotao Yin. Learning optimize: A primer and a benchmark. arXiv preprint arXiv:2103.12822 2021.
[HFL*22] Howard Heaton, Samy Wu Fung, Alex Tong Lin. Stanley Osher, and Wotao Yin. Wasserstein-basee projections with applications to inverse problems. SIAM Journal on Mathematics of Data Science, 4(2):581-60) 2022.
[CDB*21 Bingqing Chen, Priya L Donti, Kyri Baker, Zico Kolter, and Mario Bergés. Enforcing policy feasibil- ity constraints through differeentialee projection for energy optimization. In Proceedings of the Twelfth ACM International Conference on Future Energy Systems, pages 199-210, 2021.
[HSW89] Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are univer- sal approximators. Neural networks, 2(5):359-366. 1989.
10

---

Bisection Projection
[HWFGY21] Howard Hcaton, Samy Wu Fung, Aviv Gibali, and Wotao Yin. Feasibillity based fixed point networks. Fixed Point Theory and Algoritiuns for Sciences and Engineering, 2021(1):1-19, 2021.
[LLC25] Xinpeng Li, Enming Liang, and Minghua Chen. Gauge flow matching for efficient constrained gen- crative modcling over general convex set. In ICLR 2025 Workshop on Deep Generative Model in Ma- chine Learning: Theory, Principle and Efficacy, 2025.
[HZRS16] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 770- 778, 2016.
[LLPS93] Moshe Leshno, Vladimir Ya Lin, Allan Pinkus, and Shimon Schocken. Multilayer feedforward net- works with a nonpolynomial activation function can approximate any function. Neural networks, 6(6):861-867, 1993.
[KFVHW2I] James Kotary, Ferdinando Fioretto, Pascal Van Hen- lenryck, and Bryan Wilder. End-to-end constrained optimization learning: A survey. arXiv preprint arXiv:2/03, 16378, 2021.
[LM23] Meiyi Li and Javad Mohammadi. Toward rapid, optimal, and feasible power dispatch through generalized neural mapping. arXiv preprint arXiv:2311.0488 2023.
[KU23] Andrei Konstantinov and Lev Utkin. new computationally simple approach for implementing neural networks with output hard constraints. In Doklady Mathematics, volume 108, pages S233- S241. Springer, 2023.
[LZB22] Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Loss landscapes and optimization in over over- perrpaarameterized non-linear systems and neural networks. Applied and Computational Harmonic Analysis, 59:85-116, 2022.
[KZLD21] Anastasis Kratsios, Behnoosh Zamanlooy, Tianlin Liu, and Ivan Dokmanić. Universal approximation under constraints is possible with transformers. In International Conference on Learning Representa- tions, 2021.
[MH 19] Daniel K Molzahn, Ian A Hiskens, et al. A survey of relaxations and approximations of the power flow equations. 2019.
[LAL*21] Changliu Liu, Tomer Arnon, Christopher Lazarus, Christopher Strong, Clark Barrett, Mykel Kochen- derfer, et al. Algorithms for verifying deep neural networks. Foundations and Trends@ in Optimiza- tion, 4(3-4);244 404, 2021.
[Mha22] Zakaria Mhammedi. Efficient projection-fiee online convex optimization with membership oracle, In Conference on Learning Theory, pages 53 5314-5390. PMLR, 2022.
[LBGH23] Zhou Lu, Nataly Brukhim, Paula Gradu, and Elad Hazan. Projection-free adaptive regret with mem- hership oracles. In International Conference on Algorithmic Learning Theory, pages 1055-1073. PMLR, 2023.
[NC21a] Rahul Nellikkath and Spyros Chatzivasilciadis. Physics informed neural networks for ac optimal power flow. arXiv preprint arXiv:2110.0267.. 2021.
[LC23] Enming Liang and Minghua Chen. Generative learning for solving non-convex problem with multi- valued input-solution mapping. In The Twelfth Inter- national Conference Learning Representations, 2023.
[NC21b] Rahul Nellikkath and Spyros Chatzivasilciadis. Physics-informed neural networks for minimising worst-case violations in de optimal power flow. In 2021 IEEE International Conference on Commu- nications. Control, and Computing Technologies for Smart Grids (SmarGridConmm) pages 419-424 IEEE, 2021.
[LCL23] Enming Liang, Minghua Chen, and Steven H. Low. Low complexity homcomorphic projection to en- sure neural-network solution feasibility for opti- mization over (non-)convex set. In International Conference on Machine Learning. PMLR, 2023.
[NS06] Arkadi Nemirovski and Alexander Shapiro. Sce- nario approximations of chance constraints. Proba- bilistic and randomized methods for design under uncertainty, pages 3 3-47, 2006.
[LCL24] Enming Liang, Minghua Chen, and Steven H. Low. Homcomorphic projection to ensure coural-networt solution feasibility for constrained optimization. Journal of Machine Learning Rsearch, 2024.
[NSW22] Deanna Needell, William Swartworth, and David P Woodruff. Testing positive semidefiniteness using linear measurements. In 2022 IEFE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 87-97. IEEE, 2022.
[Lee13] John M Lee. Smooth manifolds. In Introduction to smooth manifolds, pages 1-31. Springer, 2013.
[LKM23] Meiyi Li, Soheil Kolouri, and Javad Mohammadi. Learning to solve optimization problems with hard linear constraints. IEEE Access, 2023.
[NW99] Jorge Nocedal and Stephen J Wright. Numerical optimization. Springer, 1999.
[PAS09] Bernardo K Pagnoncelli, Shabbir Ahmed, and Alexander Shapiro. Sample average approxima- tion method for chance constrained programming: theory and applications. Journal of optimization theory and applications, 142(2):399-416, 2009.
[LLC24] Chenghao Liu, Enming Liang, and Minghua Chen.
Characterizing resnet's universal approximation ca- pability. In Forty-ftrst International Conference on Machine Learning, 2024.

---

Bisection Projection
[PCZL222] Xiang Pan, Minghua Chen, Tianyu Zhao, and Steven Low. Decpopf: feasibility-optiiizzd deep neural network approach for ac optimal power flow problems. IEEE Systems Journal, pages 42-47, 2022.
[VQLC20] Andreas Venzke, Guannan Qu, Steven Low, and Spyros Chatzivasilciadis. Learning optimal power flow: Worst-case guarantees for neural networks. In 2020 IEEE International Conference Communi- cations, Control, and Computing Technologies for Smart Grids (Smar(GriCComm) pages 1-7. IEEE, 2020.
[PVH23] Sconho Park and Pascal Van Hentenryck. Self- supervised primal-dual learning for constrained op- timization. In Procedings of the AAA/ Conference on Artificial Intelligence, volume 37, pages 4052- 4060, 2023.
[WZG+23] Runzhong Wang. Yunhao Zhang, Ziao Guo, Tianyi Chen, Xiaokang Yang, and Junchi Yan. Linsat- net: the positive linear satisfiability neural networks. In International Conference Machine Learning, pages 36605-36625, PMLR, 2023.
[PZC19] Xiang Pan, Tianyu Zhao, and Minghua Chen. Deep- opt: A deep neural network approach for security- constrained de optimal power flow. In 2019 JEEE International Conference on Communications, Con- trol, and Computing Technologies for Smart Grids (SmarGridConm)) 2019.
[ZB20] Ahmed S Zamzam and Kyri Baker. Learning opti- mal solutions for extremely fast optimal power flow. 2020 IEEE International Conference on Communications, Control, and Computing Tech- nologies for Smart Grids (SmanGGidCommm) pages 1-6. IEEE, 2020.
PPZCZ20] Xiang Pan. Tianyu Zhao, Minghua Chen, and Shengyu Zhang. Deepopf: A deep neural net- de optimal
work approach for security-constrain power flow. IEEE Transactions on Power Systems, 36(3):1725-177 1735, 2020.
[7CC21]] Ling 7hang, Yize Chen, and Baosen Zhang. A convex neural network solver for deopf with gener- alization guarantees. IEEE Transactions on Control of Network Systems, 2021.
[SHAS24] Rajiv Sambharya, Georgina Hall, Brandon Amos, and Bartolomeo Stellato. Learning to warm-start fixed-point optimization algorithms. Journal of Machine Learning Research, 25(166):1-46, 2024.
[ZMS1]] Ray Zimmerman and Carlos Murillo-Sancher. Matpower 4.1 user's 's manual, Power Systems Engi- neering Research Center (PSERC). 20, 2011.
[ZMSG97] Ray D Zimmerman, Carlos E Munillo-Sånchez, and Deqiang Gan. Matpower. PSERC.[Online]] Software Available http:://www, pserc. cornell. edu/matpower, 1997.
[SIL18] Mahdi Soltanolkotabi, Adel Javanmard, and Ja- son Lee. Theoretical insights into the optimiza- tion landscape of over paraperraeteri shallow neu- ral networks. IEEE Transactions Information Theory, 65(2):442-765 769, 2018
[ZPC+20] Tianyu Zhao, Xiang Pan, Minghua Chen, Andreas Venzke, and Steven Low. Deepopf+: A deep neural network approach for de optimal power flow for ensuring fcasibility. In 2020 IEEE International Conference on Commanications, Control, and Com- puting Technologies for Smart Grids (SmartGrid- Comm), pages 1-6. IEEE, 2020.
[THH23] Jesus Tordesillas, Jonathan P How, and Marco Hutter. Rayen: Imposition of hard convex con- straints neural networks. arXiv preprint :xXi:23307008336, 2023.
(TT24) Zhe Tao and Aditya V Thakur. Provable editing of deep neural networks using parametric linear relax- ation. Advances in Neural Information Processing Systems, 37:1 13846-1 13883, 2024.
[ZPCL223] Tianyu Zhao, Xiang Pan, Minghua Chen, and Steven Low. Ensuring dan solution feasibility for optimization problems with convex constraints and its application to de optimal power flow problems. In International Conference on Learning Represen- tations, 2023.
[TVH24] Mathieu Tanneau and Pascal Van Hentenryck. Dual lagrangian learning for conic optimization. The Thirty-eighth Annual Conference on Neural Infor- mation Processing Systems, 2024.
[ZSRZ21] Liyuan Zheng, Yuanyuan Shi, Lillian J Ratiff, and Baosen Zhang. Safe reinforcement learning of control-affine systems with vertex networks. In Learning for Dynamics and Control, pages 336- 347, PMLR, 2021.
[TZ22a] Daniel Tabas and Baosen Zhang. Computationally efficient safe reinforcement learning for power sys- tems. 2022 American Control Conference (ACC), pages 3303-3310, 3310. IEEE, 2022.
[ZYZ+24] Hongtai Zeng, Chao Yang. Yanzhen Zhou, Cheng Yang, and Qinglai Guo. Glinsat: The general linear satisfiability neural network layer by accelerated gradient descent. The Thirty-eighth Annual Con- ference on Neural Information Processing Systems, 2024.
[T7222h] Daniel Tabas and Baosen Zhang. Safe and efficient model predictive control using neural networks: An interior point approach. In 2022 IEEE 61st Confer- ence on Decision and Control (CDC), pages 1142- 1147. IEEE, 2022.
[uAYKJ22] Zain ul Abdeen, He Yin, Vassilis Kekatos, and Ming Jin. Learning neural networks under input-output specifications. In 2022 American Control Confer- ence (ACC), pages 151 1515-1520. IEFE, 2022.
12

---

Contents
Discussion and Connection Related Work
13
A.1
Availability of Interior Points
13
A.2
Connections to Related Works (Prop. 5.2)
14
A.3
Comparison of Different Centers
15
A.4
Tackling Equality Constraint
16
A.5
Extension BP Multiple Interior Points
17
Proof for Main Results
18
B.1
Proof for Bisection-induees Projection Distance (Prop, 44.1
18
B.2 Proof for Feasibility Guarantee in (Prop.|5.1)
19
B.3 Proof for Optimality Gap and Run-time Complexity (Theorem)
19
Training for IPNN
20
Prediction-agnostie training
20
Prediction-aware training
21
Data and Experiment Sefting
21
D.1 Formulation for Optimization Problems
21
D.2
Experiment Setting Hlpee--araameters of NN and IPNN
D.3
25
Supplementary Experiment Results
26
E.1 IPNN Training and Bisection Projection over Various Constraint Sets
26
E.2 Sensitivity Analysis on y for Out-of -fa-pe Feasibility and Projection Distance
................................
27
Sensitivity Analysis on Bisection Steps on Optimality Gap and Iteration Complexity
................................
A. Discussion and Connection of Related Work
A.1. Availability of Interior Points
We note that there is line of research on NN feasibility operating under assumptions regarding the availability of IPs.
Gauge Mapping (for Linear Sets): This approach was proposed in TT22a TZ22b), establishing bijective mapping between a unit cube and a polytope, which can be used as the output layer neural networks to ensure feasibility over polytopes. The method relies on input-dependent IPs (IPs) and assumes the existence of an affine mapping from input IP, solving this mapping through semidefinite programming (SDP). However, it does not guarantee the existence of such affine policy. LOOP-LC (LKM23) directly assumes the existence of input-invariant IP and solves by linear constraint residual minimization, but it also does not provide guarantee sufficient conditions for such invariant IP.
Gauge Projection (for Convex Sets): Gauge projection (Mha22) restores solution feasibility by scaling infeasible solutions along rays from (fixed) offline-computed IP find feasible solutions at the constraint boundary. This projection technique is differentiable and computationally efficient, which has been successfully integrated into neural network architectures to enforce output fcasibility with respect input-invariant convex sets. Notable implementations include RAYEN (TH22 (supporting linear, quadratic, second-order cone, and linear matrix inequality constraints), ConstraiNet (KU23 (handling linear and quadratic constraints). LOOP-LC 2.0 (LM23) (for linear sets), and the radial projection approach (TVH24) (applicable to several convex cones).
Homeomorphic Projection (for Ball-homen Sall-homeemorrphic Sets): constraints by constructing homeomorphism between the constraint set and unit ball using invertible NN (INN), allowing efficient projection via bisection (LCL23) LCL24). This approach also relies on a valid INN to map the center unit ball to an of the constraint set. It provides a sufficient condition for feasibility guarantee (LCL23 LCL24). However, INNs have higher training and inference complexity than regular fully connected neural networks due to their sophisticated architectural design requirements.
It ensures NN solution feasibility over ball- hall-homeemorphic
13

---

Bisection Projection
Bisection Projection (for General sets): In this work, we consider more general input-dependent constraint set and propose efficient bisection projection framework. We first characterize the eccentricity of the IP, which is directly related to the disection-induced optimality loss. We then relax the minimum-eccentrriciy IP problem into tractable Chebyshev center-based formulation and employ another neural network, called IPNN, to efficiently predict IPs under varying inputs for input-dependent constraints. We also provide a sufficient condition for IPNN feasibility similar to (LCL23 LCL24), but applicable to more general sets beyond the ball-homeomorphic ones.
A.2. Connections to Related Works (Prop. 5.2)
As discussed in Sec. 2 the proposed framework is conceptually related to the homeomorphic projection (LCL23 LCL24 and gauge function based methods (TZ22h) THH23).
Definition A.1 (Gauge/Minkowski function (BM08)). ). Let C C R be a compact convex set with a non-empty interior. The Gauge/Minkowski function "ie R" x int(C) - R is defined as
(e(2, inf 2 x =x0)],
(6)
where x0 int(C)) is IP Cf
The Gauge function generalizes the concept of norm. For C that is symmetric about the origin, the gauge function (z( 0) defines norm. In particular, when C Bp {x
R" |xpp
1} is the unit ball of the p-norm, have
11s (z,, 0) = |z||p-
Based on the gauge function, we can construct the following bijection between two compact convex sets: Definition A.2 (Gauge Mapping (T222a)). Let 2, X' c. IR" be compact convex sets with IPs 2" E int (Z) and xx E int( respectively.
The gauge mapping & 2 + X is defined as:
(=2) 72 -2, 20)
(3 (=-=%) 2²) x² 2 2E2
7x 20, 200)
The inverse mapping --1 X + 2 is given by:
① --)(x)- (x x x0) 72(x - x0 20)
x0) 20 EE
(8)
In essence, the gauge mapping scales the boundary of a convex set from an IP to another convex set and with translation to IP.
When Z is unit p-norm ball, the gauge mapping is simplified as:
|=||p x2) = + x², Vz E B,
+ xxx = 70(x x x0
(2) =
(x
x²), Va EC,
(9)
| - 5.a lp
Definition A.3 (Gauge Projection (Mha2 )HH23)), Let C C Ra be compact convex set with xt E int(C). For any E R" \( C, the Gauge Projection i R" C + ac is defined as
mT (x) :=
re - x=, xo) E ac,
(10)
where OC denotes the boundary of C.
Definition A.4 (Homeomorphic Projection (LCL23)). Let K Rn be compact set that is homeomorphic to the unit ball B.
Let Φ: : B > K. be homeomorphism with inverse mapping + KC + B. For any point i IR" \ K, the Homeomorphic Projection IT IR" K. + 0K is defined as:
= (z) = + (II (
(11)
where Ts is the Fuclidean projection operator.
14

---

Bisection Projection
The following observation reveals the connection between the bisection projection framework and some existing schemes. Proposition A.1. The homeomorphic projection (LCL23) with gauge mapping (TZ22a) is equivalent to bisection projection over a convex set. The gauge projection (Mha22) is special case of bisection projection with one fixed IP.
Proof. Let's consider applying the gauge mapping to the homeomorphic projection for a compact convex set. Then we can simplify the homcomorphic projection operator as:
70 (ā - x², x²²)
f = (Projs ④ (a))) = @(Projs
(Ø z)))
(12)
|| 2011
(o x
(Ø - x²))
1 x
(
= (
(13)
No 10 (--
(Ø x²)
1 - x
| x
8-n
| 18-091
x
+ x
(14)
NC
[2-=21] 200)
2-x²
| x
3 x
x
(15)
cc(ā x,; x9
When considering è as an infeasible point, we need scale down of no such that the (0-ā== ,r,) (ø x²)
) + x will be located in the boundary. Therefore, we take a' "c( the homeomorphic projection operator is indeed the bisection projection operator in (2). It is also equivalent to the gauge projection RAYEN methods by its definition in Def. A.3
Thus, the bisection projection framework provides a unified view for some existing projection-analogon approaches over convex sets. Meanwhile, we highlight the theoretical analysis and application scenario for BP works on general compact sets under Assumption [byyond those in the existing studies, further exploring the projection-basee design and achieving substantially better performance in feasibility, optimality loss, and speedup as shown in Sec. 6
A.3. Comparison of Different Centers
Defining the centers of a set is a classic problem in mathematics, which involves various definitions tailored to serve specific purposes. Each definition captures a unique aspect of "centrality" depending on the application or theoretical requirements. Here, shown in Table we discuss several classic definitions including the proposed minimum-eccentriiityy interior point (MEIP) in work.
Table 3. Comparison of different definitions of center for set
Name
Definition
Description
MEIP
x² arg min JE
max yEOX
||æ
ull
min SEOX
|| xll
Minimizes the discrepancy between the maximum and minimum IP-to-houndary distances. Maximizes the minimum (P-to-boundary
Chebyshev Center
x
max min || xll
x yEOX
Circumcirele Center
x arg min max [xc w/l
Minimizes the maximum IP-to- bo--bound.ry.
TE vCOx
Analytical Center
arg max ( C 1og(-9(xx))
Maximizes the logarithmic barrier of the inequality resid- uals (g)(z) S 0).
Max residual Center
max t s.t. 9x(x0) +15 1- 1 20,20
Rineq
Maximize the constraint residual to find a "central" IP.
Centroid Barycenter
Zz
Calculates the average position of all points in the set. Calculates weighted average position points the set, where each point has an associated weight wi,,
2im1 WiDss/
nm Wk
The MEIP, Chebyshev Center, and Circumcircle Center focus on geometric properties of sets, specifically distances to the boundary. We propose the MEIP for bisection operation. justified by the performance guarantee in Prop.
Geometric:
15

---

Bisection Projection
Barrier: The Analytical Center and Max-residual Center use optimization techniques (BBV04 THI223 to find "central"
IP within feasible region. This approach is crucial for solving linear and nonlinear programming problems. However, maximizing the log-residual residual directly of the inequality function does not directly reflect the point-to-boundary distance for general constraint sets, which may result in large deviation for the bisection operation.
Statistical: The Centroid and Barycenter represent statistical approaches to defining centrality by calculating averages of point sets. The Centroid computes simple arithmetic mean, suitable for applications in statisties and machine learning. The Barycenter incorporates weights, allowing for differentiated influence among points. Despite their simplicity, these centers are not necessarily interior points for general non-convex sets X' making them unsuitable for our bisection operation.
A.4. Tackling Equality Constraint
Consider the following constraint set Co defined by both inequality and equality constraints:
Co (x IR" h(x,,)) 0, g 0) s 0},
(16)
where the functions h(:,,) ): TR=+ + R and g(::)) :) Ru+d - TR. Thsee are continuous with respect to x and f. For simplicity, we use h-(-) = lu(,, 0).
Assuming the equality constraint maintains a constant rank:
rank(Ja., (x)) = vO and Vo E Co.
(17)
This condition implies that Cy has Euclidean dimensior 5 of as per the Constant-Rank Level Set Theorem (Lee13
In simpler terms, we can utilize a subset of decision variables x1 E R- and reconstruct the complete set of decision variables [ x22] E [R" by solving 72 = (x1x)), such that he ( (z)))) = Note that such a parametrization are not
necessarily held globally for non-linear equality constraints. This method of reconstruction, which ensures the feasibility
of the equality constraint, is extensively used in optimization literature (Aha69) P7C19 7B20 DRK20 20 LCL.23 THH23
LM23 DWDS23).
We then denote the reduced constraint set as
C# = (ar E TR""" M( th (x1)) s 0}
(18)
This set Cp is not only equivalent to the original constraint set Co but also homeomorphic to it, implying one-to- one, continuous, and bicontinuous correspondence between the two sets. The forward and inverse mappings of this homeomorphism are described by the following transformations:
[x1, E Ce + E Cj. #1 E Că + (x()) E Co-
(19)
(20)
Let's consider two examples to illustrate this equality completion//ecoosttuutiion process:
Linear equality constraint
Let's consider an equality constraint defined {a E R" Ar = 0, E 1R"x", E ]R", where x the decision variable and 0 is the input parameter. We can assume, without loss of generality, that the rank of matrix A is rank(A)
To facilitate the reconstruction process, we partition the decision variable into two groups: E R-- and 22 E TR". Accordingly, we also partition matrix A into A = [Ai, A2), where A₁ E (Rrx("-r) and A₂ E igrrr, Hence, the equality constraint can be represented as A1 + A2zz = 8. The reconstruction process indicates that we can determine 22 using only the subset of variables 21, with the explicit relationship given by:
I2 = (x = A 10 - A
(21)
SIf open set X' is Euclidean of dimension, then every point E X has neighhorhood that homeomorphic open subset of Leel
Ra
16

---

Bisection Projection
Here, we choose the partition of 11 and 22 such that A2 has the full rank of The relevant Jacobian matrix for back-propagation in this context is:
Jos (x1) -A2 "A
(22)
Non-linear equality constraint
For non-linear equality constraint defined as {ar E IR" h(xx,) 0) = 0,0 R., h: R - RR),, we partition the decision variable into æ E _=-"" and #2 E '2' in a similar fashion to the linear case. Under the assumption that the Jacobian matrix of h with respect to ø2 has a constant rank, the completion function Φe is well-defined and satisfies:
h [21, @o (21)) 0) =.
(2.3
To solve for (21) when h is non-linear, we can employ an iterative technique such as Newton's 's method. The necessary Jacobian matrix for propaaaopaatiion can be computed using the Implicit Function Theorem, which provides the derivative of the implicitly defined function Φg. The Jacobian matrix is given by:
Job (21) - Jr. Jno (x1).
(24)
Note that by for such a non-linear constraint may not be single-valued globally and depends on the initial value for the iterative algorithm, which may bring potential convergence issues.
In conclusion, reconstruction techniques utilizing equality constraints allow for reduction in the dimensionality of the decision variable space. By modeling only a subset of the decision variables, use the equality constraints to define the remaining variables implicitly. This process is differentiable, making it suitable for integration into the training of machine learning models, hence providing a powerful tool for incorporating equality constraints into such models (Aba69; PZC19 PCZL22 DRK20 DWDS23). For the implementation issues, we follow the established procedures in previous works (DRK20) LCI.23), where the partial variables for convex problems are randomly sampled, and the ones for AC-OPF problems are strategically selected.
focus on the inequality constraints and
A.5. Extension BP to Multiple Interior Points
The bisection method can be executed in batch for multiple interior points Xú.m = { 1m C Co, and we select the projected point as the one with minimum deviation, defined as:
ig = BP Xi,m) - arg minn(loo.. - Toll]:
(25)
Bo.k
where t0, (P x))x) is the returned feasible point by bisection w.r.t. the k-th IP 29,4 E X2,m
Similarly, we can define the eccentricity of set of IPs, crucial for bounding the bisection-induced projection distance. Definition A.5 (Fecentricity of IPs). For a compact set X' satisfying Assumption | Twith non-empty interior, the eccentricity of a set of IPs X : { C X with respect to a compact subset of boundary I C OX' is defined as:
E(x ma r) - max [d(y, X min xx)ll yET
(26)
Eer
where d(y, X:) = minigkgm flly - 11 } is the point-to-set distance.
Next, we establish the connection between eccentricity and the bisection-induced projection distance.
Proposition A.2. Let ãe F()) be infeasible NN prediction with bounded prediction error as [|F(0) - xزب
< Eprei
ie = Bio X2 "m be the projected solution with m interior points X 8.m. C Co; Then, the worst-case projection distance is upper bounded as:
maX
|م00 - (P( S Epro + E(Xi,m To)),
(27)
3ig BB (T p
where B(xz) Epre) represents the NN prediction region, enclosing all infeasible NN predictions with prediction error Epre> and a = (BP(3s, X2 m), Vāg E B( cpre) \ Co defines subset of the constraint boundary containing all projected NN solutions from the NN infeasibility region.
The proof is similar to the single IP case and presented in the next section.
17

---

Bisection Projection
To
cpm
2
Figure geometric illustration cccentricity and the proof.
B. Proof for Main Results
B.1. Proof for Bisection-induced Projection Distance (Prop. 4.1
Proof. Without loss of generality, we assume that the optimal solution 26 E 3Cg lies on the boundary of the constraint set, implying the existence of active constraints at optimality. This is a standard assumption in constrained optimization theory (NW9.).
For an infeasible solution že B( Epro), recall the definition of the projected solution de as:
fp (P =g) aa" (To =3) + xg.
(28)
where a² [0, leads to 2t E 8Co.
Prediction-agnostic bound:
Then, the projection distance for an infeasible prediction žo is bounded as:
(a)
|| Ti - dell
|| - xill
|&g
(29)
||00
zall
+ |2
zill
|| - 266
(30)
IA
Epre + |20
xill
|
zgll
(31)
Epro + max zEL's
| - z-ll
min zETo
|| - 2611
(32)
Cpre + E Io)
(33)
Epr + Ex3, OCa)
(34)
Equality (a) is by three points, So. zg. and 2o. exist in the same straight line. Inequality (b) by the triangle inequality with auxiliary point wig. Inequality (c) is by Fo B(x Epro). Inequality (d) is by taking the maximum and minimum point over local boundary H (BP (BP 2g), Vēp E B(zğ. Epre) Co}. Equality (e) is by the definition of eccentricity in Def. 4.1
Prediction-aware bound: Based on 311 the projection distance for an infeasible prediction ão is bounded as:
te Sollscpre + || xill
| - xل'l min zEOC,
(35)
Sprre + || x1ll
|| xلl1
(36)
where Eins - denotes the distance between the IP prediction and the optimal solution, and y min | denotes minimum soint-to-boundare distance.
Proof for Proposition A.2
18

---

Bisection Projection
For the multiple IPs setting Nam
Cg. derive the upper bound follows:
min 15kSm
[00
f0
2
min {ppro + || isksm
r0,xl
|:0.
2. 113
(37)
Epre + min 1sk5m
min 15kmm
| 20,
(38)
Epro + max zEñ' Igk5
min
| &0,x min
min | xu,
(39)
welo
15k5m
Cre
E Ta)
(40)
Inequality (a) is by the bound for the single-IP setting above. Inequality (b) is by the minimization of the joint term, which smaller than the minimization separately. Inequality (c) is by taking the maximum and minimum point over the local boundary T' = ac, n (BP Xim)), Vēg B(2g. Epre) Øo & Co}
Thus, we complete the proof as follows:
max E Spro)
min Sksm
|ī & I Epro + E(X To)
(41)
B.2. Proof for Feasibility Guarantee in (Prop. 5.1
Proof.
Since D is an rgg-oovering dataset for θ as θ C U B(0,, re), for any 0 E O, there exists at least one 0, E D such
that:
||0 - 0.11 S re
(42)
Given that vi is Ly-Liscchitz continuous over θ we have:
(() (0,)) S L 110 0,1l S Loro.
(43)
Since constraint violation function is LG Lipscchtz in r and LG -Lipschitt 8, we can bound the change in due perturbations in both arguments:
G()(0), G()(O), + To..)l1b(0)) (b.)))l L 0.ll
G(V(0))))) (.) + LG Torr TG,oro-
Suppose for each 0 E DD the training requirement is satisfied as: ((v)(O)), 0:) + LGG. Lyro La,oro I 0, then we have for any 0 E θ, the constraint violation can be bounded as G(b(O), < O.
B.3. Proof for Optimality Gap and Run-time Complexity (Theorem)
Proof. First, the feasibility of the solution returned through bisection is guaranteed due to the bisection trajectory connecting an infeasible point and an interior point, which must intersect the constraint boundary. Thus, the bisection algorithm can always find feasible solution by scaling down the infeasible solution along the line segment. We remark that for general non-convex sets, the line segment between an infeasible point and interior point may intersect the constraint boundary multiple times, causing bisection algorithm converge to of the multiple feasible solutions.
Let áo E aC, be the converged boundary feasible solution given infinite bisection with an interior point a.j.
We divide the optimality gap by the following three terms:
|| 1
xī S ||ح io
+
Bell
+
1000
(44)
prediction ertor
projection errue
bisection eITOE
19

---

Bisection Projection
The prediction error determined by the provided NN predictor, and denoted it as épre
sup()
=
where
PEe
F(-) is the NN predictor to predict the optimal solution.
The projection error from bisection-projection,, proved in Proposition 4.1 as:
can be bounded by the eccentricity-relate term
||
Roll -
max y B (pro))
|80 dell
(45)
S Spre + 1o)
(46)
Since ie the converged boundary feasible solution under the bisection algorithm, the bisection error induced by finite step iteration can be derived as:
| - K || 1 ||a" (ig - rÿ) + z - (a k (ōg z8) + x8)1
(47)
(a* a* )1300 z-6l
(48)
1 2 K |1:00 - z6 + zg x111
(49)
5 2 K (1|ā zb6l + 1 x3)l)
(50)
$ 2 K (Cpre D)
(51)
where D = diam(Ca) denote the diameter of a compact set.
Combining the three terms together, we have:
| x51l s 2épc + (e) + (Epre + D)
(52)
The complexity of executing the bisection algorithm involves the iteration steps, the number of IPs, and the complexity of verifying the inequality constraints at each iteration as G. For example, the inequality constraint (x 0) is linear function for all 1.... Nineq: then G = n mmme In contrast, iterative algorithms such as interior point methods have complexity of O(In + Wineg))) )) at each iteration due to the matrix inversion operation.
C. Training for IPNN
C.1. Prediction-agnostic training
In scenarios where prior information about the optimal solution or a trained neural network (NN) predictor is unavailable, our objective minimize the worst-case projection distance induced by bisection under any NN predictor. Guided by Proposition 4.1. aim minimize the eccentricity relative the constraint boundary, denoted (1)( 8Cg).
Definition C.1 (Preniction-agnostii MEIP). For compact set Co with non-empty interior, the minimum eccentricity IP defined as the solution of the following problem:
min Elg aCo) A max |y z:ll min yyy
(53)
VEUCa
vEOCo
To facilitate the minimization of the MEIP, adopt the Chebyshev Center as relaxation. The Chebyshev Center provides robust central point within the constraint set by maximizing the minimal distance from the center to the boundary.
Definition C.2 (Chebyshev center). For a compact set Cp with non-empty interior, the Chebyshev Center is defined as:
max 7, s.t. B(xg. 7) C Co 25
(54)
Building upon this formulation, we derive the Prediction-Agnostic loss function, which aims to encourage the NN predictor (0) to lie within the feasible set while maximizing the robust margin
((b(0), Fy [P ru, 0)] -lg(7))
(55)
20

---

Bisection Projection
where P(x, 0) represents the penalty function for constraint violations, u is sampled from unit ball to perturb the center r.. 7 is variable representing the robust margin to be maximized, and À is positive coefficient to balance different loss terms. The first term ensures that perturbed points within the ball B(rg, 7) satisfy the constraints, while the second term encourages maximizing the margin ?.
C.2. Prediction-aware training
In contrast, when trained NN predictor F()) dataset of optimal solutions (0,zz, is available, the objective shifts to identifying interior points with minimized eccentricity within a local region of the constraint boundary. Given the bound on the bisection-induced projection distance from Equation (36):
[ & + 1 zill
min || - zill xE0Cs
(56)
We define the following Prediction-Aware MEIP: Definition C.3 (Prediction-aware MEIP).
min z6
b max ? #3
(57)
s.t.
(58)
s.t.
B(xg. S Co
To effectively minimize the Eisection-induced projection distance when the optimal solution dataset x' NN predictor F())
is available, we design the following Prediction-Aware loss function:
(()(()),7) E,, [P + yu, 0)] A log(n) + B||20 - x561
(59)
The first two terms are analogous to the Prediction-Agnoste loss, promoting feasibility and robustness.
The third term penalizes the deviation of the IP from the known optimal solution or initial NN prediction 2g F()),
enhancing optimality.
8 is positive coefficient that balances the trade-off between maximizing the robust margin y and minimizing the distance to the optimal solution zn.-
Further, to reduce training complexity, we can initialize the IPNN with the one trained NN solution predictor, then follow the loss to fine-tune the IPNN to find interior points.
Notably, when 7 0, the loss function reduces to regular supervised training with constraint violation penalty, as commonly used in NN-based constrained optimization solvers (PZC19 DRK20), By maximizing the robust margin the training process follows the preventive/adverrsriaal approach (2) seeking an NN predictor that maintains feasibility by keeping distance from constraint boundaries. Rather than directly using such a feasible IP with its larger optimality gap, we apply bisection between the and an infeasible but near-optimal NN solution, effectively balaneing the Teasibility-opiiaalii trade-off.
D. Data and Experiment Setting
D.1. Formulation for Optimization Problems
We test the Bisection Projection framework for four constrained optimization problems, including two convex optimization problems and two real-world non-convex problems. we follow the established procedures from available codes in previous works 2RK20 LCL23), where parameter configuration and sampling strategy are publicly available.
D. CONVEX PROBLEM FORMULATION
The Quadratic Program (QP) is a fundamental optimization problem where the objective function quadratic and the constraints are linear. The QP problem be formulated as:
QP
minimize xER
2 x xJQx pxx
Qx
(60)
21

---

Bisection Projection
subject to Gx < h,
(61)
Ax A,
(62)
where: Q S is positive definite matrix, ensuring the convexity of the objective function, p E IR is vector of linear coefficients, A E R is a matrix defining equality constraints, G' E IR. Rinax is matrix defining inequality constraints, E Ru is a vector specifying the upper bounds for the inequality constraints, and 0 E R is a vector specifying the right-hand side of the equality constraints.
The Convex QCQP extends the QP by including quadratic constraints. The Convex QCQP problem is given by:
Convex QCQP:
minimize XER"
x x'Qx
Qx + +
(63)
2
subject to
x H,x + g x S hi i i= 1,..., Timey:
(64)
Ax 0,
(65)
where each H; E S is positive definite matrix corresponding to the i-th quadratic constraint, gi E IR a vector of linear coefficients for the quadratic constraints, and h2 E R represents the upper bound for the i-th quadratic constraint.
The SOCP is convex optimization problem that generalizes linear and quadratic programs by allowing conic constraints. A SOCP problem is formulated as follows:
SOCP: minimize xER
x Qx + p'x
(66)
subject to
|| hill2 S c, x di, i i= 1,...y Tineqs
(67)
Ax
0,
(68)
where G; Rmxx and h; E n define the second-order cone, C; E R and d: IR are the coefficients and scalar terms of the conic constraints, respectively.
The Semidefinite Program (SDP) an optimization problem where the goal is to minimize a linear objective function subject to semidefinite constraints. The standard formulation of SDP given by:
SDP:
minimize X
tr tr(CX)
(69)
subject to
X 1 0,
(70)
tr( ((:A))) = bi, i= 1, Neg.
(71)
where X E S" is the symmetric matrix variable, C E Raxa is given symmetric matrix of coefficients for the objective function, tr(-) is the trace of a matrix, A, E Rax= are given symmetric matrices that define the equality constraints, b, E R are the given scalars that specify the right-hand side of the equality constraints, and neg is the number of equality constraints. We discuss the penalty design for PSD constraint in Appendix D.3
1.1.2. JOINT CHANCE CONSTRAINED INVENTORY MANAGEMENT (JCC-IM)
We consider the Joint Chance-Constrainee Inventory Management (JCC-IM) problem, which seeks optimize inventory levels across multiple warehouses under conditions of demand uncertainty, ensuring high probability of meeting that demand. The JCC-IM problem is formally defined as:
JCC-IM minimize xEX
c x
(72)
subject to
Prob(Ax 2 0 w) 2 1-8 Gx h, min < 5 x max
(73)
(74)
where n denotes the number of warehouses located in distinct regions, the decision variable x represents the inventory order quantity to be determined advance for n warehouse, order to satisfy future demand. The vector encapsulates the historical average demand, and the term w ~ p(-) models the stochastic deviations from this average, capturing the inherent uncertainty of demand. The matrix A characterizes the interdependencies among different warehouses, which may arise
22

---

Bisection Projection
Sample size (N 100)
Sample size (N 1000)
1.2
0.8
2 0.6
8 0.6
0.4
0.0
0.0
0.2
0.4
0.6
0.8
1.0
1.2
0.0
0.2
0.4
0.6
0.8
1.0
X1
Figure 10. This figure visualizes sample-based individual chance constraint defined Prob(w1æ1 + w222 < 1) 2 90%, where W1, W2 are independent Gaussian variables. The probability of satisfying this constraint estimated using N samples and the indicator function ((-) as: N >>= (wix + whzz s 1) 2 90%. The visualizations underscore the non-smooth geometry and optimization difficulty (PAS09). We remark that was tested a high-dinennsionll scenario with decision variables and joint constraints in our experiments.
from shared types of inventory or geographical proximity, The parameter å specifies the acceptable risk level, thus ensuring that the probability of meeting demand across all warehouses is least 6. The additional constraints, Gx h and min xx x < max represent warehouse-specife capacity limitations and inventory bounds, respectively.
The Joint chance constraint (JCC) represents the probability of the joint event of feasibility for each constraint as:
Prob(Ax 2 + w) = Prob(AAx 2 01 + W1, A x 2 9m + wm) 2 1 8
(75)
When 1 and with Gaussian uncertainty, the probability constraint can be reformulated into second-order cone constraint (BV)44) However, in the general case, given the absence of an analytical reformulation for the JCC, employ Sample-Average (SA) approach to approximate the conttrceed problem. This technique involves generating finite set of scenarios {w, ) from the underlying distribution of f. The SA variant of the JCC-IM formulated as:
SA-JCC-IM minimize XER
C x
(76)
N PN
subject to
Σ 1=1
I(Ax 2 (1)
(77)
N
Gx h, x min
<x5x max
(78)
where I(-) is the indicator function. A solution is deemed to have a probabilistic JCC feasibility guarantee if Pv 2 1 8. This empirical evaluation provides a practical measure of the reliability of the SA-based solution in adhering to the demand satisfaction requirements stipulated by the JCC-IM problem.
In practice, the problem can be solved as mixed-integer programming but is intractable for high-dimension problems with large number of scenarios; therefore, for iterative-solver-basee baselines, we solve the robust version of this problem by setting 8 0, such that the problem becomes convex with large number (N) of constraints. But for BP methods, can still project the solution to the chance constraint in (77) through bisection with easy feasibility checking shown in Alg.
D.1.3. ALTERNATING CURRENT OPTIMAL POWER FLOw (AC-OPF)
The Alternating Current Optimal Power Flow (AC-OPF) problem is pivotal in ensuring the efficient and safe operation of power grids. It requires real-time decision-making and adherence to operational constraints to maintain system integrity. The
23

---

Bisection Projection
Vi 1.05 Pai
V22
1.05
jX12 f1.1
Po2
Foz [per unit)
64
40-
jX13 =1.22
jX23 j1.5
-6-
-1g
PGS V/l 1.05
PGi (per unll)
QGa (per mii)
Figure 11. The left figure displays a simple 3-node power network, while the right figure illustrates part of its constraint set MMI 19 These visuals highlight the complex geometry and inherent challenges of the ACOPF problem. is noteworthy that our experiments, BP was tested on 200-node power network involving more than 1,000 constraints.
AC-OPF inherently a non-convex Quadratically Constrained Quadratic Program (QCQP) and is recognized as NP-hard, posing significant computational challenges. The formal mathematical formulation of the AC-OPE problem is follows:
min AC-OPF:
Pg Q/2 + bppg
(79)
P
subject to
smax 10; - (;)) S ij
V(i,)) E
(80)
(P, Pa) + (gg - qa) = diag(1) (v) We, ViEW,
(81
min < Py S Pg 9g Pg
max min 9g 9g umin s |0| < 2 mAX
(82)
where the power network comprises n nodes, indexed by the set N. The vectors Pa, qa R" represent the real and reactive power demand at each node, respectively. The vectors Pg. 9g E R. denote the real and reactive power generation, which are the decision variables of the optimization problem. The vector e E C" signifies the nodal voltage phasors. The admittance matrix W Coxn characterizes the physical properties and topology of the power network, with W denoting its complex conjugate transpose. The generation cost is represented by quadratic function with matrix Q E guxa and vector b E R" The constraints include generation limits (pmin .P max Ig .g _gmax), voltage magnitude bounds (u _mmx), thermal line limits (Staax,, and power flow balance equations. The set & denotes the set of edges (transmission lines) connecting the nodes in the power network. The equality constraint represents the complex power flow balance at each node, ensuring that the generation and demand are matched while accounting for power losses.
D.2. Experiment Setting
Computational Infrastructure: All NN-based methods are implemented in Pytorch and executed on an Ubuntu server with an NVIDIA A800 GPU. Iterative algorithms were executed in parallel on an AMD EPYC 7763 64-Core Processor. For convex optimization problems, we employed the MOSEK optimizer under an academic license. The Joint Chance- Constrained Inventory Management (JCC-IM) problem was approximated using sampled scenarios and solved with MOSEK. Alternatin Current Optimal Power Flow (AC-OPF) problems were addressed using the open-source PyPower toolkit (ZMSTT). Additional experimental configurations are detailed in the respective sections and table footnotes.
Baseline Methods:
We compare our approach against the following baselines:
Optimizer: For convex optimization problems, we employ MOSEK as the baseline solver. For AC-OPF problems, we use PyPower (ZMSTT as the specialized solver.
NN: A vanilla neural network that directly maps input parameters to solutions without feasibility guarantees. is trained with an optimal solution dataset in supervised setting.
24

---

Bisection Projection
Infeasible predictions from NN are corrected via orthogonal projections. The projection problem is formulated and solved by Optimizer.
Proj:
WS:
Infeasible NN predictions serve as warm-start initializations for iterative solvers, which may accelerate the convergence.
The differentiable projection method from DC3 (DR200) which employs gradient descent to minimize the constraint violation for constraint satisfaction. The gradient is derived via the automatic differentiation mechanism in PyTorch.
D-Proj:
H-Proj:
Homeomorphic projection applied to infeasible predictions (LCL23) The invertible neural networks (INN) are trained in advance for each constraint type.
B-Proj: Our proposed bisection- based projection (Algorithm D applied to predicted interior points for feasibility recovery.
Evaluation Metries: We evaluate all methods using the following criteria on 1,024 test instances:
Feasibility: The percentage of solutions satisfying all equality and inequality constraints within tolerance of 10"3,
[f(=)) respectively, where Optimality: The relative solution and objective optimality gap, defined ||x-æ"|| || and [(=")
||=-||
f(z) is the objective value of the predicted/projeetee solution and f(x") is the optimal objective value.
Runtime:
Wall-clock time for inference, including raw NN prediction and any post-processing steps.
D.3. Hyper-parameters of NN and IPNN
We employ fully connected neural network with residual connections (HZRST6 LLC24) and equality reconstruction (P7C19 DRK20). denoted F, predict optimal solutions interior points for constrained optimization problems given input parameters 0 E O The network architecture incorporates skip connections to facilitate gradient flow and reconstruction module to enforce equality constraints.
Data Generation for NN predictor: Training and test datasets are generated by solving optimization instances across diverse parameter configurations using established solvers:
Convex problems: MOSEK optimizer
AC-OPF problems:
PyPower (ZMSG97)
JCCCIM problems: Sample Average Approximation (SAA) solved with MOSEK
Loss Function for NN predictor: The neural network trained via supervised learning with composite loss function that balances solution accuracy, constraint satisfaction, and objective quality:
C(F) = EaND
[F(()) - 2i1 + A Σ (FL)) (2F(F()), (2)
(83)
where:
The first term minimizes prediction error with respect to optimal solutions
The second term penalizes inequality constraint violations, with 9j representing the j-th inequality constraint.
The third term encourages objective function minimization to reduce the objective optimality gap directly.
Å1 Aa > 0 are hyperparameters controlling the trade-off between feasibility and optimality
25

---

Bisection Projection
Constraint Handling in NN and IPNN:
Equality constraints: we employ variable selection and completion (detailed in Appendix A.4). which guarantees exact satisfaction for equality constraints.
Penalty function: For standard differentiable inequality constraints g(x) Σ 0, we compute the constraint violation directly as [|ReT.U(g(x)]I], which naturally naturally vanishes when constraints are satisfied.
Positive semidefinite constraints: For matrix variables X č O, We offer two penalty computation approaches
We can compute the exact penalty using negative eigenvalues via Rel.U(-eig(X)), where eigenvalues are obtained through torch. www.lling.gee... wew.lllleilla... While this method provides exact gradients through automatic differentiation, it may encounter numerical instability (e.g., singularity) during training.
We can estimate the penalty as ReLU( Σ 0g Xx:) using linear measurements {or where the vectors 0; are computed iteratively following (NSW22) This approximation offers improved computational efficiency and numerical stability compared to the eigenvalue approach.
NN and IPNN Training
We train the NN predictor following regular ML training scheme with parameters in Table The Interior Point Neural Network (IPNN) shares the same base architecture the standard NN predictor, with the same input and output dimensions. Furthermore, for the IPNN training for constrained optimization problems, we directly initialize it with parameters from a trained NN predictor to reduce its training time. Detailed architectural specifications and hyperparameters for both models are provided Table
Table Structure of IPNN/NN predictor in experiments
Parameter
Value
NN/IPNN structure
dimension of input layer dimension output layer dimension of hidden layer activation function number of layer last-layer activation
d " [(d + n) ReLU(.)
3 Sigmoid(-)
NN/IPNN training parameters
number of training samples
10,000
number of testing samples
1,024
number of iteration
10,000
optimizer
AdamW
learning rate batch size the coefficient for objective value
0.0001
64
0.001
the coefficient for incquality penalty the coefficient for robust margin
0.01
0:01
E. Supplementary Experiment Results
E.1. IPNN Training and Bisection Projection Various Constraint Sets
We evaluate the effectiveness of our BP framework two challenging non-convex constraint sets.
Test Cases: We consider two geometrically distinct non-convex sets:
Case 1: (6) = {x E Rd x T Qi + g. x +b, 5 0, = 1,...,6}
(84)
Case 2: C2) = U B(c,.ra), where B(c,r) r) fo || 1 c|l <
(85)
im
26

---

Bisection Projection
where 02 (Qu qi b= and 02 (c, ri parameterize the constraint sets. Case 1 represents ball-homeomorphic set defined by quadratic constraints, exhibiting complex non-convex geometry. Case consists of union of disjoint balls, presenting the additional challenge of disconnectivtty-a property that violates the assumptions of many projection-based methods. For each case, we:
Train the IPNN & to learn the chebyshev centers.
Evaluate bisection projection unseen test parameters
Compare against Homeomorphic Projection (H-Proj) using identical test instances
Results and Discussion. Results presented in Figures 12 We make the following key observations:
The robust margin maximization scheme provides two key benefits: it increases the interior-to-boundaay distance, improving IPNN prediction feasibility unseen samples, and enables the trained IPNN to predict central interior points for projections.
For ball-homeomorphic constraint sets (Case 1), bisection projection achieves comparable performance home- in Case 2), the
omorphic projection. However, when constraints are disconnected (i.e.. homeomorphic projection fails to identify a valid INN for projection, resulting in infeasibility. In contrast, our bisection projection consistently identifies central interior points and maintains solution feasibility.
E.2. Sensitivity Analysis on 7 for Out-of-Sample Feasibility and Projection Distance
We empirically evaluate the impact of the robust margin parameter maximization on two critical performance metries: (i) out-of-sample feasibility rates for interior point predictions on unseen parameter instances (Fig. 6), and (ii) incurred projection distances after disection-based feasibility recovery (Fig. 7)
We compare three IPNN training strategies:
No y: Trained exclusively minimize constraint violations without margin regularization (> -0).
Fixed y: Trained with a constant margin parameter (e.g., 7 = 10-2), analogous to randomized smoothing techniques
employed adversarial training.
Train y: Trained with our proposed y maximization regularization, initialized at = 10-22
To ensure statistical reliability, we trained each model configuration five times with different random seeds and report results with standard deviations.
E.3. Sensitivity Analysis on Bisection Steps on Optimality Gap and Iteration Complexity
As established in Theorem the bisection algorithm exhibits a linear convergence rate with low per-step computational cost. We empirically validate this theoretical property by systematically varying the number of bisection steps across multiple problem classes, as illustrated in Fig. 18
The results confirm our theoretical analysis, demonstrating exponential reduction in optimality gap as the number of bisection steps increases, while computational time grows linearly. This favorable trade-off enables practitioners to select an appropriate number of iterations based on their specific accuracy requirements and computational constraints. Notably, most practical applications achieve acceptable convergence within 5-10 bisection steps, making our approach well-suited for real-time decision-mann maaiin scenarios.
As shown in Fig. when the line segment between an interior point and an infeasible prediction intersects the constraint boundary at multiple points, bisection algorithm converges to such intersection. The specific convergence point depends the bisection parameter 3, which controls the search granularity.
The bisection update rule can be generalized as:
Om = -..00 + (1 B) an
(86)
27

---

Bisection Projection
where 3 E (0, determines the bisection stepsize. The standard choice 3 0.5 yields binary search.
A smaller values (e.g., 3 0.1) create conservative search biased toward the infeasible prediction, and the algorithm tends to converge to boundary points closer to the original NN prediction, better preserving the learned solution structure. However, this comes at computational cost: The number of bisection steps increases under the same convergence tolerance.
Figure 19 empirically demonstrates this trade-off, showing that practitioners can tune 3 based on their specific requirements for solution quality versus computational budget.
Ponaly lol Pertureed
bock foarooiity (50)
-1.5
3
Robust
-20
-30
Eccenitiity
Mac
2000
2000
6000
80:00
12000
2000
4000
5000
3000
13000
2200
4000
0065
2000
10000
2006
2008
500C
2000
1200
Traininng
Training ttrztion
lbbration
Training
Figure 12. Non-convex Case: Perturbed penalty loss (Left) and IPNN prediction feasibility rate (Middle Left) during training. Robust margin log(?) (Middle Right) and estimated eccentricity (Right) during training.
Input
lest irput.
lest
Input
lest
43
Drartorooete
Infexeble poitss
Projectd ports
Figure 13. Non-convex Case: Bisection Projection with IPNN prediction given test input parameters.
155t niput
Best 2
list Inpui
teal nouu
bast input
Sest input
Projected poins
Figure 14. Non-convex Case: Homeomorphic Projection with trained INN given test input parameters.
Pertureed
Robust Margi:: ogly
0.00
00
6:04
feoaially
68
Dostance
8
3.0
600
3.0
Mac
Mind
2000
5000
10000
2000
2000
6000
5200
10090
2000
4000
5200
8000
1000
4000
3200
Tratning
Training
Traninn
Training
Figure 15. Disconnected Case: Perturbed penalty loss (Left) and IPNN prediction feasibility rate (Middle Left) during training. Robust margin log(?) (Middle Right) and estimated eccentricity (Right) during training.
28

---

Bisection Projection
2
Test
Irput
Fnput
Input
Inarorocinss
Infeasible
Frodeced
Figure 16. Disconnected Case: Bisection Projection with IPNN prediction given test input parameters. injut
lest
lest
3
incu
Irieandee PORT3
Projected porta
Figure 17. Disconnected Case: Homeomorphic Projection with trained INN given test input parameters.
GP
Convax GCOP
SOGP
200
Bisectio pap (%)
Bunning time (mo)
Bioection cap (%
Running lime (mei
Bisecton gapp (%6
17/
Running lime
100
Nam of Disection stop (9)
Num of bisection step (B)
Num of bisection stop (8)
Bloection glp (%)
Rumning time (ms)
Bloecton gap (%)
1200
Running tnno (m3)
Bioection gsp (%)
Running Eime (m))
430
Num of bisection step (5)
Num bisection stop (57
Num of bisection step (8)
Figure Effect of increasing bisection steps on optimality gap (top) and computational time (bottom) across constraint classes. Results are averaged over initially infeasible neural network predictions. The panels show QP, QCQP, SOCP, SDP, AC-OPF, and JCC-IM problems sequentially, demonstrating consistent exponential convergence behavior with lincar time complexity growth.
stepsize: 0.5, converge in 9 steps
stepsize: 0.3, converge steps
stepsize: 0.1, converge steps
1.0
1.0
1.0
0.5
0.5
0.0
0.0
0.0
-0.5
-0.5
-0.5
-1.0
-1.0
-1.0
-1.0
-0.5
0.0
0.5
1.0
-1.0
-0.5
0.0
0.5
1.0
-1.0
-0.5
0.0
0.5
1.0
Interior points
Infeasible points
Projected points
Figure Effect of bisection parameter 3 on (a) optimality gap and (b) iteration count across different problem instances. Smaller values achieve better solution quality at the expense of increased iterations.
29


Reviews:
[{"review_id": "YglZOmYLFb", "reviewer": "Reviewer_cZEk", "summary": "The paper proposes a technique that enables projecting the outputs of neural nets onto arbitrary compact sets. The goal is for the neural net outputs to be feasible with respect to constraints that are often found in convex and non-convex optimization settings. The approach adopted relies on an efficient bisection projection. \n\nThe key idea is that if we want to project to a specific set, if we have access to an interior point of that set, given a neural net prediction outside that set, we can consider the line segment from the interior point to the prediction and move along this direction until the boundary is intersected. In order to improve the efficiency of the method, the paper aims to use interior points that have low eccentricity, which basically implies that the point is more 'central' in the feasible set.\n\nFinding such points is generally a hard problem and the authors resort to a relaxation that uses the Chebyshev center which finds a points that maximize the minimum distance from the boundary. To further improve efficiency, they train a neural network for this task using a suitable loss and provide sufficient conditions for this training to yield a NN that produces feasible interior points.\n\nThe method is evaluated on various convex and nonconvex problems and it consistently yields the fastest results with guaranteed feasibility and competitive objective values.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the recognition that our approach balances efficiency and optimality while improving over previous work, and that the simplicity of our method adds to its appeal. Below, we address each specific point raised in the review.\n\n---\n> `C1:  Assumptions on the objective function and optimality gap`\n---\n\nThe reviewer raises an excellent point about the relationship between solution distance and objective gap.\n\n  - We use solution distance as our primary metric for theoretical analysis, where the optimality gap is bounded by initial prediction error and projection distance. For **Lipschitz** objective functions, solution distance directly translates to bounds on objective value gaps, as demonstrated in our experiments with linear/quadratic objectives.\n\nWe acknowledge that for general non-smooth objectives, small solution distances might still yield large objective gaps. In our revision, we will clarify this relationship and specify the applicable scenarios of objective functions.\n\n\n\n\n---\n> `C2:  examples where H-proj can't be applied while B-proj can.`\n---\n\nThe H-Proj method [1] is limited by its ball-homeomorphic assumption. Our B-proj method can handle several practically relevant constraints that H-proj cannot:\n  - Non-simply-connected feasible regions (with \"holes\" or disconnected components) occurring in AC Optimal Power Flow problems [2] and rocket landing problems with exclusion zones [3].\n  - We provide a visual example in **Fig. 2** ([Link](https://anonymous.4open.science/r/Rebuttal_ICML_25-82D4/Reviewer%20cZEk.pdf)) showing where H-proj incurs significant optimality loss while our method succeeds on such topologically complex regions\n\n[1] L., C. L. Homeomorphic Projection to Ensure Neural-Network Solution Feasibility for Constrained Optimization. Journal of Machine Learning Research, 2024.\n\n[2] M. H... A survey of relaxations and approximations of the power flow equations. Foundations and Trends® in Electric Energy Systems, 2019\n\n[3] A. C. B.  Lossless convexification of nonconvex control bound and pointing constraints of the soft landing optimal control problem. IEEE TCST, 2013\n\n\n---\n> `C3:  ablation stufy of $\\gamma$ on optimality gap`\n---\n\nWe appreciate this valuable feedback. We would like to clarify that:\n\n  - Fig 3 validates Prop. 5.1, showing that robust margin $\\gamma$ reduces the number of training samples needed for feasibility under unseen inputs. With the same training sample, IPNN trained with $\\gamma$ consistently achieves better out-of-sample feasibility rates.\n  - We agree that directly evaluating objective gaps would better demonstrate our eccentricity-minimizing targets' effectiveness. We've provided additional results in **Figure 1** ([Link](https://anonymous.4open.science/r/Rebuttal_ICML_25-82D4/Reviewer%20cZEk.pdf)) showing how eccentricity minimization specifically improves solution (worst-case gap: 12\\% (no $\\gamma$) vs 5\\% (with $\\gamma$) in QP instance).\n\n\n---\n> `C4:  recent paper on linear constraints (GLinSAT)`\n---\n\nIt presents an efficient differentiable projection layer for general linear constraints. We will cite this work, along with the related works from their Table 1, and discuss their relevance in our revised manuscript.\n\n\n\n\n---\n> `C5:  eccentricity should be better motivated. formal argument for benefits  eccentricity`\n---\n\nThanks for your feedback on the formal argument of the benefit of eccentricity minimization.\n\nOur theoretical analysis formally establishes the benefits of eccentricity minimization:\n    \n- Prop. 4.1 shows the relationship between eccentricity and projection-induced distance, motivating our search for low-eccentricity interior points.\n - Prop. 5.2 demonstrates how robust margin reduces training samples needed to achieve feasibility guarantees on unseen inputs\n    \nWe'll further clarify the motivations of eccentricity with illustrations (**Fig. 3** ([Link](https://anonymous.4open.science/r/Rebuttal_ICML_25-82D4/Reviewer%20cZEk.pdf)) and explicitly present formal arguments for eccentricity minimization in bullet points in revised Section 4.2, reinforcing these points in our analysis.\n\n\n\n\n\n---\n> `Q1:  SDP feasibility and how to enforce the PSD constraint`\n---\n\nFor SDP problems (linear equality and PSD inequality):\n  - IPNN predicts independent variables and reconstructs dependent ones using equality constraints (Appendix A), then reshapes the vector prediction into matrix form.\n  - For inequality constraints, we use penalty methods to minimize constraint violation.\n\nFor PSD constraint:\n  - We use the matrix-sketching [1] to capture constraint violations by $v^TXv$ in a differentiable way, where $v$ is iteratively calculated. \n  - By maximizing $v^TXv$ when negative, IPNN learns to find interior points for PSD constraints.\n  - During bisection projection, we directly check PSD feasibility using torch.linalg.cholesky_ex()\n\n[1] N., D., S., W., W., D. P. Testing positive semidefiniteness using linear measurements. IEEE FOCS. 2022", "claims_and_evidence": "The claims are generally well supported and the paper provides clear explanations and proofs for its claims.\n\n- My main issue has to do with the use of eccentricity. On a formal level, since there are no assumptions on the function $f$ other than continuity, does minimizing the projection distance matter? The function can be nonconvex (it doesn't even have to be smooth), so unless the neural net prediction is already extremely close to the optimal point, the value of the objective could change significantly after projecting. I would expect the projection distance minimization coupled with some kind of smoothness assumption on $f$ to be more meaningful, or have I misunderstood something?\n\n\n- Conceptually, it would be nice to provide some examples of important problems where H-proj can't be applied while B-proj can. This will help emphasize how the generality of this work yields important benefits.", "methods_and_evaluation_criteria": "The proposed evaluations and methods make sense for the problem and are in line with the literature.", "theoretical_claims": "I have checked the claims and have briefly gone over the proofs. They seem correct.", "experimental_designs_or_analyses": "- I think the use of eccentricity is not well supported by the experiments. In figure 3, we see that with or without it, a certain number of samples is necessary to achieve 100% feasibility. In those plots, at least in terms of feasibility, it doesn't seem to make a difference. I believe a more interesting experiment is an ablation on $\\gamma$. Namely, what do the objective gaps look like when training the IP predictor without it? Is it necessary to deal with this issue or could any interior point work just as fine with this approach? \nI can see the appeal around the eccentricity argument though I can't help but wonder how it's ever 'cashed out' experimentally. It would be good to see a more careful experimental evaluation of its contribution.", "relation_to_broader_scientific_literature": "This paper provides a quite fast and general method for ensuring the feasibility of neural net outputs. Based on the experimental results, this paper achieves the best tradeoff between speed and optimality of solutions.", "essential_references_not_discussed": "There is a recent paper that handles linear constraints that I believe is not mentioned in the related work. See also references in that paper and its table 1.\n\nZeng, Hongtai, et al. \"GLinSAT: The General Linear Satisfiability Neural Network Layer By Accelerated Gradient Descent.\" arXiv preprint arXiv:2409.17500 (2024).", "other_strengths_and_weaknesses": "Overall, I think this approach balances efficiency and optimality well while improving significantly over previous work. At its core, the approach is fairly simple which makes it even more appealing. The paper is nicely written and it frames its contribution well in the context of related work.\n\nOn the other hand, to reiterate my main issue: I think the use of eccentricity (or a proxy for it anyway) should be better motivated and the experiments should also reflect its utility since a significant portion of the paper is spent discussing this. I can see at an intuitive level why you would like interior points with better 'centrality' and it helps minimize projection distance but, unless I misunderstood something, I don't think (as I explained above) a particularly compelling formal argument is made in the paper for its benefits.\n\nIn any case, I lean towards accepting this so I start with a tentative score and I will reconsider once the authors respond to the points/questions I brought up.", "other_comments_or_suggestions": "n/a", "questions_for_authors": "- Can you explain how you encode the SDP feasibility for the NN that predicts interior points? How do you enforce the PSD constraint on the matrix variable, i.e., what does the loss function look like in that case.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tehsmdoHQh", "reviewer": "Reviewer_h2io", "summary": "One of the main challenges of ML-based solution generation in constrained optimization is to ensure feasibility. This paper describes a method to produce feasible solutions that are close to ML-generated potentially-infeasible solutions for compact constraint sets with non-empty interiors, with a focus on efficiency. Like in typical ML-based solution generation, we assume that the constraint set is parameterized and we have training data over this parameter. The general idea is to learn an interior point with low eccentricity -- though in the implementation this is approximated with learning the Chebyshev center -- and use a standard bisection method between this interior point and the predicted solution to find a feasible solution close to the predicted one. This is supported by theoretical results that bound the projection distance and optimality gap based on the eccentricity of the interior point and other parameters. Computational results demonstrate that this method is fast relative to baselines with little loss to the optimality gap in most cases.\n\n\n### Update after rebuttal\n\nI maintain my review after rebuttals and discussions. I appreciate the authors making the improvements discussed in the rebuttals. I do not have further comments to add.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the recognition of our method's practical value for ML-based solution generation in constrained optimization problems, its theoretical foundation, and strong computational results. Below, we address specific points raised in the review.\n\n---\n> `C1: Ability to predict low-eccentricity points/Chebyshev centers`\n---\n\nWe've conducted additional experiments to verify that our IPNN indeed produces approximated Chebyshev centers with low eccentricity. As shown in **Fig. 1-2** ([Link](https://anonymous.4open.science/r/Rebuttal_ICML_25-82D4/Reviewer%20h2io.pdf)), \n  - During IPNN training: the penalty loss for constraint violation decreases and the robust margin $\\gamma$ increases. Thus, the minimum point-to-boundary distance increases and the eccentricity decreases\n  - After training, given new inputs, IPNN generalizes well to unseen input parameters, consistently producing central interior points.\n\nFor high-dimensional problems in our main experiments, directly measuring eccentricity is challenging due to difficulties in sampling boundary points, which is why we focused on end-to-end performance metrics.\n\n\n---\n> `C2: Definition of g(·)`\n---\n\n $g(x,\\theta)=[g_1(x,\\theta),\\cdots,g_{n_{\\rm ineq}}(x,\\theta)]$ refers to the constraint function for inequality constraints, as noted in Appendix A. We'll add this formal definition to the problem formulation section.\n\n\n---\n> `C3: Objective Gap calculation.`\n---\n\nYes, the Objective Gap (\\%) is averaged over all testing instances. We'll clarify this in the experimental section.\n\n\n\n---\n> `C4: Solution feasibility beyond NN applications`\n---\n\nWhile we focus on ensuring NN solution feasibility for constrained optimization, we acknowledge the broader applicability of our approach. We'll discuss generalizations to other problems in the revised manuscript.\n\n\n\n---\n> `Q1: Actual baseline computation time and IPNN training time`\n---\n\nWe provide the computation time for baseline iterative solvers shown in **Table 1**, and the IPNN training time for several optimization problems in **Table 2** via [Link](https://anonymous.4open.science/r/Rebuttal_ICML_25-82D4/Reviewer%20h2io.pdf). The training time ranges from 30 seconds to 8 minutes. \n\n\n\n\n\n---\n> `Q2:  empirical robustness and possible failure cases`\n---\n\nBased on Prop. 4.1, our method can produce significant optimality gaps in three scenarios:\n\n  - (a) \"Thin\" constraint sets with unavoidably large eccentricity\n  - (b) Poorly selected interior points (e.g., near boundaries) causing large eccentricity\n  - (c) Large initial NN prediction errors\n\nWe provide **Fig. 3** ([Link](https://anonymous.4open.science/r/Rebuttal_ICML_25-82D4/Reviewer%20h2io.pdf)) to illustrate these cases, which we'll include in our revised manuscript.\n\n\n\n---\n> `Q3: GPU usage for constraint checking`\n---\n\nYes, we use GPU for all NN-based methods and related processing (e.g., constraint checking in B-Proj and gradient evaluation in D-Proj) for fair comparison.\n\n\n\n---\n> `Q4:  0-th step in bisection and AC-OPF objective gap`\n---\n\nThe 0-th step returns the interior point.\n\nRegarding AC-OPF's objective gap: 2.5\\% gap (at the 0-th step) is significant in power systems because:\n  - Its objective represents generation cost for active power (a subset of all decision variables)\n  - Other variables primarily maintain physical power balance constraints, not in the objective\n  - In the power systems community [1,2], such gaps are meaningful as base generation costs are typically high (e.g., $260,200 for a 793-node network [2])\n\n[1] P., X., ... Deepopf: A DNN approach for security-constrained dc optimal power flow. IEEE TPS, 36(3). 2020\n\n[2] B., S., ... The power grid library for benchmarking ACOPF algorithms. arXiv. 2019\n\n\n\n---\n> `Q5: Bisection convergence with multiple intersections`\n---\n\nThe bisection algorithm can converge to one of multiple intersection points when they exist (Sec. 4.1). Although we didn't observe this in our non-convex engineering problems, we acknowledge this possibility.\n\nTo prevent convergence to points far from the initial prediction, we can adjust the bisection step size:\n- Standard bisection uses step size 0.5: $a_m = (a_l+a_u)/2$\n- Using larger step sizes (e.g., 0.75): $a_m = 0.25a_l+0.75a_u$ creates a trajectory starting closer to the initial point.\n- This approach promotes convergence to boundary points nearer to the original prediction.\n\n**Fig. 4** ([Link](https://anonymous.4open.science/r/Rebuttal_ICML_25-82D4/Reviewer%20h2io.pdf)) demonstrates that adjusting the step size from 0.5 to 0.75 helps avoid convergence to distant points. \n\n\n\n\n---\n> `Q6:  Prediction-aware variant evaluation`\n---\n\nWe only evaluated the prediction-agnostic version because it doesn't require optimal solution training data and already achieves small optimality gaps. Future work will explore prediction-aware variants for applications where objective values are highly sensitive to decision variables or where NN predictors struggle with initial approximations.", "claims_and_evidence": "The main claim of the paper is that the bisection projection method performs well for purposes of projecting a solution to a given feasible set. This is well-supported with a theoretical base and strong computational experiments. According to the experiments, this method provides feasible solutions with objective value generally comparable to the one obtained by orthogonal projection, which is the feasible solution closest to the predicted one, except that it is orders of magnitude faster. This type of computational result is valuable to make ML-based solution generation more practical.\n\nDespite the strong end-to-end results, in my opinion there is a gap in the experimental evidence: the paper proposes the prediction of an interior point to produce the projected point, but does not evaluate this predictor, only the end-to-end method. I am interested in seeing if this approach is able to predict the actual Chebyshev center, or produce points with low eccentricity. One could compute the Chebyshev centers of these sets and compare the results. While it is perfectly valid to argue that obtaining an accurate approximation to a minimum-eccentricity point is not too important if the method works well end-to-end, I would say that such experiments would help a reader validate the theoretical reasoning behind this algorithm and ensure that each step of the way is working well. That said, although this gap is a weakness of the paper, I would not say it is a major weakness in view of the end-to-end results.", "methods_and_evaluation_criteria": "The proposed method is clean and reasonable. While I would not consider the ideas in this paper to be very sophisticated, this relative simplicity is also what makes it appealing for practical use if one already has the framework for ML solution prediction. I am not well-versed in this line of work, but based on a quick literature search, this method appears to be novel. Furthermore, I believe that the impact of this method is fairly significant. Having a fast projection method like this one facilitates the use of ML-based solution generation methods in applications with strict latency requirements, particularly given how general this approach is (albeit limited to continuous optimization).\n\nAside from the experimental gap discussed above, the end-to-end experimental section is solid and comprehensive, though there is some room for improvement on the presentation of the results. The baselines are all appropriate, there is a good variety of applications, and the sensitivity analysis experiments provide additional insight. My concerns are generally minor and I put them in the Questions section below.", "theoretical_claims": "The theoretical results support the effectiveness of the method, particularly showing that you can control the quality of the projection if you use an interior point of low eccentricity. I read through the theoretical proofs in the appendix superficially and did not check them in detail.", "experimental_designs_or_analyses": "The experimental setup and analyses are generally solid with some room for improvement; more details are in the other sections.", "relation_to_broader_scientific_literature": "While I am not fully familiar with the literature of projection methods in this context, this paper does a good job at summarizing work in this area. In particular, the paper puts this method into context of previous works in Proposition 5.2.", "essential_references_not_discussed": "I am not aware of other references that need to be included in the paper.", "other_strengths_and_weaknesses": "All strengths and weaknesses are discussed in other sections.", "other_comments_or_suggestions": "Typos:\n* Line 241: Missing closing braces.\n* Prop. 5.2: Repeated \"to to\".\n* Equation (44) is missing a subscript on \\theta.\n\nEditorial issues:\n* Could you please add an explicit definition of g, if I have not missed it?\n* I assume that Objective Gap (%) is averaged over the testing instances. Could you please mention it explicitly?\n* The abstract mentions ensuring \"NN feasibility\". This was confusing at first read, as you just want to ensure solution feasibility, independently of the NN. I would suggest removing the \"NN\" from this expression.", "questions_for_authors": "1. Please address the concerns that were discussed above.\n\n2. I understand that speedup is relevant for comparing methods, but please include the actual compute time as well. This can be difficult to evaluate without absolute numbers for context.\n\n3. Could you comment on empirical robustness on the quality of the objective? While I see that the average optimality gaps are good, I am interested in knowing how often this approach might produce solutions that end up with poor solution quality. Or does it always produce good solutions? If there is anything that you could add to the paper on this topic, that would be great.\n\n4. Could you add some rough estimates on training times?\n\n5. At the end of p.7, the paper mentions that GPU-based processing accelerates constraint checking. Could you please clarify in the paper whether you are using GPUs for constraint checking in your computational experiments, or only for the neural network training and inference?\n\n6. Could you please add a clarification in Fig. 4 if the 0-th step is the midpoint or the interior point? If it is the interior point, it seems that the predicted AC-OPF interior point is not bad in terms of objective value; can you comment on why?\n\n7. If I understand correctly, the bisection method could converge to a point that is far from the NN solution if there are multiple options. For example, in Figure 2, the resulting point could lie in the boundary of the hole if the bisection point happens to fall inside it. This is of course only relevant for non-convex sets, but did you observe such a scenario occurring the applications you investigated? Is there no mechanism to avoid it? I imagine this might not be a significant issue for practical applications, but I am curious whether it could be.\n\n8. It was not clear to me if the prediction-aware variant of this method was actually evaluated. I believe that the main results are for the prediction-agnostic variant, correct? Have you performed any evalutions for the prediction-aware version? The idea of learning the two points jointly is seems promising and I am curious if it performs well.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uP2Z0PnD1K", "reviewer": "Reviewer_8qqe", "summary": "The paper introduces a bisection procedure to achieve feasibility of solution outputs from neural networks applied to constrained optimization problems.\n\n## update after rebuttal:\nI updated my recommendation following the discussion period.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Response**:\n\nThank you for reviewing our paper. We appreciate your feedback and the chance to address your concerns.\n\nWe believe our application of the bisection procedure to neural networks, while simple, offers a practical solution to feasibility challenges in constrained optimization. The simplicity is intentional and enables broader implementation.\n\nRegarding your concerns about our evaluation metrics, we believe there may be a misunderstanding about our methodology. Our approach does not require global optimal solutions of nonconvex problems but rather focuses on improving feasibility while maintaining initial NN solution quality — a practical consideration for real-world applications of neural networks in optimization.\n\nRegarding our work's relevance within the research landscape, our method contributes to the advancement of machine learning approaches for solution generation in time-sensitive applications, a value that other reviewers have also acknowledged.\n\nIn our detailed response below, we address your specific points. We also clarify the novelty, significance, and theoretical foundations of our work. We welcome your additional feedback and are committed to addressing your further comments in the following discussion period and improving both this work and our future research.  \n\nWe genuinely appreciate the time you and other reviewers have invested in evaluating our submission.\n\n\n\n\n\n---\n> `C1: The bisection procedure is very simple and relies on basic ideas. IPNN is an NN to predict IPs by minimizing some loss function with uniform sampling and Adam. Overall, this is a heuristic method.`\n---\n\nThank you for your assessment. While our approach uses fundamental principles, simplicity is advantageous when effectively solving complex problems. Our contributions are:\n\n- Addressing research gaps in identifying quality interior points (IP) for general constraint sets and developing real-time IP prediction capabilities\n- A novel loss function design specifically targeting low-eccentricity interior points to minimize projection-induced optimality gaps\n- Theoretical analysis providing optimality bounds (Prop. 4.1, Theorem 1) and feasibility conditions (Prop. 5.1), establishing our method's mathematical foundation beyond mere heuristics\n\n\n\n---\n> `C2: The evaluation measure is not sufficiently motivated considering that the global optimal solution of a nonconvex problem is unattainable, and it requires some interior point reference.`\n---\n\nWe acknowledge that global optimal solutions for general nonconvex problems are typically not guaranteed. However, our approach does not require global optimal solutions of nonconvex problems, but rather focuses on improving feasibility while maintaining initial NN solution quality — a practical consideration for real-world applications of neural networks in optimization.\n\nMoreover, our experiments evaluate solution quality by comparing objective values against state-of-the-art iterative solvers, providing direct empirical validation.\n\n\n\n---\n> `C3: Additionally, the bound established for this measure is not meaningful and seems quite straightforward.`\n---\n\nThe bounds provided in Theorem 1 offer practical guidance for minimizing the overall optimality gaps in our framework. Its value lies in its decomposition of the error sources:\n- Initial prediction errors, which are well addressed by existing NN-based approaches;\n- Projection errors, which are the primary focus of our work;\n- Finite step bisection errors, which converge exponentially, demonstrating the efficiency of our framework.\n\nThis decomposition not only clarifies the theoretical foundations of our approach but also provides insights for algorithm design and optimization. By identifying the projection error as a critical component that previous works have overlooked, we establish a clear direction for improving the performance of our framework.\n\n\n\n\n\n---\n> `C4: The key contributions ..., in my opinion, less relevant to research-related literature.`\n---\n\nWe respectfully disagree with this assessment. \n- Neural networks for accelerating optimization problems represent an active and growing research area with significant interest from both machine learning and optimization communities, as evidenced by recent publications in top-tier venues, including ICML, NeurIPS, ICLR, and JMLR (see detailed discussions in Related Work Section.)\n- Our work addresses a fundamental challenge in this domain - ensuring the feasibility of NN predictions for constrained optimization - which has been identified as a key limitation in prior work. By providing a solution with theoretical guarantees, our paper makes a meaningful contribution to this important research direction.", "claims_and_evidence": "The paper provides a bisection procedure, establishes its claims, and presents numerical results to support its contribution.", "methods_and_evaluation_criteria": "The method comprises two elements: a bisection procedure and an IPNN training.\nThe bisection procedure is very simple and relies on basic ideas -- between a feasible point in the interior and an infeasible point there is a line in which there are points that are feasible so searching on that line can yield a closer feasible point.\nIPNN is a neural network to predict interior points by minimizing some loss function with uniform sampling and Adam. Overall this is a heuristic method.\n\nThe evaluation measure is the distance between the optimal solution of the problem and the feasible point obtained from the infeasible solution output of the NN. This measure is not sufficiently motivated considering that global optimal solution of a nonconvex problem is unattainable and it requires some interior point reference. \nAdditionally, the bound established for this measure is not meaningful and seems quite straightforward.", "theoretical_claims": "The theoretical claims mainly follow from simple arguments and the underlying assumptions.\nI briefly verified their correctness.", "experimental_designs_or_analyses": "I only checked the theoretical analysis and methodology.", "relation_to_broader_scientific_literature": "The key contributions are related to implementation and utilization of NNs as optimization tools for constrained optimization, making them, in my opinion, less relevant to research related literature.", "essential_references_not_discussed": "no", "other_strengths_and_weaknesses": "The paper proposes a technical procedure to tackle feasibility issues arsing the usage of NNs to solve constrained optimization problems.\nIt uses straightforward technical solutions with simple theoretical analysis.", "other_comments_or_suggestions": "no", "questions_for_authors": "no", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper tackles an important problem when using neural networks for optimization tasks: how to make sure that the output is a feasible solution? The authors provide an algorithm to practically overcome this issue and conduct a theoretical analysis and a computational study. The significance of this work was judged differently by the different reviewers, with the main criticism by one reviewer being that the method is simple and the theoretical analysis straightforward. The discussion was productive though, with reviewers, while not agreeing, being active and understanding for the other perspective. In the end, I follow the argumentation of the two reviewers recommending accept, saying that a simple but effective method is indeed very useful and a theoretical analysis, even if not too technical, definitely appreciated. This work is certainly a solid approach to ensure feasibility, the paper is well-written and meets the quality requirements for ICML.
Decision: Accept (poster)