Questions tagged [convex-optimization]
Convex Optimization is a special case of mathematical optimization where the feasible region is convex and the objective is to either minimize a convex function or maximize a concave function.
193
questions
5
votes
0answers
68 views
Minimum of quadratic assignment (QAP) with convex objective
Suppose $A,B\succeq0$ and $C\in\mathbb R^{n\times n}$. I am hoping to solve an instance of the following optimization problem:
$$
\min_{\textrm{permutation matrices }P}
\mathrm{tr}(BP^\top AP+C^\top ...
3
votes
0answers
30 views
Sparsity-Promoting Convex Optimization Over Simplex
Say we want to find a sparse approximate minimizer to the function $f(x) : \mathbb{R}^d \to \mathbb{R}$. Then in line with the work in the field of compressed sensing, we can instead minimize $$f(x) + ...
3
votes
1answer
61 views
Convex optimization with constraints involving matrix inverse
I have the following convex optimization problem. I would like to ask is there any efficient way to solve it in Python? Can I use CVXOPT package? If so, any detailed instruction? Thanks a lot.
$$
\...
3
votes
0answers
106 views
A maximization problem, with motivation in machine learning
Consider the minimization problem described this paper. Let $f_{\lambda}$ be the minimizer. As a part of extending my work, I am able to show the following facts
$$\lim_\limits{\lambda \to 0}\|f_{\...
3
votes
1answer
73 views
Geometric Programming - symbolic version
I am interested in finding minimizers of functionals of the type $\sum x^ay^bz^c$ where the exponents are 1, 0 or -1. I have codes to find such minimizers when they exist up to machine precision, ...
0
votes
0answers
32 views
How to show equivalence between two programs?
Consider the following space $A = \{(x_1,x_2,x_3)\in \mathbb{R}^3|x_1+x_2+x_3 = 1\}.$ Then say that we want to minimize a function $J(y):\mathbb{R}^{3}\to \mathbb{R}$ subjected to the constraint that $...
0
votes
0answers
70 views
Augmented Lagrangian Techniques Frank-Wolfe Algorithm [python]
I'm trying to solve the convex quadratic problem (quadratic min cost flow problem) using the Frank-Wolfe algorithm.
$$ \min\{x^TQx+qx: Ex=b,\quad 0\leq x \leq u\} $$
The standard algorithm is okay ...
3
votes
2answers
70 views
Convexity of Sum of $k$-smallest Eigenvalue
If I have a real positive definite matrix $A\in\mathbb{R}^{n\times n}$, and denote its eigenvalues as $\lambda_1\leq \lambda_2 \leq ... \leq \lambda_n $.
Define the function as $f(A)=\sum_{i=1}^{k} \...
4
votes
1answer
47 views
Determine image of hypercube under linear map
Let $A$ be an $3\times N$ matrix (where $N$ is large) with nonnegative real entries. I'd like an algorithm for determining when a vector $v\in\Bbb R^3$ can be written as $Aw$ for some vector $w\in\Bbb ...
0
votes
1answer
57 views
Optimize multivariable function with interdependent variables
I have a cost function with 2 parameters. The variables are dependent on each other. So, if I just take a partial derivative with respect to one variable the slope is in terms of the other variable ...
0
votes
0answers
23 views
convex atomic function reformulation to meet concave dcp rule requirements
I have an atomic constraint of the form
abs(w - w_prev) >= some_threshold
It is supposed to get every value equal to or above my threshold.
I am working on a ...
2
votes
0answers
38 views
Biconvex problem whose objective function depends on only one variable
I am solving the following biconvex problem:
$$\min_{x,y} f(y)$$
$$s.t. ~~ g(x) \leq 0$$
$$~~~~~h(x,y) = 0$$
$$x \in X, y \in Y$$
where $X$ and $Y$ are compact convex sets, $g(x)$ and $f(y)$ are ...
0
votes
0answers
31 views
Minimizing the ratio of two specific non negative quadratic convex functions
$F$ is $m\times m$ diagonal, with real non negative elements
$D$ is $n \times m$ complex
$P$ is $n \times 1$ complex
$A$ is $m \times 1$ complex.
Minimize $\Gamma(A)$, with respect to $A$.
$$\...
6
votes
1answer
108 views
numerical solution of an under-determined linear equation in high dimensions
I need to solve a linear regression problem $$Ax=y$$ which is hugely underdetermined. I have around $10^6$ features but only $10^3$ equations. So $A$ is a $1,000\times 1,000,000$ matrix and $y$ a ...
0
votes
1answer
55 views
Formulate and solve a simple conic programs in cvxpy language [closed]
Let $r,\epsilon > 0$ and $a, b \in \mathbb R^n$ with $\|a\|_2 \le r$. Define $C(a) := \{x \in \mathbb R^p | \|x+a\|_2 \le r,\;\|x\|_\infty \le \epsilon\}$, and assume it is non-empty.
Question
(A)...
0
votes
0answers
36 views
In-exact line search
In my class notes, the author says:
"If $f:\mathbb{R}^n \to \mathbb{R}$ is bounded below and $p_k$ is a descent direction and the $\alpha-\beta$ also known as Armijo-Goldstein condition is met then ...
0
votes
1answer
23 views
Gradient ascent method with a constant step size?
I'm trying to use the gradient ascent method on a convex function like the multivariate-Normal density function with respect to its parameters (the original is a bit more complicated), something ...
2
votes
1answer
63 views
Question about strange outputs from the CVXPY solver
I am familiarizing myself with CVXPY, and encountered a strange problem. I have the following simple toy optimization problem:
...
3
votes
0answers
83 views
Why the MIRACLE of Lanczos/CG-like?
Lanczos/Arnoldi/Rietz/CG-like algorithm share the same core strategy...
In each, a little miracle appears, most of the Gram-Schmidt inner products are zeroes! In others words, new direction need only ...
-1
votes
1answer
23 views
Semi-Definite relaxation of non-linear constraint?
I am implementing an optimization problem using semi-definite approach. One of my constraints is of following form
$ trace(A∗X)−(k∗trace(A∗X))+(k∗\sqrt {(trace(B∗X)} )==0$
where k is a constant, A ...
2
votes
0answers
28 views
Where can I find sample data for large linear programming optimization problems?
I am doing a comparison of different algebraic modeling langues (AMPL, AIMMS, GAMS, Pyomo) in both theoretical and practical terms. As a practical experiment I am trying to measure problem model ...
1
vote
1answer
155 views
Why does Newton's method with Linear Equality Constraints use KKT condition?
Goal: Optimize convex function $f(\vec{x})$ subjected to constraint $A\vec{x} = \vec{b}$ starting at a point $\vec{x}_0$ that satisfies the constraint.
The problem only has equality constraint. Why ...
1
vote
0answers
47 views
Order of a principal term
In Yurii Nesterov's Introductory Lectures on Convex Optimization, there is a bound for the total number of iterations for some process. See page 109:
$$\left[\frac{1}{\ln(2(1-\kappa))} \ln\frac{t_0-t^...
2
votes
1answer
87 views
Convergence rate and complexity for convex minimization problem
In Yurii Nesterov's Introductory Lectures on Convex Optimization, there is a description of the rate of convergence and corresponding upper bound for the analytical complexity of a minimization ...
3
votes
0answers
76 views
First order methods for a large scale semidefinite program
I am interested in solving the following semidefinite optimization problem:
\begin{equation}
\begin{split}
\underset{X,\lambda}{\rm maximize} \;\;\;\;&\lambda^Tc \\
&-\mathbb{I} \le X \le \...
3
votes
1answer
525 views
How to transform this SOCP to the format required by cvxopt
I'm new to SOCP and want to try to get familiar with the format and how to solve it with cvxopt in python. However, for a simple toy example I'm struggling to get ...
0
votes
1answer
1k views
How to efficiently solve a QCQP with “dynamic” constraints in Python?
I want to solve a QCQP in Python. It is a problem from finance: maximise return (linear function) given some linear constraints and one quadratic constraint that turns it into a QCQP. Formally,
$$\...
1
vote
1answer
199 views
How to use CSDP to express a semidefinite program?
I am trying to use CSDP and am struggling with it. Consider, for example, the following semidefinite program
$$\begin{array}{ll} \text{minimize} & 0\\ \text{subject to} & Q - A' Q A - \...
2
votes
0answers
142 views
How to prevent BFGS from getting stuck on astronomically large gradient?
I have implemented BFGS myself from scratch in order to solve minimization problems. Part of BFGS, as I understand it, is that the approximation to the Hessian is supposed to be positive definite, ...
1
vote
0answers
33 views
Best Possible Convex bounds for optimization problems
Suppose we have a primal problem
$$
p^{*}=\min_x f(x), \\\text{s.t.}~~ h_i(x) \leq 0,
$$
where $f(.)$ and $h_i(.)$ are possibly non-convex.
Then its Lagrangian is
$$\mathcal{L}(x,z_i)= f(x) + \...
2
votes
0answers
26 views
Domain for convex perspective function
The perspective of a function $f : \mathbb{R}^n \to \mathbb{R}$ is the function $g: \mathbb{R}^n \times \mathbb{R} \to \mathbb{R}$ where $g$ is defined as $$g(x,t) = tf(x/t)$$ with $$\mathbf{\text{dom}...
1
vote
0answers
66 views
Nonlinear least square optimization
Problem description
Given data at many time instance $t$,
$$\min _{\alpha, \Lambda, \beta} \lVert y(t) - \alpha e^{\Lambda t} \beta \rVert_F$$
with $$ \lVert \alpha \rVert_2^F = 1 $$
where $y(t) \...
3
votes
2answers
158 views
How do I check if a loss function can achieve its minimum?
For example, the convex function $f(t)=e^{-t}$ doesn't achieve its minimum 0 on the real line. In a linear regression with $p$ predictors $X$, the loss function $f(\beta)=||Y-X\beta||^2$ achieves its ...
6
votes
1answer
238 views
What is required of the objective function in order to use Gauss Newton method?
From what I understand, the Gauss-Newton method is used to find a search direction, then the step size, etc., can be determined by some other method.
In addition to that, are the following ...
1
vote
1answer
796 views
How to Solve Optimisation Problems using Penalty Functions in Python
I am working on a implementing a simple quadratic optimisation problem:
$$\min _x \; {\underline{x}}^T Q {\underline{x}}$$
$$s.t. \,\quad {\underline{\mu}}^T{\underline{x}} = R^*$$
$$ \quad \quad \...
1
vote
0answers
19 views
How does the MADS algorithm work in practice
Mesh Adaptive Direct Search (MASH) is an algorithm for black box optimization
I want to understand an implement this method to solve some 2D multivariate blackbox function $f(x,y)$, but am having ...
1
vote
2answers
72 views
Making difference of log constraints convex
I have the discrete likelihood estimation problem $\max \sum m_i\log p_i $ where $m$ is a given vector of length $n$. The constraints are $0 \preceq p \preceq 1$, $\sum_{i=1}^n p_i = 1, $ and one ...
6
votes
2answers
842 views
What is the most appropriate derivative free optimization algorithm
We can use random optimization/ derivative free/ direct search to find the minimum of some black box function $f$.
If I have some 2D black box function, $f(x,y)$ - which I know to be convex - what ...
0
votes
1answer
720 views
How to define the derivative for Scipy.Optimize.Minimize
I am trying to use scipy.optimize.minimize to minimise a quadratic objective function: $f(x) =x^\top Q x$. As a start, I have successfully implemented this using the built-in Nelder-Mead Simplex ...
5
votes
1answer
424 views
Ways to speed up solving an LP with Google's ortools
I'm having an issue solving an LP of the form:
$$\min z = c^Tx$$
$$\text{s.t.}$$
$$Ax \geq b$$
$$x\geq p$$
$1 \leq a_{ij} \ll b_i$, $p \leq 0$, and $c \geq 0$
The specific problems I'm running into ...
1
vote
0answers
77 views
Sequential Quadratic Programming for Quadratically Constrained Quadratic Programs
A standard Quadratically Constrained Quadratic Program (QCQP) is of the form:
$$ \underset{x}{minimize} \frac{1}{2}x^TP_{0}x + q_{0}^{T}x
$$
$$
subject \; to \quad \frac{1}{2}x^TP_{i}x + q_{i}^{...
4
votes
0answers
48 views
Obtainting KKT for QSDP for the trace inequality constraint
I am working on developing my own solver(for implementation on hardware), based on IPM for following problem:
\begin{equation}
\begin{split}
\min_{X} \; \frac{1}{2}&\|X\|_F^2 + trace(CX)\\
\text{...
4
votes
3answers
186 views
How can I use Projected Gradient Descent for this optimization problem with constraint?
Suppose $ q $ and $ A $ are given and that $ q, p \in R^{N} $ and $ A \in R^{NxN} $, then how can I find the vector $ p $ such that
$$ (q - p)^{T}A(q - p) $$ is minimized constraint to $ \sum_{i=1}^{...
1
vote
1answer
225 views
Reformulate a strictly convex QP problem containing absolute value term
Can the following strictly convex optimization problem be reformulated into a standard form that is also a strictly convex problem?
$$\begin{align}
&\text{Minimize }\frac{1}{2} x^T Q x + a^T x + ...
3
votes
1answer
209 views
Why do active set methods or the simplex method pivot only one variable at a time?
Why do active set methods or the simplex method pivot only one variable at a time? Ostensibly, we could add multiple columns to the basis during pivoting, but the standard presentation of the methods ...
1
vote
1answer
153 views
How can I solve on a computer a large projection problem with redundant constraints?
This question is the essence of this one. After we remove all the cruft, we can recast it as follows:
Problem: Given $b \in \mathbb{R}^n$, $C\in \mathbb{R}^{n\times m}$, and $g\in \mathrm{Range}(C^...
3
votes
1answer
260 views
Imposing special structure on Positive Semi-Definite matrix
I am trying to implement the algorithm described in reference 1 using cvxpy. However I am struggling to constrain the matrix $Z_j$ as described in equations (33-35)....
3
votes
2answers
510 views
Quadratic programs with rank deficient positive semidefinite matrices
Let $A$ be a $n\times n$ square symmetric matrix. In addition, $A\succeq0$ and $\mathrm{rank}(A)<n$. This means that all eigenvalues are non-negative, but also that there are some zero eigenvalues. ...
3
votes
1answer
60 views
Linear programming with stochasticity?
Suppose I have implemented an LP, where some constraint coefficients are implemented as the mean of some probability distribution.
Now, I would like to solve the same problem but with stochasticity ...
3
votes
1answer
255 views
Translating a nuclear norm constraint to an LMI constraint
I'm attempting to solve a convex optimization problem where one of the constraints is
$$\|M\|_* \leq a$$
where $\|M\|_*$ denotes the nuclear norm of matrix $M$. I'm using CVXOPT in Python to solve ...
