Questions tagged [nonconvex-programming]

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

Filter by
Sorted by
Tagged with
2 votes
1 answer
73 views

Reducing optimality to feasibility in non-linear programs

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 ...
Erel Segal-Halevi's user avatar
0 votes
1 answer
77 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 ...
Muhammad's user avatar
0 votes
0 answers
53 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 ...
AspiringMat's user avatar
3 votes
0 answers
47 views

Are there algorithms for minimizing a sum of convex and non-convex/non-concave functions?

Consider the problem \begin{equation} \begin{aligned} \min_{x} \quad & f(x) + g(x), \\ \textrm{s.t.} \quad & x \in X \end{aligned} \tag{1} \end{equation} where $X \subset \...
mhdadk's user avatar
  • 455
1 vote
0 answers
63 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 ...
Jingwei Ma's user avatar
1 vote
0 answers
34 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}$ ...
independentvariable's user avatar
3 votes
2 answers
171 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?
Abbas Khademi's user avatar
-1 votes
1 answer
56 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}^...
KGM's user avatar
  • 2,211
-1 votes
2 answers
105 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 $...
zdm's user avatar
  • 381
3 votes
1 answer
102 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?
fischer justin's user avatar
1 vote
1 answer
45 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 &...
madhafakha's user avatar
1 vote
2 answers
205 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 \...
Meet Saiya's user avatar
2 votes
2 answers
97 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 (...
Muhammad's user avatar
1 vote
1 answer
33 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 ...
Muhammad's user avatar
1 vote
2 answers
109 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) ...
Muhammad's user avatar
1 vote
2 answers
574 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 ...
Muhammad's user avatar
2 votes
1 answer
122 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: $...
fearloathing121's user avatar
2 votes
2 answers
265 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 ...
WaMIMO's user avatar
  • 33
-1 votes
1 answer
122 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 ...
Hussein Sharadga's user avatar
0 votes
1 answer
106 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: ...
Hussein Sharadga's user avatar
0 votes
0 answers
204 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 ...
Hussein Sharadga's user avatar
1 vote
1 answer
338 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 ...
Hussein Sharadga's user avatar
2 votes
0 answers
56 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....
Reza Farahani's user avatar
4 votes
0 answers
93 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$ ...
Ghulam Mohy-ud-din's user avatar
1 vote
2 answers
184 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, ...
Hussein Sharadga's user avatar
4 votes
1 answer
298 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 ...
user12632521's user avatar
2 votes
1 answer
91 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}\...
Keith's user avatar
  • 155
1 vote
0 answers
71 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 find $n$ RGB colors with large inter set color distances and good color distance to white. ...
worldsmithhelper's user avatar
3 votes
1 answer
81 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*} ...
user1868607's user avatar
8 votes
1 answer
259 views

Maximize correlation subject to nonconvex correlation constraints

