Optimization is the process of choosing the "best" value among possible values. They are often formulated as questions on the minimization/maximization of functions, with or without constraints.

learn more… | top users | synonyms (5)

0
votes
0answers
30 views

Solutions to recurrence relations

Consider functions $s_{m},c_{m},d_{m}$ defined by the following recurrence relations $$s_{1}=n$$ $$c_{1}=s$$ $$d_{1}=0$$ $$s_{2}=n$$ $$c_{2}=s-n$$ $$d_{2}=d$$ $s,n, d$ are integers. If $c_{m}>...
0
votes
1answer
18 views

When is minimizing the sum of function equivalent to minimizing sum of independent variables

I have to admit I am not good at math, but this is a problem I am having trouble with. What kind of function $f$ can guarantee $min\sum_{i=1}^Kf(x_i)$ is equivalent to $min\sum_{i=1}^Kx_i$. Thank you. ...
0
votes
0answers
6 views

Is this solution to a pairwise Procrustes Problem correct?

I have two sets of points, let's say, $y$ and $x$. Each set has exactly $N$ elements, and each element $element$ is such that $element \in I\!R^{d}$. That is, I have two shapes with $N$ $r-\text{...
1
vote
1answer
30 views

Can this problem be formulated as an integer programming problem?

I am working on an optimization problem but I am not sure if the problem can be formulated as an integer programming problem. Assume the cost minimization problem for a set of subscribers and ...
1
vote
1answer
33 views

Why the local optimum of this problem is always global?

