Questions tagged [convex-optimization]

Convex optimization, a subfield of optimization, studies the problem of minimizing convex functions over convex sets. The convexity property can make optimization in some sense "easier" than the general case - for example, any local minimum must be a global minimum.

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

Basic question about definition of a convex optimization problem

In lecture notes by Nemirovsky and BenTal (2023), I found the following definition of a convex optimization problem: MY QUESTION: why do we need both the functions $f_i$ and the domain $G$? ...
Erel Segal-Halevi's user avatar
2 votes
2 answers
94 views

How can I relax the equality constraint in this problem?

Consider the following problem \begin{equation} \begin{aligned} \min_{x,y} \quad & f(x,y), \\ \textrm{s.t.} \quad & \exp(x) + \exp(y) = 1 \end{aligned} \tag{1} \end{...
mhdadk's user avatar
  • 440
1 vote
0 answers
47 views

transform minimize weighted sum of absolute value into a linear optimization

For example, we have an optimization problem $$ \min \sum_{i=1}^{n} |w_{i} - a_{i}| b_{i} \quad \text{s.t.} \quad \sum_{i=1}^{n} c_i w_i = 0 $$ and $a_i, b_i, c_i$ are given. How to convert it into a ...
Pique's user avatar
  • 11
1 vote
0 answers
44 views
+50

Convex programming without a lower bound on the feasible region size

I need to solve a convex minimization problem of the form: minimize $f(x)$ such that $g_i(x)\leq 0$, where the $g_i$ are convex functions given by a value oracle. As far as I know, to use the ...
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
1 vote
0 answers
67 views

MOSEK via fusion vs API vs CVXPY

In Python, I would like to solve a collection of problems, that are all solvable via MOSEK's conic optimization solvers (ExpCone, SOCP, etc.) I have tried CVXPY. I get very robust and reliable results,...
independentvariable's user avatar
0 votes
1 answer
204 views

Convex approximation of an expression

I am trying to transform an expression given by $$ \operatorname{trace} \left( {\bf{X} } \right) + \left( \sum_{n=1}^N x_n \right) $$ into convex from where $\mathbf{x}$ is complex in nature.
Muhammad's user avatar
1 vote
0 answers
43 views

Distributionally Robust Stochastic Programming - Help with derivation

I've been working through this book on robust optimization of electric energy systems, and in particular chapter 4 on distributionally robust optimization. In following the derivation of section 4.2.1....
asfiwefewrno's user avatar
5 votes
0 answers
463 views

How to write this objective in CVXPY for quasiconvex programming?

I have the following objective that I want to maximize: \begin{equation} \max_{U_T\in \mathbb{R}, x\in\mathbb{R}^T} J_\alpha(U_T) = \frac{\alpha}{\alpha-1}\log\left(\frac{\cosh(U_T)}{\cosh(\alpha U_T)^...
Uomond's user avatar
  • 86
2 votes
0 answers
34 views

I need help with finding a library or tutorial to parallel optimize given a black box function, assuming it's convex

I have a black box function to optimize with respect to 1-D input,$\beta$, and I also have other inputs, which I don't need to optimize, say (x,y). So, I need to optimize f($\beta$, x,y) over $\beta$. ...
Thiha Aung's user avatar
2 votes
0 answers
94 views

log-log regression as reward function in optimization problem

Consider the model $\hat{y}_t = e^{\text{trend} + \text{seasonality}} \prod_k^K x_{k, t}^{b_k}$ where $K$ denotes different investment alternatives. You can think that trend and seasonality are ...
pete lewis's user avatar
2 votes
1 answer
191 views

Quadratic optimisation with $\ell_1$ constraints with CVXPY

Crossposted on Mathematics SE I seek to minimize a convex quadratic objective subject to linear and $\ell_1$-based equality constraints. When I turn to CVXPY, an error is raised indicating that it ...
jam123's user avatar
  • 21
1 vote
2 answers
63 views

Relaxing non-affine equality constraints in convex optimization

Consider the convex function $f$. In section 4.2.1 in these lecture notes, the author writes: 4.2.1 Relaxing non-affine equality constraints For functions $g_i(x)$, $i \in \{1,\dots,d\}$ that are ...
mhdadk's user avatar
  • 440
1 vote
0 answers
51 views

What is the use of solvers that return approximately-feasible solutions?

Common methods for solving convex programs return solutions that are only approximately-feasible solutions. Here is an example (from lecture notes by Nemirovski on interior-point methods for convex ...
Erel Segal-Halevi's user avatar
3 votes
1 answer
60 views

Finding a starting ellipsoid and a minimum volume to approximate a convex optimization problem

Suppose we have a convex optimizatiom program: \begin{align} \min &\quad f_0(x)\\ s.t. &\quad h_i(x) = 0 && i=1,\ldots, p\\ &\quad g_i(x) \leq 0 && i=1,\ldots, m\\ &\...
eden hartman's user avatar
3 votes
1 answer
78 views

Is it possible to make a posynomial concave using a change of variables?

Note: this question was already posted on Math.SE but received no answers, so I'm re-posting it here for better reach. Consider the following posynomial with respect to the variables $x_1,\dots,x_n$: ...
mhdadk's user avatar
  • 440
0 votes
1 answer
89 views

Algorithms for maximizing the sum of power functions with linear constraints?

I’m working on an optimization problem that arises from maximizing the return obtained from investing in different marketing levers. The return from each lever exhibits diminishing returns, and is ...
Carlos Zanini'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
  • 440
0 votes
0 answers
39 views

Is a posynomial concave under the following conditions?

Update In case anyone is interested, this question has been answered here. Consider the following posynomial with respect to the variables $x_1,\dots,x_n$: \begin{align} f(x_1,\dots,x_n) &= \sum_{...
mhdadk's user avatar
  • 440
0 votes
1 answer
88 views

Linear Programming faster solver: CPLEX or Gurobi?

Which one is the best solver for solving large-sized problems in Linear Programming, CPLEX or Gurobi? Which one is faster?
Abbas Khademi's user avatar
2 votes
0 answers
62 views

Approximating an LP with an exponential number of variables and an almost-separation-oracle to its dual

Problem settings: we have $n$ agents and a set $\mathcal{S}$ of possible world-states, where the size of $\mathcal{S}$ is exponential with respect to $n$. Each agent $j$ has a utility function $u_j\...
eden hartman's user avatar
2 votes
1 answer
70 views

Question About Fritz John Theorem and Slater Constraint Qualification

Background Information I am studying constraint qualifications. Here are two theorems leading to my question: Theorem 1$\space\space\space\space$ [Fritz John Theorem] Suppose that $f, g_1, \dots, g_k$...
Beerus's user avatar
  • 123
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
3 votes
1 answer
89 views

Dual norm definition: adding new constraints

For some $c >0$ and $z \in \mathbb{R}^n$, the optimal value of \begin{align} \begin{array}{cl} \sup_{x \in \mathbb{R}^n}& z^\top x \\\text{s.t.}& \lVert x \rVert \leq c \end{array} \end{...
independentvariable's user avatar
1 vote
0 answers
24 views

Nesterov Acceleration in Proximal Iteration with Strictly Positive Variable?

I have a cost function of the form $f(x) - \log(x)$, where $f$ is some smooth function mapping $\mathbb{R}^n_+\to\mathbb{R}$and $x$ is restricted to be nonnegative by the problem constraints (and for ...
John Madden's user avatar
2 votes
0 answers
80 views

Does the value function of a quadratic program stay convex when adding constraints?

I am interested in the value function of a quadratic program of the form $$ v(y)=\min_x \frac{1}{2} x^\top Q(y) x, $$ subject to a linear equality constraint $$ E(y)x=d(y), $$ and a linear inequality ...
user_lambda's user avatar
0 votes
0 answers
46 views

Why is CVaR positively homogeneous?

I am reading the article "Some remarks on the Value at Risk and the Conditional Value at Risk" by G. Pflug. The author claims that CVaR is positively homogeneous. That is, Given a loss ...
pele's user avatar
  • 123
0 votes
0 answers
40 views

When the Weighted Sum method yields a unique solution in MOLP?

I would like to ask if there are some specific conditions under which the Weighted Sum method yields a unique solution for MOLP or more general for convex problems. Let us assume that the number of ...
Tassos's user avatar
  • 1
0 votes
0 answers
61 views

How do I implement this convex problem in CVXPY?

I am looking to implement the following optimization problem in CVXPY. $$ \max _{x_t} x_t' \mu - \frac{\gamma}{2} x'_t \Sigma x_t - x'_t\Lambda \Delta x_t $$ where $\Delta x_t := x_t - x_{t-1}$ and $\...
Lydia's user avatar
  • 1
1 vote
1 answer
113 views

Equivalent condition for indicator function

We have the following two conditions: $C1.$ $l(x) \geq 0$ for all $x\in \mathbb{R}^n$, $C2.$ $l(x) \geq 1$ for all $x\in \mathbb{R}^n$ such that $a+b^Tx \leq 0.$ Here $l(x) = \begin{bmatrix} x^T 1 \...
Cherryblossoms's user avatar
0 votes
0 answers
56 views

What the dual constraints mean?

I have a primal problem that is a network-flow: $$ min_x \sum_{a \in A} c_a x_a \\ \text{s.t.} \sum_{a \in A:n = v} X_{a}-\sum_{a \in A:n' = v} X_{a} = \begin{cases} \;\;\;1, \; v=n^{in} \\ -1, \; v=n^...
orpanter's user avatar
  • 507
2 votes
1 answer
59 views

epigraphs for quadratic constraints

I have a constraint of the following form \begin{equation} x^{\top}x + y^{\top}y \leq t \end{equation} where x, y are vector variables and t is a scalar variable. I can augment the variables x and y, ...
Kumar's user avatar
  • 153
0 votes
1 answer
59 views

Min-convex function as constraint

I have a constraint that is as follows: $$ Ax - f(x) \leq 0 $$ where $f(x)=min_y(g(x,y))$. Which is convex. I can even get the gradient in $x$. How can I reformulate my constraint? or what ...
orpanter's user avatar
  • 507
3 votes
2 answers
153 views

Simplest Quadratic Programming algorithm for teaching

Can anyone recommend a straightforward quadratic programming (QP) algorithm suitable for an undergraduate engineering class? I'm interested in finding an algorithm that they can easily grasp and ...
Walton P. Coutinho's user avatar
1 vote
1 answer
113 views

Rational LP, its Rational solution and a minimum precision

Suppose we have an LP with rational coefficients. To my knowledge, this implies that the optimal solution to that LP is also rational. In other words, every variable may be written as: $$x_{i}^{\star} ...
Cris's user avatar
  • 143
2 votes
1 answer
45 views

When is $\max_x\{f(g(x))\} = f(\max_x\{g(x)\})$?

What is the requirements on $f$ and $g$ in order for $\max_x\{f(g(x))\} = f(\max_x\{g(x)\})$ to be correct? Equivalently, when is $\min_x\{f(g(x))\} = f(\min_x\{g(x)\})$ ? Any reference for describing ...
gmn's user avatar
  • 622
1 vote
1 answer
55 views

Quadratic optimization with non-constant coefficients

I have a series of functions (very similar to convex quadratic equations, see the first comment below) $f_1(x), f_2(x), \dots, f_n(x)$. Each of these functions touches the $x$-axis at $a_i$, which can ...
svanderk's user avatar
1 vote
2 answers
60 views

Solving regularized least squares problem using black-box computation of $\mathbf{A}\mathbf{x}$ and $\mathbf{A}^T\mathbf{x}$

Let $\mathbf{A} \in \mathbb{R}^{n \times n}$. I'm working in a problem where I have a black-box algorithmic solution to compute the products $\mathbf{A}\mathbf{x}$ and $\mathbf{A}^T \mathbf{x}$ given ...
mlbj's user avatar
  • 13
2 votes
2 answers
126 views

ADMM diverges on L1 regression

TLDR: Why does ADMM diverge when solving $\ell_1$ regression? Introduction I am learning about convex optimisation and wanted to solve a simple exercise that I am having issues with. I want to solve a ...
Carol Eisen's user avatar
1 vote
1 answer
93 views

Sensitivity analysis for decision vectors in convex programming

Can we perform sensitivity analysis on the decision variables for the perturbed right-hand side of the constraints in a convex/nonlinear program? I know a basic result regarding the sensitivity of the ...
T_k's user avatar
  • 77
0 votes
0 answers
40 views

Convex relaxation of an inner product for optimization

I am trying to solve the following problem. The optimization variables are $x \in R^{+,I}$, $y \in {R}^{+,I x S}$ and $z \in {R}^{+,J x S}$. $a_{i}, b_{j}, c_{i}$ and $d_{ij}$ are parameters and all ...
econ_ugrad's user avatar
-1 votes
2 answers
133 views

Reformulate this constraint optimization problem such that I do not have to divide 2 variables?

I have a constraint optimization problem as follows: I need to assign $m$ tasks to $n$ days, with $n \geq m$. Each day can host 0 to $m$ tasks. Each task either belongs to type $A$ or $B$. I want to ...
Waldo's user avatar
  • 19
3 votes
1 answer
204 views

Solver for quadratically constrained mixed-integer linear programs

I have an optimization problem with vectors $x$, $y$, and $z$, where $x$ is an integer vector. My objective function is linear (i.e. $\|y\|_1$), but one of my constraints is quadratic ($x^Ty \leq z$). ...
Carol Eisen's user avatar
2 votes
0 answers
180 views

Distributed optimization with coupled inequality constraints

Consider the optimization problem: \begin{equation} \begin{array}{l} \min_{(x,y)\in \mathbb{R}^2_{+}} \quad x_{1}a_{1} + x_2a_{2} \\ \text {subject to } \quad\; y_{2} \ge \frac{1}{{x}_2}, \\ \quad \...
Apprentice's user avatar
4 votes
0 answers
85 views

The study of directional derivatives for functions that are minimums of convex functions

Has there been any research on the topic of directional derivatives of functions that are minimums of convex functions?
Samira Fallah's user avatar
2 votes
1 answer
106 views

Separation oracle gives optimisation

Suppose I want to minimize a linear function $f$ over a convex set $K$ and I have only access to a separation oracle, that is, given a point, the oracle returns yes if the point is in $K$ and ...
abc's user avatar
  • 121
2 votes
1 answer
64 views

Does this kind of "partition" have a name?

Consider a convex polyhedron $A$. Assume we have subsets $A_1,\ldots,A_n$ of $A$ that are themselves covex polyhedra and are mutually disjoint except maybe sharing an edge, and that their union gives $...
pele's user avatar
  • 123
4 votes
3 answers
548 views

Determining the optimize lambda in Multi-Objective Optimization

I have a convex optimization problem: Maximize obj1 Minimize obj2 Some constraint Now to solve this problem, I used lambda to make it one problem: ...
Soroosh Noorzad's user avatar
7 votes
3 answers
1k views

Solver for convex optimization with exponent in the objective function

My question is related to a previous one: Dedicated solver for convex problems To minimize a convex function of the form $~f(x_i) = \left[ C + mx_i + \frac{s}{x_i+t} \right]^p $ with various ...
Shuxue Jiaoshou's user avatar