A graph-based global optimization framework for problems with nonconvex norm constraints and penalty functions

Authors: Danial Davarnia, Mohammadreza Kiaghadi
Primary area: optimization
Keywords: Norm Constraints, Sparse Parameter Estimation, Nonconvex Regularization, Global Optimization, Mixed-Integer Nonlinear Programs, Decision Diagrams

Abstract:
Optimization problems with norm-bounding constraints appear in various applications, from portfolio optimization to machine learning, feature selection, and beyond. A widely used variant of these problems relaxes the norm-bounding constraint through Lagrangian relaxation and moves it to the objective function as a form of penalty or regularization term. A challenging class of these models uses the zero-norm function to induce sparsity in statistical parameter estimation models. Most existing exact solution methods for these problems use additional binary variables together with artificial bounds on variables to formulate them as a mixed-integer program in a higher dimension, which is then solved by off-the-shelf solvers. Other exact methods utilize specific structural properties of the objective function to solve certain variants of these problems, making them non-generalizable to other problems with different structures. An alternative approach employs nonconvex penalties with desirable statistical properties, which are solved using heuristic or local methods due to the structural complexity of those terms. In this paper, we develop a novel graph-based method to globally solve optimization problems that contain a generalization of norm-bounding constraints. This includes standard $\ell_p$-norms for $p \in [0, \infty)$ as well as nonconvex penalty terms, such as SCAD and MCP, as special cases. Our method uses decision diagrams to build strong convex relaxations for these constraints in the original space of variables without the need to introduce additional auxiliary variables or impose artificial variable bounds. We show that the resulting convexification method, when incorporated into a spatial branch-and-cut framework, converges to the global optimal value of the problem under mild conditions. To demonstrate the capabilities of the proposed framework, we conduct preliminary computational experiments on benchmark sparse linear regression problems with complex nonconvex penalty terms that existing global solvers cannot model or solve. This establishes our framework as the first algorithm capable of globally solving such challenging mixed-integer nonlinear programs.

Decision: reject
Reviewer scores: 3, 3, 5

Reviews and discussion:
<thread>
creation date:
1730205322069

thread_type:
official_review

<thread_object>
creator: reviewer_ccje

<content>
summary:
The paper considers convex optimization with a norm bounding constraint. These constraints can be any $p$-norm, where $p \in [0,\infty)$ as well as some non convex penalty terms such as SCAD and MCP. When $p\in (0,1)$, the norm is neither convex nor concave, and as a result standard methods don’t work directly. These kinds of problems appear in several applications and sometimes also appears as a regularizer. Current methods that give exact solutions either use extra variables, thus increasing the size of the problem by a lot, are tailored to the objective function, or are heuristic methods.

This paper gives a unified algorithm that can handle all the different constraints, including non continuous and non convex constraints. The method is based on using decision diagrams. The method roughly uses a scale function to capture these domain constraints, and then uses a decision diagram based relaxation to capture these constraints. The key is that the scale function is able to capture all the listed domain constraints. The paper focusses on proving how to use these scale functions within DD’s to capture the constraints. In the end there are some experiments that use a quadratic function with the SCAD penalty function and they show the solution times for selected datasets with different penalty functions.

strengths:
The paper is able to handle an important set of problems and gives a new technique. It is an interesting connection between non convex optimization and graph theory, since most of the graph theoretic optimization results are captured via convex optimization.

weaknesses:
I think there is no provable bound on the number of iterations, or the rate of convergence of the method. It seems like the authors can prove that the method converges in the limit but there is no way to show the rate of convergence even for simple objectives. Also, in the experiments it is not clear what the method is compared against.

questions:
I have some questions to the authors:

1. Points (i) to (viii) on Pages 2 and 3 seem to have a lot of redundant statements and is repeating what was stated in the paragraph before. I think it can be compressed so that the main message is clear while covering all the points.
2. The SCAD and MCP penalty terms are defined in Prop 1. Would be useful to define in the main text!
3. What all objective functions can be handled by the method? It would be useful to include this explicitly. The constraints are very clear but it is useful to know the functions we can handle as well.
4. Is it possible to show any rates of convergence even for some easy objectives?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730707036305

