# Questions tagged [nonconvex-programming]

For questions about non-convex optimization problems where the objective or any of the constraints are non-convex.

95 questions
Filter by
Sorted by
Tagged with
10 views

### Generating Random Polytopes for Nonconvex Optimization

I am working on comparing different approaches for solving the following nonconvex optimization problem: \begin{align*} \min_{x} \quad & g(x) \\ \text{s.t.} \quad & Ax = b, \\ & x \geq 0. \...
65 views

### Special Case of Minimum Cost Flow Problem with Variable Cost

I am working on an optimization problem similar to MCF with variable cost, but with an adjustment in the objective function. The cost function $f$ to minimize that is continuous, piece-wise linear and ...
28 views

### On Linear Relaxation of Convex Quadratic Maximization over Linear Constraints

Consider the following QP problem, where the matrix $Q$ is positive definite: \begin{align*} \max_{x} \quad & x^\top Qx + c^\top x \\ \text{s.t.} \quad & Ax \geq b, \\ & ...
1 vote
66 views

### On Linear Relaxation of Standard Quadratic Programming

Consider the following StQO problem where matrix $Q$ is indefinite: \begin{align*} \text{minimize} \quad & x^\top Qx \\ \text{subject to} \quad & e^\top x = 1, \\ & ...
1 vote
100 views

### How to set up a convex concave procedure (difference of convex programming) for the minimization of multilinear term?

It seems that there are a lot of advantage of approximating nonconvex problem with the convex concave procedure when one is interest in finding local extrema or KKT points only. Out of curiosity, ...
82 views

### Optimization under cardinality constraint

When we consider the following optimization problem: \label{P}\tag{P} \begin{array}{ll} \displaystyle\min_{x \in \mathbb{R}^n} & f(x) \\ \text{s.t.} & Ax = b,~ x \geq 0, \\ &...
105 views

### How to model this constraint in a better way?

I have a resource allocation problem. There are $M$ users and $N$ resources (machines). One user can be assigned to multiple resources/machines. But maximum $B$ machines can be activated at a time for ...
• 2,397
103 views

### Exception from IBM ILOG CPLEX: CPLEX Error 5002: 'q1' is not convex.->

I am currently solving a scheduling optimization problem regarding the fleet management of AGV/AMR. I always get the same error and I don't know where to start to solve it. Here's the code snippet for ...
• 1
188 views

### How to describe nonlinear programming in gurobipy?

The optimization task The optimization task concerned here is: A square matrix $A\in \mathbb{R^{5\times 5}}$ satisfies the condition: the elements of the first row all are 1, the elements of the ...
• 197
44 views

### Using Knitro or Xpress SLP via FICO Xpress Python API for Local and Global Solve Methods

Can someone guide me on how to utilize the FICO Xpress Python API to invoke Knitro or Xpress SLP, specifically for choosing between local and global optimization methods? I am referring to the version ...
• 23
27 views

### Differences between non-convex and convex optimization problem with l0-Norm Regulization

