Mathematics Stack Exchange
Mathematics Stack Exchange

Questions tagged [convex-optimization]

A convex optimization problem consists of either minimizing a convex objective or maximizing a concave objective over a convex feasible region.

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. Linear Programming is a special case. Convex Optimization problems as a class are easier to solve numerically than general mathematical optimization problems.

The following problems are all convex minimization problems, or can be transformed into convex minimizations problems via a change of variables:

  • Least squares
  • Linear programming
  • Convex quadratic minimization with linear constraints
  • Quadratic minimization with convex quadratic constraints
  • Conic optimization
  • Geometric programming
  • Second order cone programming
  • Semidefinite programming
  • Entropy maximization with appropriate constraints
7419 questions
0
votes
1 answer

convex set optimization problem

If I have a convex set $ \min f(x) $ $\sum_{i=1}^n x_{i} =1$ where $x\geq 0$. Will an $\overline x$ (a local minimizer), if $x_{i} >0$ be $ \dfrac{\partial{f(x)}}{\partial{x_{i}}} \geq \dfrac{\partial{f(x})}{\partial{x_{j}}} $ for all $j$ 1)why…
Viper Maverick
  • 1
0
votes
1 answer

How get the upper bound (maximum) of a convex function with inequality constraints?

Condition: $h,f\in \mathbb{C}^{N\times1}, \text{where}f =\hat{f} + e \text{ and } e^H e \leq 1,\ \ \ Q=h^Hff^Hh$. The function $ Q$ is convex. Now I want to get the maximum (not minimum), i.e., the upper bound of $Q$ over the variable $e$. How to…
begforopt
  • 83
0
votes
0 answers

Column Generation approach doesn't give desired solution

I am trying to implement a Column Generation approach, in which I separate the continuous and the discrete variables. (Bender is not possible due to different reasons) To get an initial feasible solution, I solve the original problem without…
QC_Pod
  • 13
0
votes
0 answers

How to represent polyhedron as the inverse image of the Cartesian product of the nonnegative orthant and the origin?

In Convex Optimization by Boyd and Vandenberghe, I don't understand how the formulation for Example 2.9 works. Example 2.9: Polyhedron. The polyhedron $ \{ x | Ax \preceq b, Cx=d \}$ can be expressed as the inverse image of the Cartesian product of…
iquitgame
  • 1
0
votes
0 answers

Dual characterization of minimal elements of a convex set

In section 2.6.3 of "Convex Optimization" by Boyd and Vandenberghe (p. 55) it is stated that If $\lambda\succ_{K^*}0$ and $x$ minimizes $\lambda^T z$ over $z\in S$, then $x$ is minimal. This is complemented a bit later with the assertion Provided…
Patricio
  • 1,604
0
votes
0 answers

Convex optimization dual problem solution

In the below solution, should “choose y = -tv_i” read “…y = tv_i”? If not, please explain the rest of the reasoning - it seems to me that as t-> +inf the second term grows large positive along with the first term
bikeactuary
  • 113
0
votes
0 answers

How to prove the convexity of a function using restriction by a line?

I'd like to understand a little more about the restriction on a line to prove the convexity of a function. Indeed, we can show that a function $f(x)$ is convex if the function $g(t) = f(x + tv)$ is convex $\forall x$ and $x + tv \in dom f$. I'll…
Peregrint
  • 31
0
votes
0 answers

Show x* = [...] is optimal for a given problem

I have a question like this: Show $$x^* = [1,1,1,1]$$ is optimal for the following problem: $$ min\ 6x_1 + .... - 10x_4$$ such that $$ Ax \preccurlyeq b$$ and I am given the matrix A which is 5x4 and vector b length 4 entries. Generally speaking…
bikeactuary
  • 113
0
votes
0 answers

Proof that $(\nabla f(x) - \nabla f(y))^T(x-y) \ge 0 \ \forall \ x, y \Rightarrow f$ is convex

Proof that $(\nabla f(x) - \nabla f(y))^T(x-y) \ge 0 \ \forall \ x, y \Rightarrow f$ is convex. I've differentiated both 2 sides and got this: $\nabla^2 f(x)^T(x-y) + \nabla f(x) - \nabla f(y) \succeq 0$ Then I choose $y = 0$: $\nabla^2 f(x)^Tx +…
MY_NAME_S3M
  • 43
0
votes
0 answers

error bounds for the subgradient method

I am struggling to understand the bound for constant stepsize with the subgradient method provided in this image taken from page 4 of this link , where $f^{(k)}_{best}$ is the best function value seen so far in the subgradient path. I dont follow…
Siddharth Kumar
  • 1
0
votes
0 answers

how to ensure existence and uniqueness of the maximizer of a function with not compact domain

Let $f: A \to \mathbb{R}$ be a function and $A\subset \mathbb{R}^d$. It looks like I can ensure existence and uniqueness of a maximizer of $f$ if I let $f$ be strictly concave and upper semicontinuous with bounded super-level sets. I wonder why this…
user12703198
  • 111
0
votes
0 answers

Inequality constraint for using ADMM algorithm

I'm trying to express the following constrained optimization problem: \begin{equation} \begin{aligned} & \underset{x}{\text{minimize}} & & \| b - x \|_1 + \lambda \| \mathbf{D}x \|_2 \\ & \text{subject to} & & x \leq b…
elnatd
  • 1
  • 2
0
votes
0 answers

Is constrained optimization equivalent to unconstrained optimization followed by a projection step?

Suppose we have a constrained convex optimization problem $min_{x \in \mathcal{C}}f(x)$. Is it correct to first solve the unconstrained problem ($\tilde{x}=argmin_{x}f(x)$) and then project the solution to the feasible set…
Vasilis Pollatos
  • 1
0
votes
1 answer

How does Slater's condition apply to $\min x_1+x_2$ subject to linear constraints

I have the following problem: $$\text{min} ~x_1 + x_2$$ subject to $$x_1 \geq 1 + 0.4 x_1 + 0.4 x_2$$ $$x_2 \geq 3 + 0.56 x_1 + 0.24 x_2$$ $$x_1 -w = 0$$ $$x_2 - w = 0$$ Clearly, the optimum exists and the optimal value is 30. There is no duality…
hari
  • 1
0
votes
1 answer

Calculating Lagrangian Dual

We have the minimization function: $$ \begin{align*} \text{minimize}~ f(x) &= \sum_{i=1}^{n} x_i \log x_i\\ \text{subject to}~ Ax &= b \end{align*} $$ And we want to find the Lagrangian dual. The first step is to find the conjugate which…
TilManG4
  • 67
  • 6
1 2 3
…
24 25