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.
192
questions
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$? ...
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{...
- 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 ...
- 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 ...
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 ...
- 67
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,...
- 3,980
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.
- 67
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....
- 11
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)^...
- 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$. ...
- 21
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 ...
- 21
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 ...
- 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 ...
- 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 ...
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\\
&\...
- 53
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$:
...
- 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 ...
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 \...
- 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_{...
- 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?
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\...
- 53
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$...
- 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?
-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}^...
- 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{...
- 3,980
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 ...
- 111
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 ...
- 121
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 ...
- 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 ...
- 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 $\...
- 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 \...
- 111
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^...
- 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, ...
- 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 ...
- 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 ...
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} ...
- 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 ...
- 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 ...
- 13
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 ...
- 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 ...
- 203
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 ...
- 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 ...
- 129
-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 ...
- 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$). ...
- 203
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 \...
- 215
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?
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 ...
- 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 $...
- 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:
...
- 143
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 ...
- 155