thread_type:
official_review

<thread_object>
creator: reviewer_htui

<content>
summary:
The authors propose an innovative graph-based method to globally solve optimization problems with generalized norm-bounding constraints. This approach leverages decision diagrams to create strong convex relaxations for these constraints directly in the original variable space, eliminating the need for auxiliary variables or artificial variable bounds. The preliminary computational experiments on benchmark sparse linear regression problems show the effectiveness of this framework.

strengths:
1. This paper presents a new graph-based framework that leverages decision diagrams to address a broad class of optimization problems with norm-bounding constraints. Unlike traditional methods, it offers a unified approach to solving convex and nonconvex problems.
2. The authors provide mathematical proof showing that, under mild conditions, the proposed method guarantees convergence to global optima.
3. Certain computational experiments are provided on benchmark problems to demonstrate the algorithm's performance.

weaknesses:
1. The proof is unreadable for readers.
2. In Section 4.2, there is no brief description of the method to obtain dual bounds inside an outer approximation framework.
3. In Figure 1, the instance number is difficult for readers to understand.
4. The experiments are insufficient to support your conclusion.

questions:
1. Could you present the proofs of your propositions in an easier way for readers to understand? For instance, consider breaking them into multiple paragraphs instead of a single block of text.
2. In Section 4.2, you should provide a brief description within the main body rather than summarizing it in the appendix.
3. The description of the x-axis in Figure 1 is challenging for readers to understand. Could you clarify its meaning?
4. Can you explain why you chose 5% for a relative optimality gap as the stopping criterion for your algorithm?
5. Did you conduct any experiments to justify setting 50 (and 100) iterations for your tests?
6. Have you conducted any experiments to explore the impact of $\lambda$ and $\gamma$? 
7. Have you compared the runtime of your method with the state-of-the-art (SOTA) method for the same problem under either convex or nonconvex conditions?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730750100673

thread_type:
official_review

<thread_object>
creator: reviewer_m5gj

<content>
summary:
The paper introduces a graph-based global optimization framework targeting problems with norm-bounding constraints and nonconvex penalty functions, such as SCAD and MCP. Utilizing decision diagrams (DDs), the method constructs strong convex relaxations directly in the original variable space without adding auxiliary variables. Preliminary experiments on sparse linear regression benchmarks demonstrate the framework’s ability to solve challenging instances that existing global solvers cannot handle.

strengths:
1. The framework accommodates a wide range of norm types, including both convex ($\ell_p$ for $p \geq 1$) and nonconvex ($\ell_p$ for $p \in (0,1)$, SCAD, MCP) regularization, enhancing its versatility across various optimization problems.

2. The paper provides the theoretical convergence guarantee to the global optimum and properties of the convex relaxations generated by the DD-based method.

weaknesses:
1. The computational experiments presented are preliminary and focus on small to medium-sized instances. To fully assess the framework’s scalability and performance, more extensive benchmarking on larger and more diverse datasets is necessary.

2. The DD-based method can grow exponentially with the number of variables. Although node-merging techniques and width limitations are proposed to control DD size, the practical scalability for very large-scale problems remains uncertain and requires further empirical validation.


3. The paper allocates a disproportionate amount of space to providing proofs in the main text while omitting essential technical details, such as the graph-based convexification method.

questions:
Please refer to Weaknesses.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper introduces a graph-based optimization framework for norm-bounded and nonconvex norm constraints. The reviewers raised several concerns regarding the clarity of the theoretical results, the scalability of the approach to larger problems, and the insufficient experimental validation of the method. The authors did not provide convincing responses to address these concerns. Overall, the paper requires significant revisions, particularly in improving the readability and presentation of the theoretical results, addressing scalability issues, and enhancing experimental validation of the method. Therefore, I recommend rejecting this paper in its current form.