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
2answers
17 views

Prove minimum of $\sum_{i=1}^n=S_i$ where all $S_i$ are limited by $x \le S_i \le y $

Sorry if this has already been asked or answered somewhere on the net. I have a set of values $S=\{S_1,S_2,S_3,... S_n\} $ where $x \le S_i \le y $. S has an unknown number of discrete members, ...
0
votes
0answers
3 views

Convergence in constraint propagation

Introduction To the best of my knowledge, constraint propagation can be thought of (in a very heuristic sense) as a class of algorithms that solve a sort of generalized Sudoku problem. Some initial ...
0
votes
1answer
19 views

Sequentially weakly lower semicontinuity on reflexive Banach spaces

Let $J$ be a functional over a reflexive Banach space $X$. Is it true that the sequentially weakly lower semicontinuity is equivalent to convexity and continuity for the functional $J$? I think the ...
0
votes
1answer
20 views

How to show the Hessian matrix of such functions are positive semi-definite?

Let $f:R\to R$, $g:R^n\to R$. Thus $f\circ g:R^n\to R$. Now suppose $f$ is non-decreasing and convex while $g$ is convex. In additon, $f,g$ are of $C^2$. I want to show that their composition is ...
2
votes
1answer
20 views

A tighter family of Markov-like inequalities

I believe there should exist tighter-than-Markov Inequalities that use the same information as the markov inequality (just expectation). Consider the proof of the markov inequality in the link below: ...
1
vote
0answers
18 views

Quantization threshold selection

I have the $256$-bin histogram representing a distribution of the values taken by a certain descriptor element. This descriptor element takes the values in $0-255$ range, hence $256$ bins. I want to ...
0
votes
0answers
16 views

Is $\arg \max_{(t_1,t_2), t_1\geq t_2} (\max_i (E(x_i\mid x_1 \geq t_1, x_2 \geq t_2) +\cdots)$ unique for given distr $(x_1,x_2) \simeq F([0,1]^2)$?

Ingredients and notation: Given is a joint distribution $F$ of two variables $(x_1,x_2)$ where $x_i \in [0,1]$, with a strictly positive joint density $f(x_1,x_2) \in C^1$, that is continuously ...
2
votes
1answer
19 views

How to optimize this function here?

How could I minimize the following? $\vec{x} \in \mathbb{R}^8$ $$f(\vec{x}) = 3\frac{|x_1 - x_2||x_3 - x_4| + |x_5 - x_6||x_7 - x_8|}{|(x_1 - x_2)(x_3 - x_4) - (x_5 - x_6)(x_7 - x_8)|} + 1$$ there ...
2
votes
1answer
22 views

Local Search algorithm: Why is the neighborhood structure $N : S \to 2^S$

I am writing a paper about meta heuristics and in particular local search. My tutor pointed this out: In every source (books, lectures, sites) I looked none explained why it is mapped like that. ...
0
votes
0answers
7 views

Submodularity definition

I am currently looking at a paper whose submodularity definition is different from whatever I thought I knew. In this paper, the authors consider a function $\Pi_2(q;a^r)$, where $q$ is composed of ...
0
votes
0answers
23 views

Explicit solution for minimization over unit box with total budget constraint

I am trying to solve question 4.8, part (e) from Convex Optimization by Boyd. The problem is to find an explicit solution for the minimization problem: Minimize $\textbf{c}^T \textbf{x}$ subject to ...
1
vote
1answer
380 views

Gradient-descent and Hidden Markov Models

I would like to use gradient-descent to fit the parameters of a simple 2-state HMM. This paper Levinson, S. E., Rabiner, L. R. and Sondhi, M. M. (1983), An Introduction to the Application of the ...
0
votes
2answers
18 views

Maximum profit by optimizing assignment

So a company has n available projects and k employees on the bench. Each project has a "number of hours" associated with it. Each employee has an hourly rate that the parent company gets paid gets ...
0
votes
1answer
397 views

Maximize profit with dynamic programming

I have 3 tables… $$\begin{array}{rrr} \text{quantity} & \text{expense} & \text{profit}\\ \hline 0 & 0 & 0 \\ 1 & 100 & 200 \\ 2 & 200 & 450 \\ 3 & 300 & 700 ...
1
vote
1answer
19 views

calculus of variations or optimize over function form

I have a question about optimizing the following quantity over function form . Given unknown function $f(\theta)$ such that $f(\theta)\geqslant 0$ and $\int f(\theta)d\theta\leq \infty$. And ...
0
votes
1answer
46 views

Finding an integral's max and min

I've been asked to find the max and min of the following: $F(x)=\displaystyle\int_0^{2x-x^2}\!\cos\dfrac{1}{1+t^2}\mathrm{d}t$ I tried applying the Fundamental Theorem of Calculus (taking the ...
1
vote
1answer
53 views

Dual program is wrong. Authors claim is right.

In a well respected book, I found the following. The authors claim that it is correct. But I think it is wrong. This is the primal Linear Problem: $$ \begin{array}{cccc} ...
2
votes
0answers
37 views

How far can the plane be tiled by congruent regular pentagons?

What is the limit, as the radius of the disk increases, of the greatest area, in proportion to the area of the disk, of the region covered by regular pentagons of the same fixed size, all lying within ...
0
votes
2answers
2k views

Finding the center of mass of a cylinder

Help finding center of mass of soda can? If you represent the soda can as a right-circular cylinder radius=$4$ cm height =$12$ cm We are told to neglect the mass of the can itself. When the can ...
0
votes
1answer
28 views

Identify if optimization problem is convex or non-convex?

I have formulated optimization problem for building, where cost concerns with energy consumption and constraints are related to hardware limits and model of building. To solve this formulation, I need ...
0
votes
0answers
35 views

Showing λu + (1 − λ)v is an optimal solution

$$\max \quad c \cdot x \\ \mathrm{s.t.} \ Ax \leq b\\ x\geq 0 \\$$ There are two optimal solutions to the LP $u$ and $v$. How do I show that for $\lambda \in [0,1]$, $\lambda u + (1-\lambda)v$ is ...
0
votes
1answer
18 views

Newton's Method in unconstrained optimization fails to converge

In order to show that Newton's method can produce a sequence of iterates that diverges, an example given in my book is apply Newton's Method to minimize $f(x)={2\over 3}|x|^{3\over 2}$. starting at ...
0
votes
1answer
16 views

Lagrange Optimization

I would like to ask for the optimization problem: $$\max_{x,y} g(x,y)$$ st. $x+y=1$ Would there be any difference if we formulate the problem as: $$g(x,y) + \lambda(1-x-y)$$ as opposed to ...
1
vote
2answers
45 views

Calculus optimisation with the speed formula

For a ship travelling at ${x}$ km/h the running cost in £ is ${(x^2 + {13500\over x})}$ per hour. Find the speed that minimises the cost of a 300km journey. The speed formula is ${speed = ...
0
votes
0answers
17 views

Maximization of Harmonic mean

Suppose x is a vector of size N with positive real elements sorted in decreasing order. Is it possible to find the analytical solution (no iterative solution) to the optimum value of M (1<= M ...
0
votes
2answers
32 views

How to describe $\lbrace \mathbf{x}\in \mathbb{R^n}: |x_j|\le1 $ for$ 1\le j\le n \rbrace $ in terms of $x_j=x_j^+-x_j^-$

How to describe the set $A$=$\lbrace \mathbf{x}\in \mathbb{R^n}: |x_j|\le1 $ for$ 1\le j\le n \rbrace $ in terms of $x_j=x_j^+-x_j^-$ where $x_j^+\ge0$ and $x_j^-\ge0$ The answer says: $B$=$\lbrace ...
0
votes
0answers
24 views

Optimization with trace and eigenvalues

Let $M \in \mathbb{R}^{n \times n}$ be a symmetric matrix with given eigenvalues $\lambda_1,\lambda_2,\cdots,\lambda_n$ with $\vert\lambda_1\vert > \vert ...
0
votes
1answer
46 views

A basic minimization problem

Does the following function has a global minimum $$f(x) = \frac{2x +1}{1-e^{-(1-\alpha) x}}$$ where $x$ is a positive real number. for $0< \alpha < 1$
0
votes
1answer
26 views

What is a good resource for a more intuitive/flexible understanding of optimization

Take the following example of optimization: $$cost = 10*x + 20*y$$ Where x = cans of soup, y = cans of juice It is easy to see in this scenario what we need to do in order to minimize cost. Just ...
1
vote
1answer
51 views

Optimization problem on graph with weights on nodes and edges

I am solving a problem where I have a complete undirected graph with weights on the nodes and on the edges. The weight on the node represents a profit that you obtain if you select that node. The ...
0
votes
0answers
13 views

Optimization: second order condition

This is the condition Where $L(x, \mu\,\lambda)$ is the Lagrangian function in a given point that satisfy the first order condition. Problem $ min (-4x -y)$ $ -x^2 -y^2 +1 <= 0 $ $ y- 1 ...
1
vote
1answer
27 views

Duality and the Positive Lagrange Multiplier

Suppose I have the following optimization problem: \begin{align} \min &f(x) \\ & f_1(x) \leq 0 \\ & \vdots \\ & f_k(x) \leq 0 \\ & g_(x) = 0 \\ ...
1
vote
0answers
24 views

Inapproximability of Combinatorial Optimization Problems

I've been reading the "Inapproximability of Combinatorial Optimization Problems" by Luca Trevisan (see: link). On pages 3-4 it mentions that a polynomial time algorithm for 3SAT would exist if there ...
0
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
0answers
25 views

Conditions for a totally unimodular coefficient matrix of a Multi-Commodity-Minimum-Cost-Flow-Problem

I'm considering the following Multi-Commodity-minimum-Cost-Flow-Problem: This leads us to a coefficient matrix $A$ with $N$ donates the incidence matrix of a directed graph and $I$ is the ...
0
votes
1answer
44 views

Finding minimum of a two variable function

Let $D=\{(x,y)\in\Bbb R^2:1\le x\le1000,1\le y\le1000\}$. Define $$f(x,y)={xy\over2}+{500\over x}+{500\over y}$$ Then the minimum value of $f$ on $D$ is Finding $f_x=\frac y2-{1000\over ...
0
votes
0answers
15 views

Want to factorize one matrix into three, with L1 regularization, which optimization algorithm to choose?

I need to factorize one matrix $R$ into three component: $ R = P^TAQ $, in which I want to apply L1 regularization on $A$ to encourage sparsity, and apply L2 regularization on $P$ and $Q$ to prevent ...
-1
votes
1answer
14 views

Optimization Problem Maximize $z= 60x_1+20x_2$

Restate the absolute value constraint as a combination of two linear constraints: I know how to find the optimal solution (std form, canonical form, simplex algorithm ...etc) I don't know how to put ...
0
votes
1answer
597 views

Dual cone of a L1 norm cone?

I am listening to convex optimization lectures and I hear that dual cone of a $L1$ norm cone is a $L-\infty$ norm cone. Can anybody please explain how? I understand that every point in the dual cone ...
0
votes
0answers
21 views

Optimization: determining maximum volume of a tube

I am unsure of how to go about solving this, the context is that there is a rectangular piece of paper with a perimeter of 100 cm that is to be rolled to form a cylindrical tube. The question wants to ...
0
votes
1answer
14 views

About Dual Simplex Method

I have a question about Dual Simplex Method (for minimization problem). While we are solving the method, when we obtain a non-negative $\bar b$, we stop the algortihm. But in addition to $\bar b ...
1
vote
1answer
51 views

Given $f(x)=4-e^{-cos(x-2)}$, find the maximum value of $f(x)$ in the range $[-2,0]$.

Given $f(x)=4-e^{-cos(x-2)}$ Find the maximum value of $f(x)$ in the range $[-2,0]$. $\forall a \in \mathbb R$, $e^a>0$ Hence, the maximum of $f(x)$ will occur when $e^{-cos(x-2)}$ is a minimum. ...
-2
votes
0answers
40 views

How to show this integer program with irrational data has no optimal solutions.

I want to show the integer program with irrational data max$\{x_1-\sqrt{2}x_2:x_1\leq \sqrt{2}x_2,x_1\geq 1,x\in Z_+^2\}$ has no optimal solution, even though there exist feasible solutions with value ...
1
vote
1answer
41 views

Do standard gradient descent methods work on complex variables

I am currently whishing to optimize a function numerically $f(z)$ where $z \in \mathbb{C} $ ($f(z) \in \mathbb{R}$) . I am doing this via numerical packages (specifically scipy in python) and I have ...
0
votes
1answer
24 views

Optimization: Minimizing the cost of pipeline over land

I have the question "A Gas Outlet is one one side of a river 120 m wide. It is exactly 300 meters downstream and across the river from a cottage. A gas line is to be constructed to join the outlet to ...
0
votes
1answer
19 views

Deriving optimal time to change

I am working in economics and I am trying to build a model that take into account the fact that indivudal can take a decision once in their life time that changes the value of a parameter R. To be ...
0
votes
0answers
43 views

Maximum of $e^{-x} \sin(x)$, $x \geq 0$

What is the maximum of $e^{-x} \sin(x)$ for $x \geq 0$? Is there a closed-form solution? If not, what is a good approximation $y$ such that $\text{max}_{x\geq 0}e^{-x} \sin(x) \leq y$?
0
votes
0answers
38 views

Comparing a maximization to an integration with economics application

This seemingly simple question has interesting interpretation in economics, but I only state the mathematical problem here. Suppose $B(0)=C(0)=C'(0)=0$, $B'(\cdot)>0,\ B''(\cdot)\leq0,\ ...
0
votes
1answer
1k views

How do I construct the Jacobian for use in a Levenberg-Marquardt algorithm.

I am working on a 3D reconstruction system and I am looking to use a Levenberg-marquardt algorithm to do bundle adjustment. I am not too sure about how LM works and what it requires. The model I am ...
2
votes
1answer
316 views

Why is Newton's method faster than gradient descent?

Can you provide some intuition as to why Newton's method is faster than gradient descent? Often we are in a scenario where we want to minimize a function f(x) where x is a vector of parameters. To do ...