I'm currently in the process of writing my bachelor's thesis and trying to deal with the theory behind the model in this paper Risk-calibrated Super-sparse Linear Integer Model (Berk Ustun and Cynthia ...
47 views

### nonlinear least square

The following objective function is non-convex. How can we solve min$\left|| A^{\dagger}A-I \right||_F$? Will adding an auxiliary matrix be helpful or not? I am trying to solve it using ADMM Any ...
110 views

### How to solve a min max problem?

The optimization model is defined as, \begin{aligned} \min_{\bf x}\max_{\bf y}f_{0}(y)\\ s.t.\bf f_1(y)=0\\ \bf f_2(y)\leq0\\ \bf f_{3}(x,y)\leq0\\ \bf f_{4}(x)\leq0 \end{aligned} where $f_0(y)$ ...
80 views

It is well-known that, given a linear program: minimize $c^T x$ such that $A x\leq b$, it is possible to reduce the program to deciding feasibility of the following set of constraints: $Ax \leq b, A^T ... • 1,015 0 votes 1 answer 101 views ### Convex approximation of an expression with fraction for CVX I have the optimization problem $$\underset{\mathbf{x} \in \Bbb C^N}{\max} \left| \frac{\mathbf{x}a-b}{\mathbf{x}c+b} \right|^2$$ where$a$,$b$and$c$are some scalars. I want to solve this ... • 37 0 votes 0 answers 71 views ### Multilinear programming over the simplex Let$\triangle_3 \in \mathbb{R}^3$be the$3-simplex. I am solving a series of multilinear programming problems that looks like this: \text{Maximize}\sum_{0\leq i, j, k \leq 3} A_{i,j,k} x_i x_j ... • 151 3 votes 0 answers 55 views ### Are there algorithms for minimizing a sum of convex and non-convex/non-concave functions? Consider the problem \begin{aligned} \min_{x} \quad & f(x) + g(x), \\ \textrm{s.t.} \quad & x \in X \end{aligned} \tag{1} where X \subset \... • 639 1 vote 0 answers 67 views ### Find arg(min) when global min is known Suppose we are trying to optimize a uniformly continuous function with multiple critical points. If the value of global minimum is already known before optimization, can we find arg(min) within ... • 11 1 vote 0 answers 39 views ### Convex quadratic maximization over cartesian product of simplices Suppose we are maximizing f(x^1,\ldots,x^t)= \begin{bmatrix}{x^1}^\top & \ldots & {x^t}^\top \end{bmatrix}^\top Q \begin{bmatrix}{x^1}^\top & \ldots & {x^t}^\top \end{bmatrix} ... • 4,010 3 votes 2 answers 192 views ### When Biconvex function is Pseudoconvex function? Is a Biconvex function f(x,y):=yg(x), (where g is a convex function, y>=0), Pseudoconvex function? -1 votes 1 answer 77 views ### How to linearize the multiplication of variables and transform this into an MILP? Let C=10, U=50 P_c,c=1,\cdots,C and \alpha_{u,c},u=1,\cdots,U,c=1,\cdots,C are optimization variables \alpha_{u,c} is binary \sigma_{u,c}, d_{u,c} are known parameters \min \sum_{c=1}^... • 2,397 -1 votes 2 answers 144 views ### How to maximize sum of cosine squared plus sum of sine squarred? I want to maximize this function\left(\sum_{k=1}^{N}\cos(2\pi f_1t_k+\phi_k+\alpha\pi(k-1))\right)^2+\left(\sum_{k=1}^{N}\sin(2\pi f_1t_k+\phi_k+\alpha\pi(k-1))\right)^2,where the variables are ... • 403 3 votes 1 answer 109 views ### using milp for a linear complementarity problem I have to minimize c^Tx subject to Ax = b, x_iw_i = 0 for all i, with x non negative continuous and w binary. What model should I use to solve this problem? 1 vote 1 answer 59 views ### \min\{f(x_1),\dots,f(x_n)\} with other constraints I have an optimization problem which goes: \begin{align*} \text{Minimize:} \\ & \sqrt{x} + \sqrt{y} \tag{NL-objective} \\ \text{Subject to:} \\ &3x + 2y \geq 2 &... 1 vote 2 answers 450 views ### Is there a way to obtain coefficient matrix A and RHS b of constraints equation from cplex or guribi in python? I have a non-linear program, minimizing sum of concave functions subject to linear constraints. Hence I'm using a different solver(in Julia). However, that solver assumes we have constraints in Ax \... 2 votes 2 answers 111 views ### Potential methods for solving quadratic optmization problem I am trying to solve a non-convex optimization problem with the help of sequential quadratic programming. I need to develop an algorithm inside SQP to solve this subproblem. What potential methods (... • 37 1 vote 1 answer 42 views ### Non convex quadratic problem with complex variables I am trying to solve a non convex optimization problem with the help of sequential quadric programing. My optimization variables are complex and I have expressions for gradients, hessian etc but all ... • 37 1 vote 2 answers 125 views ### My barrier function is always giving a complex number I am working on implementing the interior point method, and the barrier function always gives me a complex number. B(x) = f(x) - t * sum(ln(hi(x))). I have changed the value of 't' to see the B(x) ... • 37 1 vote 2 answers 606 views ### Non linear programming I want to solve a large scale non linear optimization problem and there are two methods interior point method and sequential quadric programing usually used to solve non linear optimization problem. I ... • 37 2 votes 1 answer 131 views ### Formulation of nonlinear nonconvex optimization problem and finding appropiate solver Consider the notation and objective below for this sequential resource allocation problem: Allocation channels i \in (1, 2) Spend/Cost timestep i channel j: C_{i, j} Total resource: B Horizon: ... 2 votes 2 answers 281 views ### An if-then-else logic to construct constraint I was hoping to get some help in modelling the following logic, I know that it would use some kind of Big M formulation but I am not sure how. Thank you in advance! \Omega is a set whose values are ... • 33 -1 votes 1 answer 161 views ### Ipopt finds a better solution if I do not eliminate the zeros in the hessian matrix ?(we eliminate the zeros by defining the structure) I use Ipopt to solve a problem with sparse hessian and jacobian matrices. If I provide the hessian matrix: its structure, and the non zeros elements in the hessian matrix, it will be really fast. If I ... 0 votes 1 answer 147 views ### The max_wall_time and max_cpu_time in ipopt are not working? The max_wall_time and max_cpu_time are not working in ipopt (cyipopt). See example: ... 0 votes 0 answers 360 views ### Can we use the Jax library with ipopt to calculate the hessian matrix and Jacobian and still be able to define the structures? When solve with ipopt, we can use Jax to calculate the hessian matrix and jacobian instead of providing it ourselves. However, ipopt with Jax is very slow for large problems. If we calculate the ... 1 vote 1 answer 540 views ### Should I provide the hessian matrix, hessian structure, and Jacobian structure if I use cyipopt (IPOPT) if I am concerned about computation time? If I use IPOPT (cyipopt) to solve nonlinear problems of large scale. It is optional to provide or not provide the hessian matrix, hessian structure, and Jacobian structure. The question is which one ... 2 votes 0 answers 66 views ### Minimizing sum of similar functions with a dependence Consider an objective function in the form of minimization of maximization that is the sum of N similar functions f\left(x\right)\ge 0, \ \forall x. The summation of all variables is constant (e.... 4 votes 0 answers 107 views ### How to linearize or convexify a constraint with a square root of sum of two variables? Here is the constraint:\text{Pa} + \text{Pb}=a + b \sqrt{\text{Ir}^2 +\text{Ii}^2} + c (\text{Ir}^2 +\text{Ii}^2)$$Here \text{Pa}, \text{Pb}, \text{Ir}, and \text{Ii} are variables. a, b, c ... 1 vote 2 answers 219 views ### Does the cvxpy replace the max function by MIP formulation under the hood? Does the cvxpy replace the max function, which is convex, by MIP formulation under the hood when shows up in the constraints (for example, \max(x,y)\le z) or in the objective function? In gurobipy, ... 4 votes 1 answer 300 views ### Endowment of an agent I was going through the Shapley-Folkman-Starr Lemma (https://simons.berkeley.edu/sites/default/files/docs/3605/simons2.pdf) and I came across the term "endowment" of an agent. My assumption ... • 111 2 votes 1 answer 94 views ### How do we call this optimization problem? Let f_k\colon\Bbb R^n\to\Bbb R, k=1,\dots,K, be differentiable (possibly nonconvex) functions and X\subset\Bbb R^n be a convex set. Consider the following optimization problem:$$ \min_{x\in X}\... • 155 1 vote 0 answers 75 views ### Does Gurobi solve QCQMIPs with Quadratic terms faster with then Bi-Linear terms in general? Based on the color distance function defined here i try to findnRGB colors with large inter set color distances and good color distance to white. ... • 4,037 3 votes 1 answer 88 views ### Methods to solve integer linear inequalities with products of two variables I'm interested in solving the following system of equations over the integers: \begin{align*} x_l^3 &\le x_l^1x_l^2 & \text{ for } l = 1,\ldots,s \\ A x &\le b \\ 0 &\le x \end{align*} ... • 173 8 votes 1 answer 301 views ### Maximize correlation subject to nonconvex correlation constraints Letr, z$and each of$u_i$be a length$n$vector. Iād like to maximize the correlation between$z$and$r$(when that correlation is positive) while keeping$z$āawayā from$u_i$ās. Formally, \... 2 votes 0 answers 66 views ### FOC point vs Stationary point in local optimization In this SIAM Review paper the authors are giving the following necessary condition for a point being a local maximum of a convex function: Let$F: \mathbb{R}^n \mapsto \mathbb{R}$be convex. If$x$... • 4,010 4 votes 1 answer 120 views ### Convex-Constrained Nonconvex-Nonconcave Minimax Problem In the mathematical optimization theory, I have taken a glance at many papers which deal with the unconstrained convex-concave or nonconvex-concave minimax optimization, i.e.,$$\min_{x\in X}\ \max_{... • 155 4 votes 3 answers 226 views ### How to find the point on the exterior of a given set of points? Suppose we do have a set of points (all on a plane ). How to find the smallest hull containing all these points ? How to find the points (among these given points) that are at the exterior layers of ... • 1,378 2 votes 2 answers 328 views ### Branch and bound method for solving non-convex integer non-linear multi-objective optimization problem? Following are the characteristics of my problem: Objective function: two non-linear functions and one linear function Decision variable: two integer variables ($X_1$and$X_2$) Constraint: three (two ... • 179 5 votes 1 answer 547 views ### What methods are used to solve multi-objective optimization problem with non-linear objective functions and integer decision variables? Case 1: NLP When either the objective function or at least one of the constraints or both are non-linear it is a NLP. We use generalized reduced gradient or Quadratic Programming to solve NLP. However,... • 179 4 votes 1 answer 602 views ### How to linearize a non-convex optimization objective function? The non-convex multi-objective optimization problem in my case is defined below: Objective 1: Minimize$f_1(X_1,X_2)=C_0+C_1(1/X_1)+C_2(X_2/X_1)+C_3X_1+C_4X_2+C_5(X_2^2/X_1)$Objective 2: Minimize$...
• 179
Suppose we have a bi-variate function like $f(x,y)$ which is concave in $x$, $\frac{d^2f(x,y)}{dx^2} = -g(x,y)<0$ (that is $f(x,y)$ can be a function with high order in $x$ ) but convex in $y$, ...