I am reading the paper "Continuous methods for extreme and interior eigenvalue problems" by G.H. Golub and L.-Z. Liao. The papers says for the following problem, (Lemma 2.1 (i), $0>\lambda_i-c\ge \...
2
votes
1answer
176 views

Least-squares problem with quadratic equality constraint

I want to find the solution of a Lagrange equation whose inputs are matrices. First I have the equation Ax=0. By decomposing $A$ into $A_3$ (columns 9 to 11 of A), $A_9$ (the rest of the columns), ...
3
votes
1answer
149 views

Least squares with a quadratic inequality constraint

Is there a closed form solution for the following least squares problem: $$ \min_\mathbf{x}\|\mathbf{a+Bx}\|^2 ~~\text{s.t}~~\|\mathbf{x}\|^2 \leq \alpha^2$$ where $\mathbf{a} \in \mathbb{C^{M\times 1}...
1
vote
0answers
11 views

Find closest point, subject to linear inequality constraints

Given a point $p\in \mathcal{R}^2$, I want to compute the closest point $x \in \mathcal{R}^2$, subject to linear inequality constraints $Ax \leq b$. That is, $$\begin{array}{ll} \text{minimize} & ...
0
votes
1answer
30 views

find minimum of a matrice

Let $f~:~\Bbb R^2\to \Bbb R$ be defined as: $$f(x)=\left\|\begin{bmatrix}2&1\\3&1\\4&2\end{bmatrix}\begin{bmatrix}x_1\\x_2\end{bmatrix} - \begin{bmatrix}2\\1\\7\end{bmatrix}\right\|_2^2$$ ...
2
votes
0answers
28 views
+50

Formulate as standard problem: Optimal cyclic permutations

How can we find cyclic permutations $\prod_i$ to be applied to each of corresponding $i$'th rows of a square matrix $X$ of size $n \times n$ such that a given sum of pairwise costs $\sum_{ij}C\left[\...
0
votes
1answer
43 views

Find a least upper bound for $3^{x+y-4}+(x+y+1)2^{7-x-y}-3(x^2+y^2)$ with some constraint?

This is a question in vietnamese national math exam at the end of 12th grade. Given x,y are real numbers which satisfy the condition: $x+y+1=2(\sqrt{x-2}+\sqrt{y+3})$ Find a $m$ such that: ...
0
votes
0answers
7 views

Notation for arguments that maximize functions with priority

Suppose we have some functions $f_1(x), f_2(x), \ldots, f_n(x)$ with $x \in \mathbb{Z}^n$. We can denote the subset $X_1$ of $\mathbb{Z}^n$ that maximizes $f_1(x)$ as: $$X_1 = \underset{x \in \...
1
vote
1answer
22 views

Problem about find the extreme of a function (Multipliers of Lagrange)

Good morning, i have a problem with this: Find the maximum and minimum distances from the origin to the curve $g\left(x,y\right)=5x^{2}+6xy+5y^{2}$ I make this: Function to optimize: $f\left(x,y\...
0
votes
0answers
18 views

Negative bounds on variables in Linear Programming formulation

I am new to optimization theory and encountered the following problem: I am reviewing a formulation for a network problem that is fed into a mathematical solver and I noticed that on the "bounds" ...
0
votes
0answers
13 views

How to express the optimization problem in AMPL?

The optimization problem I have is as follows: $N=5$ $M=20$ The optimization problem is given by $$\text{Maximize}\hspace{1mm}\sum_{i=1}^NT_i$$ where $T_i=\bf{C}_{[i]}\bf{E}\log_2\left(1+\frac{...
0
votes
1answer
40 views

Optimize wrt a partial matrix?

I have a common optimization problem $$\arg\min_A \text{tr}( A^TWA),$$ where $W$ is a positive semi-definite matrix, and $A$ is the matrix to be optimized. If $A$ is completely unknown, with some ...
4
votes
1answer
43 views

Maximizing $\frac{\int_r^1xf(x)dx}{2-F(r)}$

Consider a continuous distribution on $(0,1)$ with probability distribution function $f$ and cumulative distribution function $F$. Define $$g(r)=\frac{\int_r^1xf(x)dx}{2-F(r)}$$ and let $r_M\in(0,1)$ ...
2
votes
2answers
4k views

Optimization of the surface area of a open rectangular box to find the cost of materials

A rectangular storage container with an open top is to have a volume of 10 cubic meters. The length of the box is twice its width. Material for the base costs ten dollars per square meter and for the ...
0
votes
1answer
23 views

Is Frank Wolfe a descent algorithm?

A colleague was explaining to me that the Frank-Wolfe algorithm is a descent algorithm (i.e. its objective value decreases monotonically at each iteration). However, when I tried simulating it, my ...
1
vote
1answer
32 views

IF statement as Linear Constraint

I am writing a linear program, but I am currently having troubles writing a certain constraint, which is basically an IF-statment. I will try to explain it as detailed as possible: IF: $x_{it'}(t' +...
0
votes
0answers
12 views

Impact of convexity under different changes of variables for different parts of optimization

Let $$ \min_x f(x)$$ such that $$ C(x) \le 0$$ where $C$, and $f$ each are convex under respective changes of variables. How does that impact the optimization? If standard algorithms are sensitive ...
0
votes
0answers
32 views

If the primal is unbounded, then the dual is infeasible.

In the context of duality in linear programming, prove that If the primal is unbounded, then the dual is infeasible. My book says that this is a corollary to complementary slackness. What's ...
0
votes
0answers
57 views

optimal, infeasible, degenerate solutions

Note that $c_i$'s in the $z_j-c_j$ row are not coefficients of the $x_i$'s. I use instead: $r_1, r_2, r_3$. I'm assuming there's a non-negativity constraint. we need to state necessary ...
12
votes
3answers
283 views

Variable leaving basis in linear programming - when does it happen?

In the simplex algorithm in linear programming, what are conditions for a variable to leave a basis (not necessarily basis for the/an optimal solution)? I'm supposed to list as many sufficient and ...
1
vote
0answers
58 views

Feasible Region of QCQP and Semidefinite Programs

I am trying to visualize the feasible region of a Quadratically Constrained Quadratic Program (QCQP) which is expected to be non convex (actually is a set of ellipses in $\mathbb{R}^2$) and the ...
1
vote
0answers
20 views

Efficient ways of minimizing a complicated objective “function”?

My problem at hand neither has any special structure that gives me closed-form solutions nor can be written by a single expression. Yet, it is still an objective "function," as I can compute a value (...
0
votes
0answers
9 views

How to find initial values when optimizing functions of ODEs?

I want to reproduce parts of a paper and therefore have to optimize a function $f(A,B)$, where $A$ and $B$ are the solutions of the following system of ODEs: $$\frac{d}{dt}A = c_1F + \nu_{\beta} -...
2
votes
1answer
40 views

Solve the closed form solution for argmax of $ x^Ty - x^T\ln(x)$

Let $y \in \mathbb{R}^n, \ln(x) = \begin{bmatrix} \ln(x_1) \\ \vdots \\ \ln(x_n) \end{bmatrix} \in \mathbb{R}^n$ Show that $$x^* = \text{argmax}_{x \in \mathcal{D}} \quad x^Ty - x^T\ln(x)$$ ...
0
votes
0answers
33 views

Minimum value will be attained by same z

Let $y=\left(\begin{array}{c}y_1\\y_2\\\vdots\\y_n\end{array}\right)$ be a fixed non zero vector in $R^n$. Let $S \subset R^n \setminus\{0,y\}$ is a finite set. Suppose $$min\big\{\sum_{i=1}^{n}{|y_i-...
0
votes
2answers
790 views

Optimization, rectangle inscribed inside arch of the curve.

A rectangle is to be inscribed under the arch of the curve $y = 4\cos(0.5x)$ from $x = \pi$ to $x = -\pi$. What are the dimensions of the rectangle with largest area, and what is the largest area? ...
1
vote
0answers
18 views

Maximum value of $(1-F(t))t$ for probability distribution

Consider a continuous distribution on $(0,1)$ with cumulative distribution function $F$. For the value of $t\in(0,1)$ that maximizes $$P(t)=(1-F(t))t,$$ what is the lower bound of $P(t)$? For example, ...
2
votes
2answers
249 views

using the kronecker product and vec operators to write the following least squares problem in standard matrix form

I have a least squares problem with the following form: $$ \min_\mathbf{X} ~ \sum_{i=1}^n | \mathbf{u}_i^\top \mathbf{X} \mathbf{v}_i - b_i |^2 $$ where $\{\mathbf{u}_i\}_{i=1}^n$ and $\{\mathbf{v}...
0
votes
2answers
26 views

Optimization of the function of two variables

I have two functions $f(x,y)$ and $g(x,y)$. I want to minimize the sum of these functions w.r.t $x,y \in (0,1)$. I know that for fixed values of $x$, $f(.,y)$ is a decreasing function while $g(.,y)$ ...
-1
votes
1answer
14 views

Sum of convex and decreasing function

I have a sum of decreasing function and a convex function over some domain. Can I say that the sum is also a convex function (i.e. there exists a unique minimum)?
1
vote
1answer
34 views

Maximize the number of non zero elements of a product of binary matrices.

I want to find two binary matrices $A$ of size $N \times M$ and $B$ of size $M \times N$ such that: $AB=C$ is a strictly lower-triangular matrix ($j \geq i \implies C_{ij}=0$) The number of ...
0
votes
1answer
31 views

How to find the analytical solution of this optimization problem?

I have an optimization problem of the form $$\begin{align} \text{maximize}\quad&\sum_{i=1}^{k}\sum_{j=1}^{n}w_{ij}x_{ij}\\\text{s.t.}\quad \quad\quad\,\,& \sum_{i=1}^{k}x_{ij}\leq 1,\;\forall ...
0
votes
0answers
8 views

Proximal operator of the sum of two norms

I'm a little new to this and not sure how to evaluate the proximal operator in this context, assuming a closed form exists. Calculate $\text{prox}_{c,f+g}(v)$, where $f(x) = \frac{1}{2}\|Ax-b\|_2^2$...
3
votes
1answer
67 views

Team grouping troubles

Imagine there are 12 teams, numbered 1 through 12. There are 10 games those teams can compete in, with two teams needed per game. There are 10 rounds, and it is important that after the 10 rounds are ...
0
votes
0answers
21 views

Find rotation matrix to match points in parallel projection

I am given two sets of 3D points (actually 2D, see below) with corresponding pairs. I am seeking two 3D rotation matrices, such that (only) the X and Y components of the rotated points match best (...
0
votes
1answer
31 views

Minima of symmetric polynomials subject to two symmetric constraints

The homogeneous symmetric polynomial of degree $k$ in $n$ variables is $$ f_k(x_1,x_2,\dots,x_n) = \sum_{i_1<i_2<\cdots<i_k}x_{i_1}x_{i_2}\cdots x_{i_k}. $$ Consider the following ...
-1
votes
0answers
16 views

Solve $\max \mathrm{sum}(AXB \geq \gamma), X \in \{0,1\}^{N \times N}$

I have a problem to find the best permutation matrix $X \in \{0,1\}^{N \times N}$, so as to maximize the number of elements in $AXB$ which are above a certain positive number $\gamma$. In other ...
6
votes
1answer
957 views

Why does SVD provide the least squares solution to $Ax=b$?

I am studying the Singular Value Decomposition and its properties. It is widely used in order to solve equations of the form $Ax=b$. I have seen the following: When we have the equation system $Ax=b$, ...
1
vote
2answers
36 views

Maximizing the sum of the squares of numbers whose sum is constant

I wonder how one goes about to find the maximum of $\sum v_i^2$, the $v_i$'s being positive integers whose sum $\sum_i v_i$ is fixed.
0
votes
0answers
15 views

Solving $I^* = \arg\min_{I'} \left( \|\phi_\ell(I) - \phi_\ell(I')\|_2^2 + R(I') \right)$ with gradient descent

I am trying to create the results from this a paper that is trying to understand the types of features a convolutional neural network is learning to recognize. I don't think understanding ...
0
votes
1answer
14 views

In Constrained Optimization, Restrict Domain to Open Set $A\subset\mathbb{R^N}$?

In constrained optimization and context of economics (e.g. utility function with quantity of goods as arguments subject to wealth), why do textbooks always restrict domain of the objective function ...
1
vote
0answers
18 views

Invertibility of bordered Hessian

I have an optimization problem: $max f(x)$ s.t. $Ax=b$, where $x \in R^n$ and $b \in R^m$, $m \le n$. I know that $f$ is strictly quasi-concave, and that $A$ has rank $m$ (linearly independent, ...
0
votes
1answer
456 views

How to solve for maximum area of a rectangle under a curve?

Having trouble with this optimization question and was hoping I could get some help with it. The function of the curve is $8^{-\frac{x}{5}}$. I would greatly appreciate a full explanation. I already ...
0
votes
0answers
15 views

Solve $ \max U = [\sum\limits_{i = 1}^2 {a_i^{{1 \over \sigma }} } \cdot X_i^{{{\sigma - 1} \over \sigma }} ]^{{\sigma \over {\sigma - 1}}} $

The problem is $$ \eqalign{ & \max U = \left[\sum\limits_{i = 1}^2 {a_i^{{1 \over \sigma }} } \cdot X_i^{{{\sigma - 1} \over \sigma }} \right]^{{\sigma \over {\sigma - 1}}} \cr & \...
0
votes
0answers
13 views

Momentum Potential Term in Optimization Problem for Implicit Euler Solver

I'm trying to understand the explanation of the implicit Euler solver (Section 3.1) set forth in this paper: Projective Dynamics: Fusing Constraint Projections for Fast Simulation For the purposes of ...
2
votes
0answers
34 views

Finding a maximum with some constraints

I would like to maximize the term $ l_1b_1+l_2b_2+l_3b_3-2 $ such that the following conditions hold: $ 1>l_1>l_2>l_3>0 $, $ l_1,l_2,l_3 \in \mathbb{Q} $, $ b_1,b_2,b_3 \in \mathbb{N} $...