Let $r, 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, \...
boombeach's user avatar
2 votes
0 answers
62 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$ ...
independentvariable's user avatar
4 votes
1 answer
115 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_{...
Keith's user avatar
  • 155
4 votes
3 answers
166 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 ...
Optimization team's user avatar
1 vote
2 answers
249 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 ...
vp_050's user avatar
  • 169
5 votes
1 answer
482 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,...
vp_050's user avatar
  • 169
4 votes
1 answer
508 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 $...
vp_050's user avatar
  • 169
4 votes
1 answer
162 views

Maximization of a nonconvex bi-variate function

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$, ...
Amin's user avatar
  • 2,150
4 votes
1 answer
240 views

Is it always possible to optimize a multivariate function sequentially?

Suppose we have a multivariate function like $f(x,y,z)$ which should be maximized with the constraints $g_i(x,y,z)\le 0 \quad \forall i$. The general rule is to use KKT conditions and derive all KKT ...
Amin's user avatar
  • 2,150
1 vote
1 answer
101 views

Maximization of a differentiable and nonlinear function over a bounded space

I have a nonlinear bi-variate optimization problem like $\max \: f(x,y)$ where $f(x,y)$ is a nonlinear and differentiable function of both variables, and $0\le x\le 1$, $\:0\le y \le ub$. In order to ...
Amin's user avatar
  • 2,150
3 votes
1 answer
245 views

Non-Convex QCP model - Used Method in Gurobi

I have the following question: I have a non-convex QCP model. In the parameter description for method it says that "Only barrier is available for continuous QCP models". However, the dual ...
Handballer73's user avatar
1 vote
1 answer
337 views

How to convexify log(convex) function?

I have the following optimization problem: \begin{align}\max_x&\quad\log_2(1+|a+bx|^2+cx^2)\\\text{s.t.}&\quad0\le x\le1\\&\quad(1-x^2)\ge\text{constant}\end{align} where $a$ and $b$ are ...
Shayan zargari's user avatar
1 vote
1 answer
160 views

Find an upper bound for an objective function

My objective function is $\log_2(1+{x^2y^2})$ and I found two upper bounds for $x^2$ and $y^2$. For example, assumed that we have the following upper bounds: $x^2\leq\text{constant}_1^2$ and $y^2\leq\...
Shayan zargari's user avatar
1 vote
1 answer
223 views

Non-linear optimization local or global solution

In an NLP, I have a constraint that I would like to formulate in a convex manner preferably without introducing binary variables and/or big M formulations if possible. The actual problem is non-convex ...
Marry's user avatar
  • 81
4 votes
0 answers
73 views

How can non-polyhedral sets be investigated?

To derive problem-specific cutting planes for some given problem (think something like TSP problem), one common way is to study small examples. To this end, one can create small instances for the ...
user3680510's user avatar
  • 3,635
4 votes
1 answer
535 views

how to implement an optimization function with polynomial in Gurobi (Java)

I have the following problem: I have an objective function with the optimization variable $x$, which looks simplified like this: $ZF = (a+b)*(x+1)$ Here $a$ is simply a constant value. However, behind ...
Handballer73's user avatar
4 votes
1 answer
369 views

Maximizing a piecewise-linear convex function

Note: Initially posted on MathOverflow. I am working on an optimization problem where some of the terms of the objective function to maximize are expressed as a piecewise linear function of variables:...
lovasoa's user avatar
  • 141
11 votes
2 answers
2k views

Trustful Nonlinear Programming

Is it possible for an NLP solver to claim that a knowingly feasible problem is infeasible? Shouldn't the solver be able to provide a solution (of course not necessarily the global optimum but a ...
Clement's user avatar
  • 2,180
3 votes
1 answer
79 views

Maximize $\sum_{i=1}^n 1/x_i$ subject to an SDP constraint

I would like to solve the following problem: \begin{align}\max_{x_1, \ldots, x_n}&\quad\frac{1}{x_1} + \frac{1}{x_2} + \cdots + \frac{1}{x_n}\\\text{s.t.}&\quad\sum_{i=1}^n x_i A_i \succeq A_0\...
Michael S.'s user avatar
3 votes
1 answer
188 views

"Rank 1" type constraint $X=vw^\top$: MILP representation? Convex relaxation? Other tractable approach?

Suppose $X\in\mathbb{R}^{m\times n}$, $v\in\mathbb{R}^m$, $w\in\mathbb{R}^n$ are variables from an optimization problem, which also includes the constraints: $$0\le v\le a$$ $$0\le w\le 1$$ $$w_1+\...
cfp's user avatar
  • 235
3 votes
0 answers
42 views

Stationary conditions for intersection

I wondered about this question for sometime. Definition of Stationarity (P) $\mbox{min} f(x)$ s.t $x\in C$ Let $f$ be $C^1$ function over a closed and convex set $C$ . then $x^*$ is called a ...
convxy's user avatar
